7
$\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 at 13:56
  • $\begingroup$ Unfortunately no $\endgroup$
    – Kuifje
    Apr 2 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 at 17:34

Your Answer

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

Browse other questions tagged or ask your own question.