Gurobi实现多车场车辆路径规划(MDVRP)代码故障排查请求

常见错误排查点 #

• 决策变量约束缺失：未限制车辆路径必须从所属车场出发并返回，导致x_ijmk中节点与车场m无绑定关系。需添加约束确保车场m的车辆仅从m启动、最终返回m。
• 节点编号混淆：若车场与客户编号未区分（如车场和客户共用连续编号），易导致代码中节点归属逻辑错误。建议将车场单独编号（如0~init_M-1），客户编号从init_M开始（init_M~init_M+init_N-1）。
• 车辆分配约束错误：未严格限制各车场使用的车辆数不超过init_km[m]，或未绑定车辆与所属车场的对应关系。
• 负载约束逻辑错误：未关联客户需求与车辆所属车场，导致车辆负载计算与车场无关联，间接引发节点-车场匹配问题。

可运行MDVRP Gurobi实现代码 #

import gurobipy as gp
from gurobipy import GRB
import math

# 输入参数（替换为你的实际参数）
init_M = 2  # 车场数量
init_N = 5  # 客户数量
q = 10      # 车辆容量
init_km = [2, 2]  # 各车场可用车辆数
init_gi = [3, 4, 2, 5, 1]  # 客户需求（对应客户0~4）
# 车场坐标：索引0~init_M-1
init_xym = [(0, 0), (10, 10)]
# 客户坐标：索引0~init_N-1，对应编号init_M~init_M+init_N-1
init_xyii = [(2, 3), (5, 2), (7, 8), (3, 9), (8, 4)]

# 定义集合
M = range(init_M)  # 车场集合
N = range(init_M, init_M + init_N)  # 客户集合（编号从init_M开始）
V = list(M) + list(N)  # 所有节点集合

# 计算节点间距离
distance = {}
for i in V:
    for j in V:
        x1, y1 = init_xym[i] if i in M else init_xyii[i - init_M]
        x2, y2 = init_xym[j] if j in M else init_xyii[j - init_M]
        distance[i, j] = math.hypot(x1 - x2, y1 - y2)

# 创建模型
mdl = gp.Model("MDVRP")

# 决策变量：x[i,j,m,k] = 1表示车场m的第k辆车从节点i行驶到j
x = mdl.addVars(V, V, M, [range(km) for km in init_km], vtype=GRB.BINARY, name="x")
# 辅助变量：u[i,m,k]表示车场m的第k辆车到达节点i时的负载
u = mdl.addVars(V, M, [range(km) for km in init_km], vtype=GRB.CONTINUOUS, name="u")

# 目标函数：最小化总行驶距离
mdl.setObjective(gp.quicksum(distance[i,j] * x[i,j,m,k] for i in V for j in V for m in M for k in range(init_km[m])), GRB.MINIMIZE)

# 约束1：每个客户被恰好一辆车服务
for j in N:
    mdl.addConstr(gp.quicksum(x[i,j,m,k] for i in V for m in M for k in range(init_km[m]) if i != j) == 1, name=f"serve_customer_{j}")

# 约束2：路径流守恒（客户节点的流入等于流出）
for j in N:
    for m in M:
        for k in range(init_km[m]):
            mdl.addConstr(gp.quicksum(x[i,j,m,k] for i in V if i != j) == gp.quicksum(x[j,i,m,k] for i in V if i != j), name=f"flow_conservation_{j}_{m}_{k}")

# 约束3：车场m的第k辆车最多从车场出发一次
for m in M:
    for k in range(init_km[m]):
        mdl.addConstr(gp.quicksum(x[m,j,m,k] for j in N) <= 1, name=f"depart_depot_{m}_{k}")

# 约束4：车场m的第k辆车若出发则必须返回车场
for m in M:
    for k in range(init_km[m]):
        mdl.addConstr(gp.quicksum(x[i,m,m,k] for i in N) == gp.quicksum(x[m,j,m,k] for j in N), name=f"return_depot_{m}_{k}")

# 约束5：负载传递约束（仅当车辆从i行驶到j时生效）
for i in V:
    for j in N:
        for m in M:
            for k in range(init_km[m]):
                mdl.addConstr(u[j,m,k] >= u[i,m,k] + init_gi[j - init_M] - q * (1 - x[i,j,m,k]), name=f"load_transfer_{i}_{j}_{m}_{k}")

# 约束6：车辆从车场出发时负载为0
for m in M:
    for k in range(init_km[m]):
        mdl.addConstr(u[m,m,k] == 0, name=f"initial_load_{m}_{k}")

# 约束7：车辆负载不超过容量
for i in V:
    for m in M:
        for k in range(init_km[m]):
            mdl.addConstr(u[i,m,k] <= q, name=f"load_capacity_{i}_{m}_{k}")

# 约束8：服务客户时负载至少满足客户需求
for j in N:
    for m in M:
        for k in range(init_km[m]):
            mdl.addConstr(u[j,m,k] >= init_gi[j - init_M] * gp.quicksum(x[i,j,m,k] for i in V if i != j), name=f"meet_demand_{j}_{m}_{k}")

# 优化模型
mdl.optimize()

# 输出结果
if mdl.status == GRB.OPTIMAL:
    print("最优路径：")
    for m in M:
        print(f"\n车场{m}的车辆路径：")
        for k in range(init_km[m]):
            path = []
            current = m
            while True:
                next_node = None
                for j in V:
                    if x[current,j,m,k].X > 0.9:
                        next_node = j
                        break
                if next_node is None:
                    break
                path.append(current)
                if next_node == m:
                    path.append(m)
                    break
                current = next_node
            if len(path) > 1:
                print(f"车辆{k}：{' -> '.join(map(str, path))}")
else:
    print("未找到最优解")

代码说明 #

• 严格区分车场与客户编号，避免归属混淆；
• 约束确保车辆从所属车场出发并返回，绑定x_ijmk与车场m的对应关系；
• 加入负载约束保证车辆容量合规，同时关联客户需求与车辆服务逻辑；
• 输出结果时直接按车场分组展示路径，便于验证节点与车场的匹配性。

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