Pickup and delivery VSP with aggregation points

I’m trying to solve a simple pickup and delivery VRP for one vehicle only using or-tools. I was following the docs https://developers.google.com/optimization/routing/pickup_delivery, and it seems that everything works as expected when all the pickup and drop-off points are different from each other. The pickups_deliveries array looks like this:

data['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [4, 3],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]

However, let’s assume there are aggregation points where there’s more than one package to pick up and courier has unlimited space. I was trying to modify the example above to use the same pickup index in multiple pickup/delivery pairs:

data['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [2, 3],
        [2, 9],
        [1, 8],
        [1, 11],
        [2, 12],
        [2, 14],
    ]

The result I was expecting was to have only 2 pickup stops and 8 deliveries, but unfortunately when I run the solver, it returns None.

solution = routing.SolveWithParameters(search_parameters) # returns None

Is there a way around this or am I missing something more crucial? I’m pretty new to this library, so any directions would be very appreciated.

Answer

You must duplicate the node 2 to have it involve in one P&D only.

Please notice that each location can only be visited once !

Advertisement

Answer