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

何亞輝

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

1 引言

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

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

2 蟻群算法

2.1 基本思想

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

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

2.2 基本原理

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

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

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

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

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

3 改進蟻群算法求解路徑規(guī)劃

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

3.1 鏈路節(jié)點的劃分

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

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

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

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

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

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

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

3.2 信息素更新的改進

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

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

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

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

3.3 節(jié)點選擇的改進

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

圖1 節(jié)點示意圖

4 實驗分析

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

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

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

圖2 構建物流配送地圖

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

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

4.1 參數(shù)分析

1）螞蟻數(shù)量對路徑的影響

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

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

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

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

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

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

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

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

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

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

4）信息素揮發(fā)因子對路徑的影響

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

圖7 信息素揮發(fā)因子對路徑的影響

4.2 結果分析

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

圖8 算法比較

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

圖9 路徑規(guī)劃結果

5 結語

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