旅行推銷員問題是圖論中最著名的問題之一，即“已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉回路”。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效算法時，每個問題都會有有效算法。 [1]

迄今為止，這類問題中沒有一個找到有效算法。傾向于接受NP完全問題(NP-Complete或NPC)和NP難題(NP-Hard或NPH)不存在有效算法這一猜想，認為這類問題的大型實例不能用精確算法求解，必須尋求這類問題的有效的近似算法。

此類問題中，經典的還有 子集和問題; Hamilton回路問題;最大團問題。

作為圖論問題

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

非對稱和對稱

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

相關問題

圖論中的一個等價形式是：給定一個加權完全圖(頂點表示城市，邊表示道路，權重就會是道路的成本或距離), 求一權值最小的哈密爾頓回路。

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

另一個相關問題是瓶頸旅行商問題(bottleneck TSP)：求加權圖中權重最大的邊最小的哈密爾頓回路。問題在運輸和物流之外都有相當廣泛的實際意義。一個典型的例子是在印刷電路板制造中：規劃打孔機在PCB版上鉆孔的路線。在機械加工或鉆孔應用中，“城市”是需要加工的部分或需要鉆的(不同大小)的孔，而“旅行成本”包括更換機具所用的時間(單機作業排序問題)。

廣義旅行商問題，又稱“旅行政客問題”，處理“國家”中有(一個或多個)“城市”，而旅行商需要在每個“國家”訪問恰好一座“城市”。其中一種應用是在求解下料問題時，想要最小化刀具改變次數中。另一種應用與半導體制造業中的打孔有關。令人驚喜的是，Behzad與Modarres證明了廣義旅行商問題可以轉化為相同城市數量的標準旅行商問題 ，只是要改變距離矩陣。 [2]

優先順序旅行推銷員問題處理城市之間存在訪問次序的問題。

旅行購買者問題涉及購買一系列產品的購買者。他可以在若干城市購買這些產品，但價格會有不同，也不是所有城市都有售相同的商品。目標是在城市的子集中間找到一條路徑，使得總成本(旅行成本 + 購買成本)最小，并且能夠買到所有需求的商品。

TSP問題舉例

有一位商人，他想訪問中國的某些城市，要求：

1. 所走路程最近;

2. 每個城市只能訪問一次;

3. 從某城市出發，最后回到該城市。

如圖1所示：

假設從合肥出發，最后回到合肥。

問題域：X={北京，成都，廣州，上海}

目標函數：min f(x)=dist(合肥，city1) + ∑dist(cityi,cityj) + dist(cityj,合肥)

總懸浮顆粒物是指能懸浮在空氣中，空氣動力學當量直徑≤100微米的顆粒物。記作TSP,是大氣質量評價中的一個通用的重要污染指標。 總懸浮顆粒物的濃度以每立方米空氣中總懸浮顆粒物的毫克數表示，用標準大容量顆粒采樣器在采樣效率接近100%濾膜上采集已知體積的顆粒物，恒溫恒濕條件下，稱量采樣前后采樣膜質量來確定采集到的顆粒物質量，再除以采樣體積，得到顆粒物的質量濃度。

想要了解更有關TSP的信息，請繼續關注中培偉業。