如何用CPLEX解决违反三角不等式的Arc Routing Problem？

问题概述 #

使用CPLEX求解弧路径规划问题（ARP）时，得到的路径出现“瞬移”现象（如路径包含0->3、1->0这类不连续的弧段），核心原因是模型未强制路径的连续性，且当前场景违反三角不等式（节点2、3位置重合，但1到2距离6、到3距离9），导致CPLEX默认的启发式或约束无法保证生成单一连续游程。

当前距离矩阵：

distances = np.array([
    #0    1     2   3
    [0,   0.5,  5,  5], #0
    [0.5, 0,    6,  9], #1
    [5,   6,    0,  0], #2
    [5,   9,    0,  0]  #3
])

期望路径：0->1, 1->2, 2->3, 3->1, 1->0（单一连续游程）
实际得到路径：包含孤立弧段，属于多个子游程的集合。

解决方案 #

1. 添加子游程消除约束（SECs） #

三角不等式不成立时，必须显式约束路径为单一连续游程，避免CPLEX生成多个独立子游程。常用两种方式：

方式一：Miller-Tucker-Zemlin（MTZ）约束（适合小规模问题）

引入顺序变量u_i（表示节点i在路径中的访问顺序，整数类型），添加以下约束：

• 对于起点（如节点0），设置u_0 = 1
• 对于所有弧i->j（i≠j），若选择该弧（x_ij=1），则u_j ≥ u_i + 1 - M*(1 - x_ij)
  • M为足够大的常数（如所有距离之和，这里可取0.5+5+5+6+9+0=25.5）
• 所有u_i的取值范围为1到节点总数（这里是4）

该约束强制路径按顺序访问节点，避免子游程。

方式二：动态割平面法（适合大规模问题）

利用CPLEX的回调函数，在求解过程中实时检测子游程，若发现则添加割约束消除子游程：

1. 在求解回调中，获取当前解的弧选择变量x_ij的值
2. 构建由选中弧组成的图，检测是否存在多个连通分量（子游程）
3. 若存在，添加约束：对于每个子游程S，sum(x_ij for i in S, j not in S) + sum(x_ji for j in S, i not in S) ≥ 2（强制子游程与外部有连接）

2. 明确模型的游程连续性要求 #

确保模型满足单车辆弧路径规划的基本约束：

• 起点（如0）的出度 - 入度 = 1
• 终点（如0，回到起点）的入度 - 出度 = 1
• 其他所有节点的入度 = 出度
• 所有必须遍历的弧都被选中（根据你的问题，需明确哪些弧是必须遍历的，若所有弧都要遍历，需约束对应x_ij=1）

3. 特殊节点的处理（节点2、3） #

由于节点2和3之间距离为0，可在模型中明确：

• 允许2->3和3->2的弧，且成本为0
• 若这两个节点对应同一物理位置的不同任务，需确保路径在访问2后可直接到3（或反之），避免瞬移。

示例代码片段（MTZ约束） #

以Python CPLEX为例，添加MTZ约束的核心代码：

# 假设x是弧选择变量，x[i,j]表示是否走i->j
u = model.integer_var_list(n, lb=1, ub=n, name="u")
n = 4  # 节点数

# 起点约束
model.add_constraint(u[0] == 1)

# MTZ约束
M = 25.5  # 最大可能的顺序值
for i in range(n):
    for j in range(n):
        if i != j:
            model.add_constraint(u[j] >= u[i] + 1 - M * (1 - x[i,j]))

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