代婷婷

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

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

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

1 基本蟻群算法

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

設i為外出覓食螞蟻的出發(fā)點，則其到達覓食終點j的隨機行進概率可表為

(1)

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

(2)

(3)

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

2 改進蟻群算法的提出依據

2.1 改進啟發(fā)函數

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

(4)

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

2.2 更新信息素濃度

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

(5)

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

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

2.3 改進蟻群算法的參數設置與步驟

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

表1 改進蟻群算法參數設置

融合后得到的改進蟻群算法如下：

Step1:設m為螞蟻數量，s為起始點，g為目標函數，Nmax為最大的迭代次數，設置α和β的值分別為1和6，將所有的螞蟻都置于起始點。

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

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

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

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

Step6:當達到最大迭代次數的時候，輸出最短路徑，否則轉到Step2。

3 實證分析

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

3.1 利用基本蟻群算法求解

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

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

3.2 利用改進蟻群算法求解

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

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

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

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

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

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

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

4 結論

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