Gurobi仓库拣选路径优化：如何消除子回路获得单回路最优解？

开发者阿泽

2026-8-6

仓库物料拣选最优路径问题：消除子回路实现单回路

问题现状

使用Gurobi求解仓库拣选路径时，得到两个独立子回路（0-5-0 和 1-2-3-4-1），但预期是从depot（点位0）经过所有5个物料点位再返回0的单回路路径。

当前求解输出：

x(0,5,33) 1.0
q(1,33) 2.0
x(1,2,33) 1.0
q(2,33) 2.0
x(2,3,33) 1.0
q(3,33) 2.0
x(3,4,33) 1.0
q(4,33) 2.0
x(4,1,33) 1.0
q(5,33) 2.0
x(5,0,33) 1.0

现有代码

from gurobipy import*

N = [0, 1, 2, 3, 4, 5] #Material location in warehosue, 0 is depot
S = [1] #The configuration need to be pick up

#Material list with location n
I, K = multidict({1:11, 2:12, 3:13, 4:42, 5:41})

#Distance between each location
R1 = {(0,1): 3, (0,2): 6, (0,3): 5, (0,4):4, (0,5): 2,\
      (1,2): 3, (1,3): 4, (1,4): 3, (1,5): 3,\
     (2,3): 3, (2,4): 6, (2,5): 4, (3,4): 3, (3,5): 7, (4,5): 6}
R = {}
for i,j in R1:
    R[j,i]=R1[i,j]
    R[i,j]=R1[i,j] #把0,1 -> 1,0

#Capacity
C = 10
#the batch of picking
L = [l for l in range(1,60)]

#BOM list (S:K1,K2,K3,K4,K5) 
BOM = {1:[11,12,13,42,41]}

#Quantity demand of configuration
S, D = multidict({1:2})

#Decision variable
model = Model("Picking path")
x = {}
q = {}
u = {}
for l in L:
    for i in range(len(N)+1):
        q[i,l]=model.addVar(vtype="C", name="q(%s,%s)" %(i,l))
        for j in range(len(N)+1):
            x[i,j,l]=model.addVar(vtype="B", name="x(%s,%s,%s)" %(i,j,l))
for l in L:
    for i in range(len(N)+1):
        u[i,l]=model.addVar(vtype="C", name="u(%s)" %i)

model.update()

#Constraints
BigM = 10**6
for l in L:
    model.addConstr(quicksum(x[0,j,l] for j in N if j!=0)*BigM >= quicksum(q[j,l] for j in N), name="A.3")
    model.addConstr(quicksum(x[i,0,l] for i in N if i!=0)*BigM >= quicksum(q[j,l] for j in N), name="A.4")
    for j in N:
        model.addConstr(quicksum(x[i,j,l] for i in N if i!=j)\
                       -quicksum(x[j,v,l] for v in N if v!=j)==0, name="A.2")
        model.addConstr(quicksum(x[i,j,l] for i in N if i!=j)*BigM >= q[j,l], name="A.5")
        model.addConstr(q[j,l] <= C, name="A.6")
            
for i in range(1,len(N)):
    for s in S:
        for k in K:
            model.addConstr(quicksum(q[i,l] for l in L)\
                            ==quicksum(D[s] for s in BOM if K[i] in BOM[s]), name="A.7")
                
#subtour
for l in L:
    model.addConstr(u[0,l]==0)
    for i in range(len(N)+1):
        for j in N:
            if i!=j:
                model.addConstr(u[i,l]-u[j,l] + (len(N)+1)*x[i,j,l] <= (len(N)+1), name="A.8")


#Objective
model.setObjective(quicksum(R[i,j]*x[i,j,l] for i in N for j in N for l in L if i!=j), GRB.MINIMIZE)

model.optimize()

问题分析与修改方案

出现子回路的核心原因是子回路消除约束（MTZ约束）逻辑错误，同时存在变量定义冗余、约束设置不合理等问题，具体修改如下：

1. 修正子回路消除约束（MTZ约束）

原代码的MTZ约束公式和变量范围错误，正确的MTZ约束需针对非depot节点，采用标准形式：
u[i,l] - u[j,l] + (总节点数)*x[i,j,l] <= 总节点数 - 1

修改后的约束代码：

# 修正子回路消除约束
for l in L:
    model.addConstr(u[0,l] == 0, name=f"MTZ_start_{l}")
    for i in N:
        for j in N:
            if i != 0 and j != 0 and i != j:
                model.addConstr(u[i,l] - u[j,l] + len(N)*x[i,j,l] <= len(N)-1, name=f"MTZ_{i}_{j}_{l}")

限定i和j为非0节点，避免无效约束
调整系数为总节点数len(N)，确保约束能有效阻断子回路

2. 精简变量定义范围

原代码中变量i和j的范围包含无效索引（range(len(N)+1)），修改为仅遍历实际存在的节点：

# 重新定义决策变量
for l in L:
    for i in N:
        q[i,l] = model.addVar(vtype="C", name=f"q({i},{l})")
        for j in N:
            if i != j:
                x[i,j,l] = model.addVar(vtype="B", name=f"x({i},{j},{l})")
    for i in N:
        u[i,l] = model.addVar(vtype="C", name=f"u({i},{l})")

仅为实际节点创建变量，减少求解资源消耗
提前过滤自环（i==j）情况，符合路径逻辑

3. 优化需求满足约束

原约束A.7存在三重循环冗余，简化为直接关联物料节点与需求：

# 修正需求约束
for i in N[1:]:
    demand = D[1] if K[i] in BOM[1] else 0
    model.addConstr(quicksum(q[i,l] for l in L) == demand, name=f"demand_{i}")

直接匹配BOM中的物料需求，避免不必要的循环

4. 强制单批次覆盖所有节点（可选）

若期望单次拣选完成所有物料，添加约束确保目标批次覆盖所有物料节点：

# 强制指定批次覆盖所有物料节点
target_l = 33  # 对应当前求解结果中的批次33
for i in N[1:]:
    model.addConstr(quicksum(x[j,i,target_l] for j in N if j != i) == 1, name=f"force_visit_{i}_{target_l}")
    model.addConstr(quicksum(x[i,j,target_l] for j in N if j != i) == 1, name=f"force_leave_{i}_{target_l}")

确保每个物料节点的入度和出度均为1，强制纳入回路

5. 简化BigM约束

原A.3、A.4约束使用过大的BigM，替换为更合理的关联逻辑：

for l in L:
    # 确保depot入度等于出度
    model.addConstr(quicksum(x[0,j,l] for j in N[1:]) == quicksum(x[i,0,l] for i in N[1:]), name=f"depot_flow_{l}")
    for j in N[1:]:
        # 拣选量与节点访问关联
        model.addConstr(q[j,l] <= C * quicksum(x[i,j,l] for i in N if i != j), name=f"pick_visit_{j}_{l}")

用容量C替代过大的BigM，提升数值稳定性

完整修改后代码

from gurobipy import*

N = [0, 1, 2, 3, 4, 5]  # 0为depot，其余为物料点位
S = [1]  # 需要拣选的配置

# 点位对应的物料编号
I, K = multidict({1:11, 2:12, 3:13, 4:42, 5:41})

# 点位间距离矩阵（双向）
R1 = {(0,1): 3, (0,2): 6, (0,3): 5, (0,4):4, (0,5): 2,
      (1,2): 3, (1,3): 4, (1,4): 3, (1,5): 3,
      (2,3): 3, (2,4): 6, (2,5): 4, (3,4): 3, (3,5): 7, (4,5): 6}
R = {}
for i,j in R1:
    R[j,i] = R1[i,j]
    R[i,j] = R1[i,j]

C = 10  # 拣选容量
L = [l for l in range(1,60)]  # 批次范围

# BOM清单：配置1需要的物料
BOM = {1:[11,12,13,42,41]}
# 配置需求数量
S, D = multidict({1:2})

# 初始化模型
model = Model("Picking path")
x = {}
q = {}
u = {}

# 定义决策变量：仅针对实际节点
for l in L:
    for i in N:
        # q[i,l]：批次l中点位i的拣选量
        q[i,l] = model.addVar(vtype="C", name=f"q({i},{l})")
        for j in N:
            if i != j:
                # x[i,j,l]：批次l中从i到j的路径是否被选择（0/1）
                x[i,j,l] = model.addVar(vtype="B", name=f"x({i},{j},{l})")
    # u[i,l]：MTZ约束的辅助变量
    for i in N:
        u[i,l] = model.addVar(vtype="C", name=f"u({i},{l})")

model.update()

# 约束1：每个节点的入度等于出度（流量平衡）
for l in L:
    for j in N:
        model.addConstr(
            quicksum(x[i,j,l] for i in N if i != j) == quicksum(x[j,v,l] for v in N if v != j),
            name=f"flow_balance_{j}_{l}"
        )

# 约束2：拣选量与节点访问的关联
for l in L:
    for j in N[1:]:
        # 有拣选量则必须访问该节点
        model.addConstr(q[j,l] <= C * quicksum(x[i,j,l] for i in N if i != j), name=f"pick_visit_{j}_{l}")
        # 拣选量不超过容量
        model.addConstr(q[j,l] <= C, name=f"capacity_{j}_{l}")

# 约束3：需求满足
for i in N[1:]:
    demand = D[1] if K[i] in BOM[1] else 0
    model.addConstr(quicksum(q[i,l] for l in L) == demand, name=f"demand_{i}")

# 约束4：子回路消除（MTZ约束）
for l in L:
    model.addConstr(u[0,l] == 0, name=f"MTZ_start_{l}")
    for i in N:
        for j in N:
            if i != 0 and j != 0 and i != j:
                model.addConstr(
                    u[i,l] - u[j,l] + len(N)*x[i,j,l] <= len(N)-1,
                    name=f"MTZ_{i}_{j}_{l}"
                )

# 约束5：强制单批次覆盖所有节点（可选，若需单次完成）
target_l = 33
for i in N[1:]:
    model.addConstr(quicksum(x[j,i,target_l] for j in N if j != i) == 1, name=f"force_visit_{i}_{target_l}")
    model.addConstr(quicksum(x[i,j,target_l] for j in N if j != i) == 1, name=f"force_leave_{i}_{target_l}")

# 目标函数：最小化总路径距离
model.setObjective(
    quicksum(R[i,j]*x[i,j,l] for i in N for j in N for l in L if i != j),
    GRB.MINIMIZE
)

model.optimize()

# 输出结果
if model.status == GRB.OPTIMAL:
    for l in L:
        print(f"\n批次 {l} 的路径：")
        path = []
        current = 0
        while True:
            path.append(current)
            next_nodes = [j for j in N if j != current and x[current,j,l].X > 0.5]
            if not next_nodes:
                break
            current = next_nodes[0]
            if current == 0:
                path.append(current)
                break
        print(" -> ".join(map(str, path)))

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

Gurobi仓库拣选路径优化：如何消除子回路获得单回路最优解？

问题现状 #

现有代码 #

问题分析与修改方案 #

1. 修正子回路消除约束（MTZ约束） #

2. 精简变量定义范围 #

3. 优化需求满足约束 #

4. 强制单批次覆盖所有节点（可选） #

5. 简化BigM约束 #

完整修改后代码 #