How to set the vehicle's initial load

[wnglnd]

First and foremost, thank you for an amazing tool! The capabilities of the Routing Solver is impressing, and it is all open source - well done!

Now, to my question. I am solving a Capacitated Vehicle Routing Problem w Pickups and Deliveries in Python, OR-Tools version 7.4.7247.

Here is a brief problem description:

• There is a time dimension as well as a capacity dimension.
• The vehicle's capacity dimension increases at the Pickups (demand +1) and decreases at the Deliveries (demand -1).
• The nodes are paired using the AddPickupAndDelivery() which works as expected.

I am trying to build a vehicle planning system which supports re-planning. So a scenario could be that during operations one truck might breakdown which would require the truck's assignments to be re-assigned which would require a re-plan. This imposes the requirement that I somehow need to specify the initial state of the vehicle's positions, their current Pickup and Delivery assignment AND their current load (the vehicles in the Plan who did not break down should continue their task in the new plan). According to this discussion it seems like an Pickup or Delivery node cannot also be a start or end node. I think this feature could be very valuable. So far I have narrowed down these solutions:

Regarding the vehicles' initial positions:

• Add a dummy node at the vehicle's current position and set this node id as the start node using pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['starts'], data['ends']). However, if I have understood it correctly, it is not possible to also set this dummy node as part of a pickup and delivery pair (relating to the discussion above). If the vehicle already is loaded, you could also place a dummy pickup node at the same location as the dummy node and hope that the solver assigns that pickup and delivery to the vehicle. However, this is a bit uncertain.

Regarding the vehicle's initial load state:

• I have not seen any example regarding vehicle capacities where the vehicles start already loaded. Is there any way to achieve this? It would be great if you e.g. in AddDimensionWithVehicleCapacity could specify an array of the vehicle's initial load.

Once again, thanks for this great software!

[CervEdin]

I don't know if it'd work but have you considered something along the following lines:

Remove packages that have been both picked up and delivered from the previous solution. Change the the individual start-depots for each vehicle to their current location. Create new free pickup nodes for packages not delivered on non-broken vehicles and assign them to the vehicle that previously picked them up. Create new pickup nodes for the packages not delivered by the broken vehicle. Re-optimize.

I don't know your exact model but this way you don't specify any special initial load or position state that fundamentally changes the model.

You could also consider freezing parts of already planned pickups and deliveries for a given time-span into the future, so that the vehicles may continue and operate on the old schedule during re-optimization.

[wnglnd]

Thanks for the reply CervEdin! Yes we seem to think alike considering the withdrawal of already delivered material. Regarding packages not delivered I would like the following behaviour:

• Ongoing pickup and deliveries: create correspondig new pairs in the new problem formulation. These pairs I would like to assign to specific vehicles, how would I go about this?

Kind regards

[routemegood]

There is a feature called ApplyLocksToAllVehicles, which you can see here: https://google.github.io/or-tools/python/ortools/constraint_solver/pywrapcp.html#pywrapcp.RoutingModel.ApplyLocksToAllVehicles I've not used it myself, but it sounds like what you are looking for. It was designed for the purpose of replanning when halfway through the previous plan. You simply pass a vector for each vehicle of the nodes it has already visited, and it will be forced to perform them first. This would then keep all the links between pickups and deliveries intact.

Please let me know if this works or not, I'm considering using this myself in the future.

[wnglnd]

Thank you for your reply routemegood (love the username btw). I will check it out and get back here with the results.

[wnglnd]

@routemegood It worked like a charm! Starting with e.g. a standard VRP you then add initial routes for the vehicles:

data['initial_routes'] = [ [4, 7, 1], [], [], [] ] 

In this example the first vehicle should initially visit the nodes 4 -> 7 -> 1 and the remaining vehicles does not have any additional constraints on them.

Then, right before calling routing.SolveWithParameters() you add:

routing.CloseModel()
print(routing.ApplyLocksToAllVehicles(data['initial_routes'], False))

Depending on the Cost Coefficient distance_dimension.SetGlobalSpanCostCoefficient() It seems like the solver can still re-assign Initial Routes if the cost gets high enough though (difference between longest and shortest route).