改進(jìn)蟻群算法在車輛路徑優(yōu)化問題中應(yīng)用

代婷婷

(昭通學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院 云南 昭通 657000)

隨著全球經(jīng)濟(jì)和互聯(lián)網(wǎng)的飛速發(fā)展，物流產(chǎn)業(yè)已成為國民經(jīng)濟(jì)的重要組成部分。但是我國物流發(fā)展存在成本高、效率低的問題。物流配送環(huán)節(jié)是物流行業(yè)的一個重要環(huán)節(jié)，優(yōu)化物流配送路徑是降低物流運(yùn)輸成本、促進(jìn)物流發(fā)展的關(guān)鍵。因此，在物流配送中如何高效規(guī)劃物流車輛路徑就成為人們關(guān)心的焦點(diǎn)問題。合理調(diào)配優(yōu)化物流車輛，可以減少車輛的費(fèi)用支出，提高物流車輛的運(yùn)載效率，同時可以增加用戶的滿意度和企業(yè)的經(jīng)濟(jì)效益[1]。國內(nèi)外學(xué)者關(guān)于車輛路徑問題展開大量研究，并提出了多種解決方案，通常情況下這些解決方案分為精確算法和傳統(tǒng)啟發(fā)式算法、智能算法[2]，關(guān)注精確算法的學(xué)者主要研究路徑規(guī)劃問題，涉及的節(jié)點(diǎn)少，規(guī)模小的情況，VRP的集分割法是最為突出的一種精準(zhǔn)算法，是由Balinski等人提出的，并且通過一些算法的優(yōu)化設(shè)計，建立了簡單的VRP模型[3,4]。

隨著節(jié)點(diǎn)和規(guī)模的增大，精確算法不足以解決大規(guī)模的路徑規(guī)劃問題。為此，這些年學(xué)者們的關(guān)注點(diǎn)轉(zhuǎn)移到了啟發(fā)式算法的應(yīng)用。因?yàn)閱l(fā)式精確算法不但運(yùn)行時間和復(fù)雜度比之前的算法大大降低，而且應(yīng)用范圍相當(dāng)廣泛。本文將在前人研究的基礎(chǔ)上，通過將兩種改進(jìn)蟻群算法[5,6]融合，得到了解決優(yōu)化路徑問題的一種新的改進(jìn)蟻群算法。并通過具體的數(shù)據(jù)來試驗(yàn)這種方法的有效性和優(yōu)勢。

1 基本蟻群算法

Marco Dorigo[7-9]于1992年在他的博士論文中首次提出了蟻群算法的相關(guān)概念，并且闡述了該算法的靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。其實(shí)就是通過對自然界中螞蟻搜索路徑的行為進(jìn)行模擬，得到的一種模擬進(jìn)化算法。按照此機(jī)制，以達(dá)到尋找到最短路徑的目的，具體的模型如下。

設(shè)i為外出覓食螞蟻的出發(fā)點(diǎn)，則其到達(dá)覓食終點(diǎn)j的隨機(jī)行進(jìn)概率可表為

(1)

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

蟻群算法的核心就是利用螞蟻覓食過程中信息素濃度變化的原理來設(shè)計的。因此，該算法不但擁有較強(qiáng)的最短路徑計算求解能力[1]，而且在求解過程中還可避免過早收斂。除此之外，利用貪婪搜索能力可以降低尋優(yōu)路徑的時間。

2 改進(jìn)蟻群算法的提出依據(jù)

2.1 改進(jìn)啟發(fā)函數(shù)

基于基本蟻群算法的原理分析以及結(jié)合相關(guān)的參考文獻(xiàn)，我們發(fā)現(xiàn)影響最短路徑計算結(jié)果的主要原因就是節(jié)點(diǎn)之間的概率轉(zhuǎn)移和行走路徑上的信息素濃度的更新。一般情況下，取節(jié)點(diǎn)i與下一個節(jié)點(diǎn)j之間的歐氏距離的倒數(shù)作為轉(zhuǎn)移概率中的啟發(fā)函數(shù)。實(shí)際上，在最初搜索的時候，行走路徑上的螞蟻數(shù)量較少，釋放的信息素較少，造成其他螞蟻偏離正確尋找路徑的概率較大，從而形成局部最優(yōu)解或無效解[12]。因此文獻(xiàn)[5]在啟發(fā)函數(shù)中引入了下一節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的歐氏距離，從而加強(qiáng)當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的聯(lián)系，數(shù)學(xué)表達(dá)式為

(4)

其中，dij表示當(dāng)前節(jié)點(diǎn)i與下一個可行節(jié)點(diǎn)j之間的歐氏距離，djE是下一可行節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)E的歐氏距離,于是搜索路徑的方向性被加強(qiáng)，則運(yùn)行時間也就相應(yīng)縮短，提高了算法的時間效率。

2.2 更新信息素濃度

信息素濃度的更新方式對蟻群算法的效率也具有較強(qiáng)的影響力[13]。更新信息素濃度的主要原因有以下幾方面：第一，信息素濃度與路徑的長度有著密切的聯(lián)系，為了防止積累過多使算法過早局部收斂，信息素濃度進(jìn)行更新是必不可少的；第二，由于大自然的固有特性，隨著時間的推移，因?yàn)檎舭l(fā)使得路徑上信息素濃度降低；第三，經(jīng)過行走路徑的所有螞蟻都會釋放信息素，正因?yàn)槠湔答佇裕疃搪窂缴系奈浵佔(zhàn)疃?，信息素也最多；要在全部路徑中凸顯最優(yōu)路徑[14,15]。文獻(xiàn)[6]通找到了當(dāng)次迭代中的最優(yōu)路徑和最差路徑，通過加強(qiáng)最優(yōu)路徑上的信息素同時減弱最差路徑上的信息素釋放量，將信息按照式(5)的方式更新，防止收斂過快而陷入局部最優(yōu)。

(5)

上式中Lbest表示此次迭代中最優(yōu)路徑長度，Lworst表示此次迭代中的最差路徑。

針對以上兩種改進(jìn)的優(yōu)點(diǎn)，本文將文獻(xiàn)[5]的啟發(fā)函數(shù)改進(jìn)和文獻(xiàn)[6]提出的信息素濃度更新的方案結(jié)合起來提出了一種新的改進(jìn)蟻群算法。

2.3 改進(jìn)蟻群算法的參數(shù)設(shè)置與步驟

通過對文獻(xiàn)的詳細(xì)閱讀，本文將文獻(xiàn)[5]和[6]的兩種改進(jìn)算法融合得到了一種新的求解車輛路徑優(yōu)化問題的遺傳算法，具體的參數(shù)設(shè)置如表1。

表1 改進(jìn)蟻群算法參數(shù)設(shè)置

融合后得到的改進(jìn)蟻群算法如下：

Step1:設(shè)m為螞蟻數(shù)量，s為起始點(diǎn)，g為目標(biāo)函數(shù)，Nmax為最大的迭代次數(shù)，設(shè)置α和β的值分別為1和6，將所有的螞蟻都置于起始點(diǎn)。

Step2:所有螞蟻都從s點(diǎn)出發(fā)，隨后將s加入禁忌表。

Step3:依據(jù)公式(4)尋找下一個節(jié)點(diǎn)，將找到屬于可行節(jié)點(diǎn)集合的節(jié)點(diǎn)作為下一個可行節(jié)點(diǎn)，并且將其放入到禁忌表中。

Step4:對當(dāng)前螞蟻的行走路徑做好標(biāo)記，判斷螞蟻是否已到終點(diǎn)，如果沒有到達(dá)終點(diǎn)，返回至Step3；若是螞蟻到達(dá)了終點(diǎn)，接著判斷其是否已走完全程，是則執(zhí)行Step5，否則轉(zhuǎn)至Step2使下一只螞蟻出發(fā)。

Step5:等到全部螞蟻到達(dá)目標(biāo)節(jié)點(diǎn)之后，計算每只螞蟻的路徑長度，找出最優(yōu)解和最差解，然后按照公式(5)對信息素更新，同時增加迭代次數(shù)。

Step6:當(dāng)達(dá)到最大迭代次數(shù)的時候，輸出最短路徑，否則轉(zhuǎn)到Step2。

3 實(shí)證分析

本文采用Matlab2019進(jìn)行仿真實(shí)驗(yàn)，以規(guī)模為30的車輛調(diào)配問題進(jìn)行算法對比驗(yàn)證，說明本文將兩種改進(jìn)蟻群算法融合后形成新算法的可行性和有效性。在新的改進(jìn)遺傳算法的求解過程中，收斂條件設(shè)置為文獻(xiàn)[5]和文獻(xiàn)[6]中的條件，改進(jìn)算法求解過程中兩條求解最優(yōu)的路徑差值不超過0.01%。

3.1 利用基本蟻群算法求解

在使用此方法求解時，設(shè)定基本蟻群算法的參數(shù)為m=30,Nmax=120,α=1,β=4,ρ=0.7,Q=100,將此方法使用于求解規(guī)模為30的車輛調(diào)度問題時，得到的結(jié)果如圖1所示。

實(shí)驗(yàn)結(jié)果表明：采用基本蟻群算法求解30車輛的路徑優(yōu)化問題得到的最優(yōu)路徑長度為417.20，運(yùn)算過程耗時19.23 s。

3.2 利用改進(jìn)蟻群算法求解

設(shè)定改進(jìn)蟻群算法的參數(shù)如表1所示，將此方法使用于求解規(guī)模為30的車輛調(diào)度問題時，得到的結(jié)果如圖2所示。

圖1 普通蟻群算法求解規(guī)模為30車輛優(yōu)化問題時的最優(yōu)路徑與迭代次數(shù)

圖2 改進(jìn)的蟻群算法在求解30車輛得到的最優(yōu)路徑和迭代次數(shù)

針對30輛車的優(yōu)化路徑問題，改進(jìn)遺傳算法的求解結(jié)果獲得的最優(yōu)路徑長度為401.96 m，而時間耗費(fèi)時長只有12.01 s。

為了更清楚地凸顯本文得到的改進(jìn)蟻群算法在解答規(guī)模為30車輛的路徑優(yōu)化問題時具有更好的效果。在表2中將該算法和文獻(xiàn)[5,6]的算法以及基本蟻群算法的結(jié)果進(jìn)行了分析比較。

表2 不同算法得到的最優(yōu)路徑和運(yùn)行時長

根據(jù)表2的數(shù)據(jù)可以得出，本文融合改進(jìn)的蟻群算法與傳統(tǒng)的算法、文獻(xiàn)[5,6]的算法相比，在求解最優(yōu)路徑問題中具有較高的運(yùn)算效率，不管是在最優(yōu)路徑上還是運(yùn)行耗時上都比傳統(tǒng)方法具有明顯的優(yōu)勢。

4 結(jié)論

蟻群算法作為常用的智能優(yōu)化算法，除了最早的在旅行商問題上的應(yīng)用之外，還有很多其他的優(yōu)化應(yīng)用，尤其是在處理路徑規(guī)劃問題上，此方法的應(yīng)用非常的普遍。因此，通過查閱相關(guān)的資料文獻(xiàn)，本文首先對普通蟻群算法的原理進(jìn)行了詳細(xì)介紹分析，然后將文獻(xiàn)[5]中改進(jìn)的啟發(fā)因子和文獻(xiàn)[6]中改進(jìn)的信息素更新融合在一起，產(chǎn)生了一種新的改進(jìn)蟻群算法，對形成新的蟻群算法的具體步驟進(jìn)行了闡述并設(shè)置了該算法在實(shí)驗(yàn)中的相關(guān)參數(shù)，為了突出改進(jìn)遺傳算法的優(yōu)勢，本文在選擇了節(jié)點(diǎn)規(guī)模為30的車輛優(yōu)化路徑問題作為實(shí)驗(yàn)案例，使用普通的遺傳算法和改進(jìn)的遺傳算法對節(jié)點(diǎn)規(guī)模為30的車輛路徑優(yōu)化問題進(jìn)行了求解對比，得出改進(jìn)蟻群算法在求解路徑優(yōu)化問題中的可行性和有效性，且求解出的最優(yōu)路徑和迭代次數(shù)收斂曲線，以及運(yùn)行耗時上都比傳統(tǒng)的蟻群算法的優(yōu)勢明顯。