李香云，葛 華

(安徽科技學院 計算機系，安徽 鳳陽233100)

在郵件運輸車輛路徑方面主要有三個問題[1]：帶運力限制的車輛路徑問題CVRP，客戶可分的車輛路徑問題SDVRP和帶時間窗的客戶可分的車輛路徑問題SDVRPTW，本文主要利用螞蟻算法來求解第二類車輛路徑問題[2-4].闡述了基本螞蟻算法的原理、特點、組成部分，以及如何用于求解車輛路徑問題.

1 蟻群算法簡介

蟻群算法是受到自然界中的蟻群尋找食物的行為的啟發(fā)而提出的.最先提出的蟻群算法被稱為螞蟻系統(tǒng)(Ant System，AS)[5]，它是Dorigo，Colorni，Maniezzo于1992年在意大利的米蘭理工學院合作研究組合優(yōu)化問題計算機智能解決方法時的研究成果.1992年，Dorigo在他的博士論文中提到了(Ant System，AS)蟻群系統(tǒng).根據(jù)信息素更新方式的不同，給出了三種算法模型，分別稱為蟻群圈算法(ant-cycle system)、蟻群數(shù)量算法(ant-quantity system)和蟻群密度算法(ant-density system).

1995年Gambardella和Dorigo提出了Ant-Q算法.該算法建立了AS與Q-learning的聯(lián)系.模擬表明Ant-Q是一個非常有效的算法.

1996年，Gambardella和Dorigo又提出了一種修正的蟻群算法，蟻群系統(tǒng)(ant colony system，ACS)[6].ACS與前面的AS主要區(qū)別在于：螞蟻在搜索最優(yōu)路徑的過程中只能使用局部信息，即采用局部信息對信息素濃度進行調(diào)整的局部更新規(guī)則(Local Updating Rule)；在所有進行尋優(yōu)的螞蟻結(jié)束路徑尋找后，信息素的濃度會再一次調(diào)整，這次采用的是全局信息，而且只對發(fā)現(xiàn)的最好路徑上的信息素濃度進行加強；有一個狀態(tài)傳遞機制，用于指導螞蟻最初的尋優(yōu)過程，并能積累問題目前狀態(tài).局部更新的主要思想，在于避免產(chǎn)生一條過于強勢的路徑，吸引所有的螞蟻走上該路徑，如此便無法進行適當?shù)奶剿餍侣窂降膭幼?，從而陷入局部最?yōu).局部更新規(guī)則在所有螞蟻完成一次轉(zhuǎn)移后執(zhí)行，執(zhí)行公式為：

τij=(1-ρ)*τij+*Δτij.

采用這公式的ACS被稱為Ant-Qsystem.此后Stutzle和Hoos提出了最大最小蟻群系統(tǒng)(MAX-MINAntSystem，MMAS)[7]這兩種擴展的蟻群算法都被用于解決對稱旅行商問題(STSP)以及非對稱型的旅行商問題(ATSP)，并取得了比較滿意的結(jié)果.

蟻群算法被應用到各種領域中并取得了一定得成功，如蟻群優(yōu)化亞啟發(fā)式算法(AntColonyOptimizationmeta-heuristicACO)[8].蟻群算法在車輛路徑中得第一次嘗試是在1997，由學者Bullnheimer來實現(xiàn)，它建立了蟻群算法應用于經(jīng)典車輛路徑問題的基本框架，并隨后進行了改進，接著Gambardella將蟻群算法應用到求解帶時間窗的車輛路徑問題中.提出了多蟻群蟻群算法(MACS)[9]解決VRPTW的方案.

2 基本原理與數(shù)學模型和算法流程

螞蟻覓食時，會在所經(jīng)過路線上留下一種稱為信息素(pherornone)的物質(zhì)，以此來標識路線，其它螞蟻可以并且習慣追蹤此信息素爬行.因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象.由于每只螞蟻每經(jīng)過一次都要釋放信息素，那么某一路徑上走過的螞蟻越多，該路徑上的信息素濃度就越高，則后來者選擇該路徑的概率就越大.這樣整個蟻群就由開始的多路線爬行逐漸集中到最短的路線上爬行，從而使路線得到優(yōu)化選擇[10-12].

在算法的初始時刻τij(t)=c(c為常數(shù))，螞蟻獨立的選擇下一個節(jié)點，在t時刻位于節(jié)點i的螞蟻k，利用路徑(i，j)上的信息素濃度τij(t)選擇下一個節(jié)點，則下一個節(jié)點j∈Ni的轉(zhuǎn)移概率pijk(t)可表示為：

(1)

τij(t)=(1-ρ)*τij(t)+ρ*Δτij(t)

(2)

(3)

(2)與(3)式中，ρ為信息素的揮發(fā)系數(shù)(0<ρ<1)，則(1-ρ)為信息素的持久系數(shù)；τij(t)表示完成一次循環(huán)后路徑(i，j)上的信息素增量；表示第k只螞蟻在本次循環(huán)中留在路徑(i，j)上的信息量，一般來說，最基本的取值形式為：

(4)

(4)式中，Q表示螞蟻走一圈釋放的信息素強度，它在一定程度上影響算法的收斂速度，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度.

3 算法流程

在初始化的時候，m個螞蟻被放置在郵車出發(fā)地點處，賦予每條邊上的信息素濃度為τij(0)=c(c為常數(shù))，第k個螞蟻對應tabu矩陣的第k行第一個元素賦值為它所在的城市，tabu矩陣為m行n列.當所有螞蟻完成了一次完整的尋徑過程后，計算Δτijk，并且更新每條邊上的信息素濃度.然后開始新一輪的循環(huán).當循環(huán)的次數(shù)達到事先定義好的NCmax時或者所有的螞蟻都選擇了同一種路徑方式時，整個程序終止[13].

(1)Ant循環(huán)程序的偽代碼如下:

①初始化:

SetNC=0，每條邊上的τij(0)=c，并且Δτkij，放置m個螞蟻島有車調(diào)度中心0.

②fork=1tomdo

把第k個螞蟻的初始信息放置到tabuk(k，l)中.

③重復直到tabulist滿為止

④Fork=1tomdo

⑤Fork=1tomdo

對每一條邊計算，更新邊上的信息濃度

Setτij(t)=(1-ρ)*τij(t)+*Δτij(t)

SetNC=NC+1

⑥While(NC

then清空tabu陣

Goto②

Else

打印出最短路徑.

終止整個程序.

(2)蟻群算法的基本結(jié)構(gòu)如圖1所示.

圖1 算法基本結(jié)構(gòu)圖

4 改進的蟻群算法解決郵車調(diào)度和路徑問題[14]

4.1 郵車的調(diào)度與路徑問題

本文針對的車輛調(diào)度問題有如下的要求：

(1)每個需求點的貨物可以有一輛或多輛車運送.(2)每輛車從配送中心出發(fā)，最后回到配送中心.(3)每輛車一次配送的客戶貨物總量小于等于車的最大運載量.(4)假設每輛車的類型相同，且容量也是相同的.

4.2 算法的實現(xiàn)

在原有的算法的基礎上，又添加了一個掃描函數(shù)sweep()，對要服務的點進行了一次逆時針的掃描，統(tǒng)計出了所有的需求點.并根據(jù)所有點的極坐標角度的大小進行了排序，以便后來對不同的郵車分別調(diào)度改進的算法尋找一條它所服務的點的最優(yōu)路徑.具體的算法步驟如下：Step1：對蟻群算法的相關(guān)參數(shù)進行賦值，如：信息素相對重要程度參數(shù)α、啟發(fā)式信息素相對重要程度參數(shù)β、信息素的揮發(fā)度參數(shù)ρ和迭代次數(shù)NCmax.Step2：調(diào)用函數(shù)讀入所要服務的需求點，并對這些點進行掃描和排序.Step3：根據(jù)每輛車的容量和需求點的需求大小，按照需求點排序的順序給車輛裝貨，直到車裝滿為止.并記下各輛車所服務的點，統(tǒng)計需求車的總數(shù)carnumber.Step4：對每輛車所服務的點分別調(diào)用改進的蟻群算法，求出各輛車的最優(yōu)路徑及其路徑的長度.Step5：統(tǒng)計出總的路徑長度.Step6：輸出各輛車的最優(yōu)路徑及其長度和路徑總長.

5 算法應用實例與分析

在原有蟻群算法的基礎上添加sweep()函數(shù)，以車輛調(diào)度中心為原點建立坐標系，計算所有客戶需求點的極坐標角度的大小，并存于數(shù)組angle0value[i]中.函數(shù)sortarrange()主要在sweep()函數(shù)的結(jié)果上，對所有的需求點按極坐標角度的大小升序排列并統(tǒng)計各個需求點的編號存于數(shù)組demander[]中，以便算法能從較小角度的客戶需求點開始，逐一掃描所有客戶的需求，對其進行服務.

函數(shù)demand_dot()根據(jù)車輛的容量，將客戶需求按照極坐標的角度從小到大分配給不同的車輛，直到車滿為止，但最后一輛車有可能滿也有可能不滿.并在數(shù)組servers[i][j]中記下每一輛車所服務的需求點的編號，計算所需車輛總數(shù)carnumber，方便在算法中對每一輛車所走的距離進行統(tǒng)計.并且在函數(shù)ant_colony()中對每一輛車走的路徑進行統(tǒng)計，得出所走的總的路徑長度，以及輸出所走的路徑和總長度.最后計算整個算法運行所需的總時間.

設置參數(shù)α=1，β=1，ρ=0.99，這些參數(shù)是多次試驗[12]所得到的較優(yōu)的結(jié)果，Q=10.螞蟻數(shù)M=10，開始都放與點(0，0)且數(shù)量越多找到的路徑越優(yōu)，但收斂的速度將會減慢.NCmax=200，此時整個程序的最優(yōu)運行時間為0.172s，Ncmax=2000時，最優(yōu)運行時間為1.047s.表1給出了整個應用程序運行10次中的最優(yōu)結(jié)果，總的車輛數(shù)為4，以及各輛車走的最短路線和長度.

表1 各輛車的路線及行駛長度

而單純的蟻群算法在NCmax=200時運行10次所得到的結(jié)果如下表2.

表2 純蟻群算法NCmax=200時運行10次所得結(jié)果

當NCmax=2000時，結(jié)果如表3.

由此兩表可知：在此10次的運行結(jié)果中NCmax=200時最優(yōu)的路徑長度是229.209、最優(yōu)運行時間為0.297s，且NCmax=2000時最優(yōu)路徑長度時221.832、最優(yōu)運行時間為2.344s，而上述應用該算法所得的結(jié)果不論NCmax為何值所得的最優(yōu)路徑長度都為217.138、最優(yōu)運行時間是當NCmax=200時為：0.172s、NCmax=2000時為：1.047s.相比之下，顯然應用該算法的結(jié)果表明所走的路徑長度要短.而且在應用的過程中程序的運行速度明顯比單純的算法運行的要快.

6 結(jié)束語

本文對蟻群算法的應用僅在給定的限制條件下

表3 NCmax=2000時運行10次所得結(jié)果

進行的，如：保證每輛車都滿載，且在各自的需求點服務完后，直接返回調(diào)度中心.既沒有考慮時間的限制，又沒有考慮實際運輸過程中的可能要帶返程貨物的問題.同時對路徑的要求是沒有路況，對所規(guī)定的路徑都是完好無損的，車輛可以直接從調(diào)度中心出發(fā)，后又按照求出的路徑回到調(diào)度中心.因此，在該算法的應用中很多情況都是理想的.所以在很多地方是需要進一步改進和完善的，比如：顧客的需求是有時間限制的，那么運輸中心就要在規(guī)定的時間內(nèi)完成任務，否則可能引起顧客的不滿，導致喪失已有的固定客戶，給公司帶來損失.在現(xiàn)在日趨激烈的競爭環(huán)境中，誰擁有更多的顧客，誰就是勝利者.所以必須考慮時間的限制，進一步完善應用該算法，才能充分發(fā)揮該算法的優(yōu)點.另外，還必須考慮的就是運輸?shù)馁M用問題，以及在運輸?shù)倪^程中出現(xiàn)其他事故的情況下如何及時的調(diào)整等等，這些都需要進行深入的研究.

[1]張蕾，陳笑蓉，陳笑筑.基于蟻群算法的多郵車調(diào)度問題研究[J].福建電腦，2008(8):108-109，129.

[2]BodinL.D.，GoldenB.L，AssadA.A.，BallM.RoutingandSchedulingofVehiclesandCrews[J].TheStateofArt，ComPuters&OperationsResearch，1983，10：63-211.

[3]GoldenB.L.Assad.VehicleRouting，MethodsandStudies[M].ElsevierSciencePublishersB.V，1988.

[4]AltinkemerK.，GavishB.ParallelSavingsBasedHeuristicfortheDeliveryProblem[J].Operations.Reserch，1991，1.39:456-469．

[5]DorigoM，ManiezzoV，ColorniA.Theantsystem:Optimizationbyacolonyofcooperatingagents.IEEETransactionsonSystems[J].ManandCybernetics-PartB,1996，26(1):29-41.

[6]DorigoM，GambardellaLM.Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[J].IEEETransactionsonEvolutionaryComputation，1997，1(1)：53-66.

[7]StützleT，HoosH.TheMAX-MINantsystemandlocalsearchforthetravelingsalesmanproblem[C].In:Proc.of20dInt.Conf.onMetaheuristics.Wien:springer-Verlag，1997.

[8]DorigoM，GambardellaLM.AntAlgorithmsforDiscreteOptimization[J].ArtificialLife，1999，5(3)：137-172.

[9]GambardellaLM，TaillardE，AgazziG.MACS-VRPTW:AMultipleAntColonySystemforVehicleRoutingProblemswithTimeWindows[M].NewIdeasinOptimization，1999.

[10]吳云志，樂毅，王超，張友華.蟻群算法在物流路徑優(yōu)化中的應用及仿真[J].合肥工業(yè)大學學報，2009(2)：211-214.

[11]盧曉珊，何偉，賀永金.郵政運輸網(wǎng)絡中的郵路規(guī)劃和郵車調(diào)度研究[J].數(shù)學的實踐與認識(MATHEMATICSINPRACTICEANDTHEORY)，2009(9):66-71.

[12]唐連生，程文明，張則強，等.基于改進蟻群算法的車輛路徑仿真研究[J].計算機仿真，2007(04):262-264.

[13]張玉琍，樊建華，徐建剛，等.車輛路徑問題的改進遺傳算法研究[J].天津理工大學學報，2006(5):79-82.

[14]蔣毅，陳震．基于蟻群優(yōu)化算法的車輛路徑問題研究(ResearchofVehicleRoutingProblemBasedOnAntConolyOptimization)[D].長春：吉林大學，2007.