旅行推銷員問題

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