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

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

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

一、引言

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

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

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

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

1.蟻群算法的基本思想

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

2.一般物流配送問(wèn)題的蟻群算法的描述

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

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

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

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

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

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

3.算法的改進(jìn)

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

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

（3）2-opt局部?jī)?yōu)化

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

三、實(shí)例仿真

本文對(duì)兩個(gè)實(shí)例分別用改進(jìn)的蟻群算法進(jìn)行計(jì)算比較。

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

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

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

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

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

四、結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]袁曉建，張岐山，吳伶，江義火.帶時(shí)間窗和同時(shí)送取貨的車輛路徑問(wèn)題模型及算法[J].福州大學(xué)學(xué)報(bào)（自然科學(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.

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