改進的蟻群算法求解VRP問題

摘 要:為了使蟻群算法針對VRP問題解的搜索更加高效，將變異操作用于蟻群算法，給出了變異概率的設置，合理地改進可見度的計算及信息素更新方法，結合swap局部搜索，獲得了更加穩定的求解VRP問題的蟻群算法。實驗表明，該算法穩定有效。

關鍵詞:VRP; 蟻群算法; 變異; 局部搜索

中圖分類號:TP311 文獻標識碼:B

文章編號:1004-373X(2010)12-0075-03

Improved Ant Colony Algorithm for VRP

SANG Guo-zhen1， WANG Feng2， YANG Rui-chen2

(1.Weinan Teachers University， Weinan 714000， China; 2.Chengde Petroleum College， Chengde 067000， China)

Abstract:A mutation is applied to the ant colony algorithm and the mutation probability is given for solving the VRP problem more efficiently. The formula of visibility and pheromone updating method are set reasonably. Combined with swap local search， a more stable ant colony algorithm for VRP is gained. Experiments show that the algorithm is stable and effective.

Keywords:VRP; ant colony algorithm; mutation; local search

車輛路徑問題[1] (vehicle routing problem，VRP)是組合優化領域中著名的NP-hard問題之一，一般需使用啟發式搜索算法求解。蟻群算法是模擬螞蟻覓食原理的一種仿生學啟發算法，其應用于VRP問題的求解具有更為明顯的優勢，很多人對此進行了研究。

1 VRP問題

采用賦權有向圖G=(V，A，d)來表示配送路徑問題。其中，V={v0，v1，v2，…，vn}為點的集合;v0表示配送中心;vi(i=1，2，…，n)表示各顧客;A={(vi，vj)|vi，vj∈V，i≠j}為弧的集合;dij是與弧(vi，vj)相聯系，表示vi到vj的距離。對于顧客，vi給定了需求量qi(其中q0=0)，在容量及路徑長度的約束下，使用最少車輛完成配送任務，尋找最短配送路徑。假定配送中心最多可用K輛車對顧客點進行配送，每輛車載重量為Qk(k=1，2，…，K)，則設nk為第k輛車所配送的顧客點數(若nk=0表示未使用該車)，此車所走的路徑用集合Rk表示(Rk也可稱為第k條路徑)，其中的元素rki 表示顧客點在路徑k中的順序為i(不包含配送中心)。令rk0  = rk(nk  + 1)  = v0表示配送中心，有如下模型:

min Z=∑ K k=1 ∑ nk i=1 (drk(i-1)rki+drknkrk(nk+1))sign(nk-1) (1)

s.t.∑ nk i=1 qrki≤Qk，k=1，2，…，K (2)

0≤nk≤n，k=1，2，…，K (3)

∑ K k=1 nk=n (4)

Rk={rki|rki∈{1，2，…，n}，i=1，2，…，nk} (5)

Rk∩Rk2=Φ，k1≠k2 (6)

式中:sign(nk-1)=1，nk≥1

0，其他

模型中式(1)為目標函數;式(2)保證每條路徑上各個顧客點的總需求量不超過此路徑的配送車輛載重量;式(3)表明每條路徑上的顧客點數不超過總顧客點數;式(4)要求每個顧客點都得到配送服務;式(5)表示每條路徑上顧客點的組成及排列次序;式(6)限制每個顧客點的需求僅能由輛車完成。

2 蟻群算法

蟻群優化算法是在1996年由Marco Dorigo等首先提出的[2]，后來很多學者又做了許多研究，使蟻群算法得到了進一步的深化與完善。當然這里包含了很多不同版本的蟻群算法，諸如:螞蟻算法(ant algorithm，AA)[3]、螞蟻系統(ant system，AS)、蟻群系統(ant colony system，ACS)[4-5]、最大最小蟻群系統(max-min ant colony system，max-min ACS)[6]等。

設K_ant是蟻群中螞蟻的數量;dij(i，j=1，2，…，n)表示城市i與城市j之間的距離;τij(t)表示時刻t時，路徑或弧(i，j)上的信息素濃度;ηij(t)是與路徑(i，j)相關聯的啟發式信息值。初始時刻，各條路徑上的信息素濃度相等，設τij(0)=C(C為常數)。螞蟻k(k=1，2，…，K_ant)在移動過程中，根據各條路徑上的啟發值的大小和信息素量的多少決定轉移方向。這里使用輪盤賭策略，定義t時刻螞蟻k由城市i到城市j的轉移概率:

pkij(t)=[τij(t)]α[ηij(t)]β∑h∈allowedki[τih(t)]α[ηih(t)]β，if vj∈allowedki

0，otherwise

式中:allowedki是螞蟻k位于城市i時可行鄰域城市的集合，即螞蟻k尚未訪問過或允許到達城市的集合;α，β分別是控制信息素和啟發式信息值在概率pkij(t)中的權重參數。

對于傳統的蟻群算法，在螞蟻數量有限的情況下，局部最優很容易限制搜索空間[7]。

3 蟻群算法的改進

3.1 解的構造

根據最終獲得最短路徑的目標，設計啟發值的計算方案有:

ηij(t)=τij(t-1)(di/dij)

式中:di為螞蟻當前所在城市與所有其他城市的平均距離;啟發式涵義表示與當前螞蟻所在地距離越近的城市被訪問的概率越大。用ρ表示信息素揮發的系數，在螞蟻完成1次巡游后，各條路徑上的信息素做以下更新:

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

Δτij(t)=∑K_antk=1Δτkij(t)

Δτkij(t)=QL(k)，if 解使用邊(i，j)，

0， otherwise

式中:Q是常數;L(k)為螞蟻k所構造解的旅行總距離;比值Q/L(k)實際為解的質量函數，標識著此解的優秀程度;Δτkij(t)表示螞蟻k在構造解時在路徑(i，j)上留下的信息素量;Δτij(t)為K_ant只螞蟻構造解時在路徑(i，j)上留下的信息素總量。

3.2 變異操作

借鑒遺傳算法的基因突變思想，設計蟻群算法路線中顧客點的變異方法，用以在解的構造過程中跳出局部最優。主要按照以下3步進行變異:

(1) 變異顧客點的選擇。以蟻群搜索得到的各條回路為單元，在2條不同的回路中，分別選定1個可能進行變異的顧客點，以備進行變異。

① 第一變異顧客點i的選擇。變異顧客點的選擇是以概率的形式出現的，按照迭代次數由小到大，變異概率由大到小，令:

piv(t)=pmaxv-(t/T)(pmaxv-pminv)

式中:pmaxv，pminv是變異概率的上限和下限;T是總迭代次數;t是當前代數;piv(t)代表顧客點i的變異概率。

② 第二變異顧客點j的選擇。

選定第一變異顧客點i后，第二變異點j的選取就不能再按照與i相同的原則選取了，必須考慮與i之間的聯系。根據合理性分析，pjv(t)應與j與i間的距離相關。令:

pjv(t)=(d/dij)#8226;piv(t)

式中:d為i到各顧客點間距離的平均值。

(2) 交換已選定的2個顧客點，構造出新解。

(3) 按照評判參數判斷新解質量的高低。在變異操作中，有可能會違背容量約束，在這種情況下，對此加入相應的罰值Lp，對總路程的最終大小進行修正，用以影響信息素的更新操作。

Lp=(qp/Qp)#8226;L

式中:罰值Lp用于增加總路程的長度;qp為違背容量約束的車輛超出的容量值;Qp為違背容量約束的車輛的載重量。

3.3 swap局部搜索

使用swap進行局部搜索，可以有效去除路線中的交叉現象[8]。實驗發現，在配送路徑上存在著交叉現象，在配送中心附近，這種現象尤為明顯。通過實驗，swap法在增加收斂速度和跳出局部最優方面均有很好的效果，在此應用swap法提高解的質量。

3.4 信息素更新

基于nk個本代最優解的信息素更新規則，可以有效提高計算效率[9]。更新規則如下:

τNij=ρτOij+λΔτij

Δτij= ∑Kk=1[ (nk-k)/Lk] ， if(vi，vj)∈C

0， otherwise

C={(vi，vj)|(vi，vj)∈A且(vi，vj)∈ALk

式中:ρ為信息素揮發后所剩的比例系數;Lk為第k優的目標值;ALk是取得Lk解的路徑使用的弧的集合;λ為更新系數，靈活控制信息素可增加幅度。

3.5 算法流程

算法流程如圖1所示。

4 數值實驗

為了便于檢驗算法的性能，用改進算法在Matlab 6.0中進行了仿真計算。

圖1 改進的蟻群算法程序實現流程

4.1 數值實驗1

某物流中心有5臺車輛，車輛的最大載重量均為8 t，一次配送的最大行駛距離均為50 km，需向20個客戶送貨。物流中心坐標(14.5 km，13.0 km)、客戶坐標及需求量詳見文獻[10]。文獻[10]采用混合遺傳算法求解10次得到的平均最優解是122.0 km。

采用此算法，取螞蟻數為18，最大循環次數為8，α=1.2，β=2.9，ρ=0.8，λ=1.5，pminv=1/20， pmaxv=5。為了便于比較，與文獻[ 10] 一樣隨機求解10次(見表1)。平均長度為108.4，最優長度為107.8，滿意路徑為0-5-14-2-12-9-10-7-1-0-20-11-17-3-4-0-6-13-16-15-19-8-0-18-0。與文獻[10]比較，結論理想。

表1 實驗1的改進蟻群算法計算結果

計算次序123456

路徑總長/km107.8109.1108.6108.6107.8108.6

計算次序78910平均

路徑總長/km107.8109.1107.8107.8108.3

4.2 數值實驗2

數據詳見文獻[10]中實例1，采用本文所述改進的蟻群算法進行計算，取螞蟻數10，設置最大循環次數8，求解10次，全都得到了最優解67.5(與文獻[10]描述 相同)。可見算法具有相當滿意的穩定性。

5 結 語

深入闡述了將變異操作用于蟻群算法的搜索過程當中，并具體提出了變異概率的設置。另外結合合理的可見度及信息素計算，結合swap局部搜索算法，使蟻群算法在VRP問題的求解過程中更加穩定。求解結果比較表明，算法穩定有效，但由于變異操作的存在，使得收斂時間有所延長，設置更加合理的變異概率和終止變異條件，對于大量顧客點的實例研究及算法的進一步優化將是下一步的工作目標。

參考文獻

[1]BULLNHEIMER Bernd， HARTL Richard F， STRAUSS Christine. An improved ant system algorithm for the vehicle routing problem[J]. Annals of Operations Research， 1999， 89:319-328.

[2]DORIGO M， MANIEZZO V， COLORNI A. The ant system: optimization by a colony of cooperating agents[J]. IEEE Trans. Sys. Man Cyb. B.，1996，26:29-41.

[3]DORIGO M， BONABEAU E， THERAULAZ G. Ant algorithms and stigmergy[J].Future Generation Computer Systems，2000，16:851-871.

[4]DORIGO M， GAMBARDELLA LM. Ant colony system: a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Coputation，1997，1(1): 53-66.

[5]STUETZLE T， DORIGO M. ACO Algorithms for the Traveling Salesman problem[C]. Evolutionary Algorithms in Engineering and Computer Science. [ S.l.] : Wiley， 1999.

[6]STUETZLE T. MAX-MIN ant system[J].Preprint Submitted to Elsevier Science， 1999，11: 116-121.

[7]楊瑞臣，周永付，云慶夏.尋找車輛最優路徑的混合算法[J].交通運輸工程學報，2005，5(1):102-105.

[8]OSMAN I H.Metastrategy simulated annealing and tabu search algorithms for the Vehicle Routing Problem[J]. Annals of Operations Research，1993，41:421-451.

[9]楊瑞臣，郝海燕.改進的蟻群算法在物流配送路徑問題求解中的應用[J].承德石油高等專科學校學報，2009，11(2):53-56.

[10]郎茂祥，胡思繼. 用混合遺傳算法求解物流配送路徑優化問題的研究[J].中國管理科學，2002，10(10):51-56.