面向電商終端物流配送路徑優(yōu)化的改進蟻群算法

（河北工業(yè)大學 經濟管理學院，天津 300401）

0 引言

物流“最后一公里”的終端對象是顧客，本質是物流服務鏈的終端配送。隨著網購市場的發(fā)展，電商物流終端配送問題日益凸顯。電商物流終端配送成本占整個電商系統(tǒng)物流配送成本的30%以上[1]。因此，科學規(guī)劃配送路徑能夠有效提高終端配送效率和服務水平，降低企業(yè)配送能耗和成本，提高經濟效益，增加行業(yè)競爭力。

電子商務物流終端配送問題可以抽象為車輛路徑問題。車輛路徑問題（Vehicle Routing Problem，VRP）由Dantzig和Ranser提出，并在管理科學、計算機科學、交通運輸?shù)阮I域受到廣泛關注[2]。車輛路徑問題一般定義為：對一系列發(fā)貨點和收貨點，組織適當?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、車輛容量限制等）下，達到一定的目標（如路程最短、費用最小等）[3]。當車輛路徑問題的規(guī)模較大時，精確求解路徑變得非常復雜，高效近似的優(yōu)化算法就成為最佳解決辦法[4]，其中常用的算法有節(jié)約算法[5]，遺傳算法[6,7]，蟻群算法等。

蟻群算法（Ant Colony Optimization，ACO）是由Dorigo Macro等人提出的一種模擬自然界中螞蟻集體尋徑行為的啟發(fā)式算法[8]，其提出之初就是為了解決路徑優(yōu)化問題，該算法具有魯棒性、可并行性和正反饋等特點[9]。因此，本文采用蟻群算法對配送路徑進行規(guī)劃。

許多學者將蟻群算法應用到求解車輛路徑問題中。秦效宏等設計了一個帶軟時間窗的改進蟻群算法求解物流訂單的配送問題[10]。程勇等提出了將貪婪算法和快速螞蟻算法相結合的混合算法求解車輛路徑問題，取得了較好的效果[11]。田鈞對蟻群算法中的信息素更新策略的選擇和狀態(tài)轉移規(guī)則與可見度進行改進，并用改進蟻群算法求解物流配送的問題[4]。葛斌等提出動態(tài)自適應蟻群優(yōu)化算法，解決最小最大車輛路徑問題[12]。劉艷秋基于路徑可行性與倉儲集貨運輸模式的回收車輛路徑設計方案，并根據(jù)問題的特點對傳統(tǒng)蟻群算法中編碼方式以及概率選擇操作方式進行改進，提出一種逆選擇操作蟻群算法[13]。粱承姬等采用基于節(jié)約算法和鄰域搜索的最大-最小蟻群系統(tǒng)對車輛路徑問題進行了求解，并用實例證明算法的有效性[14]。

在上述研究中，蟻群算法能夠較好的求解車輛路徑問題，并且具有較強的耦合性。然而，上述研究在求解效率方面大都沒有進行深入的研究與探討。在現(xiàn)實中算法效率和求解質量有著同等的重要意義[15]。尤其是在電子商務環(huán)境下，終端物流配送點需要同時為大量的顧客進行配送，現(xiàn)實問題的規(guī)模大大高于現(xiàn)有研究測試所用的數(shù)據(jù)規(guī)模。對于大規(guī)模的電子商務終端配送問題，現(xiàn)有方法的效率和質量受到挑戰(zhàn)。

為了解決大規(guī)模的電商終端物流配送路徑規(guī)劃耗時長和方案質量較差的問題，提出改進的蟻群算法。改進算法首先將臨近城市列表引入到最大-最小蟻群系統(tǒng)，提高搜索效率。臨近城市列表使螞蟻在更可能產生最優(yōu)解的路徑中進行搜索，加快了搜索速度；最大-最小蟻群系統(tǒng)限制信息素的范圍，避免算法陷入局部最優(yōu)，使得尋優(yōu)能力提高。最后，采用菜鳥網絡上海市的物流終端配送現(xiàn)實數(shù)據(jù)，對算法性能進行比較評價。結果表明，改進算法不僅提高了求解速度，還提高了最優(yōu)解的質量。而且，問題規(guī)模越大，算法改進效果越明顯。

1 物流配送路徑優(yōu)化問題的數(shù)學模型

設某物流公司有1個配送中心和n個客戶需求點需要送貨上門，配送中心有m輛載重為Q的車輛，n個客戶需求點的需求量為qi（1≤i≤n），客戶需求點之間以及客戶需求點和配送中心之間的距離為dij。每個客戶需求點只能由一輛車進行配送，每輛車都必須從配送中心出發(fā)并回到配送中心，且每輛車的載重量不能超過最大載重量Q。建立如下數(shù)學模型：

上述模型中，式(1)表示總行駛路徑最短為優(yōu)化目標；式(2)表示車輛的負載約束；式(3)表示每個客戶的運輸車輛僅有一輛車來完成；式(4)、式(5)表示到達和離開某一個客戶的車輛僅有一輛；式(6)表示車輛k經過客戶i與客戶j之間的路徑時xijk取值為1；否則為0；式(7)表示客戶i被車輛k服務時yik取值為1；否則為0。

2 改進蟻群算法

2.1 蟻群算法

蟻群算法引入如下符號：m為螞蟻數(shù)量；n為城市數(shù)目；τij表示城市i到城市j之間路徑的信息素強度；ηij表示城市i到城市j之間的期望程度，可根據(jù)啟發(fā)式算法具體確定，通常取值為1/dij。

最初，各條路徑上的初始信息素相等，設為τij（0）=C（C為常數(shù)），起始點為m只螞蟻的出發(fā)點，假設目前螞蟻處于城市i，則t時刻螞蟻k由城市i轉到城市j的概率如下：

式(8)中，α、β分別表示信息素和啟發(fā)式信息相對重要性的參數(shù)，通常設置α=1～2，β=2～5；allowedk表示允許螞蟻k巡游下一個城市的候選集合；禁忌表tabuk用于記錄螞蟻k當前走過的城市，tabuk隨著螞蟻在巡游城市過程中動態(tài)調整，tabuk={1，2，…，n}-allowedk。

經過t個時刻，每只螞蟻巡游完全部城市后，對已訪問路徑上的信息素進行更新，更新公式如下：

式(9)中，ρ為信息素的揮發(fā)速率，隨著時間的推移而衰減；為螞蟻k在城市i到城市j路徑中留下的信息量，計算方式如下：

式(10)中，Q表示信息強度，為常數(shù)；Lk表示螞蟻k在本次循環(huán)中所走路徑的總長度。

當所有螞蟻都完成一次巡游后, 每只螞蟻在本次巡游的禁忌表已滿，應及時清空，準備下一次巡游。當巡游次數(shù)達到設定值時算法結束。

2.2 最大-最小蟻群系統(tǒng)

最大-最小蟻群系統(tǒng)（Max-Min Ant System，MMAS）對基本蟻群算法進行以下更新：

1）與基本的蟻群信息素更新規(guī)則不同，MMAS沒有使用信息素局部更新規(guī)則，僅對每一次循環(huán)中的一只螞蟻所走過的路徑進行更新，這只螞蟻是當前的全局最優(yōu)解。信息素更新公式和信息增加量，如式(11)和式(12)：

2）為避免算法收斂于局部最優(yōu)解，將信息素的濃度限制在[τmin，τmax]之間，防止由于某條路徑上的信息素不斷積累而大于其他路徑，導致所有螞蟻全部集中到信息素大的一條路徑上。最大值、最小值可根據(jù)每次產生的最優(yōu)解進行動態(tài)更新，如式(13)和式(14)：

3）將信息素濃度的初始值設τmax，算法有更好的發(fā)現(xiàn)較優(yōu)解的能力。

2.3 臨近城市列表

針對傳統(tǒng)蟻群算法求解效率低，方案質量較差的問題，提出一種引入臨近城市列表的最大-最小蟻群系統(tǒng)（Near-city Max-Min Ant System, NMMAS）。臨近城市列表使螞蟻在更可能產生最優(yōu)解的路徑中進行搜索，加快了搜索速度；最大-最小蟻群系統(tǒng)限制信息素的范圍，避免算法陷入局部最優(yōu)，提高尋優(yōu)能力。

臨近城市列表是當螞蟻選擇下一目標城市時，在不違背車輛載重的約束條件下，首先考慮與當前城市距離最近的若干城市。只有當這些城市全部被訪問過時，才考慮其余的城市。這樣每一次選擇下一城市時搜索城市范圍變小，加快了算法的搜索速度。

應用臨近城市列表時，Cnear代表臨近城市列表，Ccur代表當前城市，代表當前城市的臨近城市列表。臨近城市列表的具體實現(xiàn)步驟如下：

步驟1：建立臨近城市列表Cnear，如下所示：

其中，行表示與當前城市距離最近的若干城市，按照dij升序排列。列的數(shù)量表示與當前城市最近的城市數(shù)量。例如，第二行表示距離city2由近到遠的五個城市依次為city8、city16、city1、city4、city9。

步驟2：當前城市Ccur為配送中心時，螞蟻按照式(8)在所有未巡游的城市中選擇下一城市；當前城市Ccur不為配送中心時，則選擇與當前城市Ccur距離最近的城市列表

2.4 改進蟻群算法NMMAS步驟

NMMAS算法步驟如下：

步驟1：定義參數(shù)和設置參數(shù)的變量值，設定的參數(shù)包括：螞蟻數(shù)m、迭代次數(shù)Nc、初始信息素τij(0)，信息素最大值τmax、信息素最小值τmin、信息素揮發(fā)率ρ和臨近城市列表Cnear。

步驟2：將m只螞蟻放置在配送中心。

步驟3：判斷螞蟻k是否在配送中心。如果在配送中心，則直接按照概率轉移公式(8)，找到螞蟻k要走的下一個城市j；否則，轉到步驟4。

步驟4：判斷螞蟻k當前所在城市i的臨近城市列表Cnear是否全部被訪問過。如果是，則在當前城市i的臨近城市列表之外的城市按概率轉移公式(8)，找到螞蟻k要走的下一個城市j；否則，在當前城市的臨近城市列表內的城市，按照概率轉移公式(8)，找到螞蟻k要走的下一個城市j。

步驟5：判斷螞蟻k走過的城市i和j之間路徑的總貨運量是否超過車輛的最大負載能力。若超過，則螞蟻k回到配送中心，然后從配送中心重新出發(fā)，轉到步驟3；否則，將禁忌表按照當前狀況進行修改，即將城市j置于禁忌表tabuk中。

步驟6：判斷禁忌表是否包含所有的城市。如果不是，則執(zhí)行步驟3至步驟5，直到第k只螞蟻找到一條包含所有城市的可行路徑。然后保存螞蟻k的可行路徑，并清空禁忌表。

步驟7：判斷螞蟻是否都找到可行路徑。若k>m，則轉到步驟8；否則執(zhí)行k=k+1，轉到步驟3。

步驟8：在全部螞蟻搜索到的可行路徑中找到最優(yōu)路徑Lbest，并按照全局信息素更新式(11)和式(12)進行更新。

步驟9：判斷Nc是否已經達到最大迭代次數(shù)。如果不是，則執(zhí)行NC=NC+1，轉到步驟2；否則停止運算，輸出當前值作為最短路徑。

NMMAS算法偽代碼如下：

3 實驗測試及結果分析

采用阿里巴巴旗下菜鳥網絡科技有限公司上海市物流終端配送的大規(guī)模真實數(shù)據(jù)進行算法測試。數(shù)據(jù)來自阿里巴巴天池大數(shù)據(jù)競賽，數(shù)據(jù)下載網址：https://tianchi.aliyun.com/competition。為保護用戶隱私，數(shù)據(jù)隱去客戶的地址信息，提供配送點和客戶點的經緯度。使用C#進行程序編寫，并在運行真實數(shù)據(jù)時調用百度地圖API。NMMAS的算法參數(shù)設置為：m=城市數(shù)量，

分別對蟻群算法(ACO)、最大-最小蟻群系統(tǒng)(MMAS)和所提出的NMMAS進行測試，采用菜鳥公司的5個配送網點的數(shù)據(jù)。配送網點服務客戶規(guī)模、最優(yōu)解及運行時間如表1所示。

由表1可知，隨著問題規(guī)模的擴大，ACO和MMAS的搜索時間迅速增加、方案質量下降。NMMAS方法能夠有效彌補現(xiàn)有方法的不足，相比ACO和MMAS具有更好的求解速度和尋優(yōu)能力。其具體的尋優(yōu)質量和求解速度效果提升如表2、圖1和圖2所示。

圖1 客戶規(guī)模與時間縮短量的關系

表1 ACO和MMAS與NMMAS測試結果比較

表2 NMMAS相比ACO和MMAS的效果提升

圖2 客戶規(guī)模與距離減少量的關系

由表2可知NMMAS在平均求解效率上相比ACO和MMAS分別縮短125425.624ms和126389.528ms；NMMAS在求解距離上相比ACO和MMAS分別減少13773.209m和6533.582m?？梢奛MMAS無論求解效率和求解質量相比于ACO和MMAS都有著顯著的提升。同時，結合圖1和圖2可知，隨著數(shù)據(jù)規(guī)模的增大，NMMAS的求解質量和求解效率提升更明顯。因此，NMMAS能夠有效的解決大規(guī)模電商終端物流配送路徑規(guī)劃耗時長和方案質量較差的問題。

NMMAS之所以能夠在時間效率方面有顯著提升，是因為螞蟻優(yōu)先在臨近城市列表內搜索下一個目標城市，搜索范圍和數(shù)量大大減少，從而計算量顯著降低。NMMAS在方案質量方面顯著提升的原因是螞蟻選擇下一目標城市時，優(yōu)先在可能產生最優(yōu)方案的臨近城市列表中進行搜索，減少了非優(yōu)方案的干擾。隨著問題規(guī)模的擴大，臨近城市列表中的城市數(shù)量與全部城市數(shù)量的差異急劇增加，臨近城市列表搜索的規(guī)模減少效果迅速提升，NMMAS的效果更加顯著。

4 結束語

電子商務終端配送點需要為大量顧客進行配送，配送路徑優(yōu)化問題規(guī)模大，現(xiàn)有算法的效果和效率不夠理想。針對這一問題，提出一種引入臨近城市列表的最大-最小蟻群系統(tǒng)。臨近城市列表使螞蟻在更可能產生最優(yōu)解的路徑中進行搜索，從而更有效地收斂到最優(yōu)解；最大-最小蟻群系統(tǒng)控制路徑中的信息素，避免算法陷入局部最優(yōu)。采用菜鳥網絡科技有限公司的五個配送點的真實數(shù)據(jù)對改進算法NMMAS進行比較測試。結果表明，隨著問題規(guī)模的擴大，ACO與MMAS的算法效率和尋優(yōu)能力顯著下降。與傳統(tǒng)的蟻群算法相比，本文提出的NMMAS在求解物流配送路徑問題中擁有更好的求解效率和尋優(yōu)能力，并且隨著問題規(guī)模的擴大，改進效果越明顯?？傊?，改進算法對于解決大規(guī)模的電商終端配送路徑規(guī)劃問題能夠取得令人滿意的效果。

[1]張錦,陳義友.物流“最后一公里”問題研究綜述[J].中國流通經濟,2015,(4):23-32.

[2]Fei T, Zhang L, Chen L, et al. A Fish Swarm Ant Colony Algorithm for the Vehicle Routing Problem[J].International Journal of Simulation-Systems, Science & Technology,2016,17(13).

[3]劉云忠,宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學報,2005,19(1):124-130.

[4]田鈞.基于改進蟻群算法的物流配送應用研究[J].制造業(yè)自動化,2013,35(16): 88-90.

[5]金成,閔嘉寧.供應鏈物流配送路徑優(yōu)化節(jié)約算法改進研究[J].制造業(yè)自動化,2014,36(1):86-89.

[6]曹文梁,康嵐蘭.基于遺傳算法的混合蟻群算法及其在TSP中的應用研究[J].制造業(yè)自動化,2011,33(2):91-93.

[7]王娟,鞏建平,馮蕾潔.一種改進的遺傳蟻群混合算法[J].制造業(yè)自動化,2014,36(3):78-80.

[8]Dhawan C, Nassa V K, Bhugra M.Review on Vehicle Routing Problem using Ant Colony Optimization[J].International Journal of Advanced Research in Computer Science,2014,5(6).

[9]袁亞博,劉羿,吳斌.改進蟻群算法求解最短路徑問題[J].計算機工程與應用,2016,52(6):8-12.

[10]秦效宏,黃光球,蔡建國.基于改進的蟻群算法求解物流訂單派送問題[J].科技管理研究,2010,30(24):111-114.

[11]程勇,王峻峰,李世其.物流車輛路徑問題的混合快速螞蟻算法[J].工業(yè)工程與管理,2007,12(4):15-19.

[12]葛斌,韓江洪,魏臻,程磊,韓越.最小最大車輛路徑問題的動態(tài)自適應蟻群優(yōu)化算法[J].模式識別與人工智能,2015,(10):930-938.

[13]劉艷秋,徐世達,張穎,李佳.考慮路徑可行性與倉儲集貨模式下的回收車輛路徑問題研究[J].中國管理科學,2016,24(12):98-107.

[14]梁承姬,崔佳誠,丁一.基于混合蟻群算法的車輛路徑問題研究[J].重慶交通大學學報(自然科學版),2016,35(3):94-99.

[15]饒衛(wèi)振,金淳.求解大規(guī)模CVRP問題的快速貪婪算法[J].管理工程學報,2014,(2):45-54.