Problem when solving VRPTW - Key Error 1

[ErikUGent]

Dear,

When I run the algorithm hereunder, I get the following error:

_File "/Users/erikdekuyffer/.conda/envs/Test_2/lib/python3.9/site-packages/vrpy/vrp.py", line 252, in solve self._initialize(solver) File "/Users/erikdekuyffer/.conda/envs/Test_2/lib/python3.9/site-packages/vrpy/vrp.py", line 478, in _initialize self._convert_initial_routes_to_digraphs() File "/Users/erikdekuyffer/.conda/envs/Test_2/lib/python3.9/site-packages/vrpy/vrp.py", line 945, in _convert_initial_routes_to_digraphs edge_cost = self.G.edges[i, j]["cost"][0] File "/Users/erikdekuyffer/.conda/envs/Test_2/lib/python3.9/site-packages/networkx/classes/reportviews.py", line 1093, in getitem return self.adjdict[u][v] KeyError: 1

The problem situates around nodes 1, 2, 4, 16 and 22. When I set the upper time limit for node 1 to 675, the error is not present anymore at node 1. However, this is not the goal of the exercise and when I run the VRPTW solver of OR tools, I do get a result to the problem. Could you tell me what is going wrong?

Kind regards, Erik

from curses import A_LEFT
from networkx import DiGraph, from_numpy_matrix, relabel_nodes, set_node_attributes
from numpy import array
from vrpy import VehicleRoutingProblem
import networkx as nx
import time

def compose (f, g):
    return lambda x : f(g)

# Distance matrix
DISTANCES = [
 [0,673, 629, 629, 630, 630, 630, 631, 632, 632, 627, 628,   9,   5,   2, 521, 520, 518, 517, 516, 515, 514, 522, 519, 518,   0],
 [0,  0,  45,  45,  45,  44,  44,  44,  43,  43,  46,  46, 676, 675, 674, 224, 224, 223, 224, 226, 227, 229, 225, 225, 227, 673],
 [0, 45,   0,   1,   1,   2,   3,   4,   4,   4,   2,   1, 631, 630, 629, 198, 198, 197, 198, 199, 201, 202, 200, 199, 201, 629],
 [0, 45,   1,   0,   1,   1,   2,   3,   3,   4,   3,   2, 632, 631, 630, 199, 198, 197, 199, 200, 202, 203, 201, 200, 201, 629],
 [0, 45,   1,   1,   0,   1,   1,   2,   3,   3,   3,   2, 632, 631, 630, 200, 199, 198, 200, 201, 202, 204, 201, 201, 202, 630],
 [0, 44,   2,   1,   1,   0,   1,   2,   2,   2,   4,   3, 632, 632, 631, 200, 200, 199, 200, 201, 203, 204, 202, 201, 203, 630],
 [0, 44,   3,   2,   1,   1,   0,   1,   1,   2,   5,   4, 633, 632, 631, 201, 200, 199, 201, 202, 204, 205, 203, 202, 203, 630],
 [0, 44,   4,   3,   2,   2,   1,   0,   1,   1,   6,   5, 633, 632, 632, 202, 201, 200, 202, 203, 205, 206, 204, 203, 204, 631],
 [0, 43,   4,   3,   3,   2,   1,   1,   0,   0,   6,   5, 634, 633, 632, 203, 202, 201, 202, 203, 205, 207, 204, 204, 205, 632],
 [0, 43,   4,   4,   3,   2,   2,   1,   0,   0,   6,   6, 634, 633, 633, 203, 202, 201, 203, 204, 205, 207, 204, 204, 205, 632],
 [0, 46,   2,   3,   3,   4,   5,   6,   6,   6,   0,   1, 630, 629, 628, 196, 196, 195, 196, 197, 199, 200, 198, 197, 199, 627],
 [0, 46,   1,   2,   2,   3,   4,   5,   5,   6,   1,   0, 631, 630, 629, 197, 197, 196, 197, 198, 200, 201, 199, 198, 200, 628],
 [0,676, 631, 632, 632, 632, 633, 633, 634, 634, 630, 631,   0,   3,   6, 526, 524, 523, 522, 521, 520, 519, 527, 523, 522,   9],
 [0,675, 630, 631, 631, 632, 632, 632, 633, 633, 629, 630,   3,   0,   3, 524, 522, 521, 520, 519, 518, 517, 525, 522, 521,   5],
 [0,674, 629, 630, 630, 631, 631, 632, 632, 633, 628, 629,   6,   3,   0, 522, 521, 520, 519, 518, 517, 515, 523, 520, 519,   2],
 [0,224, 198, 199, 200, 200, 201, 202, 203, 203, 196, 197, 526, 524, 522,   0,   2,   4,   4,   5,   6,   7,   2,   2,   4, 521],
 [0,224, 198, 198, 199, 200, 200, 201, 202, 202, 196, 197, 524, 522, 521,   2,   0,   2,   2,   3,   5,   6,   4,   2,   3, 520],
 [0,223, 197, 197, 198, 199, 199, 200, 201, 201, 195, 196, 523, 521, 520,   4,   2,   0,   2,   3,   4,   6,   6,   3,   4, 518],
 [0,224, 198, 199, 200, 200, 201, 202, 202, 203, 196, 197, 522, 520, 519,   4,   2,   2,   0,   1,   3,   5,   6,   3,   3, 517],
 [0,226, 199, 200, 201, 201, 202, 203, 203, 204, 197, 198, 521, 519, 518,   5,   3,   3,   1,   0,   2,   3,   6,   3,   2, 516],
 [0,227, 201, 202, 202, 203, 204, 205, 205, 205, 199, 200, 520, 518, 517,   6,   5,   4,   3,   2,   0,   2,   7,   4,   3, 515],
 [0,229, 202, 203, 204, 204, 205, 206, 207, 207, 200, 201, 519, 517, 515,   7,   6,   6,   5,   3,   2,   0,   8,   5,   4, 514],
 [0,225, 200, 201, 201, 202, 203, 204, 204, 204, 198, 199, 527, 525, 523,   2,   4,   6,   6,   6,   7,   8,   0,   4,   5, 522],
 [0,225, 199, 200, 201, 201, 202, 203, 204, 204, 197, 198, 523, 522, 520,   2,   2,   3,   3,   3,   4,   5,   4,   0,   1, 519],
 [0,227, 201, 201, 202, 203, 203, 204, 205, 205, 199, 200, 522, 521, 519,   4,   3,   4,   3,   2,   3,   4,   5,   1,   0, 518],
 [0,  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0],
 ]

TRAVEL_TIMES = [
 [0,673, 629, 629, 630, 630, 630, 631, 632, 632, 627, 628,   9,   5,   2, 521, 520, 518, 517, 516, 515, 514, 522, 519, 518,   0],
 [0,  0,  45,  45,  45,  44,  44,  44,  43,  43,  46,  46, 676, 675, 674, 224, 224, 223, 224, 226, 227, 229, 225, 225, 227, 673],
 [0, 45,   0,   1,   1,   2,   3,   4,   4,   4,   2,   1, 631, 630, 629, 198, 198, 197, 198, 199, 201, 202, 200, 199, 201, 629],
 [0, 45,   1,   0,   1,   1,   2,   3,   3,   4,   3,   2, 632, 631, 630, 199, 198, 197, 199, 200, 202, 203, 201, 200, 201, 629],
 [0, 45,   1,   1,   0,   1,   1,   2,   3,   3,   3,   2, 632, 631, 630, 200, 199, 198, 200, 201, 202, 204, 201, 201, 202, 630],
 [0, 44,   2,   1,   1,   0,   1,   2,   2,   2,   4,   3, 632, 632, 631, 200, 200, 199, 200, 201, 203, 204, 202, 201, 203, 630],
 [0, 44,   3,   2,   1,   1,   0,   1,   1,   2,   5,   4, 633, 632, 631, 201, 200, 199, 201, 202, 204, 205, 203, 202, 203, 630],
 [0, 44,   4,   3,   2,   2,   1,   0,   1,   1,   6,   5, 633, 632, 632, 202, 201, 200, 202, 203, 205, 206, 204, 203, 204, 631],
 [0, 43,   4,   3,   3,   2,   1,   1,   0,   0,   6,   5, 634, 633, 632, 203, 202, 201, 202, 203, 205, 207, 204, 204, 205, 632],
 [0, 43,   4,   4,   3,   2,   2,   1,   0,   0,   6,   6, 634, 633, 633, 203, 202, 201, 203, 204, 205, 207, 204, 204, 205, 632],
 [0, 46,   2,   3,   3,   4,   5,   6,   6,   6,   0,   1, 630, 629, 628, 196, 196, 195, 196, 197, 199, 200, 198, 197, 199, 627],
 [0, 46,   1,   2,   2,   3,   4,   5,   5,   6,   1,   0, 631, 630, 629, 197, 197, 196, 197, 198, 200, 201, 199, 198, 200, 628],
 [0,676, 631, 632, 632, 632, 633, 633, 634, 634, 630, 631,   0,   3,   6, 526, 524, 523, 522, 521, 520, 519, 527, 523, 522,   9],
 [0,675, 630, 631, 631, 632, 632, 632, 633, 633, 629, 630,   3,   0,   3, 524, 522, 521, 520, 519, 518, 517, 525, 522, 521,   5],
 [0,674, 629, 630, 630, 631, 631, 632, 632, 633, 628, 629,   6,   3,   0, 522, 521, 520, 519, 518, 517, 515, 523, 520, 519,   2],
 [0,224, 198, 199, 200, 200, 201, 202, 203, 203, 196, 197, 526, 524, 522,   0,   2,   4,   4,   5,   6,   7,   2,   2,   4, 521],
 [0,224, 198, 198, 199, 200, 200, 201, 202, 202, 196, 197, 524, 522, 521,   2,   0,   2,   2,   3,   5,   6,   4,   2,   3, 520],
 [0,223, 197, 197, 198, 199, 199, 200, 201, 201, 195, 196, 523, 521, 520,   4,   2,   0,   2,   3,   4,   6,   6,   3,   4, 518],
 [0,224, 198, 199, 200, 200, 201, 202, 202, 203, 196, 197, 522, 520, 519,   4,   2,   2,   0,   1,   3,   5,   6,   3,   3, 517],
 [0,226, 199, 200, 201, 201, 202, 203, 203, 204, 197, 198, 521, 519, 518,   5,   3,   3,   1,   0,   2,   3,   6,   3,   2, 516],
 [0,227, 201, 202, 202, 203, 204, 205, 205, 205, 199, 200, 520, 518, 517,   6,   5,   4,   3,   2,   0,   2,   7,   4,   3, 515],
 [0,229, 202, 203, 204, 204, 205, 206, 207, 207, 200, 201, 519, 517, 515,   7,   6,   6,   5,   3,   2,   0,   8,   5,   4, 514],
 [0,225, 200, 201, 201, 202, 203, 204, 204, 204, 198, 199, 527, 525, 523,   2,   4,   6,   6,   6,   7,   8,   0,   4,   5, 522],
 [0,225, 199, 200, 201, 201, 202, 203, 204, 204, 197, 198, 523, 522, 520,   2,   2,   3,   3,   3,   4,   5,   4,   0,   1, 519],
 [0,227, 201, 201, 202, 203, 203, 204, 205, 205, 199, 200, 522, 521, 519,   4,   3,   4,   3,   2,   3,   4,   5,   1,   0, 518],
 [0,  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0],
 ]

# Time windows (key: node, value: lower/upper bound)

TIME_WINDOWS_LOWER = {0: 0, 1: 200, 2: 400, 3: 600, 4: 0, 5: 680, 6: 900, 7: 900, 8: 780, 9: 900, 10: 700, 11: 0, 12: 200, 13: 0, 14: 600, 15: 900, 16: 200, 17: 0, 18: 0, 19: 800, 20: 600, 21: 500, 22: 200, 23: 650, 24: 700,}
TIME_WINDOWS_UPPER = {1: 400, 2: 600, 3: 900, 4: 500, 5: 1200, 6: 1000, 7: 1200, 8: 1400, 9: 1000, 10: 1000, 11: 1000, 12: 1500, 13: 800, 14: 900, 15: 1200, 16: 350, 17: 900, 18: 1000, 19: 1000, 20: 700, 21: 900, 22: 300, 23: 800, 24: 1000,}

start_time = time.time()

# Transform distance matrix into DiGraph
A = array(DISTANCES, dtype=[("cost", int)])
G_d = from_numpy_matrix(A, create_using=DiGraph())

# Transform time matrix into DiGraph
A = array(TRAVEL_TIMES, dtype=[("time", int)])
G_t = from_numpy_matrix(A, create_using=DiGraph())

# Merge
G = nx.compose(G_d,G_t)

# Set time windows
set_node_attributes(G, values=TIME_WINDOWS_LOWER, name="lower")
set_node_attributes(G, values=TIME_WINDOWS_UPPER, name="upper")

# The depot is relabeled as Source and Sink
G = relabel_nodes(G, {0: "Source", 25: "Sink"})

# The VRP is defined and solved
prob = VehicleRoutingProblem(G, num_stops=None, load_capacity=None, duration=None, time_windows=True, pickup_delivery=False, distribution_collection=False, drop_penalty=None, fixed_cost=0, num_vehicles=10, use_all_vehicles=False, periodic=None, mixed_fleet=False, minimize_global_span=False)
#prob = VehicleRoutingProblem(G, time_windows=True)
prob.solve()

print(prob.best_routes_cost)
print(prob.best_routes_duration)
print(prob.best_value)
print(prob.best_routes)
print(prob.arrival_time)

print('the elapsed time:%s'% (round(time.time() - start_time, 4)))

[torressa]

I think this is the same example of your original issue?

[ErikUGent]

Hello,

Yes it is. I thought, since the other one was closed, that I needed a new one.

Regards, Erik

[Kuifje02]

I think this may be a networkx issue. I have noticed some differences between syntaxes G.edges[i, j]["cost"] and G.edges[i][j]["cost"] and this may be causing the problem.

[ErikUGent]

Thanks!

do you think you can solve It?

regards

[torressa]

Closing. Duplicate of #143 see discussion there.