CVRP物流配送路徑優化及應用研究

袁文濤　孫紅

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

關鍵詞：蟻群算法；物流配送；路徑優化；數學模型

DOIDOI：10.11907/rjdk.161974

中圖分類號：TP319

文獻標識碼：A 文章編號文章編號：16727800（2016）011014004

基金項目基金項目：

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

0 引言

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

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

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

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

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

1 車輛路徑問題

傳統的車輛路徑問題也叫VRP（Vehicle Routing Problem）問題，是關系到現代物聯網發展過程中物流配送系統的一個關鍵問題，屬于NP難題。一直以來，該問題也是管理科學和物流運輸方面的重要課題[4]，受到國內外學者的廣泛關注。

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

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

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

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

。

2 可約束蟻群算法實現

2.1 算法實現方式

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

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

2.2 算法實現步驟

根據改進的蟻群算法，將優化后的蟻群算法應用于CVRP問題的實現步驟如下：

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

（2）更新迭代（循環）次數，即Nc=Nc+1。

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

（4）更新螞蟻數目k=k+1。

（5）判斷路徑是否在搜索熱區內。按照式（a）～（f）計算出每只螞蟻應當轉移至下一個城市（節點）的概率并完成移動。

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

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

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

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

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

（11）循環執行（b）～（j），直到連續多次的迭代中得到的解已收斂或循環次數Nc的值已經達到給定的最大迭代次數的情況下選取當前輸出值作為本次最優解。

3 實驗仿真

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

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

4 結語

在當今應用數學和理論計算機科學的領域中，組合優化（Combinatorial Optimization）是在一個有限的對象集中找出最優對象的一類重要課題，屬于運籌學的一個重要分支。在很多組合優化問題中，窮舉搜索/枚舉法是不可行的。組合優化問題的特征為可行解的集是離散或者可以簡化到離散的，并且目標是找到最優解。解決組合優化問題一般采用智能算法，而這些算法都有自身的優點和缺點。組合優化的難處，主要是加進來拓撲分析，在不同的拓撲形態下，算法也需隨著不同部分的約束關系作出相應調整。從目前研究來看，隨著實際組合問題的變化，基本的智能算法已不能解決這類組合優化問題。

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

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

參考文獻：

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

[2] 宋留勇，王銳，周永旺，等.動態城市交通網絡優化模型研究及算法設計[J].測繪科學，2011，36（1）：134136.

[3] 鐘石泉，賀國光.有時間窗約束車輛調度優化的一種禁忌算法[J].系統工程理論方法應用，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] 楊中秋，張延華.改進蟻群算法在交通系統最短路徑問題的研究[J].科學計算與信息處理，2009，32（8）：7678.

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

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

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

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

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

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

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

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

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

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

（責任編輯：孫 娟）