Can ortools be used for solving the Pickup and Delivery Problem with Time Window and Transshipment

[Jaja w]

Hi all, 

Is there anyone who use ortools solving the pdp-t?

[core...@google.com]

Or-Tools support:

 Time Windows Constraint: cf https://developers.google.com/optimization/routing/cvrptw

 PickUp and Delivery: cf comment issue https://github.com/google/or-tools/issues/703#issuecomment-392479379 (doc is in progress)

For transshipment, well you'll have to do some hack since solver want to visit all node one time (it's basically a tsp at its core)

Supposing you have A -> B -> C with B the intermediate node, and note necessarily the same vehicle use.

1) You should split B in two node 'B1' and 'B2' with zero distance from each other etc...

2) And create a Pickup Delivery constraint (A, B1) and (B2, C).

routing.AddPickupAndDelivery(A, B1)

routing.solver().Add(routing.VehicleVar(A) == routing.VehicleVar(B1))

routing.AddPickupAndDelivery(B2, C)

routing.solver().Add(routing.VehicleVar(B2) == routing.VehicleVar(C))

For B1 being before B2 I would do

3) Add a time Dimension;

4) Add a constraints B1 before B2 using a time dimension for example (not tested):

`routing.solver().Add(time_dimension.CumulVar(B1) < time_dimension.CumulVar(B2))`

note: you can also make a time windows for B1 strictly before the time windows for B2...

note: if it's the same vehicle you can simply use:

routing.AddPickupAndDelivery(B1, B2)

routing.solver().Add(routing.VehicleVar(B1) == routing.VehicleVar(B2))

AddPickupAndDelivery(A, B) only add a node precedence constraint but if node are on different vehicle route this constraint is always true (i.e. even if A is visited "after" B on an absolute timeline)