Capacity Constraints with pickup and delivery not working

[Bob Voorneveld]

I'm trying to implement a capacity constraint in our VRP.

I create a problem where every node/index is a pickup or delivery point. Visiting a pickup point is adding demand and when visiting a delivery point, a negative demand is returned. Vehicles have a limited capacity (let say 20). The route is visiting around 150 locations.

I can create the optimal route without the capacity constraint added. Adding this constraint fails to find the correct route.

So, the goal is:

- Vehicle starts empty

- Vehicle picks up some packages

- Vehicle reached capacity and starts dropping (or maybe sooner if that is more optimal)

- Vehicle starts picking up packages again.

This is what I'm adding to our code:

# Add Capacity constraint.
def demand_callback(from_index):
    """Returns the demand of the node."""
    # Convert from routing variable Index to demands NodeIndex.
    from_node = manager.IndexToNode(from_index)

    location = locations[from_node]
    number_of_packages = location.number_of_packages
    if location.is_drop:
        number_of_packages *= -1
    return number_of_packages

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index,
    0,  # null capacity slack
    [50],  # vehicle maximum capacities
    True,  # start cumul to zero
    'Capacity',
)

Does anyone have a suggestion about what I'm doing wrong? Setting the maximum capacity really high (so that the vehicle never gets full), will create a route.

[blind.line]

At the risk of telling you something you already know, have you looked at the examples for the pickup and delivery problem?  For example, 
https://github.com/google/or-tools/blob/v7.1/ortools/constraint_solver/samples/vrp_pickup_delivery.py

In order to set up a solver run that picks up packages and then drops them off, you have to set up relationships between pickups and deliveries, as is done here:   https://github.com/google/or-tools/blob/v7.1/ortools/constraint_solver/samples/vrp_pickup_delivery.py#L183

I always have specific links between pickups and drop offs, as in the examples. If instead your vehicles are picking up completely generic things, say lumps of coal for delivery on Christmas Eve, you probably *still* will have to tell the solver to make sure a vehicle isn’t empty before visiting a dropoff (negative demand) node. Something like:

solver.Add(routing.ActiveVar(d_idx)*demand_dimension.CumulVar(d_idx)>=routing.ActiveVar(d_idx)

Which is a hack, but says if the node is active (routing.ActiveVar is 1) then the vehicles load on arrival at a delivery node (d_idx) must be >=1. And if the node is not active, the constraint is still satisfied because it decays in that case to 0==0. 

Regards,

James

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/93636ef5-6fd5-4387-b6fa-ca3c9d8be25d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Bob Voorneveld]

This is what we've added for the pickup and delivery (which is working as long there the capacity per vehicle is big enough to pick everything up.

I've added the part of the capacity in the beginning.

I've left out the time_callback, but don't think that should be the problem.

Solver is running, there is just no solution.

def demand_callback(self, from_index):

    """Returns the demand of the node."""
    # Convert from routing variable Index to demands NodeIndex.

    from_node = self.manager.IndexToNode(from_index)

    if from_node == 0: # Start location
        return 0
    else:

        location = locations[from_node]
        number_of_packages = location.number_of_packages

        # If it is a Drop, the demand is negative.
        if not location.is_pickup:

            number_of_packages *= -1

        return number_of_packages

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index,
    0,  # null capacity slack

    [20 for _ in range(number_of_vehicles)],  # vehicle maximum capacities

    True,  # start cumul to zero
    'Capacity',
)

horizon = 20 * 60 * 60 # Extreme time duration, to make sure that isn't bottleneck. With capacity it should be done in 1,5 hour.
routing.AddDimension(
    transit_callback_index,
    horizon,  # allow waiting time
    horizon,  # maximum time per vehicle,
    False,  # Don't force start cumul to zero.
    'Time',
)
time_dimension = routing.GetDimensionOrDie('Time')

demand_dimension = routing.GetDimensionOrDie('Capacity')

# Make sure pickup and delivery happens on same vehicle.
node = 1
while node <= len(self.orders) * 2:
    pickup_index = self.manager.NodeToIndex(node)
    delivery_index = self.manager.NodeToIndex(node + 1)
    # routing.AddPickupAndDelivery(pickup_index, delivery_index)
    routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
    routing.solver().Add(time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(delivery_index))
    routing.solver().Add(routing.ActiveVar(delivery_index) * demand_dimension.CumulVar(delivery_index) >= routing.ActiveVar(delivery_index)) # Added by your suggestion.
    node += 2

# Add time window constraints for each vehicle start node.
for vehicle_id in range(number_of_vehicles):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(0, horizon)
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.Start(vehicle_id)))
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.End(vehicle_id)))

Op woensdag 22 mei 2019 19:14:22 UTC+2 schreef blind.line:

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[blind.line]

I’m a little confused about what you are doing. On the one hand, your demand callback seems to kno about pickups and deliveries:

location = locations[from_node]
number_of_packages = location.number_of_packages

# If it is a Drop, the demand is negative.
if not location.is_pickup:
number_of_packages *= -1

But then when you set the constraints for pickup and dropoff in the while loop, you just count through integers. Why aren’t you again iterating over the locations object?  Without seeing all your code I can only guess, but that looks suspect. 

In my code, typically I store the link from pickup to delivery. Then I use the built in routing.AddPickupAndDelivery(pickup_index, delivery_index) call (see the guide https://developers.google.com/optimization/routing/pickup_delivery)

James

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4136593a-6de2-4406-9923-7f42a65e3d26%40googlegroups.com.