基于改進蟻群算法的物流配送路徑優(yōu)化研究

金菊婷 何偉杰 徐昌元 章峻耀 戴丹

摘 要：在現(xiàn)代化物流管理中，物流配送車輛的路徑優(yōu)化成為物流配送的重要環(huán)節(jié)，通過有效利用現(xiàn)有的資源，在不同的約束條件下對車輛路徑進行優(yōu)化以降低配送成本，實現(xiàn)物流科學(xué)化。本文先簡述蟻群算法的基本思想，再分析經(jīng)典蟻群算法實現(xiàn)路徑優(yōu)化的重要數(shù)學(xué)模型，再在此基礎(chǔ)上對蟻群算法進行多方面改進，以實現(xiàn)滿載率和運輸距離結(jié)合的路徑最優(yōu)。最后通過實例計算，驗證了使用改進后的蟻群算法能很好滿足新的使用場景。

關(guān)鍵詞：物流配送;路徑規(guī)劃;滿載率;改進的蟻群算法

一、引言

隨著信息技術(shù)的發(fā)展，現(xiàn)代物流作為一種先進的管理技術(shù)被稱為“第三個利潤源泉”，逐漸在世界各國形成產(chǎn)業(yè)化，并在國民經(jīng)濟中發(fā)揮著越來越大的作用。物流配送是物流中直接與消費者相連的重要環(huán)節(jié)，如何在車輛數(shù)量等限制條件下，根據(jù)不同優(yōu)化目的進行有效的配送路徑優(yōu)化成為國內(nèi)外學(xué)者的一個研究熱點。

針對配送車輛最優(yōu)路徑的多目標(biāo)問題，陳雪嬌等提出了基于進化計算的雙旅行商優(yōu)化問題，利用遺傳算法克服局部最優(yōu)解，成功實現(xiàn)高效多目標(biāo)優(yōu)化。多種車型的組合優(yōu)化也是多目標(biāo)配送問題的研究熱點，朱澤國等結(jié)合鏈表思想并對遺傳算法進行改進，發(fā)現(xiàn)隨著相關(guān)不確定參數(shù)的變化，盡管運輸成本上升但對多車型配送滿載率的影響較小。袁曉建等研究了帶時間窗和同時送取貨的車輛路徑問題，建立相應(yīng)的數(shù)學(xué)模型，并通過改進量子進化算法等方式得到更好的解。

本文以提高車輛的滿載率和減小行駛路程為優(yōu)化目標(biāo)，對實現(xiàn)路徑最短化的蟻群算法進行改進，提高算法效率，更好地應(yīng)用求解現(xiàn)實問題，期望在滿足限制條件的情況下找到滿載率和行駛路程都能得到最優(yōu)化的配送路徑，提高物流配送的效率。

二、優(yōu)化的蟻群算法

1.蟻群算法的基本思想

蟻群算法是一種源于自然界中生物世界的新的仿生類隨機型搜索算法。人們在觀察螞蟻的行為特征時，發(fā)現(xiàn)存在一種稱為信息素的物質(zhì)，在一些重要的路徑中信息素的濃度會較其他的路徑更大。這是由于每只螞蟻在行駛過程中都會分泌出信息素，在一些重要的路徑上經(jīng)過的螞蟻數(shù)量較多，信息素的殘留量較大，隨后的螞蟻根據(jù)信息素的濃度就會更容易選擇這些重要的道路。這樣子整個蟻群就會逐漸從多路徑行駛轉(zhuǎn)變成單一最優(yōu)路徑的行駛，使得行駛路徑得到優(yōu)化。1992年，意大利學(xué)者Dorigo在其博士論文中提出了螞蟻系統(tǒng)（Ant System， AS），該系統(tǒng)是最早的蟻群優(yōu)化算法，該算法模擬螞蟻覓食過程中通過螞蟻個體之間的信息素積累以及一定時間的正反饋，不斷更新收斂直至找到最短路徑。蟻群算法具有自組織性、分布式計算的特點，并有很強的魯棒性，能與其他算法融合。本文基于改進的蟻群算法對物流配送路徑進行優(yōu)化，取得了較好的實際效果。

2.一般物流配送問題的蟻群算法的描述

一般的物流配送路徑問題可以這樣描述：存在單一配送中心、多個客戶點和多輛載重限定的配送貨車，配送中心和各個客戶點的坐標(biāo)以及相應(yīng)的配送量確定。配送車輛一律由配送中心出發(fā)，完成任務(wù)后返回配送中心。要求確定配送中心每輛車的配送方案使得在滿載率和路徑兩個方面都能得到最優(yōu)，并滿足相應(yīng)的約束條件：每輛車配送的貨運量不應(yīng)超過車輛的載重量;每輛車只能服務(wù)一條路線，即每個客戶只有一輛車進行配送;配送車輛一次運行路線距離在運行里程限制范圍內(nèi)。運用蟻群算法求解配送路徑優(yōu)化問題的基本流程如下：

（1）對各參數(shù)進行初始化設(shè)置。設(shè)開始時間t=0，最大迭代次數(shù)為Nmax，初始時刻每條路徑上的信息素τij（0）=0，并設(shè)置的初值，同時建立禁忌列表tabuk，保證初始階段表中沒有任何的客戶點。

（2）將m個螞蟻隨機放置在n個配送點，每個客戶點最多分布一個螞蟻，將m個螞蟻所在客戶點的信息存入禁忌列表，并更新循環(huán)次數(shù)。

（3）對于每一只螞蟻，需要從禁忌列表中選出沒有經(jīng)歷過的點，并根據(jù)概率轉(zhuǎn)換公式，以輪盤賭算法選擇下一個客戶點，將所選的客戶點加入禁忌列表，直到螞蟻遍歷完所有的客戶點結(jié)束本輪螞蟻的循環(huán)活動。

（5）判斷是否到達最大的循環(huán)次數(shù)，若到達，則該次配送的最短路徑被找出;否則，清空禁忌列表，跳轉(zhuǎn)到步驟（1）重復(fù)工作。

（6）得到最優(yōu)解后，輸出結(jié)果，繪制出物流配送的最優(yōu)路線。

3.算法的改進

根據(jù)以上的分析，對概率轉(zhuǎn)換規(guī)則和信息素更新規(guī)則進行改進以實現(xiàn)滿載率和路徑相結(jié)合的路徑最優(yōu)。蟻群算法在很多優(yōu)化類問題中表現(xiàn)出較強的解決能力和發(fā)展?jié)摿?，但是也存在計算量過大，搜索時間過長，容易陷入局部最優(yōu)解等缺點。因此本文也通過融合其他算法，更改信息素的收斂速度，對蟻群算法進行相應(yīng)的改進，加快其收斂速度并提高其全局搜索的能力。

（1）概率轉(zhuǎn)換規(guī)則的改進

（3）2-opt局部優(yōu)化

在蟻群算法的基礎(chǔ)上利用2-opt算法進行優(yōu)化，該算法會隨機選取兩個點，選取兩點之間的路徑并對路徑進行翻轉(zhuǎn)，若新路徑的配送距離總長小于老路徑，那么新路徑就會替代老路徑成為最短的路徑，進一步實現(xiàn)了算法的優(yōu)化。2-opt算法的頻繁使用會使得蟻群算法的計算時間變長，極大地影響計算效率。因此只在每一次迭代結(jié)束之后，尋找該次迭代的最優(yōu)解進行2-opt算法的優(yōu)化，并進行一次信息素的更新，揮發(fā)系數(shù)小于首次信息素更新，以免加快收斂速度、陷入局部最優(yōu)。

三、實例仿真

本文對兩個實例分別用改進的蟻群算法進行計算比較。

實驗1：某配送中心向8個配送點進行派件，配送車輛均為最大載重量為8T的派送車，基本配送距離為10KM，具體位置和派送量如下表，求最優(yōu)配送路線。

由于實驗1路徑的復(fù)雜程度相對比較低，本文取蟻群的迭代次數(shù)為10次，取α=1，β=2，γ=3，信息素的揮發(fā)速度rho=0.1，每條路徑的初始信息素為Q=1。隨機求解十次，獲得結(jié)果分布較為簡單，在滿載率為91.67%下，出現(xiàn)行駛距離79.40和80.32兩種情況，且以79.40為主，實驗結(jié)果較為理想。

實驗2：某物流中心有5臺配送車輛，車輛的最大載重均為8T，一次配送的最大行駛距離都為50KM，需要向20個客戶送貨，物流中心和20個客戶的坐標(biāo)及其客戶的需求量隨機產(chǎn)生，其中，物流中心的坐標(biāo)為（1415KM，1310KM），要求合理安排車輛的配送路線，使配送總里程最短。

實驗2路徑的復(fù)雜程度相對較高，加大蟻群的迭代次數(shù)至100，取α=1，β=2，γ=3，信息素的揮發(fā)速度rho=0.1，每條路徑的初始信息素為Q=1。隨機求解十次，結(jié)果如表3所示。

根據(jù)實驗可以看出，在未采用滿載率和路徑綜合考慮的蟻群算法時，可以獲得行駛距離最優(yōu)解為108.6，滿載率為74%。使用后可以獲得最理想的實驗結(jié)果為行駛距離110.4，滿載率為98.75%。相較之下，雖然改進后行駛距離略長于改進前，但是滿載率得到大幅度提高，實驗結(jié)果非常理想。結(jié)果如下圖，得到最優(yōu)路徑為：

四、結(jié)束語

物流配送路徑優(yōu)化是現(xiàn)代物流中的重要環(huán)節(jié)，尤其是隨著當(dāng)今社會經(jīng)濟的快速發(fā)展，用于對物流配送的需求更加多樣化，如何有效利用現(xiàn)有的資源對車輛路徑進行優(yōu)化以減少企業(yè)的配送成本，提高企業(yè)的經(jīng)濟效益，是物流行業(yè)發(fā)展的目標(biāo)。本文從物流配送問題出發(fā)，以經(jīng)典的蟻群算法為基本，對蟻群算法的概率轉(zhuǎn)換規(guī)則和信息素更新方式進行改進，并融合2-opt算法進行優(yōu)化，提高了算法的效率。通過實例驗證了改進的蟻群算法能夠切實有效解決新的配送要求。

參考文獻：

[1]陳雪嬌.基于進化計算的多目標(biāo)優(yōu)化問題求解[D].西南大學(xué)，2020.

[2]朱澤國，廣曉平，郭敏.不確定環(huán)境下的多車型物流配送路徑優(yōu)化[J].交通科技與經(jīng)濟，2021，23（02）：6-12.

[3]袁曉建，張岐山，吳伶，江義火.帶時間窗和同時送取貨的車輛路徑問題模型及算法[J].福州大學(xué)學(xué)報（自然科學(xué)版），2020，48（05）：566-572.

[4]DORIGO M， MANIEZZO V， COLNMI A. Ant system： optimization by a colony of cooperating agents[J].IEEE Transactions on Systems， Man， and Cybernetics-part B，1996，26（1）： 29-41.

[5]ANIEZZO V， CARBONARO A. Ant colony optimization： an overview[C]∥C Ribeiro et al. Essays and Surveys in Metaheuristics[M].Kluwer Academic Publishers，2002.

作者簡介：金菊婷，浙江農(nóng)林大學(xué)，新文科求真實驗班;戴丹，浙江農(nóng)林大學(xué)信息工程學(xué)院，副教授