Instances where routing library failing

[Ashutosh Shukla]

Hello Everyone,

I have attached with this post, a detailed and well documented python script where I have implemented routing library in 7.0.

The library definitely has some upgrades in first solution heuristics. I was solving around 25 real world instances. It did an awesome job of solving around 19-20 instances. But there were few instances where I know for sure we have a feasible solution, but the library failed in constructing one. How I know we have a feasible solution ? Because we coded the same thing with MIP and it gave feasible solution. We have verified the solved 19-20 instances with MIP solutions and the results are consistent.

I am posting the code and pickle file of those instances for which routing library was unable to construct a feasible solution. The same code solved for other 19-20 instances successfully. I am not sure if we can solve even these by tuning some search parameter.

Any help would be appreciated.

[Vincent Furnon]

Thanks for forwarding, we'll look into this.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[core...@google.com]

Hi,

Summary, your model is a little bit too constrained at first so the solver can't find a first solution.

By making all node "optional" using a Disjunction constraint (see section https://developers.google.com/optimization/routing/penalties#example for explanation)

```python

    for node in range(0, len(data['distances'])):

        routing.AddDisjunction([manager.NodeToIndex(node)], 100000)

```

AND, allow your super jobs to not be active in your method `add_super_job_constraints()`, i.e. `-1` aka not active

```python

            routing.VehicleVar(manager.NodeToIndex(jobs_assigned[key][num_addresses])).SetValues([-1, key])

```
Solver was able to find a solution

e.g. for Day_Route_Feb26.pkl

```

./example.py

...

Dropped nodes:

Route for vehicle 0:

 31 Time(0,0) -> 1 Time(0,0) -> 24 Time(50,330) -> 16 Time(370,370) -> 10 Time(480,480) -> 31 Time(510,510)

Distance of the route: 139 m

Time of the route: 510 min

Route for vehicle 1:

 32 Time(0,0) -> 9 Time(0,0) -> 17 Time(60,80) -> 29 Time(150,170) -> 4 Time(240,240) -> 28 Time(320,320) -> 30 Time(400,400) -> 2 Time(480,480) -> 32 Time(510,510)

Distance of the route: 123 m

Time of the route: 510 min

Route for vehicle 2:

 33 Time(0,0) -> 3 Time(0,0) -> 27 Time(60,150) -> 19 Time(240,240) -> 21 Time(330,330) -> 20 Time(410,410) -> 5 Time(480,480) -> 33 Time(510,510)

Distance of the route: 92 m

Time of the route: 510 min

Route for vehicle 3:

 34 Time(0,0) -> 0 Time(0,0) -> 23 Time(70,150) -> 26 Time(120,200) -> 25 Time(170,250) -> 18 Time(300,300) -> 13 Time(400,400) -> 8 Time(480,480) -> 34 Time(510,510)

Distance of the route: 119 m

Time of the route: 510 min

Route for vehicle 4:

 35 Time(0,0) -> 6 Time(0,0) -> 11 Time(50,100) -> 15 Time(150,200) -> 7 Time(240,240) -> 12 Time(300,300) -> 14 Time(390,390) -> 22 Time(460,460) -> 35 Time(490,490)

Distance of the route: 96 m

Time of the route: 490 min

Total Distance of all routes: 569 m

Total Time of all routes: 2530 min

```

You can find the complete example.py in attachment (ed you must place your .pkl file in the same directory than example.py)

[Ashutosh Shukla]

Hello,

Thanks a lot for the reply. I tried the suggested changes and it indeed worked:)

 But this brings few more questions.

1)  How is the imposed penalty included in objective value (in my case total miles). If this is not included there, how can I access the penalty value ?

2) If say for constructing an initial solution, few nodes are dropped with some penalty added. If the instance is actually feasible can I be sure that this node will eventually be added back to the route ?

3) If a node is dropped and I get a route, can I be sure that the actual instance was indeed infeasible ?

4) If I don't impose the suggested changes, I got solver status: No Solution found. But in one of my previous questions (see below link Laurent's reply to question 1) Laurent mentioned that if first solution strategy doesn't work, CP solver kicks in. In such a scenario, if the problem has a feasible solution, I should never get a NO SOLUTION FOUND status. I should always get time_out status (in cases where first solution strategy was not able to find a solution but CP was searching). So how does solver say no solution found ?

5) Can you please give a little more hint on what setting SetValues with -1 does. I was not able to clearly understand the same. (Why does making constraint not active mean ?) Will it not be imposed ? or will it not be used while constructing solution

Thank you

https://groups.google.com/forum/#!topic/or-tools-discuss/tW02Y0RlN0s