旅行推銷員問題

旅行商問題（英語：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問題中，可能不是雙向的路徑都存在，或是來回的距離不同，形成了有向圖。交通事故、單行道和出發與到達某些城市機票價格不同等都是打破這種對稱性的例子。

相關問題

• 圖論中的一個等價形式是：給定一個加權完全圖（頂點表示城市，邊表示道路，權重就會是道路的成本或距離）, 求一權值最小的Hamilton圈。

• 返回到起始城市的要求不會改變問題的計算複雜度，見哈密頓路徑問題。

• 另一個相關問題是瓶頸旅行商問題（英語：bottleneck traveling salesman problem）^{[譯名請求]}（bottleneck TSP）：求加權圖中權重最大的邊最小的Hamilton圈。問題在運輸和物流之外都有相當廣泛的實際意義。一個典型的例子是在印刷電路板製造中：規劃打孔機在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