李香云，葛 華

(安徽科技學(xué)院 計(jì)算機(jī)系，安徽 鳳陽(yáng)233100)

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

1 蟻群算法簡(jiǎn)介

蟻群算法是受到自然界中的蟻群尋找食物的行為的啟發(fā)而提出的.最先提出的蟻群算法被稱為螞蟻系統(tǒng)(Ant System，AS)[5]，它是Dorigo，Colorni，Maniezzo于1992年在意大利的米蘭理工學(xué)院合作研究組合優(yōu)化問題計(jì)算機(jī)智能解決方法時(shí)的研究成果.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是一個(gè)非常有效的算法.

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

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

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

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

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

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

在算法的初始時(shí)刻τij(t)=c(c為常數(shù))，螞蟻獨(dú)立的選擇下一個(gè)節(jié)點(diǎn)，在t時(shí)刻位于節(jié)點(diǎn)i的螞蟻k，利用路徑(i，j)上的信息素濃度τij(t)選擇下一個(gè)節(jié)點(diǎn)，則下一個(gè)節(jié)點(diǎn)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)上的信息量，一般來(lái)說(shuō)，最基本的取值形式為：

(4)

(4)式中，Q表示螞蟻?zhàn)咭蝗︶尫诺男畔⑺貜?qiáng)度，它在一定程度上影響算法的收斂速度，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度.

3 算法流程

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

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

①初始化:

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

②fork=1tomdo

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

③重復(fù)直到tabulist滿為止

④Fork=1tomdo

⑤Fork=1tomdo

對(duì)每一條邊計(jì)算，更新邊上的信息濃度

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

SetNC=NC+1

⑥While(NC

then清空tabu陣

Goto②

Else

打印出最短路徑.

終止整個(gè)程序.

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

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

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

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

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

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

4.2 算法的實(shí)現(xiàn)

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

5 算法應(yīng)用實(shí)例與分析

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

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

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

表1 各輛車的路線及行駛長(zhǎng)度

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

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

當(dāng)NCmax=2000時(shí)，結(jié)果如表3.

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

6 結(jié)束語(yǔ)

本文對(duì)蟻群算法的應(yīng)用僅在給定的限制條件下

表3 NCmax=2000時(shí)運(yùn)行10次所得結(jié)果

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

[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)化中的應(yīng)用及仿真[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2009(2)：211-214.

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

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

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

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