I want to know if it is possible to set a traveling constraint for different routes, using ORTools VRPTWs problem.
For example, if I have a list of nodes
A, B, C, D, E
Where C cannot be routed with D and E.
Therefore possible routes would be (just a few examples):
B -> A -> C
A -> B
D -> E
A -> D
B -> E
Note that no solutions contains C -> [D|E]
How can I model such constraint in ORTools? Is it possible?
Some solutions recommended to set a vehicle with node constraint, for example half vehicles containing C and half of them containing D and E.
It works, but it would generate suboptimal solutions, since the vehicle number was fixed and the number of constraint nodes would be greater than the number of possible routes, inducing a suboptimal solution.
Advertisement
Answer
Did you try:
# C != D
active_c_d = routing.ActiveVar(c) * routing.ActiveVar(d)
routing.solver().Add(
active_c_d * (routing.VehicleVar(c) - routing.VehicleVar(d)) != (1 - active_c_d))
# C != E
active_c_e = routing.ActiveVar(c) * routing.ActiveVar(e)
routing.solver().Add(
active_c_e * (routing.VehicleVar(c) - routing.VehicleVar(e)) != (1 - active_c_e))
sample: https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54
Otherwise you can also test using Solver::MakeAllDifferent() (not tested)
routing.solver().AllDifferent([routing.VehicleVar(c), routing.VehicleVar(d)]) routing.solver().AllDifferent([routing.VehicleVar(c), routing.VehicleVar(e)])