TSP问题

**旅行商問題**（英語：Travelling salesman problem, TSP）是組合最佳化中的一個 NP 困難問題，在作業研究和理論電腦科學中非常重要。問題內容為「給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。」

TSP 是旅行購買者問題與車輛路徑問題的一種特殊情況。

作為計算複雜性理論中的一個典型的判定性問題，TSP 的一個版本是給定一個圖和長度 _L_，要求回答圖中是否存在比 _L_ 短的迴路（英語：circuit 或 tour）。該問題被劃分為 NP 完全問題。已知 TSP 演算法最壞情況下的時間複雜度隨著城市數量的增多而成超多項式（可能是指數）級別增長。

問題在 1930 年首次被形式化，並且是在最佳化中研究最深入的問題之一。許多最佳化方法都用它作為一個基準。儘管問題在計算上很困難，但已經有了大量的啟發式和精確方法，因此可以完全求解城市數量上萬的實例，並且甚至能在誤差 1% 範圍內估計上百萬個城市的問題。

甚至純粹形式的 TSP 都有若干應用，如企劃、物流、晶片製造。稍作修改，就是 DNA 定序等許多領域的一個子問題。在這些應用中，「城市」的概念用來表示客戶、焊接點或 DNA 片段，而「距離」的概念表示旅行時間或成本或 DNA 片段之間的相似性度量。TSP 還用在天文學中，觀察很多光源的天文學家會希望減少在不同光源之間轉動望遠鏡的時間。在許多應用場景中（如資源或時間窗口有限等等），可能會需要加入額外的約束條件。

## 描述

### 作為圖論問題

可以用無向加權圖來對 TSP 建模，則城市是圖的頂點，道路是圖的邊，道路的距離就是該邊的長度。它是起點和終點都在一個特定頂點，訪問每個頂點恰好一次的最小化問題。通常，該模型是一個完全圖（即每對頂點由一條邊連接）。如果兩個城市之間不存在路徑，則增加一條非常長的邊就可以完成圖，而不影響計算最佳迴路。

### 非對稱和對稱

在_對稱 TSP 問題_中，兩座城市之間來回的距離是相等的，形成一個無向圖。這種對稱性將解的數量減少了一半。在_非對稱 TSP 問題_中，可能不是雙向的路徑都存在，或是來回的距離不同，形成了有向圖。交通事故、單行道和出發與到達某些城市機票價格不同等都是打破這種對稱性的例子。

### 相關問題

* 圖論中的一個等價形式是：給定一個加權完全圖（頂點表示城市，邊表示道路，權重就會是道路的成本或距離）, 求一權值最小的 Hamilton 圈。
* 返回到起始城市的要求不會改變問題的計算複雜度，見哈密頓路徑問題。
* 另一個相關問題是瓶頸旅行商問題（bottleneck TSP）：求加權圖中權重最大的邊最小的 Hamilton 圈。問題在運輸和物流之外都有相當廣泛的實際意義。一個典型的例子是在印刷電路板製造中：規劃打孔機在 PCB 版上鑽孔的路線。在機械加工或鑽孔應用中，「城市」是需要加工的部分或需要鑽的（不同大小）的孔，而「旅行成本」包括更換機具所用的時間（單機作業排序問題）。
* 旅行推銷員問題，處理「國家」中有（一個或多個）「城市」，而旅行商需要在每個「國家」訪問恰好一座「城市」。其中一種應用是在求解裁切問題時，想要最小化刀具改變次數中。另一種應用與半導體製造業中的打孔有關，見美國專利第 7,054,798 號。令人驚喜的是，Behzad 與 Modarres 證明了廣義旅行商問題可以轉化為相同城市數量的標準旅行商問題 ，只是要改變距離矩陣。
* 優先順序旅行推銷員問題處理城市之間存在訪問次序的問題。
* 旅行購買者問題涉及購買一系列產品的購買者。他可以在若干城市購買這些產品，但價格會有不同，也不是所有城市都有售相同的商品。目標是在城市的子集中間找到一條路徑，使得總成本（旅行成本 + 購買成本）最小，並且能夠買到所有需求的商品。

## 整數線性規劃形式

單鑽頭的運動可以看成是典型的 TSP 問題。TSP 可以用整數線性規劃來形式化。 用數字 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,$

滿足約束。

## 參見

* 加拿大旅行者問題
* 郵遞員問題
* 柯尼斯堡七橋問題
* 車輛路徑問題

## 注釋

## 參考文獻

## 延伸閱讀

* 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