基于改進蟻群算法的物流配送路徑優化研究

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

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

關鍵詞：物流配送;路徑規劃;滿載率;改進的蟻群算法

一、引言

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

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

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

二、優化的蟻群算法

1.蟻群算法的基本思想

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

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

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

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

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

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

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

（6）得到最優解后，輸出結果，繪制出物流配送的最優路線。

3.算法的改進

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

（1）概率轉換規則的改進

（3）2-opt局部優化

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

三、實例仿真

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

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

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

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

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

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

四、結束語

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

參考文獻：

[1]陳雪嬌.基于進化計算的多目標優化問題求解[D].西南大學，2020.

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

[3]袁曉建，張岐山，吳伶，江義火.帶時間窗和同時送取貨的車輛路徑問題模型及算法[J].福州大學學報（自然科學版），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.

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