JuMP求解简单图路径问题出现循环现象的原因咨询

你当前的约束体系缺少子回路消除约束，这是VRP类整数规划问题的经典漏洞：

• 现有约束只保证了每个顶点的流入流出量相等、每个顶点仅被访问一次、每辆车都从1出发回到1，但没有限制同一辆车的所有边必须连通到起点1
• 你得到的车辆2的解里实际存在两个互不连通的合法回路：1→3→1和4→5→4，两个回路都满足流量守恒规则，也满足4、5各被访问一次的要求，所以求解器会认为这是合法解。

小规模场景下最容易实现的是MTZ（Miller-Tucker-Zemlin）子回路消除约束，你只需要新增辅助变量和对应约束即可：

1. 新增表示访问顺序的整数变量：

# u[j,v] 表示车辆v访问顶点j的顺序，顶点1的顺序默认是0
@variable(model, u[2:nbVertex, 1:nbTransp] ≥ 0, Int)

2. 新增子回路消除约束：

# 如果车辆v走i→j的边，那么j的访问顺序至少比i大1
@constraint(model, [v in 1:nbTransp, i in 2:nbVertex, j in 2:nbVertex; i≠j],
    u[j,v] ≥ u[i,v] + 1 - (nbVertex - 1) * (1 - route[i,j,v])
)
# 限制顺序最大值避免无意义的可行解
@constraint(model, [v in 1:nbTransp, i in 2:nbVertex],
    u[i,v] ≤ nbVertex - 1
)

修改之后重新求解就不会出现不连通的子循环问题了。

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