Dynamic vehicle routing problems

[bhack]

Can you add some DVRP example?

[cwelton]

I also would be interested in seeing this. I can't speak for bhack, but the scenario I would like to see is:

V: is a set of vehicles R: Is a set of pickup and delivery requests TW: Is a set of time window constraints on the pickup and delivery requests

1. An initial route is optimized
2. Several ticks go by in which the set of Vehicles V process a portion of the Pickup/Delivery requests
3. A new Request arrives
4. A new route is optimized subject to the constraints:
5. Vehicles start at their current locations, not at a depot
6. If a Pickup has already occurred on V[i] then V[i] must still perform the dropoff, unless the dropoff has also already occurred.
7. Pickups that have not yet occurred may still be shuffled between vehicles

This seems to be a use case for either the route locking functionality or the Preassignment, but the routes still allow intermediary nodes injected which seems to make locking not applicable and the fact that only some of the assignments are strict makes preassignment not quite right either? Is there a way to simply put the constraint that Location l must be serviced by V[i]?

[pocman]

We are using Ortools to model DVRP in production at Colisweb. We found the Preassignment to be limited and are using a simple solution based on "already accepted" and "already refused deliveries". To do so, we build the full model, as usual, and add a loop on nodes constraining the model.vehicleVar() (probably what @cwelton is looking for).

[aaaristo]

@lperron was this solved, if yes could you shed some light on it?

[amih77]

@pocman can you please elaborate? I have a model of which a pickup and deliveries needs to be created dynamically.

[ZhiWeiCui]

@Mizux @lperron I also encountered Dynamic pickup and delivery problems. Are there any examples of this?

[Mizux]

see: https://gist.github.com/Mizux/0bd1daadc4e64130b62492c942f163d5

• create new P&D as droppable nodes,
• use as initial solution the current routes
• solve using the local search so the new nodes are hopefully inserted in the assignment
• If you have pickup already done, (i.e. vehicle loaded) and mandatory delivery to do you can also force the VehicleVar() of those deliveries so only the vehicle with the shipment can visit them...

[ZhiWeiCui]

Thank you very much for your reply. Read your code to understand the general method, that is, when a new order appears, the previous solution is used as the initial solution. But there are still some details in your code that I don't understand, I hope to answer.

1. In your code, is the pickup of orders 1-4 depots? Why their demand is -1?

2. Why set the capacity_dimension value at the start node to 4 ?

   # 4 Orders already loaded
   index = routing.Start(0)
   capacity_dimension.CumulVar(index).SetValue(4)

[Mizux]

In this example we suppose there was 4 pickup already done so vehicle is currently loaded with 4 deliveries "only", so order 1-4 are just the remaining (mandatory) delivery to perform and thus demand is -1 (i.e. unloading goods from the vehicle)

[ZhiWeiCui]

I see. Thanks again!

[ZhiWeiCui]

I have another problem, which involves another topic. If the new order has such a constraint: Deliver right after picking up. I added the following constraints on line 134:

routing.solver().Add(routing.NextVar(5) == 6)

Although the solution can be successfully solved, initial_solution becomes None. How should I add the constraints of this new order？

[Mizux]

usually node are added one by one so it's better to use:

index = manager.NodeToIndex(5)
next = manager.NodeToIndex(6)
routing.NextVar(index).SetValues([index, next])

note: you must add the node itself because it is use by the solver when node is unassigned nextVar(i) == i iif ActiveVar(i) == false

[ZhiWeiCui]

Although I did not understand the reason you said, it is obviously feasible. Thank you very much for your quick reply.

[kazitanvirahsan]

Find this thread extremely useful to implement dynamic routing. Thanks for sharing.