CVRP with time windows and pick up and delivery

uni_r

unread,

May 10, 2021, 4:56:24 AM5/10/21

to or-tools-discuss

Hi, I am trying to write the code to get a CVRP with time windows and pick up and delivery.

I managed to get a CVRPTW , and the code seems to work ( I used the same data of the examples on google or tools, removing some nodes to speed up the process)

I have problems when I add the pick up and delivery part. The compiler gives me this error:

<built-in function RoutingModel_SolveWithParameters> returned a result with an error set

I don't understand why, could you help me? This is the code:

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

def create_data_model():

"""Stores the data for the problem."""

data = {}

data['time_matrix'] = [

[0, 6, 9, 8, 7, 3, 6, 2, 3, 2],

[6, 0, 8, 3, 2, 6, 8, 4, 8, 8],

[9, 8, 0, 11, 10, 6, 3, 9, 5, 8],

[8, 3, 11, 0, 1, 7, 10, 6, 10, 10],

[7, 2, 10, 1, 0, 6, 9, 4, 8, 9],

[3, 6, 6, 7, 6, 0, 2, 3, 2, 2],

[6, 8, 3, 10, 9, 2, 0, 6, 2, 5],

[2, 4, 9, 6, 4, 3, 6, 0, 4, 4],

[3, 8, 5, 10, 8, 2, 2, 4, 0, 3],

[2, 8, 8, 10, 9, 2, 5, 4, 3, 0],

]

data['time_windows'] = [

(0, 5), # depot

(7, 12), # 1

(10, 15), # 2

(16, 18), # 3

(10, 13), # 4

(0, 5), # 5

(5, 10), # 6

(0, 4), # 7

(5, 10), # 8

(0, 3), # 9

]

data['distance_matrix'] = [

[

0, 548, 776, 696, 582, 274, 502, 194, 308, 194],

[

548, 0, 684, 308, 194, 502, 730, 354, 696, 742

],

[

776, 684, 0, 992, 878, 502, 274, 810, 468, 742

],

[

696, 308, 992, 0, 114, 650, 878, 502, 844, 890

],

[

582, 194, 878, 114, 0, 536, 764, 388, 730, 776

],

[

274, 502, 502, 650, 536, 0, 228, 308, 194, 240

],

[

502, 730, 274, 878, 764, 228, 0, 536, 194, 468

],

[

194, 354, 810, 502, 388, 308, 536, 0, 342, 388

],

[

308, 696, 468, 844, 730, 194, 194, 342, 0, 274

],

[

194, 742, 742, 890, 776, 240, 468, 388, 274, 0

],

]

data['pickups_deliveries'] = [

[1, 3],

[2, 6],

[4, 7],

[5, 8],

]

data['num_vehicles'] = 4

data['depot'] = 0

# data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1]

data['demands'] = [0, 1, 1, -1, 4, 2, -1, -4, -2]

data['vehicle_capacities'] = [15, 15, 15, 15]

return data

def print_solution(data, manager, routing, solution):

"""Prints solution on console."""

print(f'Objective: {solution.ObjectiveValue()}')

time_dimension = routing.GetDimensionOrDie('Time')

total_time = 0

total_load=0

total_distance = 0

for vehicle_id in range(data['num_vehicles']):

route_distance = 0

route_load = 0

index = routing.Start(vehicle_id)

plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)

while not routing.IsEnd(index):

node_index = manager.IndexToNode(index)

time_var = time_dimension.CumulVar(index)

route_load += data['demands'][node_index]

plan_output += '{0} Time({1},{2}) Carico: {3} -> '.format(

manager.IndexToNode(index), solution.Min(time_var),

solution.Max(time_var), route_load)

previous_index = index

index = solution.Value(routing.NextVar(index))

route_distance += routing.GetArcCostForVehicle(

previous_index, index, vehicle_id)

time_var = time_dimension.CumulVar(index)

plan_output += '{0} Time({1},{2}) Carico:{3})\n'.format(manager.IndexToNode(index),

solution.Min(time_var),

solution.Max(time_var),route_load)

plan_output += 'Time of the route: {}min\n'.format(

solution.Min(time_var))

plan_output += 'Load of the route: {}\n'.format(route_load)

plan_output += 'Distance of the route: {}m\n'.format(route_distance)

print(plan_output)

total_time += solution.Min(time_var)

total_load += route_load

print('Total time of all routes: {}min'.format(total_time))

print('Total load of all routes: {}'.format(total_load))

print('Total distance of all routes: {}m'.format(total_distance))

def main():

"""Solve the VRP with time windows."""

# Instantiate the data problem.

data = create_data_model()

# Create the routing index manager.

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),

data['num_vehicles'], data['depot'])

# Create Routing Model.

routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.

def time_callback(from_index, to_index):

"""Returns the travel time between the two nodes."""

# Convert from routing variable Index to time matrix NodeIndex.

from_node = manager.IndexToNode(from_index)

to_node = manager.IndexToNode(to_index)

return data['time_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(time_callback)

def distance_callback(from_index, to_index):

"""Returns the distance between the two nodes."""

# Convert from routing variable Index to distance matrix NodeIndex.

from_node = manager.IndexToNode(from_index)

to_node = manager.IndexToNode(to_index)

return data['distance_matrix'][from_node][to_node]

transit_callback_index_distance = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index_distance)

# 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)

return data['demands'][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(

demand_callback)

routing.AddDimensionWithVehicleCapacity(

demand_callback_index,

0, # null capacity slack

data['vehicle_capacities'], # vehicle maximum capacities

True, # start cumul to zero

'Capacity')

# Add Time Windows constraint.

time = 'Time'

routing.AddDimension(

transit_callback_index_distance,

30, # allow waiting time

30, # maximum time per vehicle

False, # Don't force start cumul to zero.

time)

time_dimension = routing.GetDimensionOrDie(time)

# Add time window constraints for each location except depot.

for location_idx, time_window in enumerate(data['time_windows']):

if location_idx == data['depot']:

continue

index = manager.NodeToIndex(location_idx)

time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

# Add time window constraints for each vehicle start node.

depot_idx = data['depot']

for vehicle_id in range(data['num_vehicles']):

index = routing.Start(vehicle_id)

time_dimension.CumulVar(index).SetRange(

data['time_windows'][depot_idx][0],

data['time_windows'][depot_idx][1])

# Instantiate route start and end times to produce feasible times.

for i in range(data['num_vehicles']):

routing.AddVariableMinimizedByFinalizer(

time_dimension.CumulVar(routing.Start(i)))

routing.AddVariableMinimizedByFinalizer(

time_dimension.CumulVar(routing.End(i)))

# Add Distance constraint.

dimension_name = 'Distance'

routing.AddDimension(

transit_callback_index_distance,

0, # no slack

3000, # vehicle maximum travel distance

True, # start cumul to zero

dimension_name)

distance_dimension = routing.GetDimensionOrDie(dimension_name)

distance_dimension.SetGlobalSpanCostCoefficient(100)

# Define Transportation Requests.

for request in data['pickups_deliveries']:

pickup_index = manager.NodeToIndex(request[0])

delivery_index = manager.NodeToIndex(request[1])

routing.AddPickupAndDelivery(pickup_index, delivery_index)

routing.solver().Add(

routing.VehicleVar(pickup_index) == routing.VehicleVar(

delivery_index))

routing.solver().Add(

distance_dimension.CumulVar(pickup_index) <=

distance_dimension.CumulVar(delivery_index))

# Setting first solution heuristic.

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

search_parameters.first_solution_strategy = (

routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.

solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.

if solution:

print_solution(data, manager, routing, solution)

else:

print('no')

if __name__ == '__main__':

main()

angelo manzatto

unread,

May 10, 2021, 6:25:30 AM5/10/21

to or-tools...@googlegroups.com

You data['demands'] is size 9 and should be 10, exactly like the other arrays, matrices on your code.

If you change the '' pickups_deliveries' and ' demands' for the following lines it returns "no", but I suspect it is because id didn't find a feasible solution with the problem formulation that you will have to check.

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

data['demands'] = [0, 0, 1, 1, -1, 4, 2, -1, -4, -2]

--
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/7b198c3c-7aff-4cb2-a775-0087c5191913n%40googlegroups.com.

uni_r

unread,

May 10, 2021, 9:14:58 AM5/10/21

to or-tools-discuss

Thank you Angelo, I edited the data and now it prints "no" to me too!

I have tried increasing the number of vehicles and capacities, but it still does not find solutions. How is this possible?

Could it be because there is some problem in the code?

angelo manzatto

unread,

May 10, 2021, 2:45:14 PM5/10/21

to or-tools-discuss

The calculation for the time dimension have something wrong

I had to open the time windows restriction and change the time callback limit to start giving an answer

data['time_windows'] = [

(0, 9999999), # depot

(0, 9999999), # 1

(0, 9999999), # 2

(0, 9999999), # 3

(0, 9999999), # 4

(0, 9999999), # 5

(0, 9999999), # 6

(0, 9999999), # 7

(0, 9999999), # 8

(0, 9999999), # 9

]

# Add Time Windows constraint.

time = 'Time'

routing.AddDimension(

transit_callback_index_distance,

999999, # allow waiting time

999999, # maximum time per vehicle

False, # Don't force start cumul to zero.

time)

time_dimension = routing.GetDimensionOrDie(time)

Objective: 228392

Route for vehicle 0:

0 Time(0,0) Carico: 0 -> 3 Time(696,696) Carico: 1 -> 7 Time(1198,1198) Carico: 0 -> 0 Time(1392,1392) Carico:0)

Time of the route: 1392min

Load of the route: 0

Distance of the route: 1392m

Route for vehicle 1:

0 Time(0,0) Carico: 0 -> 5 Time(274,274) Carico: 4 -> 6 Time(502,502) Carico: 6 -> 8 Time(696,696) Carico: 2 -> 9 Time(970,970) Carico: 0 -> 0 Time(1164,1164) Carico:0)

Time of the route: 1164min

Load of the route: 0

Distance of the route: 1164m

Route for vehicle 2:

0 Time(0,0) Carico: 0 -> 0 Time(0,0) Carico:0)

Time of the route: 0min

Load of the route: 0

Distance of the route: 0m

Route for vehicle 3:

0 Time(0,0) Carico: 0 -> 2 Time(776,776) Carico: 1 -> 1 Time(1460,1460) Carico: 1 -> 4 Time(1654,1654) Carico: 0 -> 0 Time(2236,2236) Carico:0)

Time of the route: 2236min

Load of the route: 0

Distance of the route: 2236m

Total time of all routes: 4792min

Total load of all routes: 0

Total distance of all routes: 0m

Mizux Seiha

unread,

May 11, 2021, 6:53:27 AM5/11/21

to or-tools-discuss

Here the gist of your problem with few modifications: https://gist.github.com/Mizux/4870e4af09b31dd45b7ac632d1830a73

Note concerning my modifications:
- Feature: First I allowed nodes to be dropped, it means you can have a partial solution and focus on why few nodes have been dropped (see below)

- Rework: Technically you don't need "data" in your print_solution function you can simply look at each dimension node's CumulVar, personally I feel it better to inspect solution than "recomputing" load etc...
also since you have a distance dimension you don't need to retrieve the distance using the arc cost. (i.e. same "code" for capacity, time or distance)
- Fix: In your time dimension you wrongly use the transit_callback_index_distance instead of the transit_callback_index.

note: In my source code I renamed them and reorganize a little bit the code e.g. register the time callback just above the Time Dimension creation i.e. try to keep related code block close from each other...

- Improve: In the search parameter I enable the neighbor local search to see if we can improve the solution (this is always good to enable it when playing with GlobalSpanCoefficient)

now investigating the solution, we can see:
```sh

Dropped nodes: 2 4 6 7

...

```

Knowing there are part of Pickup&Delivery i.e. 2 -> 6, and 4 -> 7 respectively, let's try to look at the time windows...

data['time_windows'] = [

(0, 5), # depot

(7, 12), # 1

(10, 15), # 2

(16, 18), # 3

(10, 13), # 4

(0, 5), # 5

(5, 10), # 6

(0, 4), # 7

(5, 10), # 8

(0, 3), # 9

so we have the following TW constraints, (and the P&D give us an order constraint):
2 [10,15] -> 6 [5, 10]

4 [10,13] -> 7 [0, 4]

since the minimum time transit is strictly positive it is impossible to visit node 2 (or node 4) then node 6 (or 7) thus theses Pickup & Delivery are infeasibles.

Since I allow to drop node, solver had the possibility to drop them and give a "partial" solution.

Hope it will help you !

uni_r

unread,

May 12, 2021, 1:48:45 PM5/12/21

to or-tools-discuss

Thank you very much! this helped me a lot!

Now I tried to increase the problem dimension ; i used a a CPDVRPTW with time and distance matrix of 25x25.

The bad thing is that the kernel dies, do you know what could be the reason??

Mizux Seiha

unread,

May 12, 2021, 2:54:33 PM5/12/21

to or-tools-discuss

If you are using the google colab provided kernel, you may expect some limitations.

So 2 solutions:
1. Try to run it locally on your machine by installing python and the or-tools package OR

2. Setup a Jupyter kernel engine on your GCP account and do some port forwarding on your machine to connect colab with your GCP instance
Please, take a look at this video which explain it (ed it is for tensorflow BUT it will work for OR-Tools too) -> https://www.youtube.com/watch?v=U5HyNzf_ips
note: You don't need a GPU/Tensor enabled VM so you can stick on a cheaper regular CPU only VM since or-tools won't do any GPGPU...

uni_r

unread,

May 13, 2021, 6:27:41 AM5/13/21

to or-tools-discuss

Hello, i'm running the code using Jupyter Notebook...so i think is the your first point...but it doesnt' work

uni_r

unread,

May 13, 2021, 9:27:27 AM5/13/21

to or-tools-discuss

Hello, i tried again to run the code but this time i changed the waiting time and i set it as 999.

Now it works but i dont understand why he drops the request [11,8], could you tell me why??The time windows are not contradictory i think!

This are the input data:

data['distance_matrix']= [

[0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0],

[1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1] ,

[0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0],

]

data['time_matrix'] = [

[0,8,9,11,8,11,8,14,9,9,31,31,5,17,12,16,16,16,16],

[6,0,3,3,3,5,5,6,4,6,28,28,7,22,11,21,21,20,20],

[10,5,0,5,2,2,3,5,2,3,27,27,6,18,10,26,26,19,19],

[7,3,5,0,4,7,7,7,5,10,30,30,8,21,12,20,20,21,21],

[15,8,1,5,0,3,4,4,1,4,27,27,12,17,11,23,23,25,25],

[10,14,7,10,6,0,9,8,5,6,28,28,6,21,10,26,26,19,19],

[8,16,6,12,9,6,0,16,10,6,26,26,5,25,8,24,24,17,17],

[17,14,12,4,8,12,14,0,3,12,28,28,17,19,14,23,23,27,27],

[18,11,5,7,3,7,9,4,0,7,29,29,17,19,14,24,24,27,27],

[10,5,1,6,3,3,3,5,3,0,28,28,6,19,10,25,25,19,19],

[31,31,26,31,31,29,25,27,27,26,0,0,25,33,19,39,39,38,38],

[7,7,5,9,10,9,4,18,8,4,25,25,0,20,7,20,20,14,14],

[18,30,18,21,25,19,21,17,17,22,33,33,20,0,18,28,28,28,28],

[12,14,9,16,13,15,8,13,15,9,19,19,8,18,0,26,26,20,20],

[16,23,24,24,24,27,23,23,24,24,39,39,20,29,27,0,0,28,28],

[16,22,18,25,21,24,16,24,22,17,38,38,14,27,20,27,27,0,0],

]

data['pickups_deliveries'] = [

[10,7],

[11,8],

[12,3],

[13,5],

[14,4],

[15,6],

[16,9],

[17,1],

[18,2],

]

data['time_windows'] = [

(0, 1000), # depot

(420,480), # 1

(60, 120), # 2

(360, 480), # 3

(180, 300), # 4

(300, 360), # 5

(360, 480), # 6

(120, 180), # 7

(240, 360), # 8

(120, 240), # 9

(0, 10000), # 10

(0, 10000), # 11

(0, 10000), # 12

(0, 10000), # 13

(0, 10000), # 14

(0, 10000), # 15

(0, 10000), # 16

(0, 10000), # 17

(0, 10000), # 18

]

Reply all

Reply to author

Forward