CVRP物流配送路徑優(yōu)化及應(yīng)用研究

袁文濤　孫紅

摘 要：車輛行駛路徑優(yōu)化問題是智能安全交通網(wǎng)絡(luò)的重要組成部分。針對傳統(tǒng)車輛路徑求解搜索時間過長、得不到最優(yōu)解、求解質(zhì)量不高的現(xiàn)況，在研究一般物流配送路徑問題處理方法和數(shù)學(xué)模型的基礎(chǔ)上，提出了一種改進的蟻群算法求解問題以提高構(gòu)建路徑的速度和質(zhì)量，在限量車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）中用改進的蟻群算法來優(yōu)化求解車物流的配送路徑。通過MATLAB仿真結(jié)果表明，蟻群算法搜索速度相對較快，具有良好的全局求優(yōu)能力，收斂結(jié)果表明可以準(zhǔn)確求出最優(yōu)路徑，相比傳統(tǒng)方案，優(yōu)化后解的質(zhì)量得到了提高，速度提高了80%左右，是一種可行性較高的求解物流配送路徑優(yōu)化問題的有效算法。

關(guān)鍵詞：蟻群算法；物流配送；路徑優(yōu)化；數(shù)學(xué)模型

DOIDOI：10.11907/rjdk.161974

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2016）011014004

基金項目基金項目：

作者簡介作者簡介：袁文濤（1993-）男，安徽馬鞍山人，上海理工大學(xué)光電信息與計算機工程學(xué)院碩士研究生，研究方向為模式識別與智能系統(tǒng)；孫紅（1964-）女，上海人，上海理工大學(xué)光電信息與計算機工程學(xué)院副教授、碩士生導(dǎo)師，研究方向為模式識別與智能系統(tǒng)、 控制理論與控制工程、企業(yè)信息化系統(tǒng)與工程。

0 引言

解決組合優(yōu)化問題的最優(yōu)化求解算法有多種現(xiàn)代人工智能算法方案，優(yōu)化算法用來處理問題最優(yōu)解的求解，該問題通常由多個變量共同決定。當(dāng)前，求解最短路徑問題是圖論研究中的一個典型求解組合優(yōu)化算法問題，旨在尋找圖表（由節(jié)點和路徑構(gòu)成）中兩節(jié)點或多節(jié)點之間的最短路徑。常用的最優(yōu)化路徑求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蟻群算法。這些算法都有自身的優(yōu)點和不足。在對不同算法作出比較后，可以得出蟻群算法在解決網(wǎng)絡(luò)路由和城市交通系統(tǒng)的問題中是相對有利的。

就目前研究來看，隨著實際組合問題的變化，基本的智能算法已經(jīng)不能滿足解決這類組合優(yōu)化問題，同時其優(yōu)勢也在減弱[1]。本文采取改進后的組合優(yōu)化蟻群算法以彌補傳統(tǒng)蟻群算法易陷入局部最優(yōu)解的不足，加快了求全局最優(yōu)解的構(gòu)造速率。

蟻群算法（Ant Colony Optimization， ACO），是一種模擬螞蟻群體智能行為的進化仿生類優(yōu)化算法，在求解性能上具有強魯棒性、優(yōu)良的分布式計算能力、便于與其它算法相結(jié)合等優(yōu)點[2-3]。通常作為一種用來在多變量組合優(yōu)化問題的多候選解中尋找最優(yōu)化路徑的機率型算法。它由Marco Dorigo于1992年在其博士論文《Ant system： optimization by a colony of cooperating agents》中首先提出，其靈感來源于通過對蟻群社會的長期跟蹤觀察后發(fā)現(xiàn)，雖然單個螞蟻沒有視力、智慧程度低、工作方式簡單，但它們卻有強大的執(zhí)行能力和協(xié)同工作能力，依靠復(fù)雜群體的自組織協(xié)同能力發(fā)揮出超出單個個體累加的智能，是一種超個體（superorganism，又稱超有機體）存在現(xiàn)象。蟻群是在這樣的超個體案例中最有名的例子。雖然蟻群算法的嚴(yán)格理論基礎(chǔ)和實際應(yīng)用尚未成熟，國內(nèi)外相關(guān)研究暫處于實驗階段，但這并不妨礙人們對蟻群算法的研究已經(jīng)由當(dāng)初單一的解決商旅問題（TSP）發(fā)展到解決調(diào)度問題、網(wǎng)絡(luò)通信等多個方向的最優(yōu)化求解應(yīng)用。

目前，蟻群優(yōu)化算法已廣泛應(yīng)用于多種求組合最優(yōu)化問題，在面臨路例如作業(yè)安排調(diào)度問題和路由車輛的二次分派問題上表現(xiàn)出了良好的性能，也經(jīng)常被用來求旅行推銷員問題的擬最優(yōu)解。它在圖表動態(tài)變化情況問題的求解上相比螢火蟲算法和遺傳算法具有絕對優(yōu)勢：蟻群算法的最大優(yōu)點在于可以連續(xù)運行并適應(yīng)實時變化；缺陷是在處理較大規(guī)模和復(fù)雜數(shù)據(jù)問題時，容易存在運算耗時長、收斂速度慢、得不到全局最優(yōu)解等問題。

在求最優(yōu)解的歷次迭代中，單個螞蟻會根據(jù)給定的規(guī)則和限定條件選擇從一個城市（節(jié)點）轉(zhuǎn)移到另一個城市（節(jié)點）：它必須對所有城市訪問一次，而相對距離越遠(yuǎn)的城市被選中為下一個訪問點的機會越少（能見度低）；相反，在兩個城市（節(jié)點）邊際的一邊形成的信息素越濃烈，則該邊際作為路徑被選擇的概率越大；在較短路程情況下，短時間內(nèi)更多螞蟻會在所有走過的路徑上留下更多信息素，在每次迭代更新后，信息素軌跡濃度會按百分比揮發(fā)從而反饋給下一只途經(jīng)的螞蟻并影響它作出路徑選擇。

1 車輛路徑問題

傳統(tǒng)的車輛路徑問題也叫VRP（Vehicle Routing Problem）問題，是關(guān)系到現(xiàn)代物聯(lián)網(wǎng)發(fā)展過程中物流配送系統(tǒng)的一個關(guān)鍵問題，屬于NP難題。一直以來，該問題也是管理科學(xué)和物流運輸方面的重要課題[4]，受到國內(nèi)外學(xué)者的廣泛關(guān)注。

VRP問題描述如下：在一些由于經(jīng)濟或者地理限定的條件約束下，組織一個車隊，從一個或者多個初始點出發(fā)，規(guī)定達(dá)到多個不同的地點，設(shè)計一個成本最小、路程最短的路線集，使得：① 每個城市只能被一輛車訪問，只訪問一次；②所有送貨車輛必須從起始點出發(fā)再回到起始點；③某些特定的約束條件需要被滿足。

VRP的數(shù)學(xué)模型表示如下：一共有k個客戶，第i個客戶的貨物需求為gi，配送中心派出車輛承擔(dān)運輸任務(wù)，其載重為q。設(shè)gi

如果前提有約束條件用于車輛本身，即容量限制和總長限制，則稱為有能力約束的車輛路徑問題（Capacitated Vehicle Routing Problem）。此模型是車輛路徑問題的基本模型，這類VRP問題叫作CVRP問題[5]。

設(shè)每個客戶點只允許被訪問一次，車輛所訪問的客戶點的需求總和不能超過車輛的負(fù)載能力，且總行駛的路程也不得超過其最大的行駛距離，達(dá)到用最少的車輛最短的路徑完成既定任務(wù)。

。

2 可約束蟻群算法實現(xiàn)

2.1 算法實現(xiàn)方式

當(dāng)前蟻群算法領(lǐng)域存在MPDACO局部更新和MPDACO全局更新兩種方式。前者指當(dāng)單個螞蟻從一個節(jié)點到達(dá)下一個節(jié)點完成轉(zhuǎn)移后就立刻更新螞蟻通過路徑時所留下的的信息素，后者是當(dāng)螞蟻遍歷完所有給定節(jié)點后再更新整條路徑上的信息素，不再是對所有的螞蟻，而是僅對全局最優(yōu)的螞蟻得到的路徑使用。從兩種更新方式得到的結(jié)果作對比可以得出，全局信息素更新方法雖然可以加快收斂速率，但是存在著一定的缺陷和不足，易使路徑更快地集中于單一解，易陷入局部最優(yōu)，這些缺點限制了它的廣泛傳播及應(yīng)用。

本文綜合上述兩種更新方法的優(yōu)點和不足，列出了一種新的組合疊加更新方法：在路徑搜索的前十次循環(huán)中，采用局部最優(yōu)解更新，十次固定循環(huán)結(jié)束后，再采用全局最優(yōu)解進行更新，這種更新方式可以有效避免蟻群搜索得到的路徑沉入局部最優(yōu)解中，有利于發(fā)現(xiàn)更多較優(yōu)解。

2.2 算法實現(xiàn)步驟

根據(jù)改進的蟻群算法，將優(yōu)化后的蟻群算法應(yīng)用于CVRP問題的實現(xiàn)步驟如下：

（1）參數(shù)初始化。設(shè)迭代次數(shù) Nc=0；每條路徑上的信息素濃度Δτij（0）=c（c為常數(shù)），并且Δτij=0；隨機將m個螞蟻放置到初始點上。

（2）更新迭代（循環(huán)）次數(shù)，即Nc=Nc+1。

（3）初始化禁忌表，螞蟻禁忌表的索引號k=1。

（4）更新螞蟻數(shù)目k=k+1。

（5）判斷路徑是否在搜索熱區(qū)內(nèi)。按照式（a）～（f）計算出每只螞蟻應(yīng)當(dāng)轉(zhuǎn)移至下一個城市（節(jié)點）的概率并完成移動。

（6）當(dāng)螞蟻從i城市（節(jié)點）出發(fā)到達(dá)j城市（節(jié)點）時，對其所經(jīng)過的路徑上的信息素進行更新，并修改禁忌表，將禁忌表指針按照當(dāng)前狀況進行修改，即將新城市（節(jié)點）j置于禁忌表tabuk中。

（7）執(zhí)行步驟（b）～（f），直到所有螞蟻都找到了一條包含所有城市（節(jié)點）的可行路徑解。

（8）在新生成的所有可行解中找到一條最短路徑作為本次迭代中的最優(yōu)路徑解。

（9）判斷循環(huán)次數(shù)是否小于十次，若小于十次，則對螞蟻找到的最優(yōu)路徑按照本次迭代最優(yōu)值進行信息素更新；若循環(huán)次數(shù)超過十次，則按照全局信息素進行更新。

（10）對所有螞蟻經(jīng)過的路徑，按式（1）進行一次全局更新。

（11）循環(huán)執(zhí)行（b）～（j），直到連續(xù)多次的迭代中得到的解已收斂或循環(huán)次數(shù)Nc的值已經(jīng)達(dá)到給定的最大迭代次數(shù)的情況下選取當(dāng)前輸出值作為本次最優(yōu)解。

3 實驗仿真

設(shè)存在一個物流中心有4輛運輸車， 單輛車最大載重為1 000kg， 現(xiàn)需要同時向7個隨機分布的客戶點派送貨物， 蟻群算法的初始化參數(shù)為： 螞蟻總數(shù)為20只， 算法的最大迭代數(shù)為100次， α和β分別為1，2， 信息素的揮發(fā)速度為0.75， 實驗重復(fù)運行100次， 求得的平均結(jié)果為最終結(jié)果。同時初始時刻各邊上的信息痕跡為1，殘留信息的相對重要度為1，設(shè)置預(yù)見度為5。原始數(shù)據(jù)進行處理結(jié)果分析如圖3所示。按本文提出的優(yōu)化蟻群算法求解CVRP后的處理仿真結(jié)果如圖4所示。

觀測圖3、圖4的收斂曲線，可以知道蟻群算法優(yōu)化后的結(jié)果相比之前的行車路徑有大幅度優(yōu)化[810]，如圖5所示。針對每個收斂的點結(jié)合數(shù)據(jù)可以看出，傳統(tǒng)蟻群算法的平均路徑在迭代次數(shù)為45時可以得到最優(yōu)解，而改進后的蟻群算法可以在第5次左右得到最優(yōu)解，相當(dāng)于收斂速度提高了近80%。

4 結(jié)語

在當(dāng)今應(yīng)用數(shù)學(xué)和理論計算機科學(xué)的領(lǐng)域中，組合優(yōu)化（Combinatorial Optimization）是在一個有限的對象集中找出最優(yōu)對象的一類重要課題，屬于運籌學(xué)的一個重要分支。在很多組合優(yōu)化問題中，窮舉搜索/枚舉法是不可行的。組合優(yōu)化問題的特征為可行解的集是離散或者可以簡化到離散的，并且目標(biāo)是找到最優(yōu)解。解決組合優(yōu)化問題一般采用智能算法，而這些算法都有自身的優(yōu)點和缺點。組合優(yōu)化的難處，主要是加進來拓?fù)浞治?，在不同的拓?fù)湫螒B(tài)下，算法也需隨著不同部分的約束關(guān)系作出相應(yīng)調(diào)整。從目前研究來看，隨著實際組合問題的變化，基本的智能算法已不能解決這類組合優(yōu)化問題。

蟻群算法作為一種仿生類進化算法在求路徑最優(yōu)化解方面具有很好的效果。本文首先引出蟻群算法可以用于解決這一類問題，然后介紹了約束車輛路徑問題，也即CVRP問題，說明了其約束模型；接著研究了基本的蟻群算法步驟，并對其中信息素更新和改進了啟發(fā)因子，解析并改良了蟻群算法應(yīng)用于CVRP問題的實現(xiàn)步驟和處理方法。

本文提出的組合疊加更新方法可有效克服傳統(tǒng)蟻群算法收斂質(zhì)量低、耗時長、易陷入局部最優(yōu)解等缺陷，使蟻群算法的全局優(yōu)化能力得到大幅度提高。對比實驗前數(shù)據(jù)可以看出，蟻群算法找到最短路徑的收斂速度比傳統(tǒng)方法快了80%左右，確實是一種求解最短物流配送路徑的有效算法。

參考文獻(xiàn)：

[1] 陳昌敏.基于蟻群算法的物流配送路徑優(yōu)化研究與應(yīng)用[D].成都：西華大學(xué)，2012（4）：1154.

[2] 宋留勇，王銳，周永旺，等.動態(tài)城市交通網(wǎng)絡(luò)優(yōu)化模型研究及算法設(shè)計[J].測繪科學(xué)，2011，36（1）：134136.

[3] 鐘石泉，賀國光.有時間窗約束車輛調(diào)度優(yōu)化的一種禁忌算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14（6）：523527.

[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.

[5] 楊中秋，張延華.改進蟻群算法在交通系統(tǒng)最短路徑問題的研究[J].科學(xué)計算與信息處理，2009，32（8）：7678.

[6] 李松，劉興，李瑞彩.基于混合禁忌搜索算法的物流配送路徑優(yōu)化問題研究[J].鐵道運輸與經(jīng)濟， 2007， 29（3）：66 69.

[7] 陶波， 朱玉琴.改進的7動態(tài)規(guī)劃法在車輛最短路徑問題中的應(yīng)用[J].重慶工學(xué)院學(xué)報， 2009，23（1）：2427.

[8] 李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社， 2001：101113.

[9] 張萬旭，林健良，楊曉偉.改進的最大最小螞蟻算法在有時間窗車輛路徑問題中的應(yīng)用[J].計算機集成制造系統(tǒng)，2005，11（4）：572576.

[10] 余玥，胡宏智.基于改進遺傳算法的物流配送路徑求解[J].計算機技術(shù)與發(fā)展，2009，19（3）：5255.

[11] 朱慶保，蟻群優(yōu)化算法的收斂性分析[J]. 控制與決策，2006，21（7）：3016.

[12] 鄭松，侯迪波，周澤魁，動態(tài)調(diào)整選擇策略的改進蟻群算法[J].控制與決策，2008，23（2）：13.

[13] 夏亞梅，程渤，陳俊亮，等.基于改進蟻群算法的服務(wù)組合優(yōu)化[J].計算機學(xué)報，2012，35（2）：311.

[14] 曹慶奎，趙斐，基于遺傳蟻群算法的港口集卡路徑優(yōu)化[J].系統(tǒng)工程理論與實踐，2013，33（7）：182009.

[15] 侯媛彬，高陽東，鄭茂全，等.遺傳算法的混合軌跡加工走刀空行程路徑優(yōu)化[J].機械工程學(xué)報，2013，49（21）：153.

（責(zé)任編輯：孫 娟）