改進(jìn)蟻群算法在VRP問(wèn)題中的應(yīng)用及顏色Petri網(wǎng)實(shí)現(xiàn)①

鄭文艷,趙麗敏

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

計(jì)算完螞蟻當(dāng)前所處的客戶與未訪問(wèn)客戶列表中任意兩者之間的概率后,為避免陷入局部最優(yōu),采用輪盤(pán)賭的方式進(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ǔ)言完成相應(yīng)的功能.并且可以設(shè)置斷點(diǎn)進(jìn)行調(diào)試,ACO運(yùn)行的每一個(gè)中間結(jié)果都可以通過(guò)軟件實(shí)時(shí)觀察到.

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

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

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

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

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

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

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

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

4 測(cè)試實(shí)例

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

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

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

圖2 可行解生成過(guò)程

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

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

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

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

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

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

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

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

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

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

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