旅行商问题
2.8 节问题陈述（TSP 是什么）
旅行商问题（Traveling Salesman Problem, TSP；亦常称货郎担问题）是组合优化中著名的 NP-难问题。给定有向图 ，常记 为节点个数， 为弧集。若对任意 、 有从 到 的距离 ，则称对称旅行商问题（STSP, symmetric TSP）；有向、非对称时仍简记为 TSP。许多叙述中假设 为完全图，即任意两节点间均可直接到达（不存在的权可用充分大的费用在模型中排掉；可配合图 2.18(a) 一类示意图表示一条合理解）。目标：从某一可自选的起始点出发，经过每个节点恰好一次后回到起点，使总路径长度/费用最小。
从输入/输出可概括为：
- 输入：常为一组坐标或费用矩阵等；
- 输出：一条满足约束的访问顺序；
- 在模型层面常写成：每一点被进入且只进入一次、被离开且只离开一次（与「单一闭合路径」的直观一致；但单独的「每点进一次、出一次」尚不足以保证只有一条经过全体点的圈，后文「子环路」会说明「不然」在何处出现）。
有向情形下的 TSP 整数规划与 k-opt 邻域 等局搜分开书写：下节起按「TSP 建模方法」分条，顺序取问题陈述 → 指派松弛与子环 → 子环消去 (SEC) → MTZ（含拆点变体）→ 1-tree 与无向 STSP，便于按块阅读。
TSP 建模方法
有向 TSP 上，若只要求每个节点度平衡（进、出各一），与指派同型，解中仍可能出现多个互不相接的有向子环（子环路、subtour），每个子环在局部看仍「每点进一次、出一次」。要一条过所有节点的大环，需子环路消去（subtour elimination）。较常见的两条建路线为：subtour-elimination 约束（与 DFJ 型割一致）、Miller–Tucker–Zemlin（MTZ）辅助变量。对称、无向情形还可从 1-tree 图论结构出发，再写出边变量上的 STSP 模型（见「建模方法 3」）。
TSP 建模方法 1：子环路消去（subtour-elimination / DFJ, SEC）
1.1 指派的 0–1 模型与不足
将「是否选有向弧 」记为 0–1 决策 ，且不建自环 （或固定 ）：
- （2）保证：对每一节点 ，恰有一条以 为终点的弧，即进入 共一次。
- （3）保证：对每一节点 ，恰有一条以 为起点的弧，即离开 共一次。
不足：(2)–(4) 与指派/匹配的「每行每列和为 1」同型，可行解可以分解为若干有向子环；子环内部的每个点仍只进、出各一次，但整体上没有单条覆盖全体 的圈。为得到 TSP 可行解，需要再加约束。
1.2 子环路消去（DFJ / SEC）的形式与「破圈」含义
在图论中子环路也满足「过一点、离开该点」的局部要求，但解中出现的是多段相离的环；TSP 要求的是一个过所有点的大环（单圈/Hamilton 回路）。破圈思路之一：对真子集 上允许选取的、端点全在 内的有向弧条数加上界：若 中已能构成一闭有向子环，则 上弧数至少为 。于是对 、 有
例如 的直观例：在 上若成子环 ，则 ；为禁止该子环在 上自洽成圈，可要求上述和 。一般 (5) 对一切满足 的 施加，从而只能保留不在任一真子集上单独成完整有向子环的选法。
说明： 的个数在 大时可指数增长，实际建模往往不在开头枚举全部 (5)。常用做法是在分支定界/割平面中，用 callback/惰性（懒分离）在得到候选解、发现被违反的某条 (5) 时，再把被违反的实例加入模型。
1.3 有向 TSP 的完整 ILP（(1)–(5) 成组出现）
在 (1)–(4) 上并列加入全部所需的 (5)，即完整的、以弧变量 表述的有向 TSP 整数规划：目标 (1) + 度约束 (2)(3) + 0–1 (4) + 子环消去族 (5)。常见排法是在「min / s.t. /」下分条给出：先目标与入出度 (2)(3)，再 (5) 的割族，最后 (4)；读者可按同一顺序与代码实现一一对应。
下面将 (1)–(5) 合写为单块，避免只出现「见上」而留空（ 取遍 的全真子集，；实现中可懒分离而不预枚举）：
TSP 建模方法 2：MTZ 约束
除「列举 (5)」外，Miller–Tucker–Zemlin 在文献与实现中常更紧凑：引入辅助变量、用多项式条线性式排除子环，常不依赖在求解中写 callback 来加割（依具体求解器与建模习惯）。固定一个「仓库」或参考点（常记节点 0；若编号从 1 起，则排除 0 的 、 参与下式）：
对 为充分大的正数，核心约束常写
并常设 （上下界、是否固定某一点 依约定与实现； 的紧性可参考 Desaulniers 等 2006。）取紧的大-M 时常令 ，得
与
的写法等价。将目标 (1)、度约束 (2)–(4)、 时的 (7)、以及参考点 的 上下界与 (6) 的指标范围一并对齐，可合写为一套不依赖「见上」的 MTZ 型有向 TSP（记 ， 固定为 ， 在其余点上界定；若你的编号自 起无 ，将「」改为你所选的仓库点即可，以下结构不变）：
约束条数约为 ，辅助变量约为 ，与 (5) 的指数多种子集相比，写码上往往更直接。行内 (6)–(8) 的等价变形仍适用于局部分块引用；合写块与 1.1 的 (1)–(4) 的 在同一条有向建模样式中配套，实现时只保留一套 与一套 。
2.1 起点与终点不重合的写法（虚拟拆点、式 (9)–(13)）
闭路在几何上同点出发并回到该点。若希望用有向「路径」从起点到一新终点表示，可设一与起点同坐标的虚拟终点 ，点集
在 上给费用 （无实际边则用大权）。下面给出拆点后一整组建模，与上一段在 上写 (1)–(4) 的闭路二选其一同一算例、勿混用：
（10）表示除「起点 1」外每个节点 恰有一条入弧，对 在 到 上求和；（11）表示除终点 外每个 恰有一条出弧，对 在 到 上求和；（12）在 、 的指标上为 与 MTZ 的联立；(13) 的域在不同文献中常将 与 拆多行列出，与此处同义。实现上务须禁止误将 建为可选取的弧，否则可能出现全部 、其余为 0 的自环伪解。
说明：(9)–(13) 为拆点专用式号，与 1.1 的 (1)–(4) 及 (6)–(8) 的闭路另一套；勿在同一算例中混成一套变量而不区分含义。
2.2 MTZ 为何能排除三边子环（反证）
设三不同点 上若存在有向子环，则 。在 (7) 或拆点型 (12) 在弧上激活时，可推得 、、；三式相加得 ，与用「」表出的矛盾等价。故在 MTZ 与度约束联立的框架下，不能出现仅由部分点构成的有向小环；严格证明需与 的上下界、起点/拆点约定一并写清。
TSP 建模方法 3：1-tree 建模方法（无向、STSP 边模型）
3.1 自无向图与 STSP
从图论看，TSP 也可建立在无向图 上，边权不区分向： 为边 的权。此即对称 STSP 的常见设定；与有向、且 与 可不等的情形应分开建模。由图论写无向边时，应在一开始就把「无向、对称」定死，以免与有向弧变量混用。
3.2 1-tree 的定义、图 2.20 与分解
图 2.20 以两行示意 1-tree 的拼法：第一行 (a)＋(b)＝(c)，第二行 (d)＋(e)＝(f)。其中 (a)(d) 为与顶点 1 相连的两条边，(b)(e) 为在其余点上的树，(c)(f) 为合并后的 1-tree。下图为本站所附的同名示意，与上列分图对应。
在 上，以点 1 为基准，1-tree 由二部分「合并」如下（上段 (a)＋(b)＝(c)、(d)＋(e)＝(f) 即其直观）：
- 与顶点 1 关联的两条边（(a) 或 (d) 类子图）；
- 在其余顶点集 上的一棵生成树（(b) 或 (e) 侧的树）。
合并后得一株 1-tree。性质可归纳为：
- 1-tree 有且仅有一个环，且该环必经过顶点 1；
- 全图每个顶点的度 ；
- 边数恰为 。
同一 (b) 与不同 (a)/(d) 可拼出不同 1-tree。STSP 的一个可行 TSP 解是「每个点度恰为 2、唯一大环过全体点」的 1-tree 的特例。最小权 1-tree 可多项式求得，作下界；拉格朗日松弛、次梯度、分支定界与列生成等可与之衔接，见专著。
3.3 无向边变量、STSP 的 ILP 与加强的全局边数式
在边集上设 。 表示与顶点 关联的边的集合， 表示两个端点都在 内的边集。基础的 STSP 为
与有向 (1)–(5) 合写节相同，无向 STSP 也可**不依赖「见上」**地合写为一块（ 表示两端均在 内的边； 与 (16) 同）：
将 (15) 对全体 求和：每条被选边在左端计两次（两端各计一次），故对任意可行 TSP 解有
(18) 是 (15) 的推论；在作 LP 松弛时，常把 (18) 与 (14)–(17) 并列以收紧，称为「在模型上加强」——等价于记牢：全体度为 2 的等式相加、每条无向边在两端各被计一次，故无向边总数为 。
注：(14)–(18) 为无向边专用式号。方法 2 中 (9)–(13) 为拆点有向另一套；方法 1 的 (1)–(5) 为无拆点的有向在 上与 (6)–(8) 的 MTZ 闭路配套。同一实现中勿混用同名 与混淆三套编号。
全页从问题陈述、指派松弛、子环 (5)、MTZ(6)–(8) 与拆点 (9)–(13)、到 1-tree 与无向 (14)–(18)，在本文中自洽写完；各节不依赖外文书页即可阅读。