鄭文艷,趙麗敏

(德州學(xué)院 信息管理學(xué)院,德州 253023)

1 引言

蟻群算法是一種啟發(fā)式全局優(yōu)化算法,車輛路線問題(VRP)是指一定數(shù)量的客戶具有不同數(shù)量的貨物需求,配送中心向客戶提供貨物,由一個車隊負(fù)責(zé)分送貨物并組織適當(dāng)?shù)男熊嚶肪€,最終達(dá)到諸如路程最短等目的優(yōu)化問題,其最早是由Dantzig和Ramser于1959年首次提出的[1].早在1999年,Dorigo[2]和Gambardella[3]等學(xué)者首次將蟻群算法用來求解VRP問題,此后大量國內(nèi)外學(xué)者在蟻群算法在車輛路徑問題方面的應(yīng)用開展了研究工作.如文獻(xiàn)[4]把蟻群算法和遺傳算法進(jìn)行結(jié)合; 文獻(xiàn)[5]將粒子群和蟻群算法進(jìn)行結(jié)合; 文獻(xiàn)[6]把車輛容量引入狀態(tài)轉(zhuǎn)移規(guī)則的更新公式中; 文獻(xiàn)[7]通過定義螞蟻權(quán)重來更新信息素;文獻(xiàn)[8]用改進(jìn)后的蟻群算法對各類車輛路徑問題進(jìn)行求解并對比實驗結(jié)果; 文獻(xiàn)[9]采用了混合局部搜索算子,增強(qiáng)了算法的局部尋優(yōu)能力; 文獻(xiàn)[10]對應(yīng)用蟻群算法解決VRP問題做了整體回顧.

Petri網(wǎng)是1962年德國學(xué)者Petri[11]在其博士論文中提出的.Petri網(wǎng)是一個圖形化數(shù)學(xué)化的模型工具,適用于描述并發(fā)、異步、分布式、并行、非確定性或隨機(jī)的信息處理系統(tǒng),應(yīng)用于各種領(lǐng)域[12–15].

本文一方面對傳統(tǒng)的蟻群算法進(jìn)行了改進(jìn),把客戶需求量,車輛實時貨物裝載量加入可行解的構(gòu)造過程,在一定程度上優(yōu)化了初始解; 實時記錄目前的最優(yōu)路徑,通過對比自動調(diào)整信息素的更新方式,在替換最優(yōu)路徑的同時,對當(dāng)前路徑進(jìn)行懲罰或獎勵; 同時對概率選擇公式進(jìn)行了改進(jìn),避免出現(xiàn)極端情況.另外,本文借助CPN Tools仿真工具建立了改進(jìn)蟻群算法的顏色Petri網(wǎng)模型,最后對車輛路徑問題的經(jīng)典算例進(jìn)行了實驗仿真.借助CPN這一工具,不僅對螞蟻選擇路徑以及信息素更新的整個過程一目了然,在獲得最短路徑的同時又可以獲取多條路徑,從而可以根據(jù)交通等情況進(jìn)行不同的選擇.而且該模型的可擴(kuò)展性高,不僅適用于普通VRP問題,對于不確定需求,時間窗等復(fù)雜VRP只需調(diào)整元組的參數(shù)即可.

2 求解VRP的改進(jìn)蟻群算法

2.1 可行解構(gòu)造的改進(jìn)

在使用蟻群算法求解VRP問題時,螞蟻是從所有未被服務(wù)的客戶中按輪盤賭的方式進(jìn)行選擇,而改進(jìn)蟻群算法把客戶需求和當(dāng)前車輛的貨物剩余量都考慮進(jìn)去,從而進(jìn)一步縮小選擇范圍.

約束條件1: 初始時access={所有等待服務(wù)的客戶},遍歷所有等待服務(wù)的客戶,如果該客戶已被服務(wù)過,從access列表中移除該客戶; 更新access列表.

約束條件2: 遍歷更新后的access列表中所有的客戶,考察客戶的需求量是否滿足螞蟻的剩余裝載量; 滿足的留在access列表,不滿足的移除access列表.

Step2.從滿足約束條件1和2的access列表中,按照輪盤賭的方式,隨機(jī)選擇一個客戶進(jìn)行服務(wù).

Step4.判斷access是否為空,如果為空,說明螞蟻一次可以服務(wù)完所有的客戶,螞蟻放到螞蟻集合的隊尾,同時初始化access列表,并記錄該可行解,且該可行解只需一輛車即可; 如果access不為空那么跳至并執(zhí)行約束條件2,然后更新access,如果更新后access為空,說明螞蟻配送一次不足以服務(wù)完所有的客戶,需回到配送中心裝滿貨物(第二輛車)并且需放置螞蟻集合的隊首,再跳至約束條件2進(jìn)行循環(huán),如此,直至access為空,形成可行解,從配送中心出發(fā)幾次代表需要幾輛車才可以服務(wù)完所有的客戶.

2.2 信息素更新的改進(jìn)公式

傳統(tǒng)的ACO算法更新所有的可行解,并按一定的比例揮發(fā)信息素.本文信息素的變化分為增加和減少兩類,增加或減少的依據(jù)是當(dāng)前可行解的路徑長度與記錄的最小路徑長度進(jìn)行比較,的初始值為0,直接將第一個可行解的路徑長度傳給它,之后按公式(1)進(jìn)行更新:

該可行解路徑上的所有客戶的信息素τ按照公式(2)進(jìn)行更新.

2.3 概率選擇公式的改進(jìn)

如果路徑不包括所有的客戶,那么螞蟻是需要從其未訪問的客戶列表中隨機(jī)選擇一個客戶進(jìn)行服務(wù)的,其選擇客戶的依據(jù)就是選擇概率的大小.因此概率公式的計算直接決定改可行解的質(zhì)量.因此,既要考慮兩客戶之間的信息素的大小,也需要考慮兩者之間的距離,并且還需要平衡兩個因素的相對重要程度.在i和兩客戶之間的概率見公式(3):

計算完螞蟻當(dāng)前所處的客戶與未訪問客戶列表中任意兩者之間的概率后,為避免陷入局部最優(yōu),采用輪盤賭的方式進(jìn)行選擇,從而確定螞蟻下一步要選擇的服務(wù)客戶.

3 改進(jìn)蟻群算法的顏色Petri網(wǎng)模型

3.1 CPN模型及顏色集描述

本文使用顏色Petri網(wǎng)工具CPN Tools[16]完成相應(yīng)的建模,該工具使用 Standard Programming Language(SML)語言完成相應(yīng)的功能.并且可以設(shè)置斷點進(jìn)行調(diào)試,ACO運行的每一個中間結(jié)果都可以通過軟件實時觀察到.

頂層(Top)CPN模型如圖1所示,展示了整個算法的流程.三個替代變遷分別對應(yīng)著三個具體的子頁page.替代變遷GetAnt完成對循環(huán)迭代次數(shù)的控制功能; 替代變遷AntChoiceCity生成可行解,替代變遷UpdatePheromone更新信息素的更新.

圖1 改進(jìn)的ACO的CPN模型的top頁

3.2 部分模型及主要函數(shù)

圖2對應(yīng)著可行解的生成過程,螞蟻從未服務(wù)的客戶中進(jìn)行初步選擇,然后再根據(jù)車輛目前的裝載剩余量和未服務(wù)的客戶列表中客戶的需求量,進(jìn)一步對禁忌表進(jìn)行更新,最終形成符合兩個條件的所有的客戶列表.然后再根據(jù)信息素和轉(zhuǎn)移概率,利用輪盤賭進(jìn)行選擇.重復(fù)該過程,直至不存在未被服務(wù)的客戶.該可行解進(jìn)入下一步計算路徑處理過程的同時開始進(jìn)行下一輪可行解的構(gòu)造過程.

其中庫所AccessCity表示螞蟻下一步可選擇的所有客戶列表以及目前螞蟻已經(jīng)服務(wù)過的客戶列表,它的顏色集LAntCity是一個如下所示的五元組:

其分別表示螞蟻號、目前所在的客戶編號、服務(wù)過的客戶列表、下一步可選的客戶列表以及目前車輛貨物剩余量.該庫所是AccessCity變遷的輸出,存放輸入變遷的結(jié)果,同時為GenerateCityProbility這個變遷提供輸入.

變遷AccessCity將產(chǎn)生螞蟻可選擇的客戶列表,其輸入是已經(jīng)服務(wù)過的客戶列表,輸出下一步可以選擇的客戶列表.這個功能是由函數(shù)AntCityAccessNew實現(xiàn)的.而AccessCitybyDemandLast函數(shù)實現(xiàn)的是根據(jù)新的禁忌表和車輛的剩余裝載量以及AntCityAccessNew函數(shù)的輸出,進(jìn)一步按客戶需求量更新禁忌表.

變遷GenerateCityProbility根據(jù)庫所AccessCity中的令牌值,所有客戶之間的信息素,以及列表中客戶的選擇概率,通過輪盤賭的方法去選擇一個客戶,并把選擇的客戶作為變遷UpdateAntPassCity的輸入,同時該變遷更新螞蟻已經(jīng)訪問過的客戶列表; 更新螞蟻的新位置; UpdateAccessCus變遷負(fù)責(zé)更新禁忌表,同時判斷該螞蟻目前的客戶列表是否組成一個可行解,是的話,輸出可行解的客戶列表為計算可行解的路徑長度提供輸入,同時,更新螞蟻列表; 如果還未形成可行解,那么為螞蟻新位置的下一次選擇做準(zhǔn)備.

4 測試實例

為檢驗改進(jìn)蟻群算法在求解車輛路徑問題上的有效性,實驗采用國際公認(rèn)的VRP問題庫中的經(jīng)典實例和其他參考文獻(xiàn)中使用的實例作為實驗對象.

1) 案例1[17]: 某配送中心用2輛額定裝載量為8×103kg的汽車對8個客戶配送貨物,配送中心與客戶、客戶與客戶之間的距離以及客戶的需求量如表1所示,其中,0代表配送中心,其他代表8個客戶點.其余參數(shù)的設(shè)置詳見參考文獻(xiàn)[17].

表2展示了本文算法與GA算法,傳統(tǒng)蟻群算法以及其他改進(jìn)蟻群算法之間的對比,本文算法在求得比GA算法和傳統(tǒng)蟻群算法小的路徑同時獲得了三條最短路徑.所有可行解的分布情況如圖3所示.

圖2 可行解生成過程

表1 案例1的距離與需求量表

表2 各算法之間的最優(yōu)路徑,最優(yōu)路徑長度的對比

圖3 案例1所有可行解的分布情況圖

2) 案例2(E016-03m): 某配送中心(編號為0)用3輛裝載量為90噸的車輛對15個客戶配送貨物.其余參數(shù)的設(shè)置詳見參考文獻(xiàn)[18].得到的最優(yōu)解最優(yōu)路徑如圖4所示.

圖4(a)為本文算法,最優(yōu)路徑長度為278.9,(b)為改進(jìn)的遺傳算法[19],最優(yōu)路徑長度為285.7087,(c)為改進(jìn)蟻群算法[18],最優(yōu)路徑長度為284.105.

3) 案例3(eil22): 某配送中心(編號為0)用4輛裝置量為6 ×103kg的車輛對21個客戶配送貨物.其余參數(shù)的設(shè)置詳見參考文獻(xiàn)[20].得到的最優(yōu)解最優(yōu)路徑如圖5所示.

圖5(a)為本文算法,最優(yōu)路徑長度為373.661,(b)為粒子群蟻群混合算法[20],最優(yōu)路徑長度為375.812,(c)為改進(jìn)蟻群算法[21],最優(yōu)路徑長度為381.6895.

圖4 本文算法與其他算法的最優(yōu)路徑

5 結(jié)束語

本文通過對ACO設(shè)置信息素的動態(tài)更新閾值,利用局部最優(yōu)解不斷獎懲路徑進(jìn)行信息素的更新,同時采用輪盤賭方法不斷跳出局部最優(yōu),不僅可以保證可行解的多樣性,還可以加快最優(yōu)解的收斂速度.另一方面,把客戶需求量等一些因素加入禁忌表及可行解的構(gòu)造過程,從而最大程度優(yōu)化初始解,通過對概率公式進(jìn)行改進(jìn),避免某些路徑的信息素?fù)]發(fā)迅速造成數(shù)據(jù)計算的溢出.同時采用顏色Petri網(wǎng)對改進(jìn)后的算法進(jìn)行建模仿真,并通過實例與其他改進(jìn)算法進(jìn)行比較,實驗表明,該工具操作簡單,方便,改進(jìn)后的算法收斂速度快,能夠更好地解決VRP問題,并且在一定程度上確保模型的可擴(kuò)展性.

圖5 本文算法與其他算法的最優(yōu)路徑