or-tools single driver first solution problem

user_6650390 0
Viewed 205

In my application I have a single driver and many vehicles. i.e, he can drive the next vehicle after the end of the previous trip in term of constraint it is something like

routing.solver().AddConstraint(
                             time_dimension.CumulVar(routing.End(int(pre_vehicle_id))) <=
                             time_dimension.CumulVar(routing.Start(int(vehicle_id)))
                        )

after many tries I found that such constraint works only if I set the first solution strategy to PARALLEL_CHEAPEST_INSERTION.

Here, I have some problems:

  • sometimes it failed with no reason, or it takes very long time to get the first solution. is it a bug? or I do something wrong. What is the correct way to implement such constraint
or-tools
1 Answers

The routing solver is trying its utmost to build parallel routes with different drivers. You extra constraint is just breaking all feasible routes the solver is building, thus the hard time finding feasible solutions.

To solve your problem, you need to have only one driver (vehicle in the routing API).

One vehicle is not enough to visit all nodes because of the capacity limit. You need to get inspiration from the reload model where a reload at a copy of the initial node corresponds to a vehicle change.

user_99717590
Related