基于改進蟻群算法的物流配送路徑優化研究

夏鵬+張瑋

摘要：本文首先通過對傳統蟻群算法在物流配送路徑優化問題中的研究，得出蟻群算法存在如收斂速度較慢、算法易陷于局部最優等缺點，進而對蟻群算法進行優化改進，使物流配送路徑優化研究得到更好的解決。

關鍵詞：蟻群算法 物流配送路徑 優化

一、引言

互聯網在不斷地發展，這一時代慢慢興起，網購逐漸走進我們的生活大當中。伴隨著網購而不斷興盛的就是物流行業。物流行業越來越繁榮，對物流配送路徑進行優化也顯得尤為重要，因為這直接關系到物流行業的成本控制、盈利水平及配送效率。調查顯示，目前在我們國家物流行業的總成本一半以上花費在運輸當中，這一項花費遠遠高于西方的一些發達國家。

在研究物流配送路徑的時候，我們常將其歸屬于組合優化，即是一個NP完全問題。研究過程中，針對路徑優化人們經常會用到諸如方案評價法、動態規劃法、遺傳算法等各類方法。不過就目前的一些研究而言，這些算法都存在著一定程度的缺點，并不是特別完美，比如遺傳算法局部搜索能力不強，蟻群算法容易呈現停滯征象，等等。現在的研究中，針對以往在物流配送路徑優化方面的一些算法進行改進完善，以便于原有算法的所存在的缺點和不足之處能夠得到彌補。

近些年來，受到生物進化展現出來的先進特點的啟發，部分學者研究發現了一些像遺傳算法、蟻群算法等的智能算法，并常常將這些算法運用到一些復雜優化問題中去。在進行物流配送路徑問題研究的時候，遺傳算法具有收斂到全局最優的優點，不過在描述所求問題的約束條件時，這一算法往往表現的不盡如人意，而物流配送路徑優化又是一種多約束問題。和遺傳算法一樣，蟻群算法也是一種隨機搜索算法，不過蟻群算法有其自身的優點，比如其能同時兼顧解的局部構造和整體性能， 適合用來求解具有復雜約束條件以及解的組成元素之間關聯性較強的優化問題。

二、蟻群算法與物流配送路徑問題

2.1 蟻群算法描述

蟻群算法（ant colony optimization， ACO）是由意大利的著名學者Marco Dorigo最先提出來的，它是一種隨機搜索算法。這種算法是受到螞蟻群體在尋找食物時探索路徑行為的啟發，它是對日常螞蟻群體進行較優路徑搜尋這一過程的模擬，蟻群中的每一只螞蟻分別獨自地在候選解空間中去搜索一個解，螞蟻會在每次搜索完成之后留下一些信息量在相應的解上面在。根據所選擇的解的性能的差異，螞蟻會有選擇的留下信息量，當解的性能較好的時候，螞蟻會留下較多的信息量，反之留下的信息量則會比較少，其中留下較多信息量的解也相應的更加容易被再次選擇。在剛開始執行算法的時候，每個解上面的信息量都是相同的，當算法不斷地往前推進，就相當于螞蟻不斷地尋找路徑，較優解上面留下來的信息量就會漸漸變多，這樣不同解上的信息量就逐漸被拉開，進而收斂得到最優解或者近似的最優解。

在解決物流配送路徑優化問題上，蟻群算法憑借其自身的優點表現出極其強大的作用。不過這種算法仍然在一定程度上存在著一些不足之處，例如收斂速度較慢、算法易陷于局部最優、各個參數的設置還建立在實驗和經驗的基礎上、理論支持不是特別的嚴謹等。

與神經網絡、遺傳算法等一些其他的優化算法相比，蟻群算法的優點體現在它具有正反饋、分布式計算、較強的魯棒性以及富于建設性的貪婪啟發式搜索等特點。蟻群算法的這些不同于其他算法的特點，使得一些更加復雜的問題在求解方面難度有所降低。

2.2 物流配送路徑問題描述

2.2.1 問題描述

針對物流配送問題，我們一般可以進行如下描述：為滿足某一配送目標，從物流配送中心發出若干車輛，選擇一條比較合適的的運輸路線，在滿足送貨量、時間窗、車輛數量、載重量、行駛里程等條件下，完成配送目標，要求對形式路線作出合理安排，使運輸總成本最小，并且還需要滿足下列各項約束條件：

（1）當配送中心為完成一次配送任務后從該中心發出一輛運輸車輛，運輸車輛在完成配送中心布置的任務之后重新返回到配送中心；

（2）各條線路上的運輸車輛的最大運輸量應該大于或等于該路徑上面各站點的一次配送需求量；

（3）每條配送路徑的長度需控制在運輸車輛單次配送的最大行駛距離以內；

（4）有且僅能有一輛運輸車給每一位客戶送貨。

2.2.2 數學模型

在建立蟻群算法數學模型之初，我們要考慮設計出一條最優的配送路線，該線路要滿足總的配送距離最短。現作出如下假設：某一區域有一個配送中心，該配送中心服務N個目標客戶，每個目標客戶的需求量為，從配送中心發出的運輸車輛的最大運輸量為G，定義二值函數如下：

根據假設作出如下數學模型：

（1）

（2）

2.3 蟻群算法在配送路徑問題中的應用描述

根據以上建立起來的蟻群算法，我們用車輛去替代螞蟻，從配送中心發出一輛車，為配送區域中的一個配送節點配送貨物，如果從配送中心發出的車輛的貨運量能夠達到需配送的配送節點的需求量，就對貨物進行配送，如否則返回配送中心重新裝貨，表示完成一次配送。從配送中心發出的一輛運輸車輛在一個配送過程中完成了相應的配送任務之后，對每一條配送路徑上的信息素進行更新。一趟任務接著一趟任務去完成，當每一輛從配送中心發出的車輛完成了各目標客戶的配送任務之后，表示一次迭代成功的完成了，比較其便利的路徑長度并保存最短路徑，然后進行下一次迭代。

三、蟻群算法的改進與優化

3.1 改進算法數學模型

在2.2節建立的數學模型的基礎上，結合實際的物流配送情況，對蟻群算法的數學模型進行改進與優化。優化之后的算法具體描述如下：

全局信息素更新規則：

基于增強螞蟻全局搜索能力的目的，使得收斂這一現象不要發生的太快，每一只螞蟻在相同的一條路徑上通過的時候會留下相應的信息素，這些信息素對其他螞蟻訪問該路徑有抑制作用。所以可以按照下述規則對t時刻在路徑（i，j） 上的信息素進行相應調整：

在（6）式中，我們用ρ表示信息素的持久化系數，其取值范圍為0到1；用 （t，n）表示螞蟻在第n次迭代后留在路徑（i，j）上的信息素增量；

∈[0，1]為一個系數； 的含義是完成一次迭代后，螞蟻

在前面n-1次迭代中在路徑（i，j）上留下的信息素增量之和；這樣

表示屬于前面迭代中螞蟻釋放信息素加權抑制因子。

式（7）中： 表示所有的螞蟻第 n 次迭代后在路徑（i，j） 上留下

的信息量的總和， 的取值采用蟻周系統模型，值為：

式（8）中：Lk表示的是第k只螞蟻完成一次循環過程經歷的總的路徑長度；Q表示信息素強度。

局部信息素更新規則：和蟻群算法相類似。在改進的蟻群算法當中，局部信息素更新的設置主要是為了根據路徑爬行次數與總次數的比值來對該路徑上信息素的大小進行進一步的控制，然后來對螞蟻選擇該路徑的概率進行影響。所以，當螞蟻從由區域i行駛到區域j時，

式（9）中：η表示的是前n-1次迭代所有螞蟻經過路徑（i，j）的次數比上前 n-1迭代參與搜尋的螞蟻總數得到的數值大小，（1-ξ）反應了路徑（i，j）的重要程度。ξ2（0<ξ2<1）是一個參數，而 路徑上信息素最初始的濃度。

3.2 改進后的算法流程

以TSP為例，采用蟻周系統模型。改進蟻群算法的主要步驟如下：

（1）對參數進行初始化設置。在剛開始運行算法的時候，給每一個參數設置一個初始值：迭代的次數為NC=0，最大的迭代次數是Ncmax，螞蟻數量為m，信息素強度初始值為Q，最小信息素強度為 ，最大信息素強度為 和 、 的參數值；

（2）把禁忌表清空，且NC=NC+1；

（3）根據式（1）的路徑選擇概率，將螞蟻從原始位置運輸到下一個城市，再對禁忌表進行修改，在該螞蟻的禁忌表中增加該城市；

（4）如果算法中的螞蟻是在第一次迭代中，就按照步驟（3）與（4）循環執行，如果不是，那么根據式（7）進行局部信息素更新，一直到該算法中每一只螞蟻都生成一條路徑為止。

（5）對第 k 只螞蟻通過的總路徑LK進行計算，當螞蟻是第一次迭代時，根據（2）式更新全局信息素，否則螞蟻根據式（ 8） 進行所有路徑上的全局信息素更新。

（6）當循環次數 時，結束該循環，輸出螞蟻走過的路徑，此時的路徑為最優路徑，若不滿足 ，則轉至步驟（2）。

參考文獻：

[1]王訓斌，陸慧娟，陳伍濤，張火明.改進蟻群算法在物流配送路徑中的應用[J].中國計量學院學報，2008，19（4）：342-346.

[2]段愛民，陳澤琳，陳海波.基于改進蟻群算法的物流配送路徑優化[J].計算機技術與發展，2011，21（12）：178-181.

[3]王睿.物流智能配送系統集成一體化探討[J].電子測試，2014，23（4）：72-74.

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

[5]張建民，恰汗·合孜爾，高大利.基于改進蟻群算法的物流配送路徑問題研究[J].計算機工程與科學，2010，7（1）：117-119.

安徽財經大學大學生創新創業訓練計劃資助項目編號201610378141