旅行商问题（TSP）子回路消除：iJulia公路旅行优化及起止点设置

仅设置每个地点进出一次的约束，只能保证每个节点的入度和出度为1，但无法避免形成多个独立子回路——这是旅行商问题（TSP）建模的典型盲区，必须添加专门的子回路消除约束，同时强化纽约作为起点和终点的逻辑。

方案1：米勒-塔克-泽姆林（MTZ）线性约束（中小规模场景） #

这是最常用的子回路消除方法，通过引入辅助变量记录节点访问顺序，从数学上杜绝子回路生成。

具体实现（iJulia + JuMP） #

假设纽约的索引为1，总城市数为n，x[i,j]是0-1决策变量（1表示从城市i前往j）：

1. 定义辅助变量u[i]：对应除纽约外的每个城市，代表该城市的访问顺序编号（纽约固定为1）
2. 添加约束：

# 初始化辅助变量，纽约的u值固定为1
@variable(model, u[1:n] ≥ 1, Int)
@constraint(model, u[1] == 1)
@constraint(model, [i=2:n], u[i] ≤ n)

# 添加MTZ核心约束
for i in 1:n
    for j in 2:n
        if i != j
            @constraint(model, u[i] - u[j] + n * x[i,j] ≤ n - 1)
        end
    end
end

该约束的逻辑是：如果从i前往j，那么j的访问顺序必须比i大1以上，从而避免形成闭环子回路。

方案2：动态割平面法（大规模场景） #

当城市数量较多（>20个）时，MTZ约束会导致变量和约束数量剧增，此时可以用动态添加约束的方式：

1. 先运行仅含进出约束的初始模型，得到初始解
2. 检测解中的子回路（比如通过遍历路径，找出所有独立闭环）
3. 为每个子回路添加约束：sum(x[i,j] for i∈S, j∈S) ≤ |S| - 1（S是子回路的城市集合），强制打破闭环
4. 重复求解-检测-添加约束的流程，直到无任何子回路

简化代码示例 #

function find_subcycles(x_sol, n)
    visited = falses(n)
    subcycles = []
    for i in 1:n
        if !visited[i]
            cycle = []
            current = i
            while !visited[current]
                visited[current] = true
                push!(cycle, current)
                # 找到当前节点的下一个节点
                current = findfirst(j -> x_sol[current,j] ≈ 1, 1:n)
            end
            if length(cycle) > 1 && cycle[1] == current
                push!(subcycles, cycle)
            end
        end
    end
    return filter(c -> length(c) < n, subcycles) # 排除完整的主回路
end

# 循环优化
while true
    optimize!(model)
    x_sol = value.(x)
    subcycles = find_subcycles(x_sol, n)
    isempty(subcycles) && break
    # 为每个子回路添加割约束
    for cycle in subcycles
        @constraint(model, sum(x[i,j] for i in cycle, j in cycle) ≤ length(cycle) - 1)
    end
end

强化纽约作为起点终点的逻辑 #

除了上述约束，确保：

• 纽约的出度和入度均为1（已包含在通用进出约束中，但可单独显式声明：@constraint(model, sum(x[1,j] for j in 1:n if j≠1) == 1) 和 @constraint(model, sum(x[j,1] for j in 1:n if j≠1) == 1)）
• 在最终路径检测时，确认起点和终点均为纽约

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