Problem with vehicle equality constraint in CVRPTW with P&D #4145
Replies: 3 comments 1 reply
-
|
As suggested in this google group conversation I tried: both_active = routing.ActiveVar(stop1) * routing.ActiveVar(stop2)
routing.solver().Add(
both_active * routing.VehicleVar(stop1) ==
both_active * routing.VehicleVar(stop2))with: search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
search_parameters.time_limit.seconds = 20i got as output: Node 9 and 10 got dropped. Even though node 7 and 6 have the same vehicle constraint as 9 and 10 to 8. Is there no clear way to solve this problem ? |
Beta Was this translation helpful? Give feedback.
-
|
The solver gets stuck because the 'pairs' are inserted sequentially, which breaks the same vehicle constraint. Instead of a hard constraint, try using a soft constraint with a high penalty instead: if enable_pairwith:
for pair in data['pair_with']:
indices = [manager.NodeToIndex(x) for x in pair]
routing.AddSoftSameVehicleConstraint(indices, 99999) |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for the response! I appreciate it ! I was wondering if there is any way to have a hard constraint that guareentee both are dropped if not the same vehicle ? I have a very specific use case exemple where a mom and her child living at different shelters need to go to their appointement together. |
Beta Was this translation helpful? Give feedback.
-
It should work in theory, but only under the assumption that dropped nodes incur the EDIT: You can also try using penalty = 144000
if enable_pairwith:
for pair in data['pair_with']:
indices = [manager.NodeToIndex(x) for x in pair]
routing.AddDisjunction(indices, penalty, len(indices))
routing.AddSoftSameVehicleConstraint(indices, penalty)
else:
for node in range(1, len(data["time_matrix"])):
routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
|
Beta Was this translation helpful? Give feedback.
-
What are you trying to do ?
Write a constraint that forces 2 or more pairs of pickupDelivery nodes on the same vehicle or drops them both if it's not feasible.
What version of OR-tools and what language are you using?
Version: ortools-9.8.3296
Language: Python
What operating system (Linux, Windows, ...) and version?
Ubuntu 20.04.6 LTS
Smallest possible program that demonstrates the trouble:
Output:
Test 1 showcases the problem I am facing. With the vehicle equality constraint and with the PARALLEL_CHEAPEST_INSERTION, OR-Tools seems to hang and all nodes are dropped.
In Test 2, without the vehicle equality constraint and with the PARALLEL_CHEAPEST_INSERTION, we can see that it already groups them as we want and that an optimal solution is found.
In Test 3, with the vehicle equality constraint and with the PATH_MOST_CONSTRAINED_ARC, a solution is found while respecting the constraint.
In Test 4, using the Alternative constraint and PARALLEL_CHEAPEST_INSERTION, we can see that 1 pickupDelivery pair got dropped but not the other one from the vehicle equality constraint which is not an acceptable solution.
I tried to search through discussions and issues and conversations, i saw some alternative ways to write the constraint but it doesn't seem to work all the time.
I've tried:
Result:
Constraint is not always respected as described in Test 4.
Result:
This clearly doesn't work because it’s satisfied if they are assigned to different vehicles.
Result:
The first pair is dropped. Solution is not Optimal.
Result:
OR-Tools still hangs with the basic constraint. Results are still the same in all cases I think.
Questions:
Beta Was this translation helpful? Give feedback.
All reactions