旅行推销员问题

1. REDIRECT Template:Expand language

旅行商问题（Template:Langx，缩写：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。”

File:GLPK solution of a travelling salesman problem.svg

旅行商问题的解

TSP是与车辆路径问题的一种特殊情况。

作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式（可能是）级别增长。

问题在1930年首次被形式化，为最佳化中被研究得最深入的问题之一，许多优化方法都奉其为基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。

甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还被应用在天文学中，减少在不同光源之间转动望远镜的时间。在许多应用场景中（如资源或时间窗口有限等等），可能会需要加入额外的约束条件。

描述

作为图论问题

File:Weighted K4.svg

四个城市的对称旅行商问题

可以用无向加权图来对TSP建模，则城市是图的顶点，道路是图的边，道路的距离就是该边的长度。它是起点和终点都在一个特定顶点，访问每个顶点恰好一次的最小化问题。通常，该模型是一个完全图（即每对顶点由一条边连接）。如果两个城市之间不存在路径，则增加一条非常长的边就可以完成图，而不影响计算最优回路。

非对称和对称

在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图。这种对称性将解的数量减少了一半。在非对称TSP问题中，可能不是双向的路径都存在，或是来回的距离不同，形成了有向图。交通事故、单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。

相关问题

• 图论中的一个等价形式是：给定一个加权完全图（顶点表示城市，边表示道路，权重就会是道路的成本或距离）, 求一权值最小的哈密尔顿回路。
• 返回到起始城市的要求不会改变问题的计算复杂度，见哈密顿路径问题。
• 另一个相关问题是（bottleneck TSP）：求加权图中权重最大的边最小的哈密尔顿回路。问题在运输和物流之外都有相当广泛的实际意义。一个典型的例子是在印刷电路板制造中：规划打孔机在PCB版上钻孔的路线。在机械加工或钻孔应用中，“城市”是需要加工的部分或需要钻的（不同大小）的孔，而“旅行成本”包括更换机具所用的时间（单机作业排序问题）。
• 旅行推销员问题，处理“国家”中有（一个或多个）“城市”，而旅行商需要在每个“国家”访问恰好一座“城市”。其中一种应用是在求解时，想要最小化刀具改变次数中。另一种应用与半导体制造业中的打孔有关，见美国专利第7,054,798号。令人惊喜的是，Behzad与Modarres证明了广义旅行商问题可以转化为相同城市数量的标准旅行商问题 ，只是要改变距离矩阵。

• 优先顺序旅行推销员问题处理城市之间存在访问次序的问题。
• 旅行购买者问题涉及购买一系列产品的购买者。他可以在若干城市购买这些产品，但价格会有不同，也不是所有城市都有售相同的商品。目标是在城市的子集中间找到一条路径，使得总成本（旅行成本 + 购买成本）最小，并且能够买到所有需求的商品。

整数线性规划形式

单钻头的运动可以看成是典型的TSP问题。TSP可以用整数线性规划来形式化。用数字 0, ..., n 标记这些城市（打孔位置），并定义：

<math> x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases}</math>

对于 i = 0, ..., n，令 <math>u_i</math> 为一人工变量，最后把 <math>c_{ij}</math> 作为从城市 i 到 j 的距离。那么TSP可以写成下面的整数线性规划问题：

<math>\begin{align}

\min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} && \\

    & 0 \le x_{ij} \le 1  && i,j=0, \cdots, n  \\
    & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\
    & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\
    & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\

&u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n \end{align}</math>

第一组等式要求每个城市都能另一个城市前来，而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条，而不是两条或者多条分散的路径在一起覆盖的。要证明这一点，下面会去证 (1)每个可行解包含只有一条封闭城市序列，以及(2)对于每条覆盖所有城市的单独路径，虚拟变量 <math>u_i</math> 有值可以满足限制式。

证明可行解中的每个子回路经过0号城市（注意到等式保证了只有一条这样的路径），就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有 <math>x_{ij}=1</math> 对应的不等式求和的话，对 k 步不经过0号城市的任何子回路，我们得到：

<math>nk \leq (n-1)k,</math>

这构成矛盾。

必须证明对每个覆盖所有城市的单独回路，虚拟变量 <math>u_i</math> 有值可以满足约束。

为了不失一般性，定义起始点为0号城市。如果在第 t 步访问城市 i 后 (i, t = 1, 2, ..., n) 选取 <math>u_{i}=t</math>。则

<math>u_i-u_j\le n-1,</math>

由于 <math>u_i</math> 不大于 n 而 <math>u_j</math> 不小于1；因此，每当 <math>x_{ij}=0</math> 时满足约束。对于 <math>x_{ij}=1</math>，我们有：

<math> u_{i} - u_{j} + nx_{ij} = (t) - (t+1) + n = n-1,</math>

满足约束。

参见

• 邮递员问题
• 柯尼斯堡七桥问题
• 车辆路径问题

参考文献

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

延伸阅读

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

外部链接

• Traveling Salesman Problem （页面存档备份，存于互联网档案馆） at University of Waterloo
• TSPLIB at the University of Heidelberg
• Traveling Salesman Problem （页面存档备份，存于互联网档案馆） by Jon McLoone at the Wolfram Demonstrations Project
• Traveling Salesman movie (on IMDB) （页面存档备份，存于互联网档案馆）
• MAOS-TSP （页面存档备份，存于互联网档案馆） JAVA TSP Solver