Julia实现广义旅行商问题（GTSP）的约束补充咨询

你的代码出现1→1自环边，核心原因是缺少禁止自环的约束，同时流量守恒、簇选择的约束逻辑存在漏洞，且未正确使用z变量标记选中节点。以下是具体的约束补充与代码修改建议：

1. 禁止自环约束 #

直接添加约束禁止所有节点的自环边，这是解决1→1问题的关键：

@constraint(m, [i=1:n], x[i,i] == 0)

2. 正确关联z变量与选中节点 #

z[j]标记节点j是否被选中（1表示选中，0表示未选中），需要添加约束将z与x的流量关联：

# 选中的节点必须有且仅有一条入边和一条出边
@constraint(m, [j=1:n], sum(x[i,j] for i=1:n) == z[j])
@constraint(m, [j=1:n], sum(x[j,i] for i=1:n) == z[j])

3. 明确簇选择约束 #

每个簇必须恰好选中一个节点，同时节点1必须被选中（作为起点和终点）：

# 节点1必须选中
@constraint(m, z[1] == 1)
# 每个簇恰好选中一个节点
@constraint(m, sum(z[j] for j in c1) == 1)
@constraint(m, sum(z[j] for j in c2) == 1)
@constraint(m, sum(z[j] for j in c3) == 1)
@constraint(m, sum(z[j] for j in c4) == 1)
@constraint(m, sum(z[j] for j in c5) == 1)

替换原代码中关于簇流入/流出的零散约束，这些约束逻辑模糊且容易出错

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

原MTZ约束未覆盖节点1的情况，且未结合z变量（仅选中的节点需要满足顺序约束），修改为：

# MTZ子回路消除约束，仅对选中的节点生效
for i=1:n, j=2:n
    @constraint(m, u[i] - u[j] + (n-1)*x[i,j] + (n-3)*z[j] <= n-2)
end
# 调整u变量的范围，仅选中的节点需要满足
@constraint(m, u[1] == 1)
@constraint(m, [j=2:n], u[j] >= 2*z[j])
@constraint(m, [j=2:n], u[j] <= n*z[j])

完整修正后的核心约束部分 #

替换原代码中所有约束，使用以下约束块：

# 1. 禁止自环
@constraint(m, [i=1:n], x[i,i] == 0)

# 2. z变量与x流量关联
@constraint(m, [j=1:n], sum(x[i,j] for i=1:n) == z[j])
@constraint(m, [j=1:n], sum(x[j,i] for i=1:n) == z[j])

# 3. 簇选择与节点1必选
@constraint(m, z[1] == 1)
@constraint(m, sum(z[j] for j in c1) == 1)
@constraint(m, sum(z[j] for j in c2) == 1)
@constraint(m, sum(z[j] for j in c3) == 1)
@constraint(m, sum(z[j] for j in c4) == 1)
@constraint(m, sum(z[j] for j in c5) == 1)

# 4. 修正MTZ子回路消除约束
for i=1:n, j=2:n
    @constraint(m, u[i] - u[j] + (n-1)*x[i,j] + (n-3)*z[j] <= n-2)
end
@constraint(m, u[1] == 1)
@constraint(m, [j=2:n], u[j] >= 2*z[j])
@constraint(m, [j=2:n], u[j] <= n*z[j])

逻辑说明 #

• 禁止自环直接避免了1→1这类无效边的出现；
• z变量明确标记选中节点，让簇选择约束更清晰，同时关联流量确保选中节点的入度出度均为1；
• 修正后的MTZ约束仅对选中的节点生效，避免未选中节点干扰顺序逻辑，彻底消除子回路。

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