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

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

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

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

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

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

車輛路徑問題；優(yōu)化算法；蟻群算法；最大-最小螞蟻系統(tǒng)；信息素更新

1 概 述

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

車輛路徑問題是物流配送優(yōu)化中的關(guān)鍵環(huán)節(jié)，也是管理科學(xué)中的一個重要研究課題。多年來運籌學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)、計算機科學(xué)等學(xué)科學(xué)者對這個問題進行了大量的理論研究和實驗分析，取得了很大的進展。

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

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

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

2 車輛路徑問題的描述

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

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

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

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

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

設(shè)

則要解決的問題即為：

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

3 MMAS算法的原理和實現(xiàn)步驟

3.1 算法原理

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

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

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

3.2 算法步驟

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

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

Step2:條件終止判斷。當定時時間到，或達到最大迭代次數(shù)，或最優(yōu)解重復(fù)達到指定次數(shù)，結(jié)束算法，轉(zhuǎn)Step6；否則對蟻群中的每只螞蟻，重復(fù)執(zhí)行以下步驟。

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

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

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

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

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

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

然后更新信息素，增加該次迭代中表現(xiàn)最好的螞蟻經(jīng)過路徑上的信息素濃度，信息素濃度更新規(guī)則如下:

(1)

Step6:輸出結(jié)果。

4 改進的MMAS算法步驟

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

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

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

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

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

(2)

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

(3)

得到文中算法2。

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

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

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

由此得到算法3。

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

end

5 實驗與結(jié)果

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

實驗結(jié)果如表1和表2所示。

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

表1 算法2的實驗結(jié)果對比

表2 算法3的實驗結(jié)果對比

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

6 結(jié)束語

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

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

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

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

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

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

[4] 趙燕偉，張景玲，王萬良.物流配送的車輛路徑優(yōu)化方法[M].北京：科學(xué)出版社，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īng)網(wǎng)絡(luò)解法[J].計算機集成制造系統(tǒng)，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].中國公路學(xué)報，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] 劉曉勇，付 輝.基于啟發(fā)式蟻群算法的VRP問題研究[J].計算機工程與應(yīng)用，2011,47(32):246-248.

[15] 張 錦，李 偉，費 騰.交叉變異蟻群算法在VRP問題中的應(yīng)用研究[J].計算機工程與應(yīng)用，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的配送線路規(guī)劃研究與應(yīng)用[D].濟南：山東大學(xué)，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-

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

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

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