TDTSP：多面体与分支切割定价算法

# TDTSP：多面体与分支切割定价算法 ## 1. 引言 TDTSP（带时间依赖的旅行商问题）在车辆路径规划、调度等领域有重要应用。PQ 公式可推广用于多种车辆路径问题变体和复杂调度问题，TDTSP 面定义不等式也可用于这些问题。研究 TDTSP 多面体不仅有理论价值，还对算法设计有重要意义。 ## 2. 预备知识 ### 2.1 基本定义 设 \(N = \{1, 2, \ldots, n\}\)，\(N_0 = N \cup \{0\}\)，对于节点集 \(S\)，\(K(S)\) 表示 \(S\) 上的完全（无环）有向图。TDTSP 在完全图 \(K(N_0)\) 上可建模为分层图 \((V, A)\) 上的优化问题。 - \(V\) 由源节点 \(0\)、终端节点 \(T\) 和中间节点 \((i, t)\)（\(i, t \in N\)）组成。 - \(A\) 由三种类型的弧组成： - 对于 \(i \in N\)，\((0, i, 0)\) 表示从节点 \(0\) 到节点 \((i, 1)\) 的弧；\((i, T, n)\) 表示从节点 \((i, n)\) 到节点 \(T\) 的弧。 - 对于 \(i, j \in N\) 且 \(i \neq j\)，\(1 \leq t \leq n - 1\)，\((i, j, t)\) 表示从节点 \((i, t)\) 到节点 \((j, t + 1)\) 的中间弧。 ### 2.2 模型约束 Picard 和 Queyranne 将 TDTSP 建模为线性整数规划，约束如下： \(\sum_{j \in N} x_{0, j}^0 = 1\) \((1a)\) \(x_{0, j}^0 = \sum_{k \in N_j} x_{j, k}^1\)，\(j = 1, \ldots, n\) \((1b)\) \(\sum_{i \in N_j} x_{i, j}^t = \sum_{k \in N_j} x_{j, k}^{t + 1}\)，\(j = 1, \ldots, n\)，\(t = 1, \ldots, n - 2\) \((1c)\) \(\sum_{i \in N_j} x_{i, j}^{n - 1} = x_{j, T}^n\)，\(j = 1, \ldots, n\) \((1d)\) \(x_{0, j}^0 + \sum_{t = 1}^{n - 1} \sum_{i \in N_j} x_{i, j}^t = 1\)，\(j = 1, \ldots, n\) \((1e)\) \(x \geq 0\) 且为整数 \((1f)\) 使用方程 \((1a)\) 和 \((1d)\) 消除与节点 \(0\) 和 \(T\) 相关的 \(2n\) 个变量，得到等价约束： \(\sum_{i \in N} \sum_{j \in N_i} x_{i, j}^1 = 1\) \((2a)\) \(\sum_{i \in N_j} x_{i, j}^t = \sum_{k \in N_j} x_{j, k}^{t + 1}\)，\(j = 1, \ldots, n\)，\(t = 1, \ldots, n - 2\) \((2b)\) \(\sum_{k \in N_j} x_{j, k}^1 + \sum_{t = 1}^{n - 1} \sum_{i \in N_j} x_{i, j}^t = 1\)，\(j = 1, \ldots, n\) \((2c)\) \(x \geq 0\) 且为整数 \((2d)\) ### 2.3 TDTSP 多面体定义 设 \(P(n)\) 为 \(G(n)\) 中 \(s\) - 路径的关联向量的凸包，称为 TDTSP 多面体。当 \(n \geq 5\) 时，\(P(n)\) 的维度为 \(n(n - 1)(n - 2)\)。 ## 3. 可允许流约束 ### 3.1 循环定义与问题提出 设 \(p = (0, v_1, v_2, \ldots, v_n, T)\) 为 \((V, A)\) 中的 \(0 - T\) 路径，\(r\) - 循环定义为子路径 \((v_i, \ldots, v_{i + r})\) 且 \(v_i = v_{i + r}\)。整数解为 \(s\) - 路径，不包含 \(r\) - 循环，但分数解分解的路径可能包含 \(r\) - 循环。可允许流约束用于限制 \(r\) - 循环的出现。 ### 3.2 2 - 循环消除约束 考虑 \(1 \leq t \leq n - 2\)，为避免 2 - 循环，弧 \((i, j, t)\) 上的流应通过除 \((j, i, t + 1)\) 外的弧离开节点 \((j, t + 1)\)，约束如下： \(x_{i, j}^t \leq \sum_{k \in N \setminus \{i, j\}} x_{j, k}^{t + 1}\)，\((i, j, t) \in A\)，\(1 \leq t \leq n - 2\) \((3)\) 当 \(n \geq 6\) 时，每个约束 \((3)\) 定义 \(P(n)\) 的一个面。 ### 3.3 一般可允许流约束 设 \(X\) 为 \(G = (V, A)\) 中不包含节点 \(\{0, T\}\) 的连通顶点集。对于 \(e \in \delta^-(X)\)，定义 \(C(X, e) \subseteq \delta^+(X)\) 为相对于 \(X\) 对 \(e\) 可允许的离开弧集；对于 \(E \subseteq \delta^-(X)\)，定义 \(C(X, E) = \bigcup_{e \in E} C(X, e)\)。可允许流约束（AFC）如下： \(\sum_{e \in E} x_e \leq \sum_{f \in C(X, E)} x_f\) \((4)\) 当 \(X = \{(u_1, t + 1), \ldots, (u_{r - 1}, t + r - 1)\}\) 且 \(E = \{(i, u_1, t)\}\) 时的 AFC 称为 \(r\) - 循环消除约束。推测所有 \(r\) - 循环消除约束都定义面，一般 AFC 虽通常不定义面，但有以下优点： - 存在不被 \(r\) - 循环消除约束支配的 AFC。 - 对于固定的 \(X\)，可在多项式时间内作为最小割问题分离。 - 在实践中非常有用。 ## 4. 提升子回路消除约束 ### 4.1 经典子回路消除约束 经典子回路消除约束（SECs）可表示为： \(\sum_{j \in S} x_{0, j}^0 + \sum_{t = 1}^{n - 1} \sum