使用Gurobi求解VRP时触发KeyError(0,51)问题求助

错误根源 #

KeyError(0,51)的核心原因是距离矩阵字典c的索引范围和决策变量x的索引范围不匹配：

• 从CMT1实例加载的distance_matrix是51×51的（对应实例中DIMENSION=51），Python中索引为0~50，因此生成的字典c只包含(i,j)其中i,j ∈ 0~50且i≠j的键。
• 业务代码中定义决策变量x时，使用了range(n+1)（n=51，即索引0~51），目标函数遍历x的索引时，会访问到(0,51)这类c中不存在的键，触发KeyError。

解决步骤 #

1. 修正决策变量的索引范围 #

将所有定义x的循环中的range(n+1)改为range(n)，确保和c的索引范围一致：

# 修正后的决策变量定义
x = {}
for k in range(p):
    for i in range(n):
        for j in range(n):
            if i != j:
                x[k,i,j] = model.addVar(vtype=GRB.BINARY, name=f'x_{k}_{i}_{j}')

2. 修正目标函数的遍历范围 #

同步修改目标函数中的索引范围，避免访问不存在的c键：

# 修正后的目标函数
obj = quicksum(c[i,j]*x[k,i,j] for k in range(p) for i in range(n) for j in range(n) if i != j)
model.setObjective(obj, GRB.MINIMIZE)

3. 修正所有约束中的索引范围 #

检查并修改所有使用range(n+1)的约束代码，确保索引在0~50范围内：

# 修正后的约束示例
# 1. 客户访问约束
for j in range(1,n):
    model.addConstr(quicksum(x[k,i,j] for k in range(p) for i in range(n) if i != j) == 1, name=f'depot_assignment_{j}')

# 2. 车辆出发约束
for k in range(p):
    model.addConstr(quicksum(x[k,0,j] for j in range(1,n)) == 1, name=f'single_depot_{k}')

# 3. 流量守恒约束
for j in range(n):
    for k in range(p):
        model.addConstr(quicksum(x[k,i,j] for i in range(n) if i != j) == quicksum(x[k,j,i] for i in range(n) if i != j), name=f'symmetric_routes_{k}_{j}')

# 4. 容量约束
for k in range(p):
    model.addConstr(quicksum(demand[j]*x[k,i,j] for i in range(n) for j in range(n) if i != j) <= Q, name=f'capacity_{k}')

# 5. 子回路消除约束
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}')

4. 修正路径输出逻辑 #

最后修改路径输出部分的索引范围，避免越界：

# 修正后的路径输出
if model.status == GRB.OPTIMAL:
    for k in range(p):
        print(f'Depot {k+1}:')
        route = [0]
        j = 0
        while True:
            valid_i = [i for i in range(n) if i != j]
            if not valid_i:
                break
            i = valid_i[np.argmax([x[k,i,j].x for i in valid_i])]
            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}')

额外检查点 #

• 确认load_vrp_instance函数中，demands的长度为51，索引0对应depot的需求0，和业务代码中的demand[j]调用匹配。
• 运行前可以打印c的键范围，确认最大索引为50，避免再次出现索引不匹配问题。

内容的提问来源于stack exchange，提问作者rajah