求解車輛路徑問題的改進MMAS算法

謝驪玲，宋彥斌，楊 坦，駱其倫

(華南師范大學 數學科學學院，廣東 廣州 510631)

求解車輛路徑問題的改進MMAS算法

謝驪玲，宋彥斌，楊 坦，駱其倫

(華南師范大學 數學科學學院，廣東 廣州 510631)

最大-最小螞蟻系統(MMAS)只在最優解對應的路徑上更新信息素，有效地利用了最優解，但容易導致搜索過早停滯。文中分析了MMAS在求解車輛路徑問題(VRP)時的表現，針對其容易陷入局部最優解、全局搜索能力差、后期收斂速度慢等不足提出改進，給出一種新的信息素更新策略，動態改變揮發系數的數值，并在較優的幾條路線上進行信息素更新，從而在加速算法收斂的同時提高全局搜索能力，避免過早停滯。VRP仿真實驗結果表明，改進后的算法穩定性好，收斂速度比原始MMAS算法有明顯的提高。

車輛路徑問題；優化算法；蟻群算法；最大-最小螞蟻系統；信息素更新

1 概 述

車輛路徑問題(Vehicle Routing Problem，VRP)最早是1959年由G. Dantzig等提出的，問題可描述為：在諸如容量、總路程、時間窗、送貨順序等限制條件下，找到從一個或多個初始點出發，到多個不同位置的客戶的最優送貨路徑，即設計一個總代價最小的路線集，滿足：每個客戶只被一輛車訪問一次且所有車輛從起點出發再回到起點[1]。例如，最簡單最經典的VRP的要求是所有車輛的行駛路線使總的運輸成本最小。

車輛路徑問題是物流配送優化中的關鍵環節，也是管理科學中的一個重要研究課題。多年來運籌學、應用數學、物流科學、計算機科學等學科學者對這個問題進行了大量的理論研究和實驗分析，取得了很大的進展。

VRP是一個NP難題，隨著配送客戶數量的增加，可選的車輛路徑方案數量將以指數速度急劇增長。當問題規模較大時，利用傳統的理論尋優算法難以嚴格獲得精確最優解，因此求解該問題的主要方法是啟發式算法，后者一般能夠在一定時間內找到滿意的近似最優解，這是前者難以達到的。目前已成功應用于VRP的啟發式算法有掃描法[2]、節約法[3]、最近插入法[4]、遺傳算法[5]、神經網絡[6]、蟻群算法[7-8]、模擬退火法[9]、禁忌搜索法[10]等。這些方法各有優缺點，以經典TSP為測試基準，除了Lin-Kernighan的局部改進法之外，由意大利科學家Dorigo M等提出的蟻群算法(Ant Colony Algorithm)優于其他方法[1]。

蟻群算法是一種仿生類算法，應用范圍幾乎遍及各個領域。國內外多年的研究工作表明，蟻群算法在求解組合優化問題、離散優化問題方面都取得了成功，充分說明蟻群算法是一種非常有效的優化方法。蟻群算法自提出至今已在聚類分析、自動控制、系統工程、通信網絡路由選擇、車間調度問題、車輛路徑問題等方面都得到了成功的應用。算法在求解過程中利用螞蟻群體的系統性、自組織性、正反饋性和分布式計算，使算法演化過程得以進行，并且朝著優化方向收斂；另一方面，通過在算法中加入概率搜索技術來增加負反饋機制，從而提高了生成解的隨機性，一定程度上保持了解的搜索范圍，避免算法過早收斂于不好的結果。但是蟻群算法本身還是存在著搜索初期信息素匱乏、信息素積累時間較長、易陷入局部最優解的缺陷。所以研究者們提出了一系列的改進蟻群算法[11-15]。其中由Stützle等提出的最大-最小蟻群算法[16](Max-Min Ant Colony Algorithm,MMAS)是目前國際公認的用于解決VRP效果最好的蟻群算法[17]。

文中針對車輛路徑問題的特點，提出了一種改進的MMAS算法，給出一種新的信息素更新策略，通過動態改變信息素的揮發系數，達到在提高收斂速度的同時有效地防止停滯。

2 車輛路徑問題的描述

根據考慮因素的多寡、限制條件的不同，可以將車輛路徑問題分成幾種類型，但不管帶有何種條件的約束，配送總費用總是一個需要著重考慮的問題，而路徑的選擇則直接影響了配送費用的高低。

為使問題的描述更接近文中要解決的問題，下面以配送中心車輛調度問題為例重述VRP：已知若干客戶的位置坐標和貨物需求量，配送車輛的負載能力，每輛車從已知位置的物流中心出發，完成向多個客戶送貨的任務后回到起點。要求合理安排車輛配送路線，使配送總費用最少，即總里程最短，且滿足以下約束條件：

(1)每輛車所配送的客戶的需求量總和不超過車輛的負載能力；

(2)每個客戶的需求必須滿足，且只由一輛車配送。

顯然這是一個經典的有容量限制的車輛路徑問題(CVRP)，在不引起混淆的情況下，許多文獻直接將CVRP簡稱為VRP。一般地，該問題的數學模型可以表述如下[1]：

設

則要解決的問題即為：

其中：約束(a)是車輛負載能力；約束(b)保證每個客戶只被一輛車訪問一次；約束(c)-(e)保證每輛車完成任務后回到起點。參數cij是位置i到位置j的距離；di是客戶i的需求量；D為單車額定載重量。

3 MMAS算法的原理和實現步驟

3.1 算法原理

MMAS算法與基礎的AS算法比較，主要作了如下改進：

(2)完成一次迭代后，只更新最優解所在路徑上的信息，充分保留了歷史最優解的信息；

(3)算法開始時，信息素揮發速率ρ初始值較小，以便在迭代初期能讓螞蟻搜索到更多可能的路徑。但為保證搜索能順利進行，信息素的初始值被設定為上限值τmax，使得算法能在搜索初期加大對新解的探索，不至于一開始就快速接近局部最優解。從文獻實驗中還可發現，在迭代過程中，逐步提高全局最優解的應用頻率，可加快算法的搜索過程。

3.2 算法步驟

求解CVRP的帶有局部優化步驟的MMAS算法(算法1)如下：

Step1:螞蟻初始化。設有N個客戶點，每條邊上的信息素初始值為τmax，將N只螞蟻放在配送中心所在節點上，每只螞蟻的負載能力代表車輛的額定載重D；與實際蟻群不同，人工蟻群系統具有記憶功能，所以為每只螞蟻建立空禁忌表tabuk(k=1,2,…,N)，用以記錄螞蟻k當前所走過的城市，集合隨迭代過程動態調整。

Step2:條件終止判斷。當定時時間到，或達到最大迭代次數，或最優解重復達到指定次數，結束算法，轉Step6；否則對蟻群中的每只螞蟻，重復執行以下步驟。

Step3:路徑構建。tabuk的補集中小于等于當前螞蟻的負載量剩余的節點作為備選節點，即allowedk={0,1,…,N-1}-tabuk，每只螞蟻根據如下轉移概率公式選擇下一個節點，逐步形成完整路線。

同時將該節點加入tabuk中，更新當前每只螞蟻的負載量，若tabuk的補集中各節點的需求量di均大于當前剩余的負載量，則直接返回配送中心。

Step4:路徑改進。采用2-Opt局部搜索方法對第3步中形成的路線進行優化。

Step5:軌跡更新。當N只螞蟻均完成遍歷任務后，找出該代次最佳路徑并保留(當前迭代最優解)：

lmin=minlk,k∈{1,2,…,N}

式中，lk為第k只螞蟻走過的路程之和。

然后更新信息素，增加該次迭代中表現最好的螞蟻經過路徑上的信息素濃度，信息素濃度更新規則如下:

(1)

Step6:輸出結果。

4 改進的MMAS算法步驟

由3.2的MMAS算法步驟可知，在迭代過程中需要對若干參數進行設定，參數的取值對算法性能會有一定的影響，其中信息素揮發度參數ρ的取值直接影響到算法的收斂性和全局搜索能力。信息素揮發度與信息的正反饋作用是此消彼長的關系。ρ較大，則正反饋作用較弱，算法的收斂速度慢，但搜索的隨機性提高；反之則算法收斂速度較快而搜索的隨機性降低，算法容易出現搜索停滯。所以對ρ的選擇需要綜合考慮算法的全局搜索能力和收斂速度。

基本的MMAS算法將各條路徑上的信息素濃度值限定在固定的范圍內，雖然能在一定程度上避免過早陷入局部最優解，但當解的分布較分散時收斂速度較慢；另外，每完成一次迭代后，沒有考慮到各條可能路徑的優劣情況，僅以固定的揮發系數ρ對當前最優路徑上的信息素進行更新，有可能由于對當前最優路線的更新遠大于其他路徑，從而使某些次優、次次優的路徑沒有機會被選中，導致算法在這些路徑上的搜索能力相對較低，造成算法的全局尋優性能變差，影響了算法的隨機性能和全局搜索能力。

從上述分析過程可看出，固定揮發系數ρ的值總是有弊端，所以可通過動態地改變ρ的值來提高算法的全局搜索能力，并且同時應兼顧到次優路徑的信息素更新問題。

綜合文獻中的實驗結果，容易發現，蟻群算法在迭代到一定程度后，螞蟻對信息素的濃度逐漸變得不敏感，各條路徑上的信息素最大差距趨向于固定數值(上限值-下限值)，此時算法將會出現一定程度的搜索停滯。在一定的迭代次數內所得的解大致接近，如果固定揮發系數ρ，即使每次迭代都更新信息素的量，對解也不會有太大的改進。因此為加快迭代速度，考慮在迭代過程中動態地修改揮發系數ρ的值，并修改信息素更新規則。

根據上述分析，在搜索的前期和后期，為保留最優路徑更多的信息，ρ應該取得小一些，在搜索的中期，為加快迭代速度，ρ可以取得較大一些。易見ρ與迭代次數n有關，因此構造如下關于迭代次數n的函數動態地改變揮發系數ρ的值，用以路徑的信息素更新過程。

(2)

其中，自變量n為迭代次數，并且在式(1)中，將更新規則修改為：

(3)

得到文中算法2。

MMAS只對最優路徑上的信息素進行全局更新，即只增強最優解的影響程度。這種做法當解的分布較集中時收斂速度較快，但當解的分布較分散時容易出現局部收斂。為避免過早停滯，選擇同時在最優的bn個路徑上進行信息素更新，并根據路徑的優劣程度相應地在這bn個路徑上依次降低更新概率，具體規則修改如下：

由算法1的第5步，一次迭代完成后，根據路徑長度將路徑重新排序，假設由短到長依次排序為l1

其中，k=1,2,…,bn。

由此得到算法3。

最后，為保證信息素更新后依然滿足MMAS關于信息素濃度的限制，達到避免停滯現象發生的目的，在信息素更新步驟(見式(2))后面加上判斷條件：

end

5 實驗與結果

為了驗證文中提出的帶有動態信息素調整策略的算法2和帶有改進更新規則的算法3比原始的MMAS算法具有更佳的全局最優解搜索能力和更高的收斂速度，以NEO網站中提供的VRP問題的數據(http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/)為例進行實驗。實驗的硬件環境為Intel酷睿i5-2450，內存8G；軟件環境為MATLAB2013b。實驗中所采用的部分參數統一取值如下：最大循環次數NCmax=3 000，螞蟻個數m=20，重要度系數α=1，能見度系數β=2。

實驗結果如表1和表2所示。

其中：最優解是已知的該問題最好的解；平均解是指運行3次所得的3個解的平均值；平均時間是指各次運行中找到最好解的時間的平均值，單位為s。

表1 算法2的實驗結果對比

表2 算法3的實驗結果對比

實驗結果表明，帶有動態信息素調整策略的算法2以及帶有改進更新規則的算法3均比原始的MMAS算法的穩定性好，全局搜索能力較強，而算法效率與帶局部改進的MMAS算法相當，比原始的MMAS收斂速度快。

6 結束語

從蟻群搜索最短路徑的機制不難發現，算法中參數的選擇明顯地影響到蟻群算法的性能，但對各參數的選取方法和原則，通常都是根據經驗而定的，尚沒有理論上的依據。文中在對車輛路徑問題進行簡單描述的基礎上，通過對MMAS算法中有關參數的討論，發現原有算法雖然具備較好性能，但是因為算法中各參數都是固定的，沒有根據求解過程動態變化，依然存在容易陷入局部最優解、全局搜索能力差、收斂速度慢等基本蟻群算法的不足。

基于上述缺陷，文中提出一種求解車輛路徑問題的改進的自適應最大-最小螞蟻算法，對MMAS算法中的一些參數及策略作了自適應變化，給出動態調整的信息素揮發系數和新的信息素更新策略，使得算法在求解問題時能在求解過程中隨著解狀態的變化而相應變化，從而具有更好的算法性能。實驗結果表明，帶有動態信息素調整策略和新的信息素更新規則的MMAS算法增強了螞蟻搜索的有效性，提高了算法的尋優性能；而且算法效率與帶局部改進(2-Opt)的MMAS算法相當，收斂速度比原始的MMAS算法有較大的提高。

文中提出的求解車輛路徑問題的改進算法對解決類似的組合優化問題有一定的參考價值。但是，限于篇幅關系，沒有討論其他參數對算法有效性、穩定性和收斂性的影響，這將是接下來的一個研究方向。

[1] 馬 良，朱 剛，寧愛兵.蟻群優化算法[M].北京：科學出版社，2008.

[2]GillettBE,MillerLR.Aheuristicalgorithmforthevehicledispatchproblem[J].OperationsResearch,1974,22(2):340-349.

[3] 方金城，張岐山.物流配送車輛路徑問題(VRP)算法綜述[J].沈陽工程學院學報:自然科學版，2006,2(4):357-360.

[4] 趙燕偉，張景玲，王萬良.物流配送的車輛路徑優化方法[M].北京：科學出版社，2014.

[5] Laporte G,Mercure H,Nobert Y.An exact algorithm for the asymmetrical capacitated vehicle routing problem[J].Network,1986,16:33-46.

[6] 王德東，鄭丕諤.車輛路徑問題的混沌神經網絡解法[J].計算機集成制造系統，2005,11(12):1747-1750.

[7] Bullnheimer B，Hartl R F，Strauss C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operations Research，1999，89(13)：319-328.

[8] Dorigo M,Stützle T.Ant colony optimization:overview and recent advances[M]//International series in operations research & management science:handbook of metaheuristics.US:Springer,2010:227-263.

[9] 胡大偉，朱志強，胡 勇.車輛路徑問題的模擬退火算法[J].中國公路學報，2006,19(4):123-126.

[10] Barbarrosoglu G,Ozgur D.A tabu search algorithm for the vehicle routing problem[J].Computers & Operations Research,1999,26(3):255-270.

[11] 李 琳，劉士新，唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題[J].控制與決策，2010，25(9):1379-1383.

[12] Chen C,Ting C.An improved ant colony system algorithm for the vehicle routing problem[J].Journal of the Chinese Institute of Industrial Engineers,2006,23(2):115-126.

[13] Gan R,Guo Q,Chang H,et al.Improved ant colony optimization algorithm for the traveling salesman problems[J].Journal of Systems Engineering and Electronics,2010,21(2):329-333.

[14] 劉曉勇，付 輝.基于啟發式蟻群算法的VRP問題研究[J].計算機工程與應用，2011,47(32):246-248.

[15] 張 錦，李 偉，費 騰.交叉變異蟻群算法在VRP問題中的應用研究[J].計算機工程與應用，2009,45(34):201-203.

[16] Stützle T,Hoos H H.Max-min ant system[J].Future Generation Computer Systems,2000,16(19):889-914.

[17] 耿耀華.基于MMAS的配送線路規劃研究與應用[D].濟南：山東大學，2008.

An Improved MMAS for Vehicle Routing Problem

XIE Li-ling,SONG Yan-bin,YANG Tan,LUO Qi-lun

(School of Mathematics Sciences,South China Normal University,Guangzhou 510631,China)

To exploit the best solutions found during an iteration or during the run of the algorithm,Max-Min Ant System (MMAS) allows the ant on the best solution to heighten the pheromone.Unfortunately,it will lead to the premature stagnation of the search.By analyzing the performance of MMAS in Vehicle Routing Problem (VRP),in order to avoid getting a local optimum solution,poor global search optimization ability,and slow convergence rate,a new strategy for pheromone updating is presented.It changes the value of the volatilization coefficients dynamically and updates the pheromones on the best ways,thus accelerating convergence and avoiding premature stagnation.The simulation experiments of the VRP show that the stability and convergence rate of the proposed algorithm is improved significantly compared with the basic MMAS.

VRP;optimization algorithm;ant colony algorithm;MMAS;pheromone updating

2014-12-15

2015-03-21

時間：2016-02-

國家自然科學基金資助項目(11371154)；廣東省教育部產學研結合項目(2012B091100186)

謝驪玲(1977-),女，博士，副教授，研究方向為最優化算法與應用、物流與供應鏈管理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1619.006.html

TP301.6

A

1673-629X(2016)03-0027-04

10.3969/j.issn.1673-629X.2016.03.007