旅行推销员问题

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

旅行商问题的解

“TSP”重定向至此。关于其他用法，请见“TSP (消歧义)”。

TSP是旅行购买者问题（英语：travelling purchaser problem）与车辆路径问题的一种特殊情况。

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

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

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

描述

作为图论问题

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

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

非对称和对称

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

相关问题

• 图论中的一个等价形式是：给定一个加权完全图（顶点表示城市，边表示道路，权重就会是道路的成本或距离）, 求一权值最小的哈密尔顿回路。

• 返回到起始城市的要求不会改变问题的计算复杂度，见哈密顿路径问题。

• 另一个相关问题是瓶颈旅行商问题（英语：bottleneck traveling salesman problem）^{[译名请求]}（bottleneck TSP）：求加权图中权重最大的边最小的哈密尔顿回路。问题在运输和物流之外都有相当广泛的实际意义。一个典型的例子是在印刷电路板制造中：规划打孔机在PCB版上钻孔的路线。在机械加工或钻孔应用中，“城市”是需要加工的部分或需要钻的（不同大小）的孔，而“旅行成本”包括更换机具所用的时间（单机作业排序问题）。

• 旅行推销员问题，处理“国家”中有（一个或多个）“城市”，而旅行商需要在每个“国家”访问恰好一座“城市”。其中一种应用是在求解裁切问题（英语：cutting stock problem）时，想要最小化刀具改变次数中。另一种应用与半导体制造业中的打孔有关，见美国专利第7,054,798号。令人惊喜的是，Behzad与Modarres证明了广义旅行商问题可以转化为相同城市数量的标准旅行商问题 ，只是要改变距离矩阵。^[2]

• 优先顺序旅行推销员问题处理城市之间存在访问次序的问题。

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

整数线性规划形式

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

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise}}\end{cases}}}$

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

${\displaystyle {\begin{aligned}\min &\sum _{i=0}^{n}\sum _{j\neq i,j=0}^{n}c_{ij}x_{ij}&&\\&0\leq x_{ij}\leq 1&&i,j=0,\cdots ,n\\&u_{i}\in \mathbf {Z} &&i=0,\cdots ,n\\&\sum _{i=0,i\neq j}^{n}x_{ij}=1&&j=0,\cdots ,n\\&\sum _{j=0,j\neq i}^{n}x_{ij}=1&&i=0,\cdots ,n\\&u_{i}-u_{j}+nx_{ij}\leq n-1&&1\leq i\neq j\leq n\end{aligned}}}$

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

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

${\displaystyle nk\leq (n-1)k,}$

这构成矛盾。

必须证明对每个覆盖所有城市的单独回路，虚拟变量 ${\displaystyle u_{i}}$ 有值可以满足约束。

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

${\displaystyle u_{i}-u_{j}\leq n-1,}$

由于 ${\displaystyle u_{i}}$ 不大于 n 而 ${\displaystyle u_{j}}$ 不小于1；因此，每当 ${\displaystyle x_{ij}=0}$ 时满足约束。对于 ${\displaystyle x_{ij}=1}$，我们有：

${\displaystyle u_{i}-u_{j}+nx_{ij}=(t)-(t+1)+n=n-1,}$

满足约束。

参见

• 加拿大旅行者问题（英语：Canadian traveller problem）
• 邮递员问题
• 柯尼斯堡七桥问题
• 车辆路径问题

注释

1. 参见已解出精确解0.05%范围内的TSP世界巡游问题。[1] （页面存档备份，存于互联网档案馆）
2. Behzad, Arash; Modarres, Mohammad, New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem, Proceedings of the 15th International Conference of Systems Engineering (Las Vegas), 2002
3. Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, Mineola, NY: Dover, 1998 引文使用过时参数coauthors (帮助), pp.308-309.
4. Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)
5. Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, sixth printing, 1974.

参考文献

• Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J., The Traveling Salesman Problem, 2006, ISBN 0-691-12993-2.
• Arora, Sanjeev, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, 1998, 45 (5): 753–782, MR 1668147, doi:10.1145/290179.290180.
• Beardwood, J.; Halton, J.H.; Hammersley, J.M., The Shortest Path Through Many Points, Proceedings of the Cambridge Philosophical Society, 1959, 55: 299–327, doi:10.1017/s0305004100034095.
• Bellman, R., Combinatorial Processes and Dynamic Programming, Bellman, R., Hall, M., Jr. (eds.) (编), Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society: 217–249, 1960.
• Bellman, R., Dynamic Programming Treatment of the Travelling Salesman Problem, J. Assoc. Comput. Mach., 1962, 9: 61–63, doi:10.1145/321105.321111.
• Berman, Piotr; Karpinski, Marek, 8/7-approximation algorithm for (1,2)-TSP, Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06): 641–648, 2006, ISBN 0898716055, doi:10.1145/1109557.1109627, Template:ECCC.
• Christofides, N., Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976.
• Hassin, R.; Rubinstein, S., Better approximations for max TSP, Information Processing Letters, 2000, 75 (4): 181–186, doi:10.1016/S0020-0190(00)00097-1.
• Held, M.; Karp, R. M., A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, 1962, 10 (1): 196–210, doi:10.1137/0110015.
• Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M., Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs, In Proc. 44th IEEE Symp. on Foundations of Comput. Sci: 56–65, 2004.
• Kosaraju, S. R.; Park, J. K.; Stein, C., Long tours and short superstrings', Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci, IEEE Computer Society: 166–177, 1994.
• Orponen, P.; Mannila, H., On approximation preserving reductions: Complete problems and robust measures', Technical Report C-1987–28, Department of Computer Science, University of Helsinki, 1987.
• Padberg, M.; Rinaldi, G., A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems, Siam Review, 1991: 60–100, doi:10.1137/1033004.
• Papadimitriou, Christos H., The Euclidean traveling salesman problem is NP-complete, Theoretical Computer Science, 1977, 4 (3): 237–244, MR 0455550, doi:10.1016/0304-3975(77)90012-3.
• Papadimitriou, C. H.; Yannakakis, M., The traveling salesman problem with distances one and two, Math. Oper. Res., 1993, 18: 1–11, doi:10.1287/moor.18.1.1.
• Serdyukov, A. I., An algorithm with an estimate for the traveling salesman problem of the maximum', Upravlyaemye Sistemy, 1984, 25: 80–86.
• Steinerberger, Stefan, New Bounds for the Traveling Salesman Constant, Advances in Applied Probability, 2015, 47.
• Woeginger, G.J., Exact Algorithms for NP-Hard Problems: A Survey, Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer: 185–207, 2003.

延伸阅读

• Adleman, Leonard, Molecular Computation of Solutions To Combinatorial Problems (PDF), Science, 1994, 266 (5187): 1021–4, Bibcode:1994Sci...266.1021A, PMID 7973651, doi:10.1126/science.7973651, （原始内容 (PDF)存档于2005-02-06）
• Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems (PDF), Journal of the ACM, 1998, 45 (5): 753–782 [2015-08-18], doi:10.1145/290179.290180, （原始内容存档 (PDF)于2020-11-24）.
• Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert, Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem, Cahiers du GERAD, G-2005-02, Montreal: Group for Research in Decision Analysis, 2005 [2015-08-18], （原始内容存档于2011-09-19）.
• Cook, William, In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2011, ISBN 978-0-691-15270-7.
• Cook, William; Espinoza, Daniel; Goycoolea, Marcos, Computing with domino-parity inequalities for the TSP, INFORMS Journal on Computing, 2007, 19 (3): 356–365, doi:10.1287/ijoc.1060.0204.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., 35.2: The traveling-salesman problem, Introduction to Algorithms 2nd, MIT Press and McGraw-Hill: 1027–1033, 2001, ISBN 0-262-03293-7.
• Dantzig, G. B.; Fulkerson, R.; Johnson, S. M., Solution of a large-scale traveling salesman problem, Operations Research, 1954, 2 (4): 393–410, JSTOR 166695, doi:10.1287/opre.2.4.393.
• Garey, M. R.; Johnson, D. S., A2.3: ND22–24, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman: 211–212, 1979, ISBN 0-7167-1045-5.
• Goldberg, D. E., Genetic Algorithms in Search, Optimization & Machine Learning, Reading: Addison-Wesley (New York: Addison-Wesley), 1989, Bibcode:1989gaso.book.....G, ISBN 0-201-15767-5.
• Gutin, G.; Yeo, A.; Zverovich, A., Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP, Discrete Applied Mathematics, 2002, 117 (1–3): 81–86, doi:10.1016/S0166-218X(01)00195-0.
• Gutin, G.; Punnen, A. P., The Traveling Salesman Problem and Its Variations, Springer, 2006, ISBN 0-387-44459-9.
• Johnson, D. S.; McGeoch, L. A., The Traveling Salesman Problem: A Case Study in Local Optimization, Aarts, E. H. L.; Lenstra, J. K. (编), Local Search in Combinatorial Optimisation, John Wiley and Sons Ltd: 215–310, 1997.
• Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, 1985, ISBN 0-471-90413-9.
• MacGregor, J. N.; Ormerod, T., Human performance on the traveling salesman problem (PDF), Perception & Psychophysics, 1996, 58 (4): 527–539, doi:10.3758/BF03213088, （原始内容 (PDF)存档于2009年12月29日）.
• Mitchell, J. S. B., Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM Journal on Computing, 1999, 28 (4): 1298–1309 [2015-08-18], doi:10.1137/S0097539796309764, （原始内容存档于2007-12-22）.
• Rao, S.; Smith, W., Approximating geometrical graphs via 'spanners' and 'banyans', Proc. 30th Annual ACM Symposium on Theory of Computing: 540–550, 1998.
• Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Philip M., II, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal on Computing, 1977, 6 (5): 563–581, doi:10.1137/0206041.
• Vickers, D.; Butavicius, M.; Lee, M.; Medvedev, A., Human performance on visually presented traveling salesman problems, Psychological Research, 2001, 65 (1): 34–45, PMID 11505612, doi:10.1007/s004260000031.
• Walshaw, Chris, A Multilevel Approach to the Travelling Salesman Problem, CMS Press, 2000.
• Walshaw, Chris, A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem, CMS Press, 2001.

外部链接

• 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