宋海聲，呂耕耕，劉岸果

　?。ㄎ鞅睅煼洞髮W(xué) 物理與電子工程學(xué)院，甘肅 蘭州 730070）

       摘要：提出了一種新算法，有效地減少了最近鄰域法和貪婪算法在構(gòu)建旅行商問題可行解過程中引入不合理長邊的問題。該算法先借助一種由偽凸包算子所得到的分層模型對旅行商問題中的城市分布進(jìn)行分析，之后通過將分層模型中相對外層的點(diǎn)逐個(gè)添加到內(nèi)層的規(guī)則得到可行解。借助仿真實(shí)驗(yàn)求解TSPLIB標(biāo)準(zhǔn)庫中的40實(shí)例，并與最近鄰域法和貪婪算法進(jìn)行對比，結(jié)果表明分層融合算法具有更高的精度，其平均求解質(zhì)量達(dá)到8.47%。

　　關(guān)鍵詞：旅行商問題；偽凸包；分層模型；分層融合算法

　　中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.06.005

　　引用格式：宋海聲，呂耕耕，劉岸果. 一種基于分層模型的TSP構(gòu)建算法［J］.微型機(jī)與應(yīng)用，2017,36（6）：13-15，21.

0引言

　　*基金項(xiàng)目：甘肅省自然科學(xué)基金（1606RJZA065）旅行商問題（Traveling Salesman Problem, TSP）是在1954年由美國學(xué)者Dantzig［1］提出的，是已被證明的NPHard組合優(yōu)化問題［2］。由于其在郵遞員投遞路線選擇、生產(chǎn)作業(yè)排序VLSI芯片設(shè)計(jì)、電路板鉆孔、機(jī)器人控制、X光設(shè)備定位、電子地圖和計(jì)算機(jī)網(wǎng)絡(luò)等眾多領(lǐng)域有廣泛應(yīng)用價(jià)值，因此近些年來產(chǎn)生了大量的關(guān)于TSP的文獻(xiàn)。其中大多數(shù)文獻(xiàn)主要集中于啟發(fā)式算法的研究，可以分為構(gòu)建型和以構(gòu)建型為基礎(chǔ)的改進(jìn)型兩類。比較常見的改進(jìn)型算法有遺傳算法［3］、蟻群算法［4］、粒子群算法［5］、免疫算法［6］、模擬退火算法［7］、禁忌搜索算法［8］等，其求解質(zhì)量高，速度比較慢；而構(gòu)建型算法具有簡潔、求解速度快的特點(diǎn)。經(jīng)典的構(gòu)建算法有最近鄰域法（the Nearest Neighborhood Algorithm, NN）［9］、貪婪算法（Greedy Algorithm, GA）［10］、插入法［9］等。

　　由于最近鄰域法、貪婪算法和插入算法的構(gòu)建結(jié)果中均含有不合理的長邊，因此本文在繼承最近鄰域法、貪婪算法的思想后，通過建立分層模型來規(guī)避這一問題，提出了分層融合算法（Hierarchical Fusion Algorithm, HFA）。通過實(shí)驗(yàn)求解TSPLIB標(biāo)準(zhǔn)庫中的40實(shí)例并與NN和GA算法進(jìn)行對比，結(jié)果表明本文算法求解TSP具有更高的精度。

1TSP的描述

　　TSP可以描述為：在目標(biāo)城市個(gè)數(shù)和任意兩城市之間距離都已知的情況下，求解一條遍歷所有城市一次且僅一次并返回到起點(diǎn)城市的最短線路。該問題可以用如下的數(shù)學(xué)模型描述：

　　設(shè)N表示城市個(gè)數(shù)，D表示距離矩陣，dij表示兩城市間的距離，Inf為一足夠大的正數(shù),i，j為下標(biāo)表示城市，Tour表示線路的集合,Tp(l)表示線路Tp中的第l個(gè)城市，Len(Tp)為線路Tp總長度，那么有：

　　顯然，使得Len(Tp)取得最小值的線路Tp就是TSP的最優(yōu)解。根據(jù)不同的劃分標(biāo)準(zhǔn)TSP大致可以分為三類：

　?。?）按距離矩陣是否為對稱矩陣，分為對稱TSP和非對稱TSP；

　　（2）按任意3個(gè)城市間距離值是否滿足三角不等式，分為三角不等式TSP和非三角不等式TSP；

　?。?）按城市的坐標(biāo)位置是否完全符合歐幾里得平面規(guī)則（兩城市之間的距離可以通過坐標(biāo)計(jì)算得出），分為歐幾里得TSP和非歐幾里得TSP。本文在未加聲明時(shí)的TSP均為歐幾里得TSP。

2分層融合算法

　　2.1分層模型

　　分層模型是指將問題的處理過程分解為多個(gè)具有結(jié)構(gòu)相似性或功能獨(dú)立性的過程。建立分層模型可以讓問題的描述變得簡單，并使得問題的求解過程更具條理性。本文針對TSP建立分層模型并提出以下假設(shè)：

　　（1）使用坐標(biāo)點(diǎn)表示城市的位置，且所有的城市都分布在二維平面上；

　?。?）不存在具有相同坐標(biāo)的兩個(gè)點(diǎn)，若坐標(biāo)相同則按一個(gè)點(diǎn)處理；

　?。?）任意一個(gè)點(diǎn)，不能同時(shí)出現(xiàn)在兩個(gè)不同的層中；

　　（4）各個(gè)層必須采用相同的方式得到。

　　2.2偽凸包算子

　　本文采用偽凸包算子得到的偽凸包結(jié)構(gòu)進(jìn)行分層模型的建立，其步驟如下：

　　（1）找出剩余城市的坐標(biāo)矩陣tempX和剩余城市的個(gè)數(shù)ccity，按照剩余城市的橫坐標(biāo)從小到大的排序得到剩余城市在橫坐標(biāo)方向的排序xsq；

　　(2)當(dāng)ccity<4時(shí)，返回xsq和ccity,否則，執(zhí)行步驟(3)；

　　(3)按照剩余城市的縱坐標(biāo)從小到大地排序得到剩余城市在縱坐標(biāo)方向的排序ysq并取得端點(diǎn)西west=xsq(1)，東east=xsq(ccity)，南south=ysq(1)，北north=ysq(ccity)；

　?。?）初始化層layer=zero(1,N),層中城市個(gè)數(shù)cl=0；

　　(5)從西到北取得縱坐標(biāo)增大的點(diǎn)并添加到layer中，更新cl；

　　(6)從東到北取得縱坐標(biāo)增大的點(diǎn)并反向添加到layer中，更新cl；

　　(7)從東到南添加縱坐標(biāo)減小且未曾添加到layer中的點(diǎn)到layer中，更新cl；

　　(8)從西到南取得縱坐標(biāo)增大且未曾添加到layer中的點(diǎn)并反向添加到layer中，更新cl，返回layer和cl。

　　圖1是TSPLIB標(biāo)準(zhǔn)庫中att48城市的分布圖。圖2為分層模型所得到的att48城市分層圖，其中每一條多段線表示一個(gè)層。

　　2.3分層融合算法求解TSP

　　本文提出的分層融合算法建立在分層模型基礎(chǔ)之上，采用偽凸包算子得到TSP的分層模型，之后將分層模型中相對外層的城市加入到相對內(nèi)層的層中完成融合。其中融合過程只限于兩層之間并且是從最內(nèi)層向最外層進(jìn)行的。分層融合算法求解TSP的過程可以分為兩個(gè)階段：第一階段使用偽凸包算子進(jìn)行分層模型的構(gòu)建；第二階段將得到的分層模型按照融合規(guī)則進(jìn)行融合求出構(gòu)造解。

　　第一階段：得到分層模型。

　　(1)初始化城市個(gè)數(shù)N，剩余城市的集合CITY=1:N，剩余城市個(gè)數(shù)ccity=N，城市坐標(biāo)矩陣X。

　　(2)如果ccity>0，創(chuàng)建層記錄矩陣xLayers=zeros(ccity,N)并令層個(gè)數(shù)clayers=0，跳到步驟(3)；否則，提示錯(cuò)誤。

　　(3)當(dāng)ccity>0時(shí)，重復(fù)執(zhí)行步驟(4)；否則返回分層模型矩陣Layers=xLayers(1:clayers,:)。

　?。?）采用偽凸包算子得到一層，更新剩余城市的集合CITY，ccity，clayers++。

　　第二階段：對分層模型進(jìn)行融合。

　?。?）初始化得到第一階段所生成的分層模型矩陣Layers和層個(gè)數(shù)clayers。

　?。?）當(dāng)clayers>1時(shí)；重復(fù)執(zhí)行步驟（3）；否則，返回Layers(1,:)。

　　（3）分取得相對內(nèi)層inlayer=Layers(clayer,:)和相對外層outlayer=Layers(clayer-1,:)，利用融合規(guī)則算子將兩層融合并將得到的結(jié)果賦給Layers(clayer-1,:)。

　　其中步驟（3）中所用到的融合規(guī)則算子詳細(xì)步驟如下：

　?、偃〉孟鄬?nèi)層inlayer、相對外層outlayer、outlayer中城市的個(gè)數(shù)coutlayer以及inlayer中城市的個(gè)數(shù)cinlayer。

　?、诋?dāng)coutlayer>0時(shí)，重復(fù)執(zhí)行步驟②；否則，返回inlayer。

　?、垭S機(jī)從outlayer中選擇一個(gè)點(diǎn)作為將要添加的點(diǎn)addpoint。

　?、墚?dāng)cinlayer<3時(shí)，neighbourhood=inlayer;否則，從inlayer中選擇2個(gè)距離addpoint最近的點(diǎn)的集合作為neighbourhood。

　?、萦?jì)算addpoint分別插入到neighbourhood中兩點(diǎn)兩側(cè)時(shí)的距離增量，將addpoint插入到距離增量最小的位置，coutlayer--，更新inlayer。

3算法測試

　　實(shí)驗(yàn)求解了TSPLIB標(biāo)準(zhǔn)庫中的40個(gè)實(shí)例，通過比較NN、GA與HFA三種算法的求解質(zhì)量，對算法的性能進(jìn)行了測試。實(shí)驗(yàn)平臺(tái)為MATLAB 7.10.0（R2010a），CPU為AMD A83500M，內(nèi)存為2.0 GB，主頻為1.5 GHz。三種算法求解TSP實(shí)例的結(jié)果對比表如表1所示。其中實(shí)例名稱指的是TSP的名稱和該問題所包含的城市個(gè)數(shù)；最優(yōu)路徑長度指的是實(shí)例已知的最優(yōu)路徑長度；平均解和最優(yōu)解分別指的是平均求解質(zhì)量和最優(yōu)求解質(zhì)量，計(jì)算方法為：（解得路徑長度/最優(yōu)路徑長度-1）*100%。需要注意的是，GA為確定算法，每次求出的結(jié)果都相同，所以只求解一次；而NN和HFA為不確定算法，所以進(jìn)行了多次實(shí)驗(yàn)。當(dāng)城市個(gè)數(shù)n≤100時(shí)，進(jìn)行n次求解；當(dāng)100<n≤1 000時(shí)，進(jìn)行100次求解；當(dāng)n>1 000時(shí)，進(jìn)行50次求解。

　　由表1可知，在求解質(zhì)量上NN的平均求解質(zhì)量最差，為26.02%；NN的最優(yōu)求解質(zhì)量和GA的求解質(zhì)量相當(dāng)，為18%左右；本文提出的分層融合算法求解質(zhì)量明顯優(yōu)于NN和GA。其平均求解質(zhì)量和平均最優(yōu)求解質(zhì)量的均值分別為8.47%和4.99%，說明算法的魯棒性和求解質(zhì)量同時(shí)得到提高，相對于GR+MVODM的性能更好［11］。

4結(jié)論

　　本文針對旅行商問題提出了分層融合算法，借助分層模型從整體入手有效避免了經(jīng)典構(gòu)造算法后期引入長邊的問題，從新的方向給出了旅行商問題構(gòu)造解方式。該算法的優(yōu)點(diǎn)在于求解質(zhì)量高，建立了可重復(fù)使用的分層模型；不足之處在于偽凸包算子構(gòu)建的層模型過于單一，各層之間進(jìn)行融合時(shí)鄰域制約了構(gòu)造解的多樣性。

參考文獻(xiàn)

　　［1］ DANTZIG G, JOHNSON S. Solution of a largescale travelingsalesman problem［J］. Operations Research, 1954, 2(4):393410.

　?。?］ GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NPcompleteness［M］.W.H. Freeman and Company， 1979.