咨询TSP中允许多次访问城市的子回路消除约束方案

你当前使用的Ui+Uj-k*Xij <= k-1是经典的Miller-Tucker-Zemlin（MTZ）子回路消除约束，它是专门为每个城市仅访问一次的标准TSP设计的——因为它依赖Ui表示城市i的访问顺序，每个城市只能有唯一的顺序值，所以当你允许非仓库城市多次访问时，这个约束完全不适用：要么会限制合法的重复访问路径，要么移除后就会出现独立子回路的无效解。

针对你的场景（仅出发仓库是唯一的“起点/终点锚点”，其他城市允许多次访问），最适合的是基于流量守恒的子回路消除约束。这种约束不限制城市的访问次数，只通过流量连通性来杜绝子回路，完美匹配你的需求。

具体约束设计（假设仓库编号为0，总共有k个城市） #

首先定义变量：

• Xij：0-1决策变量，取值1表示路径中包含从城市i到城市j的直接弧，0则不包含。
• fij：非负连续变量，表示从仓库0出发，经过弧(i,j)的流量（可以理解为这条弧被使用的“次数权重”）。

然后设置以下约束：

1. 仓库的流量收支平衡：

   Σ(j=1到k-1) f0j = K
   Σ(j=1到k-1) fj0 = K
   

   这里的K是一个足够大的常数，建议设为至少等于非仓库城市的数量（比如K = k-1），确保能覆盖每个非仓库城市至少被访问一次的需求；如果允许大量重复访问，也可以设更大的值。

2. 非仓库城市的流量守恒：
   对于每个非仓库城市i（i≠0），流入的总流量等于流出的总流量：

   Σ(j=0到k-1) fij = Σ(j=0到k-1) fji
   

   这个约束保证了非仓库城市可以被多次进出（只要流入流出相等），但不会形成独立的子回路——因为子回路里的城市无法和仓库连通，流量会全部在内部循环，无法满足仓库的流量收支要求。

3. 弧流量与路径变量的绑定：
   对于所有i≠j：

   0 ≤ fij ≤ K * Xij
   

   这个约束确保只有当Xij=1（即存在这条弧）时，fij才能取正值；如果Xij=0，则fij必须为0，避免无效的流量分配。

额外补充（如果需要保证每个非仓库城市至少被访问一次） #

如果你的场景要求每个非仓库城市至少被访问一次，还需要给每个i≠0加上：

Σ(j=0到k-1) Xij ≥ 1
Σ(j=0到k-1) Xji ≥ 1

这能确保每个城市至少有一条入弧和一条出弧，不会被遗漏。

这种流量式约束的核心优势是完全不限制非仓库城市的访问次数，只通过“所有流量必须从仓库出发并返回”的逻辑，从根源上杜绝了独立子回路的产生，完美适配你的TSP场景。

内容的提问来源于stack exchange，提问作者Hossein Beheshti Fakher