Route Optimization to handle one pickup, one delivery at a time

[Heri Agape]

Hello, 
I am new to the forum. I have this problem where:
- 6 trucks, each truck can only carry a load of 1000 liters of water. (one discrete capacity)

- Multiple water filling points around the city

- Multiple customers to which the water needs to be delivered.

I am trying to solve a variation of PDP where I need to handle one pickup then its corresponding dropoff, avoiding the next pickup till the previous dropoff has been completed.

Using the resource on https://developers.google.com/optimization/routing/pickup_delivery with the help of this blog post https://activimetrics.com/blog/pdptw/fifo_constraints/ 
I have a able to achieve:
- every truck would be assigned at least one delivery
- even though one customer might have multiple deliveries, both the filling point and the customer are considered as a separate node, to achieve single visit.

The output of the program is:
driver 1: depot -> pick1 -> pick2 -> pick3 -> drop3 -> drop2 -> drop1 -> depot

My desired output:
driver 1: depot -> pick3->drop3->pick1->drop1->pick2->drop2->depot
basically fulling one pickup-dropoff at a time.

I have attacked, my python code and the output of my generate_data_model() in the hope to get assistance of any form.

OR-Tools: version 9.6.2534

Thanks in advance,
Heri

[Laurent Perron]

Just merge pickup and delivery nodes.

--
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/8a3db73f-27b2-442c-9c11-f099127066a6n%40googlegroups.com.

[Heri Agape]

Hi Laurent,

Is there resources I can refer to. My pickups and deliveries are linked already as [(1,2),(3,4),...]

[youssef kaichouh]

Hello, i think u just have to set something like nextVar(Pi)=Di 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/dc482f85-42c7-4bc1-b0d2-398f61158346n%40googlegroups.com.

[Laurent Perron]

No,  I meant merging the nodes in the graph. instead of P -> D in a graph, just have a single node V.

With all incoming arcs n -> V being n -> P and all outgoing V -> n being D -> n

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAOtwtKWOTpy1M3Q%3Djp71YYv4v52HxXR6_d%3DLGVFqCWeO0A%3D4hw%40mail.gmail.com.

[youssef kaichouh]

@Laurent Perron yes this will even reduce the size of the problem, but seems tricky to get right if we have time windows constraint as well! (or multiple tw)

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeYgQF4pcdLkYjgC0FBDQ3%3DgGq%2B7N1oW1ByF-3mZZfA9DA%40mail.gmail.com.

[Heri Agape]

How would I merge the two, in that scenario how does the distance matrix change?

for request in data['pickups_deliveries']:
pickup_index = manager.NodeToIndex(request[0])
delivery_index = manager.NodeToIndex(request[1])

# merged = routing.AddDisjunction([pickup_index, delivery_index])

# Add pickup and delivery nodes directly
routing.AddPickupAndDelivery(pickup_index, delivery_index)

routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
routing.solver().Add(distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index))

# Add order constraint: pickup must be visited before delivery
routing.solver().Add(routing.NextVar(delivery_index) > routing.NextVar(pickup_index))