賴志柱，戈冬梅，張云艷（1.貴州工程應(yīng)用技術(shù)學(xué)院a.理學(xué)院；b.生態(tài)工程學(xué)院，貴州畢節(jié)551700）

?

求解TSP問題的改進(jìn)最鄰近法

賴志柱1a，戈冬梅1b，張云艷1a
（1.貴州工程應(yīng)用技術(shù)學(xué)院a.理學(xué)院；b.生態(tài)工程學(xué)院，貴州畢節(jié)551700）

摘要：考察TSP問題的線路構(gòu)造，建立TSP問題的數(shù)學(xué)模型，分析了最鄰近法的基本思想及不足，通過改進(jìn)最鄰近法構(gòu)造線路的方向及將所有城市均作為一次線路構(gòu)造的起點，提出了雙向最鄰近法、完全最鄰近法和完全雙向最鄰近法三種改進(jìn)方法，算例表明改進(jìn)后的方法比最鄰近法能獲得更多的不同線路及更優(yōu)的線路。

關(guān)鍵詞：TSP問題；最鄰近法；線路

1引言

旅行商問題（Traveling Salesman Problem,TSP），也稱為旅行推銷員問題或貨郎擔(dān)問題，是運(yùn)籌學(xué)、圖論以及組合優(yōu)化中的著名難題，由于其應(yīng)用的廣泛性，引起了人們的極大的興趣。TSP問題的解決方法可以直接或較容易地應(yīng)用于解決類似的問題，如交通車輛的巡回線路問題、民航機(jī)組人員的輪班安排問題、教師任課班級負(fù)荷分配問題、裝配線進(jìn)度問題等。該問題的求解算法主要分為兩類：與問題特征相關(guān)的啟發(fā)式搜索算法[1][2]（如動態(tài)規(guī)劃法、分支定界法等）以及獨立于問題的智能優(yōu)化算法[3][4]（如遺傳算法、模擬退火算法等）。通常，將TSP問題的啟發(fā)式方法分為線路構(gòu)造法、線路改進(jìn)法和綜合法三類[5]，最鄰近法是線路構(gòu)造法中最簡單的一種，但該方法對于城市規(guī)模較大的TSP問題求解效果較差，本文擬就最鄰近法做些改進(jìn)，以期改進(jìn)后的方法在線路構(gòu)造中能給出更優(yōu)的結(jié)果以及對規(guī)模較大的TSP問題也有較好的效果。

2 TSP問題的描述及數(shù)學(xué)模型

3最鄰近法的改進(jìn)

3.1最鄰近法簡述及分析

求解TSP問題的最鄰近法（NearestNeighbor，NN）的基本思想可以簡述為：給定源點作為線路的起點，尋找并加入距離上一次加入線路中頂點（城市）最近的頂點（城市），依次重復(fù)直到所有頂點（城市）已經(jīng)加入線路，最后將源點加入到線路末尾即可。

顯然該方法的本質(zhì)是貪心策略（以距離上一次加入的頂點最近的點為策略）在線路中的具體實現(xiàn)，由于貪心算法在復(fù)雜問題中未必能得到最優(yōu)解，因而該方法通常不能得到問題真正的最優(yōu)路徑，但勝在直觀和速度較快。在使用最鄰近法尋找TSP的線路時，也存在一些疑難或問題，例如，最鄰近法在選定哪一個城市作為源點上并沒有標(biāo)準(zhǔn)；另一方面，當(dāng)線路尋找過程中如果有兩條子路徑長度一樣，如何選擇新的子路徑，最鄰近法也沒有給出明確的做法。在實踐中，筆者發(fā)現(xiàn)選擇源點不同，最鄰近法獲得的最優(yōu)線路也有所不同；有時即使源點選擇相同，但尋路中間如果有長度相同的子路徑，此時選擇的方式不同也會有差異。下面以一個例子[5]說明，該問題共有8個城市，具體數(shù)據(jù)如表1。

表1　8個城市間的距離數(shù)據(jù)

文獻(xiàn)利用最鄰近法得到的線路為1-3-7-8-6-2-4-5-1，線路總長度為62。分析最鄰近法獲得的線路，當(dāng)將城市1和3加入線路后，距離城市3最近的城市有兩個（4和7），如果此時不選擇城市7而選擇城市4加入線路中，則可得到另一條線路：1-3-4-5-7-8-6-2-1，總長度為54。若將城市2作為源點，則可得到兩條線路：（1）線路1長度為66，表示為2-6-7-8-3-1-4-5-2；（2）線路2長度為61，表示為2-6-8-7-3-1-4-5-2。

3.2改進(jìn)1：雙向最鄰近法

這種改進(jìn)是將最鄰近法中尋找下一個城市的單一方向變化為兩個方向同時尋找，具體步驟如下：

算法：雙向最鄰近法（Both-side NearestNeighbor，BSNN）

Step 1：選定一個城市作為源點，將該點加入線路中，以RightC表示右前方剛加入的城市，以LeftC表示左后方剛加入的城市，此時RightC=LeftC=源點。

Step 2：查找還未加入線路且距離RightC最近的一個城市RC，更新RightC=RC及線路信息；查找還未加入線路且距離LeftC最近的一個城市LC，更新LeftC=LC及線路信息。

Step 3：檢查剩下的還未加入線路的城市個數(shù)，若剩下的城市個數(shù)大于2，轉(zhuǎn)Step 2；若剩下一個城市，則直接將剩下的城市作為RightC加入線路；若還剩下兩個城市（記為C1和C2），若C1比C2距離RightC更近，則賦值RightC=C1及LeftC=C2，否則RightC=C2，LeftC=C1。

Step 4：將RightC與LeftC之間的子路徑加入線路，輸出獲得的線路。

3.3改進(jìn)2：完全最鄰近法

由2.1的分析可知，最鄰近法獲得的結(jié)果總是差強(qiáng)人意，為得到較優(yōu)的結(jié)果，對最鄰近法改進(jìn)得到完全最鄰近法（Complete NearestNeighbor，CNN），具體做法為：依次對每一個頂點（城市）執(zhí)行最鄰近法搜索，匯總所有獲得的TSP線路，將重復(fù)的線路刪除，最后對剩下的線路依據(jù)長度進(jìn)行排序。

3.4改進(jìn)3：完全雙向最鄰近法

有時利用雙向最鄰近法獲得的TSP線路效果不是很理想，仿照完全最鄰近法的做法，對雙向最鄰近法改進(jìn)得到完全雙向最鄰近法（Complete Both-side NearestNeighbor，CBSNN），具體做法為：依次對每一個頂點（城市）執(zhí)行雙向最鄰近法搜索，匯總所有獲得的TSP線路，將重復(fù)的線路刪除，最后對剩下的線路依據(jù)長度進(jìn)行排序。

4算例及結(jié)果

為檢驗最鄰近法及其三種改進(jìn)的效果，分別基于MATLAB 7.1編制程序，首先以表1中8個城市的數(shù)據(jù)運(yùn)行，結(jié)果如表2。由于最鄰近法的結(jié)果可從完全最鄰近法的結(jié)果中查找，而雙向最鄰近法的結(jié)果也可從完全雙向最鄰近法的結(jié)果中查找，故表2僅列出了完全最鄰近法及完全雙邊最鄰近法的結(jié)果；另外，為便于線路對比，所有線路最后都轉(zhuǎn)化為從頂點（城市）1出發(fā)，最后都回到頂點（城市）1。從表2可看出，改進(jìn)后的三種方法，尤其是完全最鄰近法及完全雙邊最鄰近法，不比原來的最鄰近法效果差，而且總是能得到TSP問題的眾多不同線路，從而可在后續(xù)的研究或?qū)嵺`中使用其它算法（如遺傳算法、蟻群算法等智能算法進(jìn)一步優(yōu)化獲得最佳解）。另外，由于完全雙向最鄰近法使用的兩個方向同時尋找，可以獲得比完全最鄰近法更多的不同線路，從而在使用智能算法后續(xù)優(yōu)化中更具優(yōu)勢。

表2　完全最鄰近法及完全雙邊最鄰近法的結(jié)果

其次，以TSP問題中經(jīng)典的kroal100數(shù)據(jù)（含100個城市）為例進(jìn)行運(yùn)算，四種算法的結(jié)果如表3所示。表3中，最鄰近法NN和雙邊最鄰近法BSNN僅給出了原始起點為頂點（城市）1時的結(jié)果，從結(jié)果可以看出BSNN的效果明顯優(yōu)于NN（25413.38<26856.39）；而CNN總共獲得97條不同的線路，CBSNN總共獲得99條不同的線路，限于篇幅都僅給出前8條較短的不同線路，從結(jié)果可看出，CBSNN的效果明顯優(yōu)于CNN（24510.75<24698）。詳細(xì)對比CNN和CBSNN的前8條較短的不同線路，CBSNN的前3條較短線路都比CNN獲得最短路更短，且CNN獲得第二短的線路都比CBSNN的第8短線路還長。

表3　四種算法求解kroal100的部分結(jié)果

5結(jié)論與討論

最鄰近法是構(gòu)造TSP線路的一種簡單方法，其效果差強(qiáng)人意，尤其是對于規(guī)模較大的TSP問題，如kroal100。文章提出的雙向最鄰近法從兩個方向同時構(gòu)造線路，其效果明顯優(yōu)于最鄰近法。當(dāng)對所有頂點（城市）執(zhí)行最鄰近法及雙向最鄰近法（即文章提出的CNN和CBSNN）時，既可以獲得眾多的不同線路，也能獲得比最鄰近法和雙向最鄰近法都較好的線路，而且可以將獲得眾多的不同線路作為后續(xù)智能算法繼續(xù)優(yōu)化時的初始群體，這樣既可以彌補(bǔ)隨機(jī)生成線路的不足，又可以減少智能算法中群體規(guī)模的參數(shù)設(shè)置。

參考文獻(xiàn)：

[1]楊忠程,徐新黎,葉雙挺.基于組合拆分策略求解TSP的動態(tài)規(guī)劃算法[J].計算機(jī)工程,2012(13):185-187,191.

[2]余文飛,鄭鵬.分枝限界法的實現(xiàn)及改進(jìn)方案[J].計算機(jī)應(yīng)用與軟件,2003(12):99-101.

[3]王劍文,戴光明,謝柏橋,等.求解TSP問題算法綜述[J].計算機(jī)工程與科學(xué),2008(2):72-74,155.

[4]潘正君,康立山,陳毓屏.演化計算[M].北京:清華大學(xué)出版社,1997.

[5]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社,2001:6.

（責(zé)編：郎禹責(zé)校：明茂修）

ImprovedNearestNeighborMethodforSolvingTSP

LAIZhi-zhu1a,GEDong-mei1b,ZHANGYun-yan1a
(1a.SchoolofScience,1b.SchoolofEcologicalEngineering,GuizhouUniversityofEngineeringScience,Bijie,Guizhou551700,China)

Abstract:TodesignthepathofTSP,weestablishthemathematicalmodelandanalyzethenearestneigh?bormethod,andthenproposethreeimprovedmethods,whichcalledboth-sidenearestneighbormethod,com?pletenearestneighbormethodandcompleteboth-sidenearestneighbormethod.Atlast,someexamplesare givingandtheresultsshowthattheimprovedmethodsarebetterthanthenearestneighbormethod.

Keywords:TSPProblem;NearestNeighborMethod;Path

作者簡介：賴志柱（1980-），男，江西贛州人，貴州工程應(yīng)用技術(shù)學(xué)院理學(xué)院副教授。研究方向：智能算法及其應(yīng)用、多式聯(lián)運(yùn)。

基金項目：貴州省科技廳、畢節(jié)市科技局、畢節(jié)學(xué)院科技聯(lián)合基金項目“百里杜鵑旅游開發(fā)與生態(tài)環(huán)境協(xié)調(diào)機(jī)制模擬”，項目編號：黔科合J字LKB[2012]23號；貴州省科技廳、畢節(jié)市科技局、畢節(jié)學(xué)院科技聯(lián)合基金項目“對兩類橢圓方程解的理論研究”，項目編號：黔科合J字LKB[2013]24號；貴州省科技廳、畢節(jié)市科技局、貴州工程應(yīng)用技術(shù)學(xué)院科技聯(lián)合基金項目“車輛調(diào)度運(yùn)輸多目標(biāo)模型及智能算法優(yōu)化研究”，項目編號：黔科合LH字[2014]7532號。

收稿日期：2015-09-25

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：A

文章編號：2096-0239（2016）01-0139-04