旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
基本介紹
- 中文名：旅行商問題
- 外文名：Travelling Salesman Problem
- 別名：旅行推銷員問題、貨郎擔問題
- 領域：數學
- 屬於：組合最佳化問題
- 性質：具有NPC計算複雜性
簡介,描述,作為圖論問題,非對稱和對稱,相關問題,TSP問題舉例,其他,
簡介
TSP問題是一個組合最佳化問題。該問題可以被證明具有NPC計算複雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
旅行推銷員問題是圖論中最著名的問題之一，即“已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉迴路”。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效算法時，每個問題都會有有效算法。
迄今為止，這類問題中沒有一個找到有效算法。傾向於接受NP完全問題（NP-Complete或NPC）和NP難題（NP-Hard或NPH）不存在有效算法這一猜想，認為這類問題的大型實例不能用精確算法求解，必須尋求這類問題的有效的近似算法。
描述
作為圖論問題
可以用無向加權圖來對TSP建模，則城市是圖的頂點，道路是圖的邊，道路的距離就是該邊的長度。它是起點和終點都在一個特定頂點，訪問每個頂點恰好一次的最小化問題。通常，該模型是一個完全圖（即每對頂點由一條邊連線）。如果兩個城市之間不存在路徑，則增加一條非常長的邊就可以完成圖，而不影響計算最優迴路。
非對稱和對稱
在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖。這種對稱性將解的數量減少了一半。在非對稱TSP問題中，可能不是雙向的路徑都存在，或是來回的距離不同，形成了有向圖。交通事故、單行道和出發與到達某些城市機票價格不同等都是打破這種對稱性的例子。
相關問題
- 圖論中的一個等價形式是：給定一個加權完全圖（頂點表示城市，邊表示道路，權重就會是道路的成本或距離）, 求一權值最小的哈密爾頓迴路。
- 返回到起始城市的要求不會改變問題的計算複雜度，見哈密頓路徑問題。
- 另一個相關問題是瓶頸旅行商問題（bottleneck TSP）：求加權圖中權重最大的邊最小的哈密爾頓迴路。問題在運輸和物流之外都有相當廣泛的實際意義。一個典型的例子是在印刷電路板製造中：規劃打孔機在PCB版上鑽孔的路線。在機械加工或鑽孔套用中，“城市”是需要加工的部分或需要鑽的（不同大小）的孔，而“旅行成本”包括更換機具所用的時間（單機作業排序問題）。
- 廣義旅行商問題，又稱“旅行政客問題”，處理“國家”中有（一個或多個）“城市”，而旅行商需要在每個“國家”訪問恰好一座“城市”。其中一種套用是在求解下料問題時，想要最小化刀具改變次數中。另一種套用與半導體製造業中的打孔有關。令人驚喜的是，Behzad與Modarres證明了廣義旅行商問題可以轉化為相同城市數量的標準旅行商問題 ，只是要改變距離矩陣。
- 優先順序旅行推銷員問題處理城市之間存在訪問次序的問題。
- 旅行購買者問題涉及購買一系列產品的購買者。他可以在若干城市購買這些產品，但價格會有不同，也不是所有城市都有售相同的商品。目標是在城市的子集中間找到一條路徑，使得總成本（旅行成本 + 購買成本）最小，並且能夠買到所有需求的商品。
TSP問題舉例
有一位商人，他想訪問中國的某些城市，要求：
1. 所走路程最近；
圖1.商人問題2. 每個城市只能訪問一次；
3. 從某城市出發，最後回到該城市。
如右圖所示：
假設從合肥出發，最後回到合肥。
問題域：X={北京，成都，廣州，上海}
目標函式：min f(x)=dist(合肥，city1) + ∑dist(cityi,cityj) + dist(cityj,合肥)
如下圖：
圖2.例題其他
另：TSP電信服務供應商；
另：tsp總懸浮顆粒物。
