车辆路径问题线性规划模型补全求助：消除子回路约束

你遇到的这个问题太典型了——VRP的基础流量守恒约束确实没法堵住子回路的漏洞，尤其是节点规模上去之后，求解器很容易跑出这种“表面符合约束但实际没法执行”的解。别担心，这有两种成熟的解决方案，帮你完善模型：

1. Miller-Tucker-Zemlin (MTZ) 约束：引入顺序变量打破子环 #

这是最常用的子回路消除方法，核心思路是给每个节点加一个“访问顺序”变量，从逻辑上禁止子环形成：

步骤： #

• 新增连续变量 u_i，其中 u_i 表示车辆访问节点 i 的顺序编号（仓库节点0的u_0=0，第一个被访问的客户节点u_i=1，以此类推）。
• 添加以下约束：
  • 对所有非仓库节点 i：1 ≤ u_i ≤ N（N是客户节点的总数，确保顺序编号在合理范围内）
  • 对所有非仓库节点 i,j（i≠j）：u_j ≥ u_i + 1 - M(1 - x_ij)
    这里的M是一个足够大的常数（比如直接取N就行，因为最大的顺序编号不会超过客户节点数）。

原理： #

如果存在子回路（比如i→j→k→i），那么根据约束会得到：
u_j ≥ u_i + 1，u_k ≥ u_j + 1，u_i ≥ u_k + 1
把这三个式子加起来会得到0 ≥ 3，显然矛盾，所以子回路不可能满足这个约束，自然就被排除了。

2. 子回路割约束：按需添加的高效方案 #

如果觉得MTZ的额外变量会增加求解负担，尤其是大规模问题，可以用割约束的思路：

约束逻辑： #

对于任何不含仓库的非空客户节点子集S，添加约束：

∑_{i∈S, j∈S} x_ij ≤ |S| - 1

意思是子集S内部的行驶边数最多只能比节点数少1，而形成一个子回路需要恰好|S|条边，这样就直接禁止了子环的存在。

注意点： #

直接把所有可能的子集约束都加进去不现实（子集数量是指数级的），所以通常用分支定界+割平面的方式：

1. 先跑你现有的基础模型；
2. 求解器得到解后，检查是否存在子回路；
3. 如果发现子回路，就把对应子集的割约束添加到模型里，重新求解；
4. 重复这个过程直到没有子回路为止。

CPLEX本身支持通过回调函数实现这个逻辑，你可以利用它的内置工具来自动检测子回路并添加割约束，效率会比直接加所有约束高很多。

选哪种方案？ #

• 小规模问题：MTZ约束实现简单，不需要额外的检测逻辑，直接加变量和约束就行；
• 大规模问题：割平面法更高效，因为它只在需要的时候添加约束，不会让模型变得过于庞大。

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