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

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

此類問題中，經(jīng)典的還有 子集和問題; Hamilton回路問題;最大團(tuán)問題。

作為圖論問題

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

非對稱和對稱

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

相關(guān)問題

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

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

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

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

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

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

TSP問題舉例

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

1. 所走路程最近;

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

3. 從某城市出發(fā)，最后回到該城市。

如圖1所示：

假設(shè)從合肥出發(fā)，最后回到合肥。

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

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

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

想要了解更有關(guān)TSP的信息，請繼續(xù)關(guān)注中培偉業(yè)。