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

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

?

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

賴志柱1a，戈冬梅1b，張?jiān)破G1a
（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)造的起點(diǎn)，提出了雙向最鄰近法、完全最鄰近法和完全雙向最鄰近法三種改進(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ī)組人員的輪班安排問題、教師任課班級(jí)負(fù)荷分配問題、裝配線進(jìn)度問題等。該問題的求解算法主要分為兩類：與問題特征相關(guān)的啟發(fā)式搜索算法[1][2]（如動(dòng)態(tài)規(guī)劃法、分支定界法等）以及獨(dú)立于問題的智能優(yōu)化算法[3][4]（如遺傳算法、模擬退火算法等）。通常，將TSP問題的啟發(fā)式方法分為線路構(gòu)造法、線路改進(jìn)法和綜合法三類[5]，最鄰近法是線路構(gòu)造法中最簡單的一種，但該方法對(duì)于城市規(guī)模較大的TSP問題求解效果較差，本文擬就最鄰近法做些改進(jìn)，以期改進(jìn)后的方法在線路構(gòu)造中能給出更優(yōu)的結(jié)果以及對(duì)規(guī)模較大的TSP問題也有較好的效果。

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

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

3.1最鄰近法簡述及分析

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

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

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

文獻(xiàn)利用最鄰近法得到的線路為1-3-7-8-6-2-4-5-1，線路總長度為62。分析最鄰近法獲得的線路，當(dāng)將城市1和3加入線路后，距離城市3最近的城市有兩個(gè)（4和7），如果此時(shí)不選擇城市7而選擇城市4加入線路中，則可得到另一條線路：1-3-4-5-7-8-6-2-1，總長度為54。若將城市2作為源點(diǎn)，則可得到兩條線路：（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)是將最鄰近法中尋找下一個(gè)城市的單一方向變化為兩個(gè)方向同時(shí)尋找，具體步驟如下：

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

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

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

Step 3：檢查剩下的還未加入線路的城市個(gè)數(shù)，若剩下的城市個(gè)數(shù)大于2，轉(zhuǎn)Step 2；若剩下一個(gè)城市，則直接將剩下的城市作為RightC加入線路；若還剩下兩個(gè)城市（記為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é)果，對(duì)最鄰近法改進(jìn)得到完全最鄰近法（Complete NearestNeighbor，CNN），具體做法為：依次對(duì)每一個(gè)頂點(diǎn)（城市）執(zhí)行最鄰近法搜索，匯總所有獲得的TSP線路，將重復(fù)的線路刪除，最后對(duì)剩下的線路依據(jù)長度進(jìn)行排序。

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

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

4算例及結(jié)果

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

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

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

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

5結(jié)論與討論

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

參考文獻(xiàn)：

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

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

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

[4]潘正君,康立山,陳毓屏.演化計(jì)算[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)。

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

收稿日期：2015-09-25

中圖分類號(hào)：TP301.6

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

文章編號(hào)：2096-0239（2016）01-0139-04