蟻群算法在多郵車調度中的應用

李香云，葛 華

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

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

1 蟻群算法簡介

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

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

1996年，Gambardella和Dorigo又提出了一種修正的蟻群算法，蟻群系統(ant colony system，ACS)[6].ACS與前面的AS主要區別在于：螞蟻在搜索最優路徑的過程中只能使用局部信息，即采用局部信息對信息素濃度進行調整的局部更新規則(Local Updating Rule)；在所有進行尋優的螞蟻結束路徑尋找后，信息素的濃度會再一次調整，這次采用的是全局信息，而且只對發現的最好路徑上的信息素濃度進行加強；有一個狀態傳遞機制，用于指導螞蟻最初的尋優過程，并能積累問題目前狀態.局部更新的主要思想，在于避免產生一條過于強勢的路徑，吸引所有的螞蟻走上該路徑，如此便無法進行適當的探索新路徑的動作，從而陷入局部最優.局部更新規則在所有螞蟻完成一次轉移后執行，執行公式為：

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

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

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

2 基本原理與數學模型和算法流程

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

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

(1)

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

(2)

(3)

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

(4)

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

3 算法流程

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

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

①初始化:

SetNC=0，每條邊上的τij(0)=c，并且Δτkij，放置m個螞蟻島有車調度中心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)蟻群算法的基本結構如圖1所示.

圖1 算法基本結構圖

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

4.1 郵車的調度與路徑問題

本文針對的車輛調度問題有如下的要求：

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

4.2 算法的實現

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

5 算法應用實例與分析

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

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

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

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

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

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

當NCmax=2000時，結果如表3.

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

6 結束語

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

表3 NCmax=2000時運行10次所得結果

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

[1]張蕾，陳笑蓉，陳笑筑.基于蟻群算法的多郵車調度問題研究[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]吳云志，樂毅，王超，張友華.蟻群算法在物流路徑優化中的應用及仿真[J].合肥工業大學學報，2009(2)：211-214.

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

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

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

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