I'm trying to solve a Vehicle Routing Problem (VRP) using Gurobi and Python. By using the following code I get this error :
obj = quicksum(c[i,j]*x[k,i,j] for k in range(p) for i in range(n+1) for j in range(n+1) if i != j)
~^^^^^
KeyError: (0, 51)
The error message indicates that there is a KeyError at line 25, which corresponds to the objective function definition.
It seems that the issue is related to the distance matrix or the decision variables, as the key (0,51) is not found.
The used code :
import numpy as np
import vrp_utils
from gurobipy import *
# Load VRP instance from the vrp lib
instance_name = 'CMT1'
instance_path = f'vrp_lib/{instance_name}'
distance_matrix, demand, capacity = vrp_utils.load_vrp_instance(instance_path)
# Define model variables and parameters
n = len(distance_matrix)
p = 1
Q = capacity
c = {(i,j): distance_matrix[i][j] for i in range(n) for j in range(n) if i != j}
# Initialize Gurobi model
model = Model()
# Define decision variables
x = {}
for k in range(p):
for i in range(n+1):
for j in range(n+1):
if i != j:
x[k,i,j] = model.addVar(vtype=GRB.BINARY, name=f'x_{k}_{i}_{j}')
# Define objective function
obj = quicksum(c[i,j]*x[k,i,j] for k in range(p) for i in range(n+1) for j in range(n+1) if i != j)
model.setObjective(obj, GRB.MINIMIZE)
# Define constraints
for j in range(1,n):
model.addConstr(quicksum(x[k,i,j] for k in range(p) for i in range(n+1) if i != j) == 1, name=f'depot_assignment_{j}')
for k in range(p):
model.addConstr(quicksum(x[k,0,j] for j in range(1,n)) == 1, name=f'single_depot_{k}')
for j in range(n):
for k in range(p):
model.addConstr(quicksum(x[k,i,j] for i in range(n+1) if i != j) == quicksum(x[k,j,i] for i in range(n+1) if i != j), name=f'symmetric_routes_{k}_{j}')
for k in range(p):
model.addConstr(quicksum(demand[j]*x[k,i,j] for i in range(n+1) for j in range(n+1) if i != j) <= Q, name=f'capacity_{k}')
for s in range(1,n):
for k in range(p):
for S in vrp_utils.subsets(range(1,n), s):
model.addConstr(quicksum(x[k,i,j] for i in [0] + list(S) for j in [0] + list(S) if i != j) <= s-1, name=f'subset_{k}_{S}')
# Solve model
model.optimize()
# Print solution
if model.status == GRB.OPTIMAL:
for k in range(p):
print(f'Depot {k+1}:')
route = [0]
j = 0
while True:
i = np.argmax([x[k,i,j].x for i in range(n+1) if i != j])
if x[k,i,j].x == 0:
break
route.append(i)
j = i
route.append(0)
print(f' -> '.join(map(str, route)))
print(f'Total distance: {model.objVal:.2f}')
else:
print('No solution found.')
The load)_instance function is defined as follows:
def load_vrp_instance(filename):
with open(filename, 'r') as f:
lines = f.readlines()
# Parse problem size
n, capacity = None, None
for line in lines:
if line.startswith("DIMENSION"):
n = int(line.split(":")[1])
elif line.startswith("CAPACITY"):
capacity = int(line.split(":")[1])
# Parse node coordinates and demands
coordinates = []
demands = []
for line in lines[7:7+n]:
_, x, y, d = line.split()
coordinates.append((float(x), float(y)))
demands.append(int(d))
# Compute distance matrix
distance_matrix = []
for i in range(n):
row = []
for j in range(n):
xi, yi = coordinates[i]
xj, yj = coordinates[j]
distance = ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
print(distance)
row.append(distance)
distance_matrix.append(row)
return distance_matrix, demands, capacity
The error occurs when trying to solve this instance :
NAME : CMT1
COMMENT : 524.61
TYPE : CVRP
DIMENSION : 51
EDGE_WEIGHT_TYPE : EUC_2D
CAPACITY : 160
NODE_COORD_SECTION
1 30.00000 40.00000 0
2 37.00000 52.00000 0
3 49.00000 49.00000 0
4 52.00000 64.00000 0
5 20.00000 26.00000 0
6 40.00000 30.00000 0
7 21.00000 47.00000 0
8 17.00000 63.00000 0
9 31.00000 62.00000 0
10 52.00000 33.00000 0
11 51.00000 21.00000 0
12 42.00000 41.00000 0
13 31.00000 32.00000 0
14 5.00000 25.00000 0
15 12.00000 42.00000 0
16 36.00000 16.00000 0
17 52.00000 41.00000 0
18 27.00000 23.00000 0
19 17.00000 33.00000 0
20 13.00000 13.00000 0
21 57.00000 58.00000 0
22 62.00000 42.00000 0
23 42.00000 57.00000 0
24 16.00000 57.00000 0
25 8.00000 52.00000 0
26 7.00000 38.00000 0
27 27.00000 68.00000 0
28 30.00000 48.00000 0
29 43.00000 67.00000 0
30 58.00000 48.00000 0
31 58.00000 27.00000 0
32 37.00000 69.00000 0
33 38.00000 46.00000 0
34 46.00000 10.00000 0
35 61.00000 33.00000 0
36 62.00000 63.00000 0
37 63.00000 69.00000 0
38 32.00000 22.00000 0
39 45.00000 35.00000 0
40 59.00000 15.00000 0
41 5.00000 6.00000 0
42 10.00000 17.00000 0
43 21.00000 10.00000 0
44 5.00000 64.00000 0
45 30.00000 15.00000 0
46 39.00000 10.00000 0
47 32.00000 39.00000 0
48 25.00000 32.00000 0
49 25.00000 55.00000 0
50 48.00000 28.00000 0
51 56.00000 37.00000 0
DEMAND_SECTION
1 0
2 7
3 30
4 16
5 9
6 21
7 15
8 19
9 23
10 11
11 5
12 19
13 29
14 23
15 21
16 10
17 15
18 3
19 41
20 9
21 28
22 8
23 8
24 16
25 10
26 28
27 7
28 15
29 14
30 6
31 19
32 11
33 12
34 23
35 26
36 17
37 6
38 9
39 15
40 14
41 7
42 27
43 13
44 11
45 16
46 10
47 5
48 25
49 17
50 18
51 10
EOF
I try printing the distance matrix and decision variables to see if there are any unexpected values or missing entries, but the problem persist.
If you have any idea please help.
Could it be that you append only n values to distance_matrix instead of n+1 in your code below, meaning you would want to range over n+1 instead?
# Compute distance matrix
distance_matrix = []
for i in range(n):
row = []
for j in range(n):
xi, yi = coordinates[i]
xj, yj = coordinates[j]
distance = ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5
print(distance)
row.append(distance)
distance_matrix.append(row)
since your objective function runs over n+1:
obj = quicksum(c[i,j]*x[k,i,j] for k in range(p) for i in range(n+1) for j in range(n+1) if i != j)
There might also be some +1 discrepancy with the following line?
c = {(i,j): distance_matrix[i][j] for i in range(n) for j in range(n) if i != j}