基于改進蟻群算法的物流配送路徑規劃算法?

何亞輝

（河南公路項目管理有限責任公司 鄭州 450045）

1 引言

路徑規劃是物流配送研究領域的熱點問題［1］。物流配送路線規劃的本質是在已知的道路網拓撲結構中，從初始點到結束點規劃出合理路線的最優路徑規劃問題［2］。如何快速、有效地規劃出最優路徑具有重要意義。目前，基于最短路徑的搜索方法已經不能滿足實際物流配送的需求，而基于最優路徑的規劃不僅要求尋找最短路徑，而且還要求嚴格的實時性［3］。在路徑規劃過程中，從應用的角度來看，合理規劃路線并提高計算響應速度顯得尤為重要。大量的專家學者對物流配送路線規劃問題進行了深入的研究。如何及時規劃出合理的路徑對于研究問題具有非常現實的意義。關于路徑規劃算法的研究很多，如遺傳算法［4］、粒子群算法［5］、神經網絡［6］、圖論［7］和群體優化［8］。文獻［9］利用網格法對物流配送的運輸環境進行建模，將蟻群算法應用于路徑規劃，并且結果表明蟻群算法能夠很好地求解路徑規劃問題。

鑒于蟻群算法具有分布式計算和啟發式搜索等諸多優點，本文將蟻群算法與物流配送路徑規劃有效結合，在分析蟻群算法原理的基礎上，建立了針對物流配送的路徑規劃模型，提出了改進的蟻群算法來進行更合適的路徑規劃。

2 蟻群算法

2.1 基本思想

蟻群算法是一種用來尋找優化路徑的概率型算法，它來源于螞蟻搜索食物問題的研究［10］。該算法不僅是一種自適應的分布式算法［11］，而且也是一種隨機搜索算法［12］。螞蟻在覓食的過程中通過遺留在路徑上的化學物質完成溝通與合作，這種化學物質稱為信息素。信息素越強，對應的路徑距離越短。當路徑信息素濃度較高時，螞蟻發現該路徑的概率越大，同時，經過該路徑的其他螞蟻也會釋放一定量的信息素來增強該路徑信息素的濃度，從而構成了一種學習信息的正反饋現象。在這種積極反饋的作用下，蟻群最終將找到從巢穴到食物源的最佳路徑。然而，生物學家發現隨著時間的推移，路徑上信息素的濃度將逐漸衰減。

蟻群算法求解最優化問題的基本步驟是：將螞蟻行走路徑視為最優化問題的可行解，所有路徑上的蟻群組成最優化問題的解空間。信息素在短徑路中的釋放量較多，隨著時間的推移，信息素在短徑路中的積累量逐漸增加，越來越多的螞蟻會選擇這些短徑路。最終，螞蟻在正反饋的作用下會聚焦在最佳路徑上。

2.2 基本原理

在不失一般性的前提下，假設整個蟻群的螞蟻數量為m，道路網絡拓撲的節點數為n，道路節點i和節點j之間的距離為dij（i，j=1，2，…，n），在t時刻，節點i和節點j之間的信息素濃度為τij(t)，每個道路節點中的每個信息素濃度在初始時間內設置為τij(0)=τ0。

第k個螞蟻根據道路節點上的信息素濃度決定下一個選擇節點，假設(t)表示螞蟻在t時刻從節點i移動到節點j的概率，則其計算公式為

其中，τij(t)表示在t時刻節點i到節點j之間的信息素濃度，它隨著時間的推移逐漸衰減；ηij(t)表示道路節點i和節點j的路徑期望，并與距離dij的倒數相對應，它代表了一種引導更好路徑的局部啟發式信息；α表示信息素濃度τij(t)的因子，該值可通過實驗進行調整；β表示路徑期望ηij(t)的因子，該值也可通過實驗進行調整；Ak(t)表示在t時刻螞蟻移動到下一個節點的集合，由于螞蟻的移動根據信息素濃度的變化，所以該值呈現動態變化。假設在n時刻，螞蟻完成從起始點到結束點的路徑搜索，則信息素濃度的更新公式為

其中，ρ為常數，τij表示路徑中節點i到節點j的信息素濃度變化，其可表示為

其中，表示第k個螞蟻從節點i到節點j所釋放的信息素濃度。

3 改進蟻群算法求解路徑規劃

本文將通過MAKLINK圖論［13］建立物流配送路徑規劃模型并對路徑網絡拓撲進行初始化，由MAKLINK圖中的幾條MAKLINK線生成物流配送路徑規劃可行區域。其中，MAKLINK線可以表示相鄰物流集散地之間的連接線。

3.1 鏈路節點的劃分

在MAKLINK圖論中，利用Dijkstra算法［14］規劃出次優路徑S，P1，P2，…，Pd，T，Li(i=1，2，…，d)是與節點對應的自由鏈路線。假設和是Li的兩個端點，則其他節點可以表示為

其中，hi表示尺度參數，d表示鏈路劃分中的節點數。式（4）表明，Dijkstra算法可通過鏈路線得到初始路徑，只要定義一組參數(h1，h2，…，hd)，就可以從初始點到結束點獲得一條新的路徑，因此，蟻群算法的目標是求解(h1，h2，…，hd)中的最佳參數。

在使用蟻群算法之前，還需要對道路空間進行離散處理。由于路徑初始規劃的自由鏈路線選擇，其鏈路線的長度各不相同，本文采用基于固定距離分類的鏈路分割方法［15］，假設鏈路線L的長度為ξ，則其分隔編號為

如果Int(Li/ξ)為奇數，則πi加1后的中點也是路徑點，考慮到鏈路線Li按照πi劃分，則鏈路線Li-1到達鏈路線Li具有πi+1條路線可供選擇。

本文采用蟻群算法得到路徑參數集合(h1，h2，…，hd)，目的是在離散道路空間中找到最短路徑。假設有m個螞蟻從起始點S到結束點T構成環形路徑：S→n1j→n2j→…→ndj→T。其中，ndj表示位于鏈路線d中位置j的路徑點。隨著每個螞蟻的移動，螞蟻從鏈路線Li到鏈路線Li-1選擇節點j的規則為

其中，I表示鏈路線中的路徑點，q表示［0，1］之間的隨機參數，q0表示［0，1］中的可調參數，τi，k表示關于信息素的啟發值。

對于節點j的計算方法，首先計算從鏈路線節點i到下一個節點j的選擇概率Pi，j，然后使用輪盤賭選擇下一個節點j，其中選擇概率Pi，j為

3.2 信息素更新的改進

本文所改進的信息素更新包括實時信息素更新和路徑信息素更新。其中，實時信息素更新要求每個螞蟻必須在選擇節點之后更新節點信息素，即：

其中，τ0是信息素的初始值，ρ表示信息素的揮發因子，且其值為［0，1］的可調參數。

當所有螞蟻從初始點移動到結束點時，即可完成迭代搜索過程。為了在所有螞蟻移動到結束點時所選擇的路徑長度最短，還應更新每條道路上的路徑信息素：

其中，Δτi，j=1/L*，L*表示最短路徑的長度。

3.3 節點選擇的改進

當螞蟻搜索節點pi-1到下一個節點pi時，傳統的蟻群算法是根據信息素和距離從所有可選節點pi=(pi1，…，pim)中計算螞蟻移動到下一個節點的概率。每個節點選擇都是為了減少從當前節點到結束點的總長度。因此，本文在選擇節點pi-1到下一節點pi時，起始點與結束點之間的最短連線穿過所有可選節點(pi1，…，pim)構成的鏈路線，通過比較最短連線與鏈路線所構成的最大夾角來選擇下一節點pi，如圖1所示。在本文中，將使用此方法來查找下一個節點pi。

圖1 節點示意圖

4 實驗分析

本文設計了一種基于MAKLINK圖論建立物流配送路徑網絡拓撲模型，并基于改進蟻群算法構建了配送路徑規劃方案。

本文的實驗內容和目標分為三部分。

1）在Matlab編程環境下構建物流配送運輸環境的仿真模擬地圖：假設起始點S到結束點T必須經過四個大型山脈，為了降低物流運輸成本，運輸車輛應盡可能地避免爬行山路，因此，所規劃的物流配送路徑需繞過這些山脈。所構建的物流配送地圖及具體坐標信息如圖2所示。

圖2 構建物流配送地圖

2）在Matlab編程環境下，對比各種參數的不同數值對改進蟻群算法迭代計算路徑規劃的性能影響，在對比參數不同數值前，先固定其他參數數值保持恒定，從而逐一確定改進蟻群算法計算過程中的參數尋優。

3）在Matlab編程環境下，對改進的蟻群算法和傳統蟻群算法的物流配送路徑規劃結果進行性能分析，并且各自生成路徑規劃結果，驗證本文提出的改進算法的有效性。

4.1 參數分析

1）螞蟻數量對路徑的影響

為了討論螞蟻數量對最優路徑的影響，本文分析了六組不同的螞蟻數量，圖3給出了當螞蟻數量m分別選擇5、10或15時，隨著螞蟻數量的增加所規劃的最短路徑將逐漸減少。

圖3 螞蟻數量為5、10和15時的影響

相反，為了更細致地觀察m=15、20和30時，隨著螞蟻種數的增加所規劃的最短路徑的波動變化，本文單獨繪制m=15、20和30時的路徑總長度變化，如圖4所示。隨著螞蟻種數的增加所規劃的最短路徑將逐漸增大。因此，當m=15時，所提出的改進蟻群算法可以進行最優路徑規劃。

圖4 螞蟻數量為15、20和30時的影響

2）信息素濃度因子對路徑的影響

圖5表明，當信息素濃度因子α=1或2時，路徑規劃總長度的差異并不明顯，但當α=1時，路徑規劃的收斂速度明顯快于α=2，因此本文最后選擇α=1作為信息素濃度因子參數。

圖5 信息素濃度因子對路徑的影響

3）路徑期望因子對路徑的影響

圖6表明，當路徑期望因子β=1時，路徑規劃的結果并不穩定。相反，當路徑期望因子β=2時，路徑規劃結果較為穩定。因此，本文選擇β=2作為路徑期望因子，它在計算過程中可以得到比其他路徑期望因子更穩定的路徑規劃效果。

圖6 路徑期望因子對路徑的影響

4）信息素揮發因子對路徑的影響

圖7表明，當信息素揮發因子選擇ρ=0.1時，隨著迭代次數的增加最短路徑逐漸收斂，當ρ=0.2或0.3時，路徑規劃結果隨著迭代次數的增加而產生較大波動。因此，本文選擇ρ=0.1可以進行更為理想的路徑規劃。

圖7 信息素揮發因子對路徑的影響

4.2 結果分析

本文選取了最優計算參數進行物流配送路徑規劃：螞蟻數量為m=15，信息素濃度因子為α=1，路徑期望因子為β=2，信息素揮發因子為ρ=0.1，迭代次數為500。圖8給出了改進蟻群算法和傳統蟻群算法的性能比較。

圖8 算法比較

圖8表明改進的蟻群算法比傳統蟻群算法具有收斂效果。且傳統蟻群算法計算的物流配送路徑規劃最優距離為205.5889km，而改進后的蟻群算法路徑規劃最優距離為194.5734km。圖9給出了改進的蟻群算法和原始蟻群算法共同規劃的路徑。其中，實線代表采用改進的蟻群算法進行最優路徑規劃，虛線代表采用原始蟻群算法。結果表明，改進后的蟻群算法比傳統蟻群算法可以規劃出更好的物流配送路徑。

圖9 路徑規劃結果

5 結語

本文將改進的蟻群算法應用于物流配送路徑規劃問題，運用MAKLINK圖論建立物流配送路徑規劃模型，選取Dijkstra算法作為初始規劃算法并得到初始路徑尺度參數，以此來確定蟻群算法的尋優目標函數。并對蟻群算法的信息素更新和節點選擇進行了改進，通過該改進算法可以規劃出從起始點到結束點的最優路徑。通過與傳統蟻群算法的仿真比較，結果表明，改進后的蟻群算法比傳統蟻群算法具有更好的路徑規劃性能。