TSP問題及其應(yīng)用綜述

林沐霖　何茂森　朱俊明

摘 要 TSP是數(shù)學(xué)領(lǐng)域內(nèi)一道著名的難題之一，如何求解一直是學(xué)術(shù)界研究的熱點問題。本文首先闡述了TSP問題的基本概念，介紹了TSP問題的一般描述及數(shù)學(xué)模型，然后歸納了現(xiàn)有對TSP問題求解的較為有效的方法—蟻群算法和遺傳算法，最后闡述了TSP的應(yīng)用領(lǐng)域。

關(guān)鍵詞 TSP 遺傳算法 蟻群算法

中圖分類號：TP301.6 文獻標(biāo)識碼：A

1 TSP問題的基本概念

TSP（Traveling Salesman Problem）問題，可譯為旅行商問題，是數(shù)學(xué)領(lǐng)域中著名的組合優(yōu)化類難題之一。

1.1 TSP問題的描述

現(xiàn)有對TSP問題的標(biāo)準(zhǔn)描述為：已知有城市數(shù)量為，一位旅行商人從其中的某一個城市出發(fā)，途中需要經(jīng)過所有的城市，但經(jīng)過的次數(shù)有且僅有一次，最后再回到出發(fā)的城市，怎樣規(guī)劃路線才能使旅行商所走的路線最短。

1.2 TSP問題的數(shù)學(xué)模型

設(shè)城市集合為V={v1，v2，…，vA}，對城市的訪問順序為T={t1，t2，…，tA}，其中ti=V（i=1，…A），而且ti+1=t1，則問題的目標(biāo)函數(shù)如下：

意為目標(biāo)函數(shù)的最優(yōu)值為所有途徑城市之間的路徑和最短。

1.3 TSP問題的分類

從上述描述中可以看出TSP問題即是在若干城市或地點之間尋找一條回路，根據(jù)vi→vi+1與vi+1→vi的距離是否相當(dāng)，可以將TSP問題分為對稱TSP問題和非對稱TSP問題。

2 TSP問題的求解方法

TSP問題已經(jīng)被證明是一個NP-hard問題，即在P≠NP的假設(shè)下，找不到一個多項式時間算法來求解其最優(yōu)解。TSP問題很容易被描述清楚，但是卻較難找到合適的求解算法，自1932年TSP問題出現(xiàn)以來，已經(jīng)有諸多學(xué)者在研究相關(guān)領(lǐng)域的問題，但至今仍為找到有效的方法。

曾經(jīng)傳統(tǒng)的經(jīng)典優(yōu)化算法經(jīng)常被用來求解TSP問題的解，但是當(dāng)城市數(shù)量較大時，就難以快速找到最優(yōu)解。隨著人工智能的發(fā)展，出現(xiàn)了許多獨立于問題的獨立算法，如蟻群算法、粒子群算法、遺傳算法、魚群算法、狼群算法等等。這些算法通過模擬自然界的某些現(xiàn)象而得出求解復(fù)雜問題的新思路和新方法。在優(yōu)化領(lǐng)域，這類算法的由于其很好的收斂性和有效性而被廣泛使用。

2.1蟻群算法求解TSP問題

蟻群算法最初是通過對螞蟻群落的觀察，受蟻群行為特征啟發(fā)而得出的。螞蟻是一種群居昆蟲，在覓食、清理巢穴等活動中，彼此依賴、相互協(xié)作共同完成特定的任務(wù)。就個體來講，單個螞蟻的智力和體力是極其有限的，服務(wù)于整個群落的生存與發(fā)展；就群體來講，蟻群在行為上的分工協(xié)作、在完成任務(wù)過程中所體現(xiàn)的自組織特征等反應(yīng)出蟻群具有較高的智能和自我管理能力，具有很高層次組織性，這使得蟻群能夠完成一些復(fù)雜的任務(wù)。

蟻群的特點是并發(fā)性、魯棒性、正反饋性等。在蟻群算法求解問題的過程中，利用蟻群在問題空間中同時構(gòu)造問題的多個解體現(xiàn)了算法的并發(fā)性。蟻群不會因為單個螞蟻尋找到較差的解或者因為問題空間發(fā)生改變而使得算法喪失作用。這體現(xiàn)了魯棒性。在螞蟻構(gòu)造問題解的過程中，以蟻群覓食行為為例，會在經(jīng)過的解的路上釋放信息素，而解空間中活得信息素越多的路徑，對螞蟻的吸引力就越大，使更多的螞蟻經(jīng)過該路徑并進一步在上面釋放信息素，這體現(xiàn)了算法的正反饋性。

矯德強等人使用非線性尋優(yōu)算法增強蟻群算法的局部搜索能力，鄭旭峰等人使用K-means聚類算法提高蟻群算法精度等，改進了蟻群算法的收斂速度及容易陷入局部最優(yōu)解的問題，并將其應(yīng)用在TSP問題中。

2.2遺傳算法求解TSP問題

遺傳算法的概念是由Holland于1973年受生物進化論的啟發(fā)而首次提出的，它是一種通過模擬生物界自然選擇和遺傳機制的隨機搜索算法。

遺傳算法是一種比較通用的優(yōu)化算法，編碼技術(shù)和遺傳操作比較簡單，主要操作有選擇、交叉和變異。根據(jù)TSP的目的，只是求最短路徑，而傳統(tǒng)解法非常在意得到路徑的過程，遺傳算法直接將目標(biāo)指向距離最短，因此能較快地得到問題的答案。

3 TSP問題的應(yīng)用領(lǐng)域

3.1 TSP在物流配送中的應(yīng)用

物流配送是指從貨運總公司出發(fā)，將貨物沿途送到指定的各個分公司，最后返回總公司的配送路線。此類問題是在一個平面區(qū)域內(nèi)對所有點的遍歷問題，即選擇一條閉合線路可以覆蓋所有點，并使得路線在某種條件下達到最優(yōu)，符合TSP問題的數(shù)學(xué)模式，可以將其應(yīng)用于此類問題中。

3.2 TSP在機器人路徑規(guī)劃中的應(yīng)用

機器人的路徑規(guī)劃問題主要是找到一條從出發(fā)點到目標(biāo)點的最佳或次佳路徑，或是在盡可能短的時間內(nèi)游歷盡可能多的目標(biāo)點，類似于傳統(tǒng)的TSP問題，因此同樣可以采用TSP問題的方法進行求解。

參考文獻

[1] Garey，M.R&D.S.Johnson.Computers and Intractability： A Guide to the Theory of NP-Completeness[M]. San Francisco： Freeman W H， 1979.

[2] 許能闖.基于改進蟻群算法的TSP問題研究[J].軟件導(dǎo)刊， 2018（02）.

[3] 矯德強，常淮陽.一種改進蟻群算法在TSP問題上的應(yīng)用[J].科技與創(chuàng)新，2018（01）：145-146.

[4] 鄭旭峰，周健勇.K-means聚類蟻群優(yōu)化算法求解大型TSP問題[J].物流科技，2018（02）：37-40