求解時(shí)間依賴型綠色車輛路徑問題的算法研究

葛非,閔珊,邱含,代振陽(yáng),楊智敏

(華中師范大學(xué)計(jì)算機(jī)學(xué)院,湖北 武漢 430079)

0 引言

物流運(yùn)輸行業(yè)作為商品供應(yīng)鏈管理的重要環(huán)節(jié),成了不同地區(qū)經(jīng)濟(jì)發(fā)展的重要紐帶,隨著其市場(chǎng)規(guī)模的不斷擴(kuò)張,發(fā)揮著越來越重要的作用。隨著綠色環(huán)保理念的普及,公眾對(duì)交通運(yùn)輸中溫室氣體排放問題的關(guān)注度日益提升。然而,物流企業(yè)在追求成本降低和效率提升的過程中,往往忽視了運(yùn)營(yíng)活動(dòng)對(duì)環(huán)境的影響,尤其是碳和氮氧化物排放,這些溫室氣體不僅加劇了全球氣候變化,還對(duì)人類健康和生態(tài)系統(tǒng)構(gòu)成了威脅。自2009年哥本哈根世界氣候大會(huì)以來,低碳環(huán)保和節(jié)能減排已成了全球關(guān)注的重點(diǎn),我國(guó)政府和相關(guān)部門采取了多項(xiàng)措施,包括控制企業(yè)排放、實(shí)施碳稅政策和建立企業(yè)碳排放交易系統(tǒng),以減少運(yùn)輸行業(yè)的碳排放。公路運(yùn)輸是我國(guó)主要的溫室氣體排放源之一,碳排放量占交通運(yùn)輸行業(yè)總排放量的80%以上。因此,推動(dòng)燃油汽車的節(jié)能降碳是實(shí)現(xiàn)“雙碳”目標(biāo)的關(guān)鍵環(huán)節(jié)[1]。在城市配送中,車輛的燃料消耗和二氧化碳排放與城市每天的交通擁堵情況緊密相關(guān),擁堵的路況會(huì)使車輛的油耗量和碳排放量增加,間接對(duì)運(yùn)輸過程中的經(jīng)濟(jì)成本和環(huán)境成本產(chǎn)生負(fù)面影響。城市交通擁堵是市區(qū)交通碳排放快速增長(zhǎng)的關(guān)鍵原因[2]。此外,交通擁堵也會(huì)導(dǎo)致車輛配送時(shí)間延長(zhǎng),致使車輛不能在客戶規(guī)定時(shí)間窗口內(nèi)按時(shí)到達(dá)客戶點(diǎn)完成配送任務(wù)。因此,研究基于時(shí)變交通網(wǎng)絡(luò)的綠色物流模式,對(duì)于適應(yīng)當(dāng)前的運(yùn)輸需求和減少環(huán)境影響具有重要意義。

綠色車輛路徑問題(GVRP)是一個(gè)新興的研究領(lǐng)域,定義為:在滿足客戶服務(wù)要求、車輛容量等約束條件的前提下,將降低運(yùn)作成本、減少能耗和碳排放、提供顧客滿意的服務(wù)等作為優(yōu)化目標(biāo),科學(xué)規(guī)劃發(fā)車數(shù)量、發(fā)車時(shí)間與車輛行駛路線,實(shí)現(xiàn)經(jīng)濟(jì)效益、環(huán)境效益和社會(huì)效益的協(xié)調(diào)優(yōu)化[3]。作為基本車輛路徑問題(VRP)的擴(kuò)展,GVRP同樣被歸類為非確定性多項(xiàng)式(NP)-Hard問題。在國(guó)際上,對(duì)于GVRP的研究已經(jīng)取得了顯著成果。BEKTAS等[4]提出污染路徑問題(PRP),該問題綜合考慮了行駛路程、溫室氣體排放以及行駛時(shí)間成本,主要目的是減少車輛行駛過程中的燃油消耗,并建立了帶時(shí)間窗和不帶時(shí)間窗PRP的混合整數(shù)數(shù)學(xué)模型,同時(shí)采用綜合模式排放模型(CMEM)[5]計(jì)算燃油消耗量。在BEKTAS等[4]的研究基礎(chǔ)上,DEMIR等[6]回顧和比較了幾種常見的與公路貨運(yùn)燃料消耗和溫室氣體排放相關(guān)的排放模型,并將模型結(jié)果與實(shí)際道路數(shù)據(jù)進(jìn)行了比較分析。DEMIR等[7]提出一種自適應(yīng)大規(guī)模鄰域搜索(LNS)算法求解PRP,該算法通過使用新的和現(xiàn)有的刪除和插入策略來優(yōu)化自適應(yīng)大規(guī)模鄰域搜索算法,從而提高求解質(zhì)量,并通過大量實(shí)驗(yàn)驗(yàn)證了該算法的有效性。MEHLAWAT等[8]提出一種混合遺傳算法用于解決多車輛GVRP問題,并通過實(shí)驗(yàn)驗(yàn)證了該算法的魯棒性。

雖然已有研究對(duì)GVRP問題進(jìn)行了一系列探討,但多數(shù)研究未充分考慮交通擁堵的影響。文獻(xiàn)[5]研究表明:二氧化碳(CO2)排放量與燃料消耗量成正比,且這一關(guān)系受車輛行駛速度的影響,嚴(yán)重堵塞將伴隨著頻繁的加速和減速動(dòng)作,這將極大增加溫室氣體的排放量。若在求解綠色車輛路徑優(yōu)化問題時(shí)假設(shè)車輛速度恒定,這可能導(dǎo)致車輛的日均CO2排放偏離率高達(dá)20%,在嚴(yán)重?fù)頂D的交通中偏離率更高[9]。因此,在研究車輛行駛過程中的碳排放量時(shí),考慮交通擁堵能讓計(jì)算結(jié)果更加準(zhǔn)確,也更符合實(shí)際情況。FRANCESCHETTI等[10]提出時(shí)間依賴型污染路徑問題(TDPRP),考慮交通擁堵場(chǎng)景對(duì)PRP進(jìn)行擴(kuò)展,并對(duì)TDPRP的整數(shù)線性規(guī)劃公式進(jìn)行詳細(xì)描述,并假設(shè)車輛速度在一組離散值之間進(jìn)行優(yōu)化。CIMEN等[11]考慮在時(shí)變路網(wǎng)中車輛速度的時(shí)間依賴性和隨機(jī)性,提出一種基于近似動(dòng)態(tài)規(guī)劃的啟發(fā)式算法來解決時(shí)間依賴型綠色車輛路徑問題(TDGVRP)。KAZEMIAN等[12]將溫室氣體排放和燃料消耗作為TDGVRP優(yōu)化目標(biāo),并通過將帶時(shí)間窗的問題轉(zhuǎn)化為不帶時(shí)間窗的問題來降低求解復(fù)雜性,在減少碳排放和油耗的同時(shí)控制總成本。

考慮載重和時(shí)變路網(wǎng)的TDGVRP研究在最近幾年才獲得較多的關(guān)注,國(guó)內(nèi)就此展開的研究較少。趙志學(xué)等[13]研究了考慮不同擁堵情況下的GVRP,將車輛管理使用費(fèi)用和油耗碳排放成本作為優(yōu)化目標(biāo),并根據(jù)模型的特點(diǎn)將模擬退火算法和差分進(jìn)化算法相結(jié)合對(duì)GVRP進(jìn)行求解,實(shí)驗(yàn)結(jié)果證明該算法能有效減少運(yùn)輸成本以及碳排放成本。周鮮成等[14]考慮車輛不同出發(fā)時(shí)刻對(duì)行駛時(shí)間的影響,針對(duì)TDGVRP模型的特點(diǎn),設(shè)計(jì)基于路段劃分策略的車輛行駛時(shí)間計(jì)算方法,并利用改進(jìn)的蟻群算法進(jìn)行求解。珠蘭等[15]將包括油耗成本在內(nèi)的運(yùn)輸總成本作為TDGVRP的優(yōu)化目標(biāo),提出嵌套遺傳算法對(duì)其進(jìn)行求解。QI等[16]利用基于Q學(xué)習(xí)的多目標(biāo)進(jìn)化算法(QMOEA)來求解帶時(shí)間窗的時(shí)間依賴型綠色車輛路徑問題(TDGVRPTW),在QMOEA中設(shè)計(jì)1種混合生成初始解的方法和2種基于Pareto前沿的交叉策略以提高算法的求解性能,最后將一個(gè)實(shí)際物流系統(tǒng)作為實(shí)驗(yàn)案例,驗(yàn)證了該算法的有效性和優(yōu)越性。

對(duì)于GVRP的研究,多數(shù)文獻(xiàn)使用元啟發(fā)式和啟發(fā)式算法進(jìn)行求解,因?yàn)榫_解法通常僅適用于小規(guī)模問題。在GVRP的最新研究成果中,相當(dāng)一部分內(nèi)容聚焦于單目標(biāo)優(yōu)化,這是因?yàn)榕c雙目標(biāo)問題相比,單目標(biāo)優(yōu)化在簡(jiǎn)化問題和尋找全局最優(yōu)解方面更具優(yōu)勢(shì),然而多目標(biāo)優(yōu)化考慮了更多因素和需求,能夠提供多樣化的解決方案。多數(shù)文獻(xiàn)假設(shè)GVRP中車輛的行駛速度恒定,只有少數(shù)文獻(xiàn)考慮了城市路網(wǎng)中時(shí)變速度下的碳排放量計(jì)算。因此,在時(shí)變路網(wǎng)中的雙目標(biāo)TDGVRPTW仍有很大的研究空間。

本文通過加入鄰域算子、優(yōu)化信息素更新方式和狀態(tài)轉(zhuǎn)移規(guī)則等手段對(duì)蟻群算法進(jìn)行了改進(jìn),設(shè)計(jì)了綠色智能進(jìn)化蟻群優(yōu)化(G-IEACO)算法,以更好地求解雙目標(biāo)TDGVRPTW。

1 問題描述與模型建立

1.1 問題描述

在TDGVRPTW中,考慮以下核心假設(shè):首先,配送中心擁有數(shù)量固定、規(guī)格相同的車輛用于物流配送;然后,每個(gè)客戶點(diǎn)的配送需求包括地理位置、貨物需求量、服務(wù)時(shí)間等,這些信息彼此獨(dú)立且已知,同時(shí)每輛車在最大載貨量的約束下可服務(wù)多個(gè)客戶點(diǎn),但每個(gè)客戶點(diǎn)只能由一輛車提供服務(wù);最后,所有車輛均從配送中心出發(fā)并在完成配送后返回原點(diǎn),同時(shí)所有客戶點(diǎn)和配送中心均有時(shí)間窗的限制,車輛須在規(guī)定的時(shí)間窗內(nèi)為其服務(wù),若提前到達(dá)則須等到客戶的最早服務(wù)時(shí)間才能開始服務(wù),若超過時(shí)間窗則不能服務(wù)客戶。

TDGVRPTW的目標(biāo)是在城市交通條件變化的情況下,車輛安排要最小化碳排放量和總行駛時(shí)間。碳排放量與車輛的行駛速度和載重密切相關(guān)[17],因此在求解時(shí)須考慮實(shí)時(shí)交通狀況。已有研究在求解車輛行駛過程中的碳排放量時(shí)忽略了交通擁堵和假設(shè)行駛速度恒定,不符合實(shí)際情況。在時(shí)變交通下,一個(gè)工作日被劃分為多個(gè)時(shí)段M={[b1,e1],[b2,e2],…,[bk,ek],…,[bm,em]},其中,bk和ek分別表示周期k的開始時(shí)間和結(jié)束時(shí)間,且e(i-1)=bi,?i∈{2,3,…,m}。在任一個(gè)路徑(i,j)上的每一個(gè)周期的行駛速度(vijm,?m∈M)是已知的且每一個(gè)周期的行駛速度在該時(shí)段內(nèi)是不變的。TDGVRPTW需要在考慮城市道路擁堵的情況下安排車輛服務(wù)完所有客戶,并以最小化碳排放量和車輛總行駛時(shí)間為目標(biāo)函數(shù),給出配送方案。

1.2 符號(hào)說明

參數(shù)和決策變量定義如表1所示。

表1 符號(hào)定義Table 1 Symbol definition

1.3 車輛碳排放的計(jì)算方法

根據(jù)文獻(xiàn)[4]可知:車輛的碳排放量與燃油消耗量成正比,可以用CO2轉(zhuǎn)換因子將汽車的油耗量轉(zhuǎn)化為碳排放量,故可以先利用車輛和道路的有關(guān)參數(shù)求得消耗的燃油量,再計(jì)算出車輛的碳排放量。DEMIR等[18]分析了影響燃料消耗的因素,并調(diào)查現(xiàn)有的車輛排放模型和回顧綠色道路貨運(yùn)的相關(guān)文獻(xiàn),并對(duì)多種已有的油耗模型進(jìn)行了詳細(xì)介紹,其中提到的CMEM如今被廣泛使用在GVRP中。CMEM由BARTH等[19]提出,由發(fā)動(dòng)機(jī)功率、發(fā)動(dòng)機(jī)轉(zhuǎn)速和燃油率3個(gè)部分組成,基于微觀的角度,以車輛的瞬時(shí)油耗和狀態(tài)參數(shù)之間的關(guān)系為推導(dǎo)依據(jù),通過車輛的發(fā)動(dòng)機(jī)運(yùn)行狀態(tài)參數(shù)逐秒計(jì)算燃油排放,可以準(zhǔn)確計(jì)算車輛的油耗,被用于估算車輛行駛過程中的燃料消耗量和CO2排放量[4,6,10]。根據(jù)該模型,總?cè)加拖牧縁的計(jì)算公式如下:

F=RFR·T=

(1)

其中:RFR為瞬時(shí)燃油率;T為行駛時(shí)間;α=gsinθ+gCrcosθ,g為重力常數(shù),Cr為地面摩擦阻力系數(shù),θ為道路坡度;β=0.5CdAρ,Cd為空氣阻力系數(shù),A為車輛迎風(fēng)面積,ρ是空氣密度;γ=1/(1 000εω),ε是車輛傳動(dòng)系統(tǒng)效率,ω是柴油發(fā)動(dòng)機(jī)的效率參數(shù);λ=ξ/κΨ,ξ是燃料與空氣質(zhì)量比,κ是經(jīng)典柴油熱值,Ψ是轉(zhuǎn)換因子;B是發(fā)動(dòng)機(jī)摩擦因子;Ne是發(fā)動(dòng)機(jī)轉(zhuǎn)速;V為發(fā)動(dòng)機(jī)排量;G為車輛整備質(zhì)量;m為貨物重量;d為車輛行駛路程;v為車輛行駛速度。

1.4 時(shí)段劃分方式

MALANDRAKI等[20]通過模擬交通路網(wǎng)中的偶發(fā)性交通事故、路障等隨機(jī)事件,研究車輛出發(fā)時(shí)間對(duì)路徑規(guī)劃的影響,提出TDVRP的混合整數(shù)規(guī)劃公式。隨后,MALANDRAKI等[21]又提出一個(gè)動(dòng)態(tài)規(guī)劃公式來解決時(shí)間相關(guān)的旅行商問題。上述2篇文獻(xiàn)通過離散的階梯函數(shù)來計(jì)算車輛的行駛時(shí)間,其中車輛行駛時(shí)間與不同的時(shí)段相關(guān),雖然這種計(jì)算方法能夠體現(xiàn)出速度隨時(shí)間的周期性改變,但并不滿足先進(jìn)先出(FIFO)準(zhǔn)則,這意味著在后面出發(fā)的車輛可能會(huì)超過另一輛更早開始行駛的車輛,該問題在文獻(xiàn)[22-25]中被先后討論,并且這些學(xué)者都根據(jù)FIFO準(zhǔn)則對(duì)時(shí)變車輛路徑問題進(jìn)行了建模,之后FIFO準(zhǔn)則被廣泛應(yīng)用于時(shí)變路網(wǎng)的車輛行駛時(shí)間計(jì)算過程。

JABALI等[26]構(gòu)建VRP模型,在時(shí)變路網(wǎng)下計(jì)算車輛行駛時(shí)間、燃料消耗和CO2排放成本,建立的行駛時(shí)間模型遵從FIFO準(zhǔn)則,之后被FRANCESCHETTI等[10]應(yīng)用于時(shí)變污染路徑問題。

為了描述真實(shí)的交通狀況,本文利用高德地圖的海量交通出行數(shù)據(jù)、車輛軌跡數(shù)據(jù)和位置數(shù)據(jù),并采用實(shí)時(shí)擁堵延時(shí)指數(shù)來描述交通狀況。擁堵延時(shí)指數(shù)是指實(shí)際出行時(shí)間與自由流(道路完全暢通)狀態(tài)下的比值,值越高代表道路越擁堵,車輛行駛速度也越慢。這里選取2022年11月28日—2022年11月29日武漢市的交通擁堵延時(shí)指數(shù),如圖1所示(彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML版,下同),選擇06:00—22:00的數(shù)據(jù)進(jìn)行分析,06:00—07:00道路暢通,07:00—09:00發(fā)生了早高峰的擁堵,09:00—17:00道路暢通,隨后17:00—19:00又發(fā)生了晚高峰的擁堵,在擁堵結(jié)束后19:00—22:00車輛再次以自由流速度行駛。顯然,路網(wǎng)的交通擁堵情況會(huì)隨著時(shí)間而改變,車輛的速度也會(huì)因?qū)嶋H交通狀況而變化,這里通過擁堵延時(shí)指數(shù)觀察得到的交通情況與高德地圖《2022Q3中國(guó)主要城市交通分析報(bào)告》的結(jié)論相符,即在全天工作時(shí)段內(nèi),早高峰是07:00—09:00,晚高峰通常是17:00—19:00(由于時(shí)區(qū)原因,因此烏魯木齊市的早晚高峰時(shí)段有所不同)。

圖1 擁堵延時(shí)指數(shù)Fig.1 Congestion delay index

基于上述分析結(jié)果,參考JABALI等[26]提出方法,將1 d的工作時(shí)間劃分為5個(gè)工作時(shí)段,并假設(shè)每個(gè)時(shí)段內(nèi)的交通擁堵是恒定的,即在這一短時(shí)間段內(nèi)車輛的行駛速度保持不變,給出一種遵循FIFO準(zhǔn)則的跨時(shí)段的路段行駛時(shí)間計(jì)算方法。圖2(a)是不同時(shí)段車輛的行駛速度,圖2(b)是路徑(i,j)上根據(jù)車輛的行駛路程和離開時(shí)刻計(jì)算得到的行駛時(shí)間,其中,圖2(a)的橫軸表示整個(gè)工作時(shí)間,圖2(b)的橫軸是車輛離開客戶點(diǎn)i的時(shí)刻。

圖2 車輛行駛速度和時(shí)間Fig.2 Vehicle driving speed and time

(2)

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

TDGVRPTW的數(shù)學(xué)模型考慮了2個(gè)層次的目標(biāo),建立了以最小化碳排放量和總行駛時(shí)間的雙目標(biāo)模型,具體如下:

(3)

(4)

約束條件如下:

(5)

(6)

(7)

(8)

xijm≤xij,?(i,j)∈A,m∈M

(9)

(10)

(11)

(12)

qixij≤gij≤(W-qj)xij,?(i,j)∈A

(13)

φi=ai+δi

(14)

li≤φi≤ri

(15)

aj-wi=tij+L(1-xij),

?(i,j)∈A,L?0

(16)

(17)

xij∈{0,1},xijm∈{0,1},σk∈{0,1},

(18)

0≤qi≤W,?i∈C

(19)

式(3)和式(4)分別表示模型的2個(gè)目標(biāo)函數(shù);式(5)和式(6)表示每個(gè)客戶點(diǎn)只能被車輛訪問一次;式(7)確保使用的車輛數(shù)不超過配送中心擁有的車輛數(shù);式(8)表示車輛需要完整行駛2個(gè)客戶點(diǎn)之間的路程;式(9)和式(10)使xij和xijm狀態(tài)保持一致;式(11)保證車輛從配送中心出發(fā)完成運(yùn)輸任務(wù)后返回配送中心;式(12)和式(13)是車輛載重約束,確保車輛在行駛過程中的實(shí)時(shí)載重不超過車輛的最大載重;式(14)和式(15)是時(shí)間窗約束,如果車輛提前到達(dá)客戶點(diǎn),則需要等待直到客戶點(diǎn)允許進(jìn)行服務(wù)的最早時(shí)刻再進(jìn)行服務(wù),故φi=max(ai,li)且φi≤ri,即車輛不能超過最晚服務(wù)時(shí)間;式(16)是行程時(shí)間約束;式(17)是路徑(i,j)上行駛時(shí)間的計(jì)算方式;式(18)和式(19)給出了變量的取值范圍。

2 G-IEACO算法設(shè)計(jì)

VRP是一個(gè)NP-Hard組合優(yōu)化問題,通常使用精確解法、啟發(fā)式算法和元啟發(fā)式算法來獲得最優(yōu)解或近似最優(yōu)解。ACO算法能在動(dòng)態(tài)變化的環(huán)境中無需任何外部指導(dǎo)或控制解決幾何分布的NP-Hard組合優(yōu)化問題,由于具有動(dòng)態(tài)規(guī)劃等傳統(tǒng)算法不具備的解決大型組合優(yōu)化問題的優(yōu)勢(shì)而得到了廣泛應(yīng)用。因此,本文對(duì)傳統(tǒng)ACO算法做出了改進(jìn),應(yīng)用4種鄰域搜索算子來加強(qiáng)G-IEACO算法的局部搜索性能,在優(yōu)化的過程中加入大規(guī)模鄰域算法進(jìn)一步提高解的質(zhì)量,并利用輪盤賭策略改進(jìn)了算法的狀態(tài)轉(zhuǎn)移公式。根據(jù)TDGVRPTW的特性,加入信息素更新、解的分割和規(guī)避擁堵3個(gè)重要的改進(jìn)策略,設(shè)計(jì)G-IEACO算法。

2.1 編碼方式

針對(duì)車輛路徑問題的特點(diǎn),采用自然數(shù)編碼和解碼策略,將每一只螞蟻視為一輛配送車輛,螞蟻?zhàn)哌^的路線即為每一輛車服務(wù)的運(yùn)輸路線,配送中心的編號(hào)為0,n個(gè)客戶點(diǎn)的編號(hào)序列為{1,2,…,n}。例如,序列{0,2,8,3,0,6,7,5,1,0,9,10,4,0}對(duì)應(yīng){0,2,8,3,0}、{0,6,7,5,1,0}和{0,9,10,4,0}3條子路徑。

2.2 狀態(tài)轉(zhuǎn)移公式

人工螞蟻根據(jù)狀態(tài)轉(zhuǎn)移公式?jīng)Q定要訪問的下一個(gè)節(jié)點(diǎn),傳統(tǒng)ACO轉(zhuǎn)移概率由信息素濃度和啟發(fā)式因子決定,利用輪盤賭可以增強(qiáng)算法的全局搜索能力。計(jì)算過程如下:

(20)

(21)

(22)

2.3 解的分割策略

在G-IEACO算法中的可行解采用自然數(shù)編碼和解碼方式,編碼序列分割的目標(biāo)是從包含所有客戶的給定序列中生成使得車輛總行駛時(shí)間最小的可行解,并且在所得可行解中每個(gè)子路線必須滿足約束條件。將文獻(xiàn)[27]中的最優(yōu)分割用于TDGVRPTW,以確定給定編號(hào)序列分割的最佳方案,分割算法的基本流程如算法1所示。

算法1分割算法

輸入編號(hào)序列R={r1,r2,…,rn}

輸出可行解

1. F←ArcsCollection(R)∥將輸入的客戶點(diǎn)編號(hào)序列∥轉(zhuǎn)換為一系列的路徑(F)

2. S←ShortestPathCollection(F)∥對(duì)于每一對(duì)客戶∥點(diǎn),找出它們之間的最短路徑并放入集合S

3. BestTrvelTime←∞∥初始化最佳行駛時(shí)間

4. BestSegmentation←{}∥初始化最佳分割方案為空集

5. for s∈S do

6. if travelTime(s)

7. BestSegmentation←s∥如果是,則更新最佳分∥割方案

8. shortestTravelTime(s)=travelTime(s)∥更∥新記錄的最短行駛時(shí)間為當(dāng)前路徑的行駛時(shí)間

9. end if

10. end for

在分割算法中,將問題定義在一個(gè)有向無環(huán)圖G={N,F}上,其中,N是節(jié)點(diǎn)集,節(jié)點(diǎn)0表示配送中心,C=N{0}是客戶點(diǎn)集合,F是道路網(wǎng)絡(luò)上連接2個(gè)節(jié)點(diǎn)的路徑的集合。利用最短路徑算法可以確定從配送中心到節(jié)點(diǎn)n的最短路徑集合,最后需要為最優(yōu)解找到最佳的路徑分割方式,選擇行駛時(shí)間最小的集合的路徑。解決方案的有效性只取決于所得路線的數(shù)量,并且不能超過配送中心可用車輛的數(shù)量。

2.4 鄰域算子

為了增強(qiáng)算法的局部搜索能力和豐富構(gòu)造解的多樣性,在IEACO算法中加入4種鄰域操作算子,具體為路徑內(nèi)插入算子(Op1)、路徑間插入算子(Op2)、路徑內(nèi)2-opt鄰域算子(Op3)、路徑間2點(diǎn)交換算子(Op4)。

1)Op1。隨機(jī)選擇解S中的1條子路徑R1,再選出子路徑R1中的1個(gè)客戶點(diǎn)i,將i與R1中所有可行的位置進(jìn)行交換,記錄交換過程中使解S變得最優(yōu)的插入點(diǎn)point,遍歷完整個(gè)R1之后再根據(jù)point將i插回子路徑R1。

2)Op2。從解S中選出客戶點(diǎn)最少的子路徑R1,再隨機(jī)從解S中選擇另1條子路徑R2,確保R2≠R1。選中R1中最后1個(gè)客戶點(diǎn)i,按照Op1中的插入規(guī)則,將R1中的客戶點(diǎn)i插入子路徑R2。

3)Op3。從解S中隨機(jī)選出1條滿足客戶點(diǎn)數(shù)量不小于2的子路徑R1,選中R1中的2個(gè)客戶點(diǎn)i和j,i之前和j之后的路徑順序不變,將i到j(luò)的路徑翻轉(zhuǎn)后與i之前和j之后的路徑進(jìn)行拼接得到新的子路徑R′1。

4)Op4。隨機(jī)選出解S中的2條子路徑R1和R2,確保R2≠R1。從R1和R2中各選中1個(gè)客戶點(diǎn)i和j,交換這2個(gè)客戶點(diǎn)的位置。

2.5 信息素更新策略

在蟻群算法中,人工螞蟻由狀態(tài)轉(zhuǎn)移公式?jīng)Q定要訪問的下一個(gè)節(jié)點(diǎn),其轉(zhuǎn)移概率由信息素濃度和啟發(fā)式因子決定,合適的信息素更新策略在整個(gè)求解過程中至關(guān)重要。因信息素正反饋機(jī)制的存在,傳統(tǒng)ACO算法在迭代過程中容易造成優(yōu)質(zhì)路徑上信息素濃度過高,人工蟻群在這些路徑上的轉(zhuǎn)移概率過大,從而錯(cuò)過不是當(dāng)前最優(yōu)解的較高質(zhì)量的解,這將會(huì)使算法過早收斂而陷入局部最優(yōu),為了彌補(bǔ)這種不足,避免過早收斂和陷入局部最優(yōu),可以采用更新信息素策略,具體如下:

(23)

2)為避免過早收斂陷入局部最優(yōu),需要設(shè)置較大的信息素?fù)]發(fā)因子,而在算法后期,為加快算法的收斂速度,需要設(shè)置較小的信息素?fù)]發(fā)因子,加大各路徑上信息素濃度的差距,使螞蟻快速向高質(zhì)量的路徑移動(dòng)。因此,信息素?fù)]發(fā)因子應(yīng)該設(shè)置為一個(gè)動(dòng)態(tài)的值,式(24)是模擬信息素?fù)]發(fā)因子變化的階段函數(shù):

(24)

其中:ρmin表示信息素?fù)]發(fā)因子的下限值。

2.6 擁堵規(guī)避策略

常發(fā)性擁堵一般只發(fā)生于特定時(shí)段,具有一定規(guī)律,可以提前進(jìn)行預(yù)測(cè)。規(guī)避擁堵策略能有效減少車輛行駛時(shí)間和環(huán)境污染。由于車輛在2個(gè)地點(diǎn)之間的行駛時(shí)間和碳排放量與行駛的速度有關(guān),而行車速度又取決于車輛所在時(shí)段,因此可以通過停車等待來避開嚴(yán)重交通擁堵的時(shí)段,最大限度地減少每條路線的行駛時(shí)間和碳排放量。假設(shè)[Ts,Te]時(shí)段是嚴(yán)重?fù)矶缕?車輛位于路徑(i,j),Tk是當(dāng)前時(shí)間點(diǎn),規(guī)避擁堵策略具體如下:

1)Tk>Te,表示當(dāng)車輛行駛到原擁堵路段時(shí),道路上發(fā)生的擁堵已經(jīng)結(jié)束,車輛正常行駛,不停車等待。

2)TkTs,則表明車輛在行駛途中會(huì)發(fā)生交通擁堵,車輛需要在時(shí)刻Ts時(shí)在路徑(i,j)上合適的點(diǎn)處等待,直到嚴(yán)重?fù)矶陆Y(jié)束。

3)Ts

2.7 G-IEACO算法流程

首先,利用改進(jìn)的螞蟻狀態(tài)轉(zhuǎn)移概率公式構(gòu)造得到集合P,按照分割策略對(duì)P中的自然數(shù)序列進(jìn)行分割解碼,解碼后通過計(jì)算得到集合P中的最優(yōu)解SbestRoute1。然后,在SbestRoute1的基礎(chǔ)上,根據(jù)4種鄰域算子以及大規(guī)模鄰域算法得到本次迭代的最優(yōu)解SbestRoute2,并更新歷史最優(yōu)解SbestEver。接著,在確定SbestRoute2和SbestEver后,按照信息素更新策略更新路徑上的信息素,同時(shí)重新計(jì)算信息素?fù)]發(fā)因子ρiter的值。最后,依據(jù)規(guī)避擁堵策略調(diào)度車輛得到最終解決方案Ssolution。G-IEACO具體執(zhí)行步驟如算法2所示。

算法2G-IEACO算法

輸入客戶點(diǎn)信息

輸出全局最優(yōu)解Ssolution

1. SbestEver← {}

2. while iter≤itermaxdo

3. ρiter=0.8×ρiter-1

5. 利用分割算法從集合P選擇最優(yōu)解SbestRoute1

6. 應(yīng)用4種鄰域搜索算子和LNS算法對(duì)SbestRoute1進(jìn)行優(yōu)化獲得可行解SbestRoute2

7. if fitness(SbestRoute2)>fitness(SbestEver)

8. 更新歷史最優(yōu)解

9. SbestEver←SbestRoute2

10. end if

11. 根據(jù)SbestRoute2和歷史最優(yōu)解SbestEver更新全局信息素和局部信息素

12. δaward=(SbestRoute2-SbestEver)/SbestRoute2

13. 給本次迭代的最優(yōu)解SbestRoute2額外增加一個(gè)信息素獎(jiǎng)勵(lì)值δaward

14. if ρiter>ρmin∩iter>1

15. ρiter=0.8×ρiter-1

16. else if

17. ρiter=ρmin

18. end if

19. end while

20.對(duì)SbestEver采用規(guī)避擁堵策略,調(diào)度車輛獲得全局最優(yōu)解Ssolution

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

由于沒有TDGVRPTW的標(biāo)準(zhǔn)測(cè)試庫(kù),為了驗(yàn)證算法的適用性與有效性,采用Solomon標(biāo)準(zhǔn)測(cè)試集中2種不同規(guī)模(客戶規(guī)模為50和100)的算例進(jìn)行仿真實(shí)驗(yàn)。每個(gè)算例都有唯一的配送中心,并按照其地理分布分為R2類和RC2類。在R2類的算例中,客戶的地理分布是隨機(jī)的;在RC2類的算例中,大部分的客戶點(diǎn)為隨機(jī)分布,小部分的客戶點(diǎn)為集中分布。此外,R2類和RC2類算例的時(shí)間窗較大,每輛車能服務(wù)的客戶點(diǎn)較多,允許更少的車輛完成配送任務(wù)。為符合TDGVRPTW的測(cè)試要求,參考文獻(xiàn)[28]的方式,并做出如下補(bǔ)充:設(shè)定配送中心的工作時(shí)間為06:30—22:30,即車輛最早從配送中心出發(fā)的時(shí)刻為06:30,允許車輛最晚回到配送中心的時(shí)刻為22:30,則配送中心在1 d中的服務(wù)時(shí)長(zhǎng)為960 min。

根據(jù)城市擁堵延時(shí)指數(shù),將1 d的工作時(shí)間劃分為5段。將06:30—07:00、09:00—17:00和19:00—22:30設(shè)置為正常時(shí)段,將07:00—09:00和17:00—19:00設(shè)為城市交通擁堵時(shí)段。在正常時(shí)段,車輛的行駛速度為在[50 km/h, 70 km/h]內(nèi)隨機(jī)產(chǎn)生;在擁堵時(shí)段,車輛的行駛速度在[20 km/h, 40 km/h]內(nèi)隨機(jī)產(chǎn)生。ACO算法的參數(shù)設(shè)置如表2所示。

表2 ACO算法參數(shù)設(shè)置Table 2 Parameter settings of ACO algorithm

算法代碼運(yùn)行在64位Windows操作系統(tǒng)上,處理器為AMD Ryzen7 5800HS Creator Edition 3.20 GHz,內(nèi)存為16 GB。

3.2 結(jié)果分析

在實(shí)驗(yàn)中,以優(yōu)化車輛碳排放量和車輛總行駛時(shí)間為目標(biāo)。為避免偶然性,減少實(shí)驗(yàn)誤差,對(duì)每1個(gè)測(cè)試算例均運(yùn)行10次,從10次運(yùn)行結(jié)果中選出最優(yōu)解。TT表示車輛總行駛時(shí)間,TCO2代表碳排放量,TA表示車輛總使用時(shí)間(由車輛總行駛時(shí)間、總等待時(shí)間和在客戶點(diǎn)處服務(wù)的時(shí)間共同決定)。

為驗(yàn)證車輛規(guī)避擁堵策略對(duì)車輛行駛時(shí)間、碳排放量和總使用時(shí)間的影響,選擇客戶規(guī)模為50的R2類和RC2類算例進(jìn)一步進(jìn)行測(cè)試,如表3所示。由表3可以看出,車輛選擇規(guī)避交通擁堵期時(shí)最多能減少3.96%的碳排放量,平均減少1.67%的碳排放量,而車輛總行駛時(shí)間最多能降低16.19%,平均減少7.97%,說明規(guī)避交通擁堵策略確實(shí)能有效縮短車輛總行駛時(shí)間和有效降低車輛碳排放量,實(shí)現(xiàn)低碳出行的目的,但由于在避開高峰期時(shí)在某些路段選擇停車等待的策略,因此可能致使車輛總使用時(shí)間會(huì)有所增加。

表3 規(guī)避擁堵與不規(guī)避擁堵的實(shí)驗(yàn)結(jié)果比較Table 3 Comparison of experimental results between avoiding congestion and not avoiding congestion

又由表3可以看出,與不停車等待主動(dòng)規(guī)避擁堵相比,選擇規(guī)避擁堵會(huì)延長(zhǎng)車輛總使用時(shí)間,平均延長(zhǎng)8.46%的總時(shí)間,可見規(guī)避擁堵策略對(duì)車輛的總使用時(shí)間產(chǎn)生的影響比較明顯,特別是對(duì)于硬時(shí)間窗的車輛路徑優(yōu)化問題,在實(shí)際運(yùn)輸過程中需要在車輛總使用時(shí)間成本與節(jié)能環(huán)保之間做出取舍權(quán)衡。綜上,表3的結(jié)果符合理論分析結(jié)果。

為了進(jìn)一步評(píng)估算法的有效性以及處理較大規(guī)模算例的效果,選用客戶規(guī)模為100的R2類和RC2類算例執(zhí)行了基準(zhǔn)測(cè)試,并且將G-IEACO算法與遺傳算法(GA)進(jìn)行實(shí)驗(yàn)對(duì)比,采用了不同客戶點(diǎn)分布情況的算例。為了實(shí)驗(yàn)的公平性以及避免偶然誤差,GA與G-IEACO算法在每一個(gè)測(cè)試集中算法均獨(dú)立運(yùn)行10次,從10次運(yùn)行結(jié)果中選出最優(yōu)解進(jìn)行比較,每個(gè)實(shí)例的結(jié)果如表4所示。

表4 GA與G-IEACO算法實(shí)驗(yàn)結(jié)果比較Table 4 Comparison of experimental results between the GA and G-IEACO algorithms

根據(jù)表4中的數(shù)據(jù)可分析得出:對(duì)于車輛總行駛時(shí)間,G-IEACO算法在所有算例上的表現(xiàn)均明顯優(yōu)于GA,最高能縮短25.18%,最低能縮短2.60%,平均節(jié)約行駛時(shí)間為13.32%;對(duì)于車輛的碳排放量(TCO2),G-IEACO算法在所有算例上的計(jì)算結(jié)果也均優(yōu)于GA,最高減少24.92%,最低減少1.38%,平均優(yōu)化率為13.64%。這是由于車輛在2個(gè)地點(diǎn)之間的行駛時(shí)間和碳排放量與行駛速度有關(guān),根據(jù)規(guī)避交通擁堵策略,行車速度取決于車輛所在時(shí)段,故通過停車等待來避開嚴(yán)重交通擁堵的時(shí)段,最大限度地減少了每條路線的行駛時(shí)間和碳排放量,因此基于規(guī)避交通擁堵策略的G-IEACO算法能有效縮短車輛的行駛時(shí)間以及明顯降低車輛的溫室氣體排放。關(guān)于車輛的總使用時(shí)間,G-IEACO算法在大部分算例上均高于GA,這也從間接驗(yàn)證了規(guī)避擁堵策略的有效性,符合表3的實(shí)驗(yàn)結(jié)果,即規(guī)避擁堵策略能明顯降低車輛的污染物排放量,但正因?yàn)橐?guī)避過程中的停車等待動(dòng)作可能在某些情況下會(huì)使車輛總使用時(shí)間有所增加,即以增加車輛總使用時(shí)間為代價(jià),降低了車輛的污染物排放量。

圖3給出了GA和G-IEACO算法在客戶規(guī)模為100的RC208算例上分別運(yùn)行10次的優(yōu)化結(jié)果,GA在2個(gè)目標(biāo)上的優(yōu)化結(jié)果均劣于G-IEACO算法,并且G-IEACO算法所求解的波動(dòng)較小、穩(wěn)定性較強(qiáng)。

圖3 2種算法運(yùn)行10次所得解Fig.3 Solutions obtained by two algorithms running ten times

從節(jié)能減排的角度出發(fā),G-IEACO算法在解的質(zhì)量和穩(wěn)定性上要優(yōu)于GA,以增加車輛總使用時(shí)間為代價(jià),可以有效規(guī)避擁堵路況、降低車輛總行駛時(shí)間、減少車輛的油耗和溫室氣體排放。本節(jié)實(shí)驗(yàn)結(jié)果可以給物流企業(yè)在低碳條件下的車輛配送方案提供一定的參考。

4 結(jié)束語

針對(duì)傳統(tǒng)ACO算法在解決VRP時(shí)容易陷入局部最優(yōu)及過早收斂的問題,本文提出一種綠色智能進(jìn)化蟻群優(yōu)化算法。該算法設(shè)計(jì)并應(yīng)用了多種鄰域搜索算子,增強(qiáng)了算法的全局搜索和局部搜索能力,通過大規(guī)模鄰域搜索算法擴(kuò)大了搜索空間,提高了解的質(zhì)量,利用輪盤賭策略改進(jìn)了算法的狀態(tài)轉(zhuǎn)移規(guī)則,進(jìn)一步優(yōu)化結(jié)果。同時(shí),針對(duì)城市交通擁堵現(xiàn)狀以及車輛碳排放情況,引入規(guī)避擁堵策略,力求最小化行駛時(shí)間和碳排放量,平衡時(shí)間成本和環(huán)境成本。通過在Solomon測(cè)試集的不同類型的算例上進(jìn)行對(duì)比實(shí)驗(yàn),結(jié)果表明對(duì)于大規(guī)模算例,基于時(shí)變交通擁堵的G-IEACO算法相比于傳統(tǒng)算法能有效降低車輛行駛時(shí)間和碳排放量。以上結(jié)果驗(yàn)證了該算法在優(yōu)化城市物流配送方面的潛力,有助于實(shí)現(xiàn)綠色物流的目標(biāo),并且對(duì)于尋求實(shí)施低碳、高效物流策略的城市規(guī)劃者和物流企業(yè)具有重要的借鑒意義,同時(shí)可以提示企業(yè)和政策制定者在制定交通管理和物流策略時(shí),綜合考慮交通擁堵模式、環(huán)境影響和經(jīng)濟(jì)效益,以實(shí)現(xiàn)更可持續(xù)的城市發(fā)展。