VRP: Does vehicle auto accumulate/deduct loads in pickup & delivery setting?

[冷凌玉]

The example is quite vague as there is only the paired pickups_deliveries relationship described. How does the vehicle handle the loading/unloading demands?

For example, 

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

The mode gives one of the truck routes as:

Route for truck 1:

 0 ->  5 ->  2 ->  10 ->  16 ->  14 ->  9 -> 0

when the truck picksup loads at node 2 and then visits node 10, will this vehicle unloads the goods collected from node 2 at node 10, before visting  node 16 to collect more loads given part of the previous loads has been unloaded. Is such process automatically handled by the solver by simply adding routing.AddPickupAndDelivery method?

[Corentin "Mizux" Le Molgat]

To handle the loading/unloading demands you need to create a capacity dimension
see: https://developers.google.com/optimization/routing/cvrp

[冷凌玉]

yes, my current model considers both driving distance, truck capacity (different types) and time window. will this be everything or do I need to make further special configurations to tell trucks releasing the capacity after unloading at the delivery node, so that the truck can continue to visit other locations to pickup more loads.

[Corentin "Mizux" Le Molgat]

The capacity dimension would need an unary transit callback. This callback will let you express the load/unloading at each node.

note for advanced users: You could also use the AddVectorDimension() method overload
ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L474-L486

[冷凌玉]

This is how I setup in my current model, is this everything enough for solver to auto increase/decrease capacity during the likely iterative pickups and deliveries.

def add_capacity_constraints(routing, data, demand_callback_index, manager):
"""Adds capacity constraint"""
capacity = "Capacity"
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
capacity_vector(), # vector vehicle_capacity
True, # start cumul to zero
capacity)

# Add Capacity constraint
demand_evaluator = CreateDemandEvaluator(data, manager).demand_evaluator
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_evaluator)
add_capacity_constraints(routing, data, demand_callback_index, manager)

[Corentin Le Molgat]

Seems OK

I suppose your "demand_evaluator" returns a positive integer at each pickup location (aka loading) and a negative integer at each delivery location.

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/RplMRoTdV78/unsubscribe.
To unsubscribe from this group and all its topics, 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/719ce46d-f1a6-47c3-b9b2-133fb1a3c848n%40googlegroups.com.

[冷凌玉]

well this seems to be an issue... 

"demand_evaluator" returns a positive integer at each pickup location (aka loading) and a negative integer at each delivery location. " --- what is the simplest way to make this logic?

if I have a demand pickup list like: 

data["demand"] = [6, 2, 5, 9]

should I also make a demand delivery list like:

data["delivery"] = [-6, -2, -5, -9]  

I should then combine them in an appropriate order according to each location's index.

if pickups_deliveries relationship is like this:

data['pickups_deliveries'] = [
 [1, 8],
 [2, 7],
 [3, 5],
 [4, 6],
]

then the dmand_evaluator returns data based on this list (aka pickup_delivery_list):

[6, 2, 5, 9, -5, -9, -2, -6]  

def demand_evaluator(self, from_index):
"""Returns the demand of the current node"""
from_node = self._manager.IndexToNode(from_index)
return self. pickup_delivery_list  [from_node]

would this be ok? is there easier/simpler approach to do so? many thanks

[Corentin "Mizux" Le Molgat]

Yes it's OK, but beware of start and end node too + python array are zero indexed (I guess here your depot is node 0)

so prefer to use:

pickup_delivery_list = [0, 6, 2, 5, 9, -5, -9, -2, -6] 

Also instead of using a demand evaluator you could pass this array directly using

```python

routing.AddVectorDimension(

pickup_delivery_list,
capacity, # vehicle capacity same for all vehicle

True, # start cumul to zero
capacity

)

```

note: we don't have an AddVectorDimensionWithVehicleCapacity() method yet...

[冷凌玉]

Thanks, if I follow your suggest to use it,

routing.AddVectorDimension(

pickup_delivery_list,
capacity, # vehicle capacity same for all vehicle

True, # start cumul to zero
capacity

)

where should I add it? is it replacement of using "routing.AddDimensionWithVehicleCapacity"?  which parts below are no longer needed and can be removed from the model?

def demand_evaluator(self, from_index):
"""Returns the demand of the current node"""
from_node = self._manager.IndexToNode(from_index)
return self. pickup_delivery_list  [from_node]  

def add_capacity_constraints(routing, data, demand_callback_index, manager):
"""Adds capacity constraint"""
capacity = "Capacity"
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
capacity_vector(), # vector vehicle_capacity
True, # start cumul to zero
capacity)

# Add Capacity constraint
demand_evaluator = CreateDemandEvaluator(data, manager).demand_evaluator
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_evaluator)
add_capacity_constraints(routing, data, demand_callback_index, manager)

[冷凌玉]

Hello  Corentin,

I have tried to do the split to make the different unique delivery_node for each pickup_node, so they have 1:1 relationship.

However, I still got some issues related to manager index conversion. I have no idea what's the root cause of below error:

Traceback (most recent call last):

  File "C:/Users/usr/Dropbox/usr/VRP_17.0.py", line 273, in vehicle_cost_callback

    from_node = manager.IndexToNode(from_index)

  File "C:\Users\usr\AppData\Roaming\Python\Python36\site-packages\ortools\constraint_solver\pywrapcp.py", line 2818, in IndexToNode

    return _pywrapcp.RoutingIndexManager_IndexToNode(self, index)

OverflowError: in method 'RoutingIndexManager_IndexToNode', argument 2 of type 'int64_t'

This error happens in below function, which is working fine before I make adjustment for Pickup_Delivery setting:

def define_total_cost(self, data, routing, manager):
     for vehicle_idx in range(data.num_vehicles):
           def vehicle_cost_callback(from_index, to_index, i=vehicle_idx):
                 from_node = manager.IndexToNode(from_index)
                 to_node = manager.IndexToNode(to_index)
                 return cost_vector()[i] * self.dist_matrix[from_node][to_node]
           cost_callback_index = routing.RegisterTransitCallback(vehicle_cost_callback)
           routing.SetArcCostEvaluatorOfVehicle(cost_callback_index, vehicle_idx)

Here are all my codes and  3  input csv (i.e. order_info, dist_matrix, time_matrix)

https://gist.github.com/Westlife1002/3e4cce18dba6c6f8ac530934c011d920

Great thank for your help.

[冷凌玉]

I uploaded a wrong version of code. I have updated in my gist. It's still the same error.