Multiple Vehicle Routing Problem with all Vehicles going to all nodes but not at same time and with distance constraint in or-tools

[Kyle King]

I am not sure how to get from a regular VRP to the solution that I am looking for:

Multiple vehicles all start and end at the depot. All vehicles must go to all nodes but in a unique order and never present at the same time. There is a max distance for each vehicle and nodes can be dropped if necessary.

I have tried to program this in or-tools but not sure how to handle it. Could really use some guidance ;)

[Mizux Seiha]

please add link to cross post -_-
https://stackoverflow.com/questions/66213044/multiple-vehicle-routing-problem-with-all-vehicles-going-to-all-nodes-but-not-at

[Priidik Vilumaa]

I would use CP-SAT and model this as a scheduling problem. 

1. All tasks are optional intervals (i.e. you can drop nodes)

2. Transit time between tasks is the traveling time from node to node

3. "never present at the same time" -> NoOverlap()

4. "All vehicles must go to all nodes" -> duplicate nodes (intervals) for every vehicle

5. You will probably have to use circuit constraint. Here's how I did a VRP with circuit once (see image):

Upper half is the total problem graph with 2 vehicles and 2 nodes. Lower half is a sample solution, where car1 does node T1 and car2 does T2.

This graph allows to keep track of which car is doing what node during the search. Combining this with optional might be difficult.

6. "but in a unique order" -> something lexicographic or do it lazily. I.e. solve and see if each vehicle has a unique order or not. If not, then add a constraint forbidding that solution for that vehicle and solve again.

For materials see:

https://developers.google.com/optimization/scheduling

https://github.com/google/or-tools/blob/stable/examples/python/jobshop_ft06_distance_sat.py

Disclaimer : this approach might not be easy so if someone knows how to do it using routing solver, then follow their advice. 

Best,

Priidik 

[Laurent Perron]

This is IMO the best approach.

Inter-route constraints are really bad for the routing solver.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0cfdc289-a73e-4f23-9751-39c9c381c4b9n%40googlegroups.com.

[Kyle King]

Awesome! Thank you so much! I'll give that a try and let you know how it goes!