# OR-TOOLS : delivery node with multiple possible pickup nodes

I am using ortools to model a VRP with pickup and delivery constraints, where pickups can be done at different nodes. For example, if node A has a demand, it must be picked at node B or C.

Here is how I do this:

# data["pickups_deliveries"] is a dict with keys delivery_nodes and values a list of possible pickup nodes
# example : data["pickups_deliveries"][a] = [b,c]

for delivery_node in self.data["pickups_deliveries"]:
# choose one node among all pickup options
all_pickups = [
self.manager.NodeToIndex(p)
for p in self.data["pickups_deliveries"][delivery_node]
]

# same vehicle for pickup and delivery
delivery_index = self.manager.NodeToIndex(delivery_node)
sum(
self.routing.ActiveVar(p) * self.routing.VehicleVar(p)
for p in all_pickups
)
== self.routing.VehicleVar(delivery_index)
)

# precedence constraint
time_dimension = self.routing.GetDimensionOrDie("Time")
sum(
self.routing.ActiveVar(p)
* time_dimension.CumulVar(p)
for p in all_pickups
)
<= time_dimension.CumulVar(delivery_index)
)


This works if everything fits into 1 vehicle. But if capacity constraints require more than 1 vehicle, the solver does not find a solution after a few minutes (solver status 3).

I suspect something is wrong with the constraints imposing that the same vehicle is used for the pickup and delivery, but I am not sure. I have also tried using the following code (from here), but it does not help:

pickup_vehicles = [self.routing.VehicleVar(i) for i in all_pickups]
deliver_vehicle = [self.routing.VehicleVar(delivery_index)]
self.routing.solver().Max(pickup_vehicles)== self.routing.solver().Max(deliver_vehicle))


Can someone help ? Thanks!

Note : I have cross posted on ortools mailing list.

• did you find any solution to this? Apr 2, 2021 at 13:56
• Unfortunately no Apr 2, 2021 at 15:23
• Well, I do not know how to do this using the OR-TOOLS. But, I am pretty confident you can solve this problem using the VRPSolver (vrpsolver.math.u-bordeaux.fr), I think that with a small adaptation in the given Pickup and Delivery demo (vrpsolver.math.u-bordeaux.fr/pdptwdemo.zip) you can solve this problem. Jul 25, 2021 at 17:34

As stated in the official tutorials, in order to set pickup and deliveries you must use routing.AddPickupAndDelivery() for each pickup-delivery pair, otherwise the optimization process cannot find a solution efficiently. since we are dealing with multiple pickup options, instead of AddPickupAndDelivery, we must use routing.AddPickupAndDeliverySets() which accepts two disjunction indices as parameters.

....

delivery_index = self.manager.NodeToIndex(delivery_node)

delivery_disjunction_index = self.routing.AddDisjunction([delivery_index], -1)  # Negative penalty forces the algorithm to visit the node.