基于改進(jìn)的蟻群算法的目標(biāo)物流車輛路徑優(yōu)化

曾 勝，王 兵，戴賢君

（1.皖江工學(xué)院電氣信息工程學(xué)院，安徽馬鞍山 243000；2.安徽工業(yè)大學(xué)電氣與信息工程學(xué)院，安徽馬鞍山 243000；3.中國(guó)計(jì)量大學(xué)生命科學(xué)學(xué)院，浙江杭州 310000）

0 引 言

冷鏈物流是指在整個(gè)物流過程中對(duì)溫度敏感的產(chǎn)品（如食品、藥品、化學(xué)品等）進(jìn)行溫度控制和監(jiān)測(cè)的一種物流管理方式。冷鏈物流的發(fā)展受到全球經(jīng)濟(jì)、技術(shù)創(chuàng)新和消費(fèi)者需求等多方面因素的影響。全球化趨勢(shì)促使企業(yè)將供應(yīng)鏈整合到全球范圍內(nèi)，這對(duì)冷鏈物流提出了更高的要求。協(xié)同作業(yè)、跨國(guó)合作和全球供應(yīng)鏈的整合需要更高水平的冷鏈技術(shù)和管理。

冷鏈物流的發(fā)展已經(jīng)近幾十年了，但是冷鏈物流的路徑設(shè)計(jì)一直困擾著物流公司，在路徑行駛過程中總會(huì)遇到障礙物或者路況復(fù)雜的情況，針對(duì)此類情況車輛在行駛過程中應(yīng)找到一條無障礙路線，縮短運(yùn)輸時(shí)間，降低運(yùn)輸成本，為物流公司節(jié)約成本。文獻(xiàn)[1]提出了一種自適應(yīng)調(diào)整啟發(fā)函數(shù)解決機(jī)器人路徑規(guī)劃問題的改進(jìn)蟻群算法；文獻(xiàn)[2]改進(jìn)了蟻群算法的狀態(tài)轉(zhuǎn)移方式和信息素更新方式，引入最大最小蟻群算法與2-opt 局部搜索算法；文獻(xiàn)[3]在文中闡述所有螞蟻遍歷完所有待訪問的收貨點(diǎn)后搜索到的所有路徑上的信息素進(jìn)行更新而導(dǎo)致算法收斂和計(jì)算效率降低等缺陷，改進(jìn)了算法中的狀態(tài)轉(zhuǎn)移概率公式，優(yōu)化了信息素濃度設(shè)定和更新方式；文獻(xiàn)[4]構(gòu)建多核心的蟻群選擇算法，并設(shè)計(jì)深度選擇定義模型，利用臨界預(yù)設(shè)法設(shè)計(jì)路徑優(yōu)化的選擇方法。文獻(xiàn)[5]針對(duì)傳統(tǒng)蟻群優(yōu)化（ACO）算法搜索路徑時(shí)易陷入局部最優(yōu)、路徑過長(zhǎng)、轉(zhuǎn)彎角度過大等問題，提出一種基于轉(zhuǎn)彎角度約束的改進(jìn)ACO 算法。文獻(xiàn)[6]提出一種改進(jìn)的蟻群優(yōu)化（IACO）算法，利用工作環(huán)境的全局信息建立目標(biāo)吸引函數(shù)，提高蟻群選擇最佳路徑到達(dá)目標(biāo)點(diǎn)的概率，縮短了算法的迭代時(shí)間；文獻(xiàn)[7]提出一種改進(jìn)蟻群算法，動(dòng)態(tài)改進(jìn)信息素更新策略和啟發(fā)因子，并采用可行解先行策略；文獻(xiàn)[8]基于多約束條件對(duì)傳統(tǒng)蟻群算法狀態(tài)轉(zhuǎn)移啟發(fā)函數(shù)和信息素進(jìn)行了改進(jìn)，較好地改善了算法的動(dòng)態(tài)優(yōu)化性能；文獻(xiàn)[9]針對(duì)傳統(tǒng)蟻群算法在解決室內(nèi)疏散問題時(shí)存在收斂速度慢、容易陷入局部最優(yōu)的缺陷問題，將火場(chǎng)的動(dòng)態(tài)參數(shù)引入到蟻群算法中，對(duì)其路徑選擇策略、啟發(fā)函數(shù)和信息素更新策略進(jìn)行改進(jìn)，為整個(gè)疏散群體求解更優(yōu)的疏散路徑；文獻(xiàn)[10]研究物流路徑優(yōu)化問題，目的是有效降低物流配送距離，實(shí)現(xiàn)配送任務(wù)完成的高效率與低成本，通過對(duì)基本蟻群算法啟發(fā)函數(shù)的優(yōu)化提出改進(jìn)蟻群算法。文獻(xiàn)[11]采用局部最優(yōu)和全局最優(yōu)兩種方式對(duì)傳統(tǒng)蟻群算法的信息素更新方式加以擴(kuò)大至最優(yōu)解尋覓范圍，并對(duì)啟發(fā)因子的函數(shù)定義范圍擴(kuò)展至初始節(jié)點(diǎn)。文獻(xiàn)[12]對(duì)客戶選擇策略采取分段計(jì)算的方法，以加快算法的收斂速度，并在構(gòu)建一條完整的閉合路徑時(shí)過濾距離路徑較遠(yuǎn)的客戶，提高搜索最優(yōu)路徑的能力。文獻(xiàn)[13]設(shè)計(jì)隨迭代時(shí)間改變的信息素濃度更新機(jī)制，改進(jìn)蟻群算法實(shí)現(xiàn)放牧路徑隨牧場(chǎng)條件變化的及時(shí)優(yōu)化，解決持續(xù)放牧的盲目性。

基于上面的研究成果，本文提出一種改進(jìn)最優(yōu)最差蟻群算法和啟發(fā)因子算法進(jìn)行路徑優(yōu)化的方法，此類方法可以縮短車輛行駛路徑、節(jié)約時(shí)間，以最快的時(shí)間把生鮮產(chǎn)品運(yùn)輸?shù)侥康牡亍?/p>

1 目標(biāo)物流車輛路徑優(yōu)化模型

本文以某H 公司為例，該公司的主要營(yíng)業(yè)產(chǎn)品為運(yùn)送冷鏈物流產(chǎn)品，產(chǎn)品主要由食品、生鮮產(chǎn)品等組成，其主要配送任務(wù)是把產(chǎn)品運(yùn)輸?shù)礁鱾€(gè)網(wǎng)點(diǎn)，以達(dá)到客戶的需求。為了下面建模方便，本文調(diào)查了該公司每月的運(yùn)輸量，圖1 為2022 年一年的運(yùn)輸量。

圖1 冷鏈物流每個(gè)月運(yùn)輸量

根據(jù)圖1 可以看出，2022 年各月份對(duì)冷鏈物流產(chǎn)品需求量不一樣，特別在夏季的時(shí)候?qū)滏溛锪鞯男枨罅看蠓仍黾?，此時(shí)就會(huì)增加冷鏈物流公司的壓力，為了解決面臨的問題，要在時(shí)間、成本上節(jié)約，那此時(shí)就需要規(guī)劃好路徑。

1.1 問題描述

目標(biāo)車輛運(yùn)輸過程中其目的在于降低運(yùn)輸成本，保證生鮮冷鏈物流產(chǎn)品在規(guī)定的時(shí)間內(nèi)到達(dá)目的地。針對(duì)本文研究狀況提出以下假設(shè)：

1）冷鏈物流運(yùn)輸車輛必須從始發(fā)地裝滿貨物出發(fā)運(yùn)送到目的地，再?gòu)哪康牡乜哲嚪祷厥及l(fā)地。

2）對(duì)于車輛在運(yùn)輸過程中，保證其在每個(gè)運(yùn)輸點(diǎn)消耗的時(shí)間在一定的范圍內(nèi)。

3）車輛在滿載過程中與空載過程中其行駛速度穩(wěn)定，不考慮其擁堵情況。

4）對(duì)于運(yùn)輸所有車輛必須要保證滿載貨物不能超過其車輛運(yùn)輸?shù)淖畲笙薅取?/p>

5）所有車輛型號(hào)保持一樣且司機(jī)身體健康良好。

6）每輛車只服務(wù)本次指派的任務(wù)，不增加其他任務(wù)指標(biāo)。

1.2 數(shù)學(xué)模型

傳統(tǒng)的車輛運(yùn)輸沒有考慮碳的排放運(yùn)輸成本，本文研究設(shè)計(jì)主要從兩個(gè)方面降低運(yùn)輸成本：一是降低碳的排放成本；二是車輛運(yùn)輸成本。式（1）為總的運(yùn)輸成本。

1.2.1 碳排放因素成本

《碳排放權(quán)交易管理辦法（試行）》已于2020 年12 月25 日由生態(tài)環(huán)境部部務(wù)會(huì)議審議通過，自2021年2月1 日起施行。此政策的出臺(tái)致力于解決碳排放對(duì)環(huán)境產(chǎn)生的影響，本文冷鏈物流車的運(yùn)輸是通過燃油車進(jìn)行運(yùn)輸，由于電動(dòng)車行駛距離較近，不適合冷鏈物流的運(yùn)輸，所以采用燃油車進(jìn)行運(yùn)輸，在使用燃油車的同時(shí)也應(yīng)最大程度降低其運(yùn)輸成本，其中如下兩個(gè)因素影響碳的排放成本：

1）冷鏈物流車的行駛速度影響碳的排放成本；

2）冷鏈物流車重量影響冷鏈物流車的排放標(biāo)準(zhǔn)。

G為冷鏈物流車重量，v為車輛行駛的速度，dij為倉(cāng)庫(kù)到客戶之間的距離，xi為坐標(biāo)點(diǎn)的橫坐標(biāo)，yi為坐標(biāo)點(diǎn)的縱坐標(biāo)，(xi1,yi1)為倉(cāng)庫(kù)坐標(biāo)，(xi2,yi2)為客戶點(diǎn)坐標(biāo)，k為運(yùn)輸車輛數(shù)量，每千米固定燃油消耗為M，碳的每千米固定排放量為q，每千米碳排放成本為s，N= 1,2,…,n為物流點(diǎn)坐標(biāo)點(diǎn)，α1為速度系數(shù)，α2為冷鏈物流車重量系數(shù)。

車輛行駛速度與重量不同，則排放成本不同，其成本計(jì)算公式如下：

速度成本：

重量成本：

碳排放總成本：

1.2.2 運(yùn)輸成本

1）固定成本

假設(shè)B0為冷鏈物流車與工作人員固定費(fèi)用，xijk為決策變量，該固定費(fèi)用主要包括運(yùn)輸過程中折損費(fèi)用、司機(jī)的工資等費(fèi)用。以下公式為冷鏈物流運(yùn)輸過程中固定費(fèi)用：

2）制冷成本

為保證冷鏈產(chǎn)品足夠新鮮，本文要控制制冷箱的溫度，針對(duì)此類情況就會(huì)產(chǎn)生一個(gè)制冷成本，由于制冷成本與時(shí)間有關(guān)系，由此假設(shè)t1為倉(cāng)庫(kù)到卸貨點(diǎn)時(shí)間，由于卸貨過程中也會(huì)產(chǎn)生一個(gè)時(shí)間，設(shè)定為t2，假設(shè)每分鐘行駛過程中的固定成本為Y1元，卸貨過程中每分鐘花的成本為Y2元，則制冷總成本如下：

3）運(yùn)輸成本

冷鏈物流車運(yùn)輸過程中也會(huì)產(chǎn)生相應(yīng)的成本，比如車輛的油費(fèi)，但是由于運(yùn)輸車輛重量影響油費(fèi)的高低，那么設(shè)置每千米油耗率為β，β0為初始油耗率，公式如下：

4）損耗成本

?1為貨物在勻速行駛過程中新制冷系數(shù)，?2為打開車廂物品制冷系數(shù)，t3為打開車廂時(shí)間。

5）總運(yùn)輸成本

總的運(yùn)輸成本主要由碳排放因素成本與運(yùn)輸成本構(gòu)成。

約束條件：

2 算法模型

2.1 環(huán)境建模

本文針對(duì)蟻群算法采用柵格法進(jìn)行路徑規(guī)劃，柵格法在Matlab 中仿真矩陣主要采用0、1 兩個(gè)數(shù)據(jù)，0 代表無障礙物，1 代表有障礙物，柵格的設(shè)計(jì)主要以黑白為主，模型中柵格設(shè)計(jì)主要以正方形或者長(zhǎng)方形為主，依次對(duì)網(wǎng)格區(qū)間設(shè)計(jì)各個(gè)區(qū)域。為表示網(wǎng)格的各個(gè)位置，使用了一種連續(xù)的標(biāo)序，從左到右、從上到下依次排列，形成了一個(gè)完整的柵格圖，圖2 為環(huán)境模擬圖。

圖2 路徑模型柵格圖

2.2 傳統(tǒng)的算法模型

傳統(tǒng)的蟻群算法的研究設(shè)計(jì)如下：假設(shè)t時(shí)刻第k只螞蟻從i位置點(diǎn)爬行到下個(gè)位置點(diǎn)j，設(shè)置初始釋放的信息素為τij和啟發(fā)信息βij，同時(shí)設(shè)置轉(zhuǎn)移概率為Pk ij，α為信息素啟發(fā)因子，β為期望啟發(fā)式因子，dij表示從i位置點(diǎn)到j(luò)位置點(diǎn)的距離，ηij為期望啟發(fā)式函數(shù)。則有：

螞蟻在經(jīng)過路徑時(shí)會(huì)釋放信息素，由于信息素隨時(shí)間的推移產(chǎn)生揮發(fā)，傳統(tǒng)蟻群在爬行過程中會(huì)產(chǎn)生迭代，此時(shí)會(huì)更新信息素，信息素更新公式如下：

式中：ρ是信息素?fù)]發(fā)系數(shù)，一般設(shè)置為0 ＜ρ＜1；Δτij(t)表示是螞蟻爬行從i城市到j(luò)城市t時(shí)刻的最佳釋放信息素量；Q表示釋放信息素的強(qiáng)度；Lbest表示螞蟻爬行的最佳路徑長(zhǎng)度。

2.3 改進(jìn)后的算法模型

改進(jìn)后的蟻群算法主要對(duì)螞蟻爬行過程中的釋放因子進(jìn)行改進(jìn)，由于螞蟻在爬行過程中其信息會(huì)發(fā)生很大的變化，對(duì)其信息素的收集會(huì)發(fā)生兩種變化：一是所有螞蟻爬行過程中螞蟻群會(huì)選擇另外一只優(yōu)等螞蟻而不是起初的優(yōu)等螞蟻，此時(shí)螞蟻爬行過程中不同路徑釋放的信息素濃度會(huì)發(fā)生改變，由于在爬行過程中選擇優(yōu)等的螞蟻，此時(shí)通過計(jì)算公式得出多個(gè)螞蟻釋放的信息素濃度；二是所有螞蟻在爬行結(jié)束過程中選擇其信息素濃度，但是由于優(yōu)等螞蟻不只是一個(gè)，有多條路徑由多只螞蟻釋放的信息素濃度，此時(shí)尋找出的路徑看不出哪條路徑是最優(yōu)路徑，可能隨機(jī)尋找出其中一條釋放出信息素濃度比較多的一條路徑，這種表面選擇出來的路徑并不代表是最優(yōu)的路徑，導(dǎo)致路徑的選擇發(fā)生改變。針對(duì)這兩類情況，本文對(duì)蟻群算法的路徑進(jìn)行優(yōu)化。

對(duì)于最優(yōu)路徑的尋找，規(guī)定了只有在最優(yōu)路徑上面的信息素濃度才會(huì)逐漸增加，非最優(yōu)路徑上的信息素都會(huì)慢慢揮發(fā)直至沒有；其次，為了盡量避免出現(xiàn)搜索停滯的現(xiàn)象，把信息素限定在一個(gè)區(qū)間[τmin,τmax]中，任何大于或低于這個(gè)區(qū)間的信息素都會(huì)相應(yīng)的用τmin、τmax進(jìn)行替換。優(yōu)化公式如下：

若τij(t) ≥τmax，則：

若τij(t) ＜τmin，則：

1）最優(yōu)最差蟻群算法改進(jìn)

最優(yōu)最差蟻群算法的改進(jìn)思想是通過更大限度地增強(qiáng)最優(yōu)解，縮減更小的最差解，這樣做的目的是使得螞蟻在爬行路徑中優(yōu)化路線的信息素濃度與劣勢(shì)路徑信息素濃度彼此之間差距變大，促使螞蟻都爬向優(yōu)化路線那條路徑，此時(shí)螞蟻爬行基本上聚集在最優(yōu)路線上，該方法也是改變傳統(tǒng)的螞蟻爬行路徑，當(dāng)信息素釋放完，更新最差路徑信息素濃度。

式中：ε為引入的算法參數(shù)；τ(i,j)為兩地之間的信息素軌跡；Lbest為搜索路徑中最優(yōu)長(zhǎng)度；Lworst為搜索路徑中最差長(zhǎng)度。

2）啟發(fā)因子算法改進(jìn)

由于螞蟻在爬行過程中有熱搜索過程，螞蟻爬行過程中所謂繞開障礙物是指，由于在爬行過程中遇到路徑區(qū)域溫度高于其正常生存溫度，此時(shí)螞蟻就會(huì)繞開此路徑，那此時(shí)螞蟻的整個(gè)爬行路徑會(huì)隨之發(fā)生改變，對(duì)其啟發(fā)因子就會(huì)產(chǎn)生影響。針對(duì)此類情況，本文對(duì)其傳統(tǒng)的啟發(fā)因子進(jìn)行改進(jìn)，引入一個(gè)自適應(yīng)因子μ，dik為第k輛車到i點(diǎn)的距離，djk為第k輛車到j(luò)點(diǎn)的距離，啟發(fā)因子的改進(jìn)公式如下：

轉(zhuǎn)移概率公式為：

2.4 改進(jìn)后的算法步驟

改進(jìn)后算法步驟如下：

Step1：初始化信息素。在問題空間中的每個(gè)可能的解都有一個(gè)與之相關(guān)的信息素值τij。初始時(shí)，信息素值通常被設(shè)置為與τij相等的小值。

Step2：初始化蟻群。在問題空間中隨機(jī)放置螞蟻數(shù)量為k，每只螞蟻從問題的一個(gè)解空間點(diǎn)開始。

Step3：螞蟻路徑選擇。每只螞蟻按照一定的規(guī)則選擇移動(dòng)路徑，通常螞蟻選擇路徑的概率與路徑上的信息素濃度和路徑距離dij有關(guān)，信息素濃度高的路徑和之前螞蟻?zhàn)哌^的路徑有更大的概率被選擇。

Step4：改進(jìn)算法螞蟻移動(dòng)。螞蟻按照選擇的路徑移動(dòng)到下一個(gè)解空間點(diǎn)。在移動(dòng)過程中可以考慮引入一些隨機(jī)性，加入最優(yōu)最差、啟發(fā)因子算法的多樣性。

Step5：更新信息素。當(dāng)所有螞蟻完成移動(dòng)后，根據(jù)其走過的路徑更新路徑上的信息素。通常路徑上的信息素會(huì)蒸發(fā)，則引入[τmin,τmax]信息素濃度，此外由于熱區(qū)域的影響，引入新的啟發(fā)因子η*ij，然后根據(jù)螞蟻的移動(dòng)路徑和問題的優(yōu)化目標(biāo)增加新的信息素。

Step6：重復(fù)迭代最大迭代次數(shù)Ncmax。重復(fù)上述步驟多次，直到滿足停止條件Ncmax＜N。停止準(zhǔn)則可以是達(dá)到一定的迭代次數(shù)、找到滿意的解或其他預(yù)定條件。

Step7：輸出結(jié)果。最后從所有螞蟻的移動(dòng)路徑中選擇一條最優(yōu)解作為算法的輸出。

3 目標(biāo)物流車路徑優(yōu)化實(shí)證

3.1 路徑模擬仿真

設(shè)置初始釋放的信息素為τij和啟發(fā)信息βij，同時(shí)設(shè)置轉(zhuǎn)移概率為Pkij，α為信息素啟發(fā)因子，β為期望啟發(fā)式因子，ρ是信息素?fù)]發(fā)系數(shù)，Q表示釋放信息素的強(qiáng)度，ε為引入的算法參數(shù)，μ為自適應(yīng)因子，Ncmax為最大迭代次數(shù)。各參數(shù)設(shè)置如表1 所示。

表1 參數(shù)設(shè)置

圖3 為傳統(tǒng)蟻群算法的路徑優(yōu)化仿真圖。圖4 為改進(jìn)后蟻群算法的路徑優(yōu)化仿真圖。

圖3 傳統(tǒng)的蟻群算法仿真

圖4 改進(jìn)后的蟻群算法仿真

根據(jù)圖3 與圖4 仿真對(duì)比可以看出，經(jīng)過改進(jìn)后的蟻群算法路徑更近且收斂性更好，更符合冷鏈物流公司的設(shè)計(jì)方案。

3.2 成本計(jì)算

本文以H 冷鏈物流公司為例，對(duì)其參數(shù)與路徑坐標(biāo)進(jìn)行設(shè)置。G為冷鏈物流車標(biāo)準(zhǔn)重量6 t，v為車輛行駛的速度60 km/h，dij為倉(cāng)庫(kù)到客戶之間的距離，k為運(yùn)輸車輛數(shù)量，每千米固定燃油消耗為M=0.08 L，碳的每千米固定排放量為q=0.3 mg，每千米碳排放成本為s=0.5 元，設(shè)置物流車數(shù)量為k=15，α1為速度系數(shù)0.2，α2為冷鏈物流車重量系數(shù)0.3。t1為倉(cāng)庫(kù)到卸貨點(diǎn)時(shí)間3 h，卸貨過程中也會(huì)產(chǎn)生一個(gè)時(shí)間t2為1 h，假設(shè)每分鐘行駛過程中的固定成本為Y1=10 元，卸貨過程中每分鐘花的成本為Y2=2 元，每千米油耗率為β=0.06 L，初始油耗率β0=0.03 L，?1為貨物在勻速行駛過程中新制冷系數(shù)0.3，?2為打開車廂物品制冷系數(shù)0.5，t3為打開車廂時(shí)間2 min。車輛行駛坐標(biāo)如表2 所示。

表2 車輛行駛坐標(biāo)

表2 為車輛可供選擇的路線，通過蟻群算法和優(yōu)化后蟻群算法選擇出路徑最短的路線，再計(jì)算相應(yīng)的成本。從表中可以看出3號(hào)路線路徑最短，那么所花的成本最低。

根據(jù)表2 選擇dij為3 號(hào)路線的距離。表3 為成本計(jì)算表。通過表3 成本計(jì)算可以看出：利用蟻群算法的模型可以降低運(yùn)輸成本；優(yōu)化后的成本比傳統(tǒng)蟻群算法的成本要低。

表3 成本計(jì)算表元

4 結(jié) 語(yǔ)

本文通過研究表明，H 冷鏈物流公司運(yùn)輸量較大，通過蟻群算法模型設(shè)計(jì)明顯提升了運(yùn)輸效率，大大增加了公司的運(yùn)輸量，但本文同時(shí)也對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，優(yōu)化車輛路徑，使得H 冷鏈物流公司達(dá)到了最低成本，有效地節(jié)約了配送成本，改善了物流配送的效率。

注：本文通訊作者為曾勝。