Google OR-tools VRP - Pickup/Dropoff at same node

I'm currently using Python and the Google-Or-Tools to solve an VRP problem, that I am not sure how exactly to model. (If someone has a solution with another library/tool, absolutely interested as well)

Problem Statement:

I have basically the classical CVRP problem also described and modelled on the documentation page, but with one addition. So the basic CVRP problem is, I have a depot where cargo is loaded and vehicles start from / end at. Also I have locations where goods are to be delivered to, e.g. they have a demand. Now the addition is, that I not only dropoff goods at the specific locations but also want to pickup goods at the same locations, and eventually dropping them off at the depot again.

Since it is possible for a location to have more goods to pickup than to dropoff, I need to explicitly check this, too ... but I can't find a way so far to do this.

Example: So say I have one Depot node 0 and two location nodes (A,B).

• At location A I need to dropoff 10 units and pickup 11.
• At location B I need to dropoff 10 units and pickup 9.

Now for a vehicle with max capcity 20 the possible solution would be:

• 0 --> B --> A --> 0

First visiting A and then B would not work, since it would violate the capacity constraint in A.

What I've tried:

So to consider the basic dropoff capacity constraint I have the standard

routing.AddDimensionWithVehicleCapacity(
    dropoff_callback_index,
    0,  # null capacity slack
    data['vehicle_capacities'],  # vehicle maximum capacities
    True,  # start cumul to zero
    'Capacity')

However, for the pickup I can ofcourse add another one using the pickup demands. But obviously this will not suffice but I would need to combine those two. Since technically the model cumulates the volume over the nodes and does only know the amount of capacities a vehicle is starting from the depot after forming a complete trip, I can't build such a dimension that can check the constraint while running through the nodes but only after he found a complete trip.

So this is what I believe a possible way to do this, kinda check after a solution is found, if the then known volume a vehicle would load in the depot initially (i.e. the sum of dropoffs of a route) fits considering the pickups and does not violate the vehicle capacity. Not sure though, how exactly to do this. Does anyone have an idea here?

Also I tried modelling it using the pickup and delivery model, and splitting one shipment with pickup and delivery into two shipments, also duplicating the nodes to have two nodes instead of one (since one node cannot be pickup and delivery). However, since my tours are all starting from depot / to depot, I would also need to duplicate the depot nodes and then attach an pickup/dropoff demand for them, which doesn't make sense because I can't set this in advance, but the model should find a solution (hope this makes sense to you).

I tried searching for similar problems (here, googlegroups, github) but didn't manage to find anything helpful.

IIRC, already answered on the mailing list.
Here a gist with a sample: Mizux/vrp_collect_deliver.py

Basically you'll need two dimensions.

• One to track only deliveries goods
• One to track the total load (pickup and delivery)
• One constraint on start nodes to make both dimension cumul vars equals.

Main idea: Having two dimensions instead of one, will avoid the solver to use pickup goods to perform deliveries.

deliveries = [0, -10, -10, 0]
total = [0, +1, -1, 0]

...

# Add Deliveries constraint.
def delivery_callback(from_index):
    """Returns the demand of the node."""
    # Convert from routing variable Index to demands NodeIndex.
    from_node = manager.IndexToNode(from_index)
    return deliveries[from_node]
    
delivery_callback_index = routing.RegisterUnaryTransitCallback(delivery_callback)
routing.AddDimensionWithVehicleCapacity(
    delivery_callback_index,
    0,  # null capacity slack
    20,  # vehicle maximum capacities
    False, # start_cumul_to_zero=False since we start full of goods to deliver
    'Deliveries')

# Add Load constraint.
def load_callback(from_index):
    """Returns the load of the node."""
    # Convert from routing variable Index to demands NodeIndex.
    from_node = manager.IndexToNode(from_index)
    return total[from_node]

load_callback_index = routing.RegisterUnaryTransitCallback(load_callback)
routing.AddDimensionWithVehicleCapacity(
    load_callback_index,
    0,  # null capacity slack
    20,  # vehicle maximum capacities
    False,  # start_cumul_to_zero=False
    'Loads')

    # Add Constraint Both cumulVar are identical at start
    deliveries_dimension = routing.GetDimensionOrDie('Deliveries')
    loads_dimension = routing.GetDimensionOrDie('Loads')
    for vehicle_id in range(manager.GetNumberOfVehicles()):
      index = routing.Start(vehicle_id)
      routing.solver().Add(
          deliveries_dimension.CumulVar(index) == loads_dimension.CumulVar(index))

...