Hi! I'm currently working on a particular VRP. The goal is the same as the traditional VRP, which is to minimize the time associated with the longest route. The fundamental difference that is blocking me at the moment is that I need to remove the constraint related to the depot. Each vehicle can start from a different location, and once it has visited the last location of its assigned route, it must return to its starting location (two vehicles cannot depart from the same location).
After several searches on the internet, I found that the recommended solution is to set the distance between the depot and the locations to zero. However, this solution does not solve my problem because it does not result in a closed loop route. Indeed, within the route obtained in this way, the last segment corresponding to the vehicle's return from the last location to the starting one is not taken into account. Therefore, I would like to ask if it is possible to solve this problem (I'm aware that the computational complexity increases significantly by removing the depot), and if so, how could I achieve the desired result. Thank you in advance for your attention, and if you can provide any help, I would be infinitely grateful.
My first attempt would be:
Duplicate each location twice:
A -> A', A''
B -> B', B''
_' will serve as depot-out node
_'' will serve as depot-in node
(Those are normal nodes and the routing-solver doesn't allow multiple visits -> two copies).
Remove all outgoing-edges of the depot-node, except for _'
(aka mutate cp-domain of next-var to reduce graph-connectivity).
Remove all ingoing-edges of the depot-node, except for _''.
All edges incident to the depot-node have 0 transit costs and time-accumulation.
Model pickup-delivery semantics for each pair of _' and _'' in this order:
_' precedes _'' (and is on same tour).
Links: