GurobiPy实现LRP路径规划异常求助：车辆未批量配送客户

问题描述 #

使用GurobiPy实现LRP时，客户可正确分配至仓库，但车辆路径不符合预期：每辆车仅服务单个客户，即便车辆容量仍有剩余，未实现多客户同趟配送。

数据集 #

3 10 
 10000 7500. 
 10000 7500. 
 10000 7500.  
 146 
 6739.72500 10355.05000 7650.40000  
 87 
 3204.86250 5457.07500 3845.40000
 672 
 4914.00000 26409.60000 19622.40000
 1337 
 32372.11250 29982.22500 21024.32500 
 31 
 1715.46250 2152.17500 1577.90000
 559 
 6421.51250 23701.60000 16197.02500
 2370 
 81972.37500 28499.25000 43134.00000 
 1089 
 33391.46250 26544.37500 6370.65000  
 33 
 2020.83750 2480.77500 1869.45000 
 32 
 1459.60000 1995.20000 1402.40000 

原代码核心问题分析 #

1. 车辆固定成本计算错误：原目标函数对每条路径弧都收取固定成本F，导致模型为减少成本尽量减少路径弧数量，最终选择单客户配送（仅产生仓库→客户、客户→仓库两条弧）。正确逻辑应为每调用一辆车收取一次固定成本，而非每条弧。
2. 路径成本矩阵不完整：仅定义仓库到客户的运输成本，未定义客户到客户、客户到仓库的成本，Gurobi默认未定义系数为0，进一步加剧模型倾向单客户配送的行为。
3. 流量守恒约束缺失：仅对客户节点做入度=出度约束，未对仓库节点的车辆进出流量做约束，无法关联车辆使用次数与路径的关系。
4. MTZ约束不完善：未限制跨仓库客户间的路径触发MTZ约束，且初始装载量约束过弱，无法有效引导多客户同趟配送。

修正后代码 #

from gurobipy import Model, GRB, quicksum
import math
import networkx as nx
import matplotlib.pyplot as plt

# ------------------------- Data input ----------------------------
def parse_allocation_format(filepath): 
    with open(filepath, 'r') as f:
        lines = [line.strip() for line in f if line.strip()]

    m, n = map(int, lines[0].split())
    I = list(range(m))  # Depots
    J = list(range(n))  # Customers

    W, O = {}, {}
    for i, line in enumerate(lines[1:1 + m]):
        capacity, fixed_cost = map(float, line.split())
        W[i] = capacity
        O[i] = fixed_cost

    d = {}
    depot_customer_cost = {}
    cust_coords = {}  # 存储客户坐标（数据集第二行为客户x,y坐标）
    j_index = 0
    i = 1 + m
    while i < len(lines):
        if len(lines[i].split()) == 1:
            d[j_index] = float(lines[i])
            coords = list(map(float, lines[i+1].split()))
            cust_coords[j_index] = (coords[0], coords[1])
            depot_customer_cost[j_index] = coords  # 仓库到客户的成本
            j_index += 1
            i += 2
        else:
            i += 1

    return I, J, d, W, O, depot_customer_cost, cust_coords

# ------------------------- Modell ----------------------------
filepath = "C:/Users"  # 请调整为实际文件路径
I, J, d, W, O, depot_customer_cost, cust_coords = parse_allocation_format(filepath)

m = Model("CLRP")

Q = 2500  # Vehicle capacity
F = 1500  # Fixed costs per vehicle

V = list(range(len(I))) + [j + len(I) for j in J]  # Depots + Customers

# 完善成本矩阵：仓库→客户、客户→仓库、客户→客户
c = {}
# 仓库到客户
for j in J:
    for i in I:
        c[(i, j + len(I))] = depot_customer_cost[j][i]
# 客户到仓库（假设往返成本相同）
for j in J:
    for i in I:
        c[(j + len(I), i)] = depot_customer_cost[j][i]
# 客户到客户：计算欧氏距离作为成本
for j in J:
    for k in J:
        if j != k:
            x1, y1 = cust_coords[j]
            x2, y2 = cust_coords[k]
            dist = math.hypot(x2 - x1, y2 - y1)
            c[(j + len(I), k + len(I))] = dist

# Decision variables
y = m.addVars(I, vtype=GRB.BINARY, name="y")  # 仓库i是否启用
w = m.addVars(J, I, vtype=GRB.BINARY, name="w")  # 客户j是否分配给仓库i
x = m.addVars(((i, j) for i in V for j in V if i != j), vtype=GRB.BINARY, name="x")  # 路径i→j是否启用
u = m.addVars(J, vtype=GRB.CONTINUOUS, name="u")  # MTZ变量：客户j处的装载量
z = m.addVars(I, vtype=GRB.INTEGER, name="z")  # 仓库i使用的车辆数

# Objective function
m.setObjective(
    quicksum(x[i, j] * c.get((i, j), 0) for i, j in x.keys()) +  # 所有路径的运输成本
    quicksum(z[i] * F for i in I) +  # 车辆固定成本：每辆车收一次
    quicksum(y[i] * O[i] for i in I),  # 仓库固定成本
    GRB.MINIMIZE
)

# Constraints
# 1. 每个客户被恰好一辆车服务（入度=1）
for j in J:
    cust = j + len(I)
    m.addConstr(quicksum(x[i, cust] for i in V if i != cust) == 1, name=f"cust_in_{j}")
    # 2. 每个客户被服务后车辆必须离开（出度=1）
    m.addConstr(quicksum(x[cust, i] for i in V if i != cust) == 1, name=f"cust_out_{j}")
    # 3. 每个客户恰好分配给一个仓库
    m.addConstr(quicksum(w[j, i] for i in I) == 1, name=f"cust_assign_{j}")

# 4. 客户只能分配给启用的仓库
for j in J:
    for i in I:
        m.addConstr(w[j, i] <= y[i], name=f"assign_open_{j}_{i}")

# 5. 仓库总容量约束
for i in I:
    m.addConstr(quicksum(w[j, i] * d[j] for j in J) <= W[i], name=f"depot_cap_{i}")

# 6. 路径只能在同仓库的节点间存在
for i in I:
    for j in J:
        cust_j = j + len(I)
        # 仓库到客户的路径仅当客户分配给该仓库
        m.addConstr(x[i, cust_j] <= w[j, i], name=f"path_depot_cust_{i}_{j}")
        # 客户到仓库的路径仅当客户分配给该仓库
        m.addConstr(x[cust_j, i] <= w[j, i], name=f"path_cust_depot_{j}_{i}")
    # 客户到客户的路径仅当两者都分配给该仓库
    for j in J:
        for k in J:
            if j != k:
                cust_j = j + len(I)
                cust_k = k + len(I)
                m.addConstr(x[cust_j, cust_k] <= w[j, i], name=f"path_cust_cust_{j}_{k}_{i}_1")
                m.addConstr(x[cust_j, cust_k] <= w[k, i], name=f"path_cust_cust_{j}_{k}_{i}_2")

# 7. 仓库流量守恒：出发的车辆数=返回的车辆数=使用的车辆数z[i]
for i in I:
    m.addConstr(quicksum(x[i, j] for j in V if j != i) == z[i], name=f"depot_out_{i}")
    m.addConstr(quicksum(x[j, i] for j in V if j != i) == z[i], name=f"depot_in_{i}")
    # 启用的仓库才能使用车辆
    m.addConstr(z[i] <= len(J) * y[i], name=f"z_depot_open_{i}")

# 8. MTZ子回路消除与车辆容量约束
for j in J:
    # 客户j的装载量至少为自身需求，不超过车辆容量
    m.addConstr(u[j] >= d[j], name=f"mtz_low_{j}")
    m.addConstr(u[j] <= Q, name=f"mtz_high_{j}")

for j in J:
    for k in J:
        if j != k:
            cust_j = j + len(I)
            cust_k = k + len(I)
            # 仅当存在路径j→k时，MTZ约束生效
            m.addConstr(u[j] + d[k] <= u[k] + Q * (1 - x[cust_j, cust_k]), name=f"mtz_{j}_{k}")

# 9. MTZ初始约束：从仓库出发到客户j时，装载量为d[j]
for i in I:
    for j in J:
        cust_j = j + len(I)
        m.addConstr(u[j] >= d[j] * x[i, cust_j], name=f"mtz_init_{i}_{j}")

# ------------------------- Optimisation ----------------------------
m.optimize()

# ------------------------- Visualisation ----------------------------
if m.status == GRB.OPTIMAL:
    G = nx.DiGraph()
    for i, j in x.keys():
        if x[i, j].X > 0.5:
            G.add_edge(i, j)

    pos = nx.spring_layout(G, seed=42)

    active_nodes = set(G.nodes)
    depots = [i for i in I if i in active_nodes]
    customers = [j + len(I) for j in J if (j + len(I)) in active_nodes]

    nx.draw_networkx_nodes(G, pos, nodelist=depots, node_color='red', node_shape='s', node_size=700)
    nx.draw_networkx_nodes(G, pos, nodelist=customers, node_color='skyblue', node_shape='o', node_size=700)
    nx.draw_networkx_edges(G, pos, arrows=True)
    nx.draw_networkx_labels(G, pos)

    plt.title("CLRP-Solution: Depots (red), Customers (blue)")
    plt.axis('off')
    plt.show()
else:
    print("未找到最优解")

修复说明 #

1. 修正固定成本计算：新增车辆数变量z[i]，仅对每辆车收取一次固定成本，模型会优先组合多客户以减少车辆使用数量。
2. 完善成本矩阵：补充客户到仓库、客户到客户的路径成本，让模型能准确评估多客户配送的总成本。
3. 补充流量守恒约束：关联仓库的车辆进出次数与车辆使用数，确保路径的完整性。
4. 优化MTZ约束：调整约束逻辑，仅对存在路径的客户对生效，避免无效约束干扰求解。

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