Very bizarre error code in Python script based on VRPy

Question

Hereunder you can find the Python script I use to solve a vehicle routing problem with time windows. I have used exactly the same script with 8, 16, 24, 32 and 40 data points and for all, except the 24 case, it works. When I set the parameter time_window to False, it works, but that is not an option.

The error I get is:

  File "/Users/erikdekuyffer/Documents/Doctoraat/Second Project/VRPy/VRPTW_VRPy_Square_24.py", line 97, in <module>
    prob.solve()
  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 Script is:

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=999, use_all_vehicles=False, periodic=None, mixed_fleet=False, minimize_global_span=False)
#prob = VehicleRoutingProblem(G, time_windows=False)
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)))

I expected the routes that take into account time windows.

I'm not familiar with `vrpy`, but FWIW, this looks like a bug in it or `networkx` since it's a generic error while accessing a private member. You could use [a Python debugger](/q/4929251/4518341) to isolate the problem and file a bug against `vrpy`, and they'll be able to tell whether it's an issue in their package or `networkx` (as it's a dependency). — wjandrea, Jan 24 '23 at 21:04
Oh, actually, there seems to be [an existing issue about this](https://github.com/Kuifje02/vrpy/issues/131). There might be others too; look through [these](https://github.com/Kuifje02/vrpy/issues?q=is%3Aissue+KeyError). — wjandrea, Jan 24 '23 at 21:09
BTW, welcome to Stack Overflow! Check out the [tour], and [ask] if you want tips. If my comments point you to the solution, you can [answer your own question](/help/self-answer) :) — wjandrea, Jan 24 '23 at 21:09
Dear wjandrea, thanks for the link to the existing issue. I had a look at it and yes, this error is completely similar. However, there is no solution mentionned. :-( Could you tell me perhaps what he means by 'The issue lied in simply not making the TIME_WINDOW_UPPER & TIME_WINDOW_LOWER variables correctly.' or could I get in contact with dschoon98? — Erik De Kuyffer, Jan 25 '23 at 21:20
If you make an account on GitHub, you can comment on the issue. You could also open a new issue if you want, since it seems to me like the error message is not very clear. — wjandrea, Jan 26 '23 at 01:29
Dear, I still did not get a response. I created an issue on GitHub for it, since I think there is a bug. Thanks for having a closer look.... https://github.com/Kuifje02/vrpy/issues/144#issue-1570605674 — Erik De Kuyffer, Feb 03 '23 at 23:42

Very bizarre error code in Python script based on VRPy

0 Answers0