旅行推销员问题

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

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问题中，可能不是双向的路径都存在，或是来回的距离不同，形成了有向图。交通事故、单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。

整数线性规划形式

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

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

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

{\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)对于每条覆盖所有城市的单独路径，虚拟变量 $u_{i}$ 有值可以满足限制式。

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

nk\leq (n-1)k,

这构成矛盾。

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

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

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

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

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

满足约束。

参见

注释

[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 , 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

[1] [1]
参见已解出精确解0.05%范围内的TSP世界巡游问题。[1] （页面存档备份，存于互联网档案馆）

[2] [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] [3]
Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, Mineola, NY: Dover, 1998 , pp.308-309.

[4] [4]
Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)

[5] [5]
Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, sixth printing, 1974.

[1]

[2]

[3]

[4]

[5]

描述