改進蟻群算法在VRP問題中的應用及顏色Petri網實現①

鄭文艷,趙麗敏

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

1 引言

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

Petri網是1962年德國學者Petri[11]在其博士論文中提出的.Petri網是一個圖形化數學化的模型工具,適用于描述并發、異步、分布式、并行、非確定性或隨機的信息處理系統,應用于各種領域[12–15].

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

2 求解VRP的改進蟻群算法

2.1 可行解構造的改進

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

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

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

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

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

2.2 信息素更新的改進公式

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

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

2.3 概率選擇公式的改進

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

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

3 改進蟻群算法的顏色Petri網模型

3.1 CPN模型及顏色集描述

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

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

圖1 改進的ACO的CPN模型的top頁

3.2 部分模型及主要函數

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

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

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

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

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

4 測試實例

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

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

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

圖2 可行解生成過程

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

表2 各算法之間的最優路徑,最優路徑長度的對比

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

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

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

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

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

圖4 本文算法與其他算法的最優路徑

5 結束語

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

圖5 本文算法與其他算法的最優路徑