8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ did you find any solution to this? $\endgroup$
    – Bharat
    Apr 2, 2021 at 13:56
  • $\begingroup$ Unfortunately no $\endgroup$
    – Kuifje
    Apr 2, 2021 at 15:23
  • $\begingroup$ 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. $\endgroup$ Jul 25, 2021 at 17:34

2 Answers 2

1
$\begingroup$

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(
...
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.