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

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

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

作為圖論問(wèn)題

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

非對(duì)稱和對(duì)稱

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

相關(guān)問(wèn)題

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

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

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

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

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

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

TSP問(wèn)題舉例

有一位商人，他想訪問(wèn)中國(guó)的某些城市，要求：

1. 所走路程最近;

2. 每個(gè)城市只能訪問(wèn)一次;

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

如圖1所示：

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

問(wèn)題域：X={北京，成都，廣州，上海}

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

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

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