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

何亞輝

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

1 引言

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

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

2 蟻群算法

2.1 基本思想

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

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

2.2 基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 信息素更新的改進(jìn)

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

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

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

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

3.3 節(jié)點(diǎn)選擇的改進(jìn)

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

圖1 節(jié)點(diǎn)示意圖

4 實驗分析

本文設(shè)計了一種基于MAKLINK圖論建立物流配送路徑網(wǎng)絡(luò)拓?fù)淠Ｐ停⒒诟倪M(jìn)蟻群算法構(gòu)建了配送路徑規(guī)劃方案。

本文的實驗內(nèi)容和目標(biāo)分為三部分。

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

圖2 構(gòu)建物流配送地圖

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

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

4.1 參數(shù)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 結(jié)果分析

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

圖8 算法比較

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

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

5 結(jié)語

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