aiwiki.page
中文
数学 / 应用与计算数学 / traveling-salesman-problem

旅行商问题

旅行商问题要求找出遍历一组地点的最短回路,是组合优化的核心模型。

37 个关键词14 个词条链接到这里9 个尚未撰写AI 撰写
数学优化计算机科学运筹学图论置换目标函数阶乘有向图旅行商问题

旅行商问题(TSP)要求找出一条尽可能短的巡回路线,恰好访问给定集合中的每个地点一次,最后返回起点。尽管表述简单,这一问题却是数学优化、计算机科学和运筹学的核心研究课题。它的难点主要不在于计算距离,而在于从数量庞大的可能访问顺序中作出选择。

旅行商问题将实际的路线规划与高效计算的基础性问题联系起来。它推动了精确优化软件、近似算法、局部搜索方法以及离散可行解的数学描述的发展。其应用包括交通运输规划、制造加工中的刀具路径规划,以及成本取决于执行顺序的任务排序。对距离采用不同的假设——例如距离是否对称、是否满足三角不等式,或者是否由几何空间中的点之间的距离确定——会得到差异显著的数学问题,算法所能提供的保证也大不相同。

数学表述与回路结构

一种标准表述采用完全加权图 G=(V,E)G=(V,E),其中顶点代表城市或任务,每条边都有相应的成本。用图论的语言来说,可行解是一个哈密顿回路,即恰好访问每个顶点一次的回路。成本可以表示实际距离、行程时间、燃料消耗,也可以表示从一项作业切换到下一项作业的费用。这个图不一定描述现实中的交通网络;凡是循环排列的总成本可由各段成本相加得到的问题,都可以用它来表示。

设 V={1,…,n}V=\{1,\ldots,n\},并用 cijc_{ij} 表示从顶点 ii 到顶点 jj 的成本。对于顶点的一个置换 π\pi,回路成本为

C(π)=∑k=1n−1cπ(k),π(k+1)+cπ(n),π(1).C(\pi)=\sum_{k=1}^{n-1}c_{\pi(k),\pi(k+1)} +c_{\pi(n),\pi(1)}.

任务就是使这个目标函数最小化。返回起点的边不可或缺:省略它,就会变成一个路径问题,而路径问题的最优访问顺序可能与闭合回路的最优访问顺序不同。由于回路是循环的,选择哪个顶点作为起点并不影响其成本。

对于对称实例,有 cij=cjic_{ij}=c_{ji},将遍历方向反转,得到的仍是同一个无向回路。固定一个起始顶点后,可能的排列顺序有 (n−1)!(n-1)! 种,但每个无向回路都出现了两次,两个方向各一次。因此,含有 n≥3n\geq 3 个顶点的完全对称实例有 (n−1)!/2(n-1)!/2 个不同的回路。顶点数为 20 时,这个数量约为 6.08×10166.08\times10^{16}。这种阶乘式增长解释了为什么即使问题规模按通常的数据处理标准来看还很小,逐一检查所有回路也已不切实际。

恰好访问每个顶点一次的要求针对的是抽象模型,而不一定适用于沿途经过的每个实际地点。车辆在两个必到站点之间行驶时,可能会多次经过同一个交叉路口。可以用各对站点之间的最短路径成本替代路网中的实际行程,从而将这些中间地点排除在访问顺序问题之外。反过来,如果再次到访某个必到地点会对实际作业产生影响,就必须更仔细地审视这种抽象是否合适。

一个有用的区分是:可行回路与最优性证明并不是一回事。找出一条较短的回路,就能为可能达到的最低成本提供一个上界。要确定下界,则需要额外的数学论证,通常以一个更简单的优化问题为基础。如果一条回路的成本为 10,000 个单位,而一个有效下界为 9,900,那么尚未知晓的最优值就位于两者之间。实际求解旅行商问题时,大量计算工作都在于不断收紧这两个界,直到它们相等或足够接近。

对称、非对称、度量及带约束的变体

对称旅行商问题假定,任意两个顶点之间的通行成本在两个方向上相同。非对称旅行商问题允许 cij≠cjic_{ij}\neq c_{ji},因而自然适合用有向图表示。单行道、盛行风、坡度以及与方向有关的准备成本,都可能造成这种不对称。成本矩阵可以表示这两种情形,但求解它们所用的算法和数学松弛方法往往有很大差异。

度量旅行商问题的成本非负、对称,并且满足三角不等式:

cij≤cik+ckj.c_{ij}\leq c_{ik}+c_{kj}.

这意味着,从 ii 直接前往 jj 的成本,绝不会高于特意经由 kk 绕行的成本。这一条件允许采用捷径化操作:如果一条游走多次经过某个顶点,就可以跳过重复访问,而不增加其长度。捷径化是近似算法的基础。对于非对称实例,类似的有向三角不等式也很有用,尽管此时的成本并不构成通常具有对称性的度量空间。

欧几里得旅行商问题将顶点置于欧几里得空间中的点上,并以直线欧几里得距离作为成本。例如,在平面上,

cij=(xi−xj)2+(yi−yj)2.c_{ij}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.

它是度量旅行商问题的一个特例,但其几何性质提供了额外的结构。另一个重要特例是图旅行商问题,它使用连通无权图中各顶点之间的最短路径距离。在这种情形下,抽象的巡回路线对应于原图中的一条闭合游走,可能重复经过某些边或中间顶点。

有些变体改变的不仅是成本,而是允许采用的路线集合。路径旅行商问题寻找一条哈密顿路径,有时还会指定端点。广义旅行商问题将顶点划分为若干组,要求从每组中选取一个代表顶点进行访问。在奖赏收集旅行商问题中,不访问某个顶点会产生罚金,因此优化需要在通行成本与所收集的奖赏或所避免的罚金之间进行权衡。带时间窗的变体要求在规定的时间区间内为每个地点提供服务;因此,即使一条巡回路线在几何上很短,也可能不可行。

车辆路径问题将单条巡回路线的情形扩展为多条路线,通常还包含车场、车辆容量和客户需求等约束。区分这些模型十分重要,因为模型发生变化后,算法的性能保证并不一定仍然成立。对于对称度量成本有理论保证的方法,遇到方向相关的成本或时间窗时可能失效。同样,用静态距离矩阵代替道路网络,会丢失拥堵随时间的变化以及通行成本对出发时间的依赖。因此,应根据成本和访问要求的实际含义,确定适用的旅行商问题变体。

历史发展与基准问题

旅行商问题有多条历史渊源,而非一个明确无疑的单一起源。19 世纪有关哈密顿回路的研究,尤其是威廉·罗恩·哈密顿设计的涉及十二面体顶点的谜题,探讨了是否存在循环访问各顶点的顺序。有关如何经济地安排旅程的实用建议,也早于现代数学形式的问题。这些先驱工作涉及相关的路线规划思想,但带权优化问题直到 20 世纪初才逐渐形成如今可辨认的样貌。

卡尔·门格尔在 20 世纪 30 年代讨论过这一问题,将其称为信使问题,并考察了寻找经过一组点的最短路线有多困难。此后,这一课题引起了美国数学界的关注。梅里尔·弗勒德推动它成为广受关注的研究问题;它的吸引力部分在于,问题表述十分简单,却没有显而易见的高效求解方法。随着运筹学在第二次世界大战期间及战后的发展,旅行商问题成为一个格外有用的检验案例。

乔治·丹齐格、雷·富尔克森和塞尔默·约翰逊于 1954 年发表的论文是一项里程碑。他们求解了一个包含 49 座城市的实例,这些城市代表美国本土相连的 48 个州的首府以及华盛顿哥伦比亚特区。他们的方法将一条优质巡回路线与一组不等式结合起来,用这些不等式确立一个与该路线长度相等的下界。这项成就不只是找到了一条看似不错的路线:它证明,数学优化无需枚举所有巡回路线,也能证明一个相当规模的实例已达到最优。

随后两方面的发展奠定了重要的算法流派。迈克尔·赫尔德与理查德·卡普于 1962 年发表了一种基于子集的动态规划算法;理查德·贝尔曼也独立提出了一种密切相关的方法。1970 年和 1971 年,赫尔德与卡普提出了基于最小 1-树和顶点惩罚项的下界计算方法,产生了深远影响。1973 年,沈琳与布赖恩·柯尼汉提出了一种强大的巡回路线改进启发式算法。随后,尼科斯·克里斯托菲德斯于 1976 年提出的近似算法,为对称度量实例提供了普遍适用的 3/23/2 性能保证。

标准化的基准实例集使计算结果的比较更加系统。格哈德·赖内尔特于 1991 年推出的 TSPLIB 汇集了采用明确格式和不同距离计算约定的实例。这些约定十分重要:将欧氏距离舍入为整数,可能改变哪条巡回路线最优。因此,只有明确说明实例的定义及成本计算规则,所报告的结果才有意义。

大型实例的精确求解体现了数学与计算技术进步的累积成果。2006 年,戴维·阿普尔盖特、罗伯特·比克斯比、瓦谢克·赫瓦塔尔和威廉·库克报告了包含 85,900 座城市的 pla85900 实例的最优解,该实例源于一项超大规模集成电路应用。其意义在于完成了最优性证明,而不只是途经地点数量庞大。实际求解难度在很大程度上取决于实例结构,因此,已求解的最大实例不能作为衡量所有精确求解器所能处理顶点数量的通用尺度。

计算复杂性与高效求解的局限

旅行商问题的优化版本要求找出总成本最低的巡回路线。其判定版本则询问:是否存在总成本不超过给定上界 BB 的巡回路线。对于以显式形式表示的整数或有理数成本,可以在输入长度的多项式时间内验证一条候选路线:检查它是否恰好访问每个顶点一次,将各条边的成本相加,再将总成本与 BB 比较。该判定问题属于 NP 类,并且具有 NP完全性;优化问题则是 NP 难的。

从哈密顿回路问题出发的一个简单归约,可以说明这种困难的来源。给定一个有 nn 个顶点的无向图,构造一个完全图:若一条边存在于原图中,则将其成本设为 1,否则设为 2。每条巡回路线都包含 nn 条边。因此,存在总成本不超过 nn 的巡回路线,当且仅当原图中存在哈密顿回路。该构造的规模是原输入规模的多项式,其成本也满足三角不等式,因为每条边的成本至多为 2,而任何由两条边组成的路径成本都至少为 2。

这确立了一个重要区别:度量结构使近似求解更容易,却不能让最坏情况下的精确优化变得容易。平面上的欧几里得旅行商问题同样是 NP 难的。因此,一个实例具有几何形式,本身并不意味着存在高效的精确算法。对于欧几里得输入,严格的复杂性论述还必须区分精确的几何距离与经过舍入或显式给出的成本,因为比较平方根之和会引入整数权重实例中不存在的算术问题。

P与NP问题关系到一个尚未解决的核心问题。如果 P 不等于 NP,就不存在能在多项式时间内精确求解所有显式编码的旅行商问题实例的算法。这并不意味着每个实例都很难求解,也不意味着必须进行指数规模的枚举,更不意味着无法开展有实际价值的精确计算。特殊结构、强有力的下界、预处理以及有利的数据特征,都可能使规模很大的实例变得可求解。

如果不施加度量限制,即使近似求解也面临严重障碍。对于任何固定的近似比,都可以将原图中已有边的成本设为 1,将缺失边的成本设为一个足够大的值。若存在具有该近似比的多项式时间算法,就能用它区分哪些图具有哈密顿回路、哪些图没有,从而推出 P = NP。三角不等式排除了这种制造巨大成本差距的特定构造,并使常数近似比的算法成为可能。

因此,最坏情况复杂性与实测运行时间描述的是问题的不同方面。复杂性理论研究的是:随着输入规模增大,对于所有输入能够给出何种保证。计算实验衡量的则是特定实现和硬件条件下,算法在某些特定实例族上的表现。两者不能相互替代:启发式算法反复取得成功,并不能证明它具有普遍保证;而 NP 难性也无法预测某个具体工业实例的确切运行时间。

精确算法:子集、搜索树与下界

最直接的精确算法是枚举所有巡回路线,但重复出现的局部计算可以共用结果。Held–Karp 动态规划算法固定一个起始顶点(例如顶点 1),并记录从该顶点出发、访问指定子集中的顶点、最终到达某个指定顶点的最低成本路径。对于 S⊆V∖{1}S\subseteq V\setminus\{1\} 和 j∈Sj\in S,定义 D(S,j)D(S,j) 如下:

D({j},j)=c1j,D(\{j\},j)=c_{1j},

以及

D(S,j)=min⁡i∈S∖{j}[D(S∖{j},i)+cij].D(S,j)= \min_{i\in S\setminus\{j\}} \left[D(S\setminus\{j\},i)+c_{ij}\right].

将路径闭合,即可得到最优巡回路线的成本:

min⁡j≠1[D(V∖{1},j)+cj1].\min_{j\neq1} \left[D(V\setminus\{1\},j)+c_{j1}\right].

子集的数量虽然呈指数级增长,但仍远少于排列的数量。常规实现的时间复杂度为 O(n22n)O(n^2 2^n),存储空间复杂度为 O(n2n)O(n2^n),这里使用大O记号描述渐近增长率。该方法既适用于对称成本,也适用于非对称成本,而且不要求满足三角不等式。它既是重要的理论基准,也是求解较小规模实例或大型算法内部子问题的实用方法。其主要局限不仅在于运行时间,也在于内存需求。

分支定界法采取了另一种思路。它将解空间划分为若干子问题,例如通过规定某些边必须选取或禁止选取来划分。对每个子问题,都计算其中任意巡回路线成本的一个下界。如果该下界不低于某条已知可行巡回路线的成本,就可以舍弃整个子问题。当所有其他可能性都已被探索,或已根据有效下界排除时,搜索便告结束,同时也证明了所得解的最优性。

一些较简单的结构可以提供下界。对于边成本非负的情形,从任意巡回路线中删除一条边,便得到一棵生成树,因此最小生成树的成本给出了一个下界。一种经典且更强的构造是 1-树:选定一个特殊顶点,在其余所有顶点上构建一棵生成树,再接入两条与该特殊顶点关联的边。每个哈密顿回路都是一棵 1-树,但大多数 1-树并不满足每个顶点的度都为二这一要求。

Held–Karp 惩罚方法通过修改边成本,抑制这类违反度数约束的情况。给定顶点惩罚值 πi\pi_i,将 cijc_{ij} 替换为 cij+πi+πjc_{ij}+\pi_i+\pi_j。这样,每条巡回路线的成本都恰好改变 2∑iπi2\sum_i\pi_i,因此可以将调整后的最小 1-树成本换算为巡回路线成本的有效下界。优化这些惩罚值时,会用到拉格朗日对偶的思想。

下界的强弱决定了能省去多少搜索,但更强的下界也可能需要更高的计算成本。高效的精确求解器会权衡这两者,并利用启发式方法尽早找到成本较低的可行巡回路线。高质量的当前最优可行解与强下界相辅相成:前者使剪枝更容易,后者则明确了还可能有多大的改进空间。

整数规划与多面体方法

对称旅行商问题的一种标准建模方式,是为每条无向边 ee 引入一个二元变量 xex_e。巡回路线使用该边时,变量取值为 1,否则为 0。用 δ(v)\delta(v) 表示与顶点 vv 关联的边集,则度数约束为

∑e∈δ(v)xe=2for every v∈V.\sum_{e\in\delta(v)}x_e=2 \qquad \text{for every }v\in V.

仅靠这些等式还不能确定一条巡回路线。它们允许出现多个互不相交的环,这些环合起来称为环覆盖或 2-因子。主要难点在于保证所有选中的边都属于同一个连通的环。

对于顶点子集 SS,用 δ(S)\delta(S) 表示恰有一个端点位于 SS 中的边集。子回路消除约束要求

∑e∈δ(S)xe≥2for every ∅≠S⊊V.\sum_{e\in\delta(S)}x_e\geq2 \qquad \text{for every }\varnothing\neq S\subsetneq V.

一条巡回路线必须离开每个非空真子集,随后再返回其中,因此至少有两条边跨越每个这样的割。这些约束连同度数等式和二元取值限制,构成一个精确的整数规划模型,其目标为

min⁡∑e∈Ecexe.\min\sum_{e\in E}c_e x_e.

这一模型中的子集约束数量呈指数级增长。求解器不必一开始就列出全部约束,而可以先只使用少量约束,再按需添加其余约束。去掉二元取值限制,允许 0≤xe≤10\leq x_e\leq1,就得到一个线性规划松弛。其最优值是原问题的下界,因为每条巡回路线仍然可行,同时模型还允许额外的分数解。一个分数最优解可能为许多边赋予介于 0 和 1 之间的值,却并不对应任何实际路线。

分离算法用于寻找当前分数解所违反的不等式。对于子回路约束,这相当于寻找一个 xx 值之和小于 2 的割。最小割算法可以高效完成这项任务。加入被违反的约束,可以排除当前解,同时不排除任何有效的巡回路线。这就是割平面法,将其与分支过程结合,就得到分支切割法。

从几何角度看,研究对象是旅行商多胞体,即所有巡回路线的边关联向量的凸包。度数约束和子回路约束只刻画了其部分结构。更强的有效不等式(包括梳形不等式)能够排除更多分数解,并显著改善下界。这些不等式是否实用,不仅取决于其强度,也取决于发现它们所需的计算成本。

Concorde 是一款著名的对称旅行商问题精确求解器,体现了优化方法、图算法、专门设计的不等式与搜索技术的结合。完整运行至结束的计算可以证明不存在更优的巡回路线;提前终止计算时,通常只能得到由当前最佳巡回路线成本与最佳下界所界定的区间。在将精确求解器与启发式算法进行比较,或报告基准问题的数值“解”时,这一区别至关重要。

近似算法与性能保证

近似算法在多项式时间内运行,并保证所得解与最优解的比值不超过指定的近似因子。对于最小化问题,α\alpha-近似算法得到的巡回路线,其成本至多为 α OPT\alpha\,\mathrm{OPT}。这是针对最坏情况的数学保证,而不是实际观测到的平均误差。对于对称度量旅行商问题,三角不等式使这样的保证成为可能,因为跳过重复访问的顶点不会增加成本。

最简单的经典构造方法是将最小生成树的每条边加倍。这样一来,所有顶点的度数都变为偶数,因此所得的连通多重图具有一条欧拉回路,即恰好经过每条边一次的闭合路线。通过抄近路跳过重复出现的顶点,就能得到一条哈密顿巡回路线。由于最小生成树的成本不超过最优巡回路线的成本,所得巡回路线的成本至多为 2 OPT2\,\mathrm{OPT}。这一算法清楚地区分了访问每个顶点与遍历每条边这两个概念。

克里斯托菲德斯算法将近似因子改进到 3/23/2。首先构造一棵最小生成树 TT,并令 OO 为其中所有奇度顶点组成的集合。奇度顶点的数量必为偶数。在 OO 上求一个最小权完美匹配,将匹配中的边加入 TT,然后求出一条欧拉回路,再通过抄近路跳过重复顶点。加入匹配边后,每个奇度顶点的度数都变为偶数,同时图的连通性保持不变。

近似保证的证明关键在于说明,匹配的成本至多为最优值的一半。在最优巡回路线上抄近路,可得到一个经过 OO 中所有顶点的环。将环上的边交替分为两组,即可得到两个完美匹配,其中至少一个的成本不超过该环成本的一半。最小权匹配的成本不会比它更高。因此,

c(T)+c(M)≤OPT+12OPT=32OPT.c(T)+c(M)\leq \mathrm{OPT}+\frac12\mathrm{OPT} =\frac32\mathrm{OPT}.

数十年来,3/23/2 一直是对称度量旅行商问题已知最好的通用多项式时间近似保证。安娜·卡林、内森·克莱因和沙扬·奥韦斯·加兰于 2020 年公布了一项研究,给出了一种随机算法,其期望近似比为 3/2−ε3/2-\varepsilon,其中 ε\varepsilon 是一个固定的正数,但数值极小。这一进展证明了经典界限可以被突破,但并不意味着实际性能也有同样显著的提升。

关于子巡回线性规划松弛,仍有一些重要问题尚未解决。它的整数间隙衡量的是最优巡回路线成本与分数最优值之间的比值。一个由来已久的猜想认为,对称度量旅行商问题的最坏情况整数间隙为 4/34/3。这一猜想不同于证明某个具体的舍入算法能够达到该近似比。

非对称度量旅行商问题有其独立的近似理论。生成树边加倍和无向图中的奇偶性修正方法,不能直接用于具有方向性的成本。奥拉·斯文松、雅库布·塔尔纳夫斯基和拉斯洛·韦格在 2018 年发表的研究中建立了常数因子近似算法,解决了一个重要的定性问题:是否能够给出不依赖于顶点数量的近似保证。

启发式方法、局部搜索与计算实践

启发式方法力求快速找到较好的巡回路线,但不一定证明最坏情况下的近似比,也不一定证明解的最优性。构造型启发式方法首先生成一个可行的访问顺序。最近邻启发式方法每次都前往距离当前位置最近的未访问顶点。插入法则通过不断插入新顶点来扩展一条部分巡回路线,例如选择使路线长度增加最少的插入方式。这些方法的计算开销很小,但早期的选择可能导致最后不得不采用代价高昂的连接。

局部搜索通过替换选定的边来改进一条完整的巡回路线。在 2-opt 中,先删除巡回路线上的两条边,再以另一种仍能构成单条巡回路线的方式重新连接由此得到的路径。对于对称问题,这相当于将访问顺序中的一个片段反转。如果这一操作能降低总代价,就接受它。只要能方便地获取所需距离,就可以根据受影响的四处连接来计算代价变化,而不必重新计算整条巡回路线。

2-opt 局部最优解不存在这种形式的改进操作,但它未必是全局最优解。转向 3-opt 或更一般的 kk-opt 邻域,可以摆脱某些令 2-opt 束手无策的局面,代价是需要考察更多备选方案。对于非对称代价,反转一个片段会改变其内部每条弧的方向,因此不能原封不动地套用对称情形下的 2-opt 计算方式。

Lin–Kernighan 启发式算法会动态调整边交换序列的规模与结构,而不是预先固定一个较小的 kk。它利用增益计算和搜索限制来寻找有希望的交换,而不必遍历整个组合邻域。Keld Helsgaun 开发的一个影响广泛的实现通常称为 LKH,它将这一总体思路与候选边、有效的搜索规则以及下界信息相结合。它的成功表明,即使最终计算不能给出最优性证明,数学结构仍然可以为启发式方法提供指引。

模拟退火有时会接受使解变差的操作,以跳出局部极小值。禁忌搜索通过限制近期使用过的操作或属性,避免搜索陷入循环。进化方法维护由候选巡回路线组成的种群,而蚁群方法则强化与优良解相关的边。混合方法通常将多样化搜索与深入的局部改进相结合。这些方法的表现取决于实现细节、参数设置、停止准则以及实例结构。

可靠的实验评估应区分巡回路线的质量、计算开销以及是否已有最优性证明。需要报告的信息包括代价的计算约定、随机种子的使用策略、运行次数、硬件、运行时间以及已知的最佳下界。对于正下界 LL 和巡回路线代价 UU,(U−L)/L(U-L)/L 是一种有用的相对差距指标。仅与此前找到的最佳巡回路线比较,并不能确定当前解与未知最优解之间的差距。

大规模实现也会尽可能避免考察所有可能的边。基于几何邻近性或结构评分建立的候选列表,可以大幅减少搜索开销。除非能够证明这些限制不会排除最优解,否则它们仍属于启发式做法:候选列表中遗漏的某条边,仍可能属于某条最优巡回路线。

欧几里得几何与概率结构

欧几里得旅行商问题具有任意加权实例所不具备的性质。在平面上的最优巡回路线中,两条边不可能在各自内部形成真交叉。如果线段 abab 和 cdcd 相交,就可以用适当的不交叉连接替换它们,在保持单一回路的同时缩短总长度。这一论证是在交点处应用三角不等式得出的;对于真交叉,替换后的长度会严格减小。因此,消除交叉是一种有效的局部改进手段,但没有交叉的巡回路线仍可能远非最优。

对于处于一般位置的点集,在最优巡回路线中,凸包边界上的顶点必定按照它们沿边界的循环顺序出现,方向可以相反。若顺序不一致,就必然产生交叉。不过,内部点可以以多种方式穿插其中,因此这一性质并不能确定完整路线。几何约束缩小了可能解的范围,却没有消除问题在组合层面的困难。

从算法角度看,一个更强的优势是:在每个固定维度中,欧几里得旅行商问题都存在多项式时间近似方案。桑吉夫·阿罗拉和约瑟夫·米切尔在20世纪90年代各自独立开展的研究表明,对任意固定的 ε>0\varepsilon>0,都能在多项式时间内找到长度不超过 (1+ε)OPT(1+\varepsilon)\mathrm{OPT} 的巡回路线。不过,计算开销对精度和维度有很强的依赖,因此,这一定理并不意味着求得任意高精度的解都只需很少的计算资源。

阿罗拉的方法使用递归细分的几何区域、称为“门户”的指定穿越点,以及针对受限边界交互方式的动态规划。通过结构性论证可以证明,一条近似最优的巡回路线可以经过修改来满足这些限制,而长度只会有很小的相对增幅。随后,算法搜索的是一组有限且规模可控的边界状态,而非所有访问顺序。维度固定是控制这些状态复杂度的关键。

随机几何实例呈现出另一种结构。1959年发表的比尔德伍德–哈尔顿–哈默斯利定理,描述了遍历有界区域内独立采样点的最优巡回路线长度的渐近行为。在该定理的标准密度假设下,对于维度 d≥2d\geq2,有

Lnn(d−1)/d⟶βd∫Rdf(x)(d−1)/d dxalmost surely,\frac{L_n}{n^{(d-1)/d}} \longrightarrow \beta_d\int_{\mathbb{R}^d} f(x)^{(d-1)/d}\,dx \quad\text{almost surely},

其中,LnL_n 为最短巡回路线的长度,ff 为采样密度,βd\beta_d 为一个取决于维度的常数。

对于均匀分布在面积为 AA 的平面区域内的点,这一定理给出的首阶增长量与 nA\sqrt{nA} 成正比。这解释了为什么将密集散布的停靠点数量增加一倍,通常并不会使最优几何路线的长度也增加一倍。该定理讨论的是大规模随机样本及其渐近行为,而不是对某个具体的有限街道网络或聚簇客户数据集作出精确预测。

应用、建模选择与新兴方法

在物流中,旅行商问题(TSP)用于描述单辆车访问一组固定站点并返回车场的情形。两站之间的成本可以通过计算道路网络中的最短路径得到,而不一定采用直线距离。这种度量闭包将两个站点之间如何行驶的问题与所有站点如何排序的问题分离开来。将选定的抽象边还原为道路路径,就能得到可实际执行的行程,但该行程可能多次经过某些实际地点。

TSP 与中国邮递员问题的区别在实际作业中十分重要。TSP 要求访问指定的顶点;中国邮递员问题则要求遍历指定的边,例如某个服务区域内的每一条街道。向各个地址投递包裹可能更接近顶点路径规划问题,而街道清扫则更适合建模为边路径规划问题。混淆二者,可能导致优化模型求解的并非实际需要完成的任务。

在制造业应用中,各项作业取代了城市的位置。例如,钻头可能需要依次到达印刷电路板上的许多孔位,而孔位之间的移动会产生非生产性耗时。检测仪器也可能需要依次到达各个测量位置。即使不存在实际移动,依赖作业顺序的设备换型成本也可能形成非对称成本矩阵。只有当从最后一项作业回到第一项作业的转换确实属于运行周期的一部分时,采用闭合回路形式的 TSP 才合适;否则,可能需要采用路径或调度模型。

实际运动也揭示了仅以距离为优化目标的局限性。机器人或切削工具可能受到加速度上限、转弯半径、障碍物或朝向要求的约束。几何距离最短的访问顺序不一定使执行时间最短。如果转换成本取决于到达方向或先前的动作,简单的顶点间成本矩阵就可能遗漏关键状态。更丰富的模型可以纳入这些影响,但并非所有针对经典 TSP 证明的结论都仍然适用。

研究者已尝试利用机器学习构造巡回路线、对候选边排序、选择分支决策,或引导局部搜索。神经网络模型可以从抽样得到的实例中学习规律,而基于优化的组件则用于确保解的可行性,或改进预测出的路线。评估时,必须区分模型在熟悉的训练分布上的表现,以及在不同规模、几何布局和成本结构下的表现。学习得到的策略不能仅凭良好的基准测试结果,就被认定具有可证明的近似保证。

TSP 也出现在非常规计算的实验中,包括量子退火和伊辛模型的建模研究。常见的编码方法使用二元变量将城市分配到巡回路线中的各个位置,并通过惩罚项抑制无效分配。所需的变量数量、连接结构、系数精度以及约束落实方式,都会影响方法的可扩展性。成功的编码只能说明问题可以用这种方式表示;若要声称具有计算优势,还需要与适当的经典方法进行受控比较,其中包括成熟的启发式方法和精确求解器。