VRP: add pickup & delivery capability along with exsiting capacity, distance and time constraints

[冷凌玉]

I just realized that the official example of pickup and delivery has not conisdered any demands at each location. 

https://developers.google.com/optimization/routing/pickup_delivery

My model considers both capacity, distance and time constraints, and I believe there are more setups to be required than in the simple example above. But I have no idea.

I tried to simply copy and paste  below codes in the Main(). However, my model is running with no stop. Apparently this is wrong! I am sure there are somethings which are missing in my model. Many thanks for your advice.

    # Define Transportation Requests.
    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        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))  

[Corentin "Mizux" Le Molgat]

don't fully understand what you mean by "has not conisdered any demands at each location".

If you means that you have some locations  which are part of two Pickup&Delivery pairs (i.e. one time as Pickup and one time as Delivery).
Then you need to split this location in two in your model aka duplicate this node and adapt the transit matrix accordingly. (with distance between both being 0).

i.e. each location shouldn't be part of two P&D pairs...

[冷凌玉]

I mean in the given example there is no array of location demands. Are there any additional configurations needed if the model further consiers capcity, distance, and time window constraints, except by simply adding below codes? (BTW, it won't work for my model and the model is running with no stop. seems no solution found)

    # Define Transportation Requests.
    for request in data['pickups_deliveries']:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        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))    

[冷凌玉]

My current model considers capacity, distance, and time constraints. All trucks starts from node 0 (I make it 0 distance to all other locations as dummy node),  and all trucks ends at an universal location which is the last location index in data["locations"]. 

I would like to convert the current model into a pickup & delivery model, by making the end node (last location index) as the delivery_index in the data["pickups_deliveries]. i.e. if I have a list of locations: [0, 1, 2, 3, 4, ...50], with 0 as start_node and 50 as end_nodes, I made the data["pickups_deliveries]  = [[1,50],[2,50],[3,50].....[49,50]]. Then I changed the manager settings to replace the array of ends as array of starts (dummy end_node) to avoid duplicating the actual end_node:

manager = pywrapcp.RoutingIndexManager(data.num_locations, data.num_vehicles, data.starts, data.ends) to

manager = pywrapcp.RoutingIndexManager(data.num_locations, data.num_vehicles, data.starts, data.starts) 

Then I run the model but it's just running with no stop and no solution. Certainly, something is wrong here. Many thanks for your advice

在2021年7月22日星期四 UTC+8 下午11:23:56<Corentin "Mizux" Le Molgat> 写道：