OR-TOOLS : delivery node with multiple possible pickup nodes

Question

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]
            ]
            self.routing.AddDisjunction(all_pickups, 0)
          
            # same vehicle for pickup and delivery
            delivery_index = self.manager.NodeToIndex(delivery_node)
            self.routing.solver().Add(
                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")
            self.routing.solver().Add(
                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().AddConstraint(
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.

Answer 1

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.

....
pickup_disjuncton_index = self.routing.AddDisjunction(all_pickups, 0)
          
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.

self.routing.AddPickupAndDeliverySets(pickup_disjunction_index, delivery_disjunction_index)

self.routing.solver().Add(
...

Answer 2

OR-Tools (and most other libraries) can't split up a node for you. If you want to enable split-deliveries, you need to split up the node yourself. For example if your node has a demand of 10, you introduce two duplicate nodes with demand 5.

If you want to the solver to be able to choose between split delivery and full delivery, you can introduce both nodes (so 3) and set a constraint that either the full node is active or the split node is active.