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

葛非,閔珊,邱含,代振陽,楊智敏

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

0 引言

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

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

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

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

1.2 符號說明

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

表1 符號定義Table 1 Symbol definition

1.3 車輛碳排放的計算方法

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

F=RFR·T=

(1)

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

1.4 時段劃分方式

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

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

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

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

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

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

(2)

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

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

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

VRP是一個NP-Hard組合優(yōu)化問題,通常使用精確解法、啟發(fā)式算法和元啟發(fā)式算法來獲得最優(yōu)解或近似最優(yōu)解。ACO算法能在動態(tài)變化的環(huán)境中無需任何外部指導(dǎo)或控制解決幾何分布的NP-Hard組合優(yōu)化問題,由于具有動態(tài)規(guī)劃等傳統(tǒng)算法不具備的解決大型組合優(yōu)化問題的優(yōu)勢而得到了廣泛應(yīng)用。因此,本文對傳統(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個重要的改進(jìn)策略,設(shè)計G-IEACO算法。

2.1 編碼方式

針對車輛路徑問題的特點,采用自然數(shù)編碼和解碼策略,將每一只螞蟻視為一輛配送車輛,螞蟻走過的路線即為每一輛車服務(wù)的運輸路線,配送中心的編號為0,n個客戶點的編號序列為{1,2,…,n}。例如,序列{0,2,8,3,0,6,7,5,1,0,9,10,4,0}對應(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定要訪問的下一個節(jié)點,傳統(tǒng)ACO轉(zhuǎn)移概率由信息素濃度和啟發(fā)式因子決定,利用輪盤賭可以增強(qiáng)算法的全局搜索能力。計算過程如下:

(20)

(21)

(22)

2.3 解的分割策略

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

算法1分割算法

輸入編號序列R={r1,r2,…,rn}

輸出可行解

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

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

3. BestTrvelTime←∞∥初始化最佳行駛時間

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

5. for s∈S do

6. if travelTime(s)

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

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

9. end if

10. end for

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

2.4 鄰域算子

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

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

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

3)Op3。從解S中隨機(jī)選出1條滿足客戶點數(shù)量不小于2的子路徑R1,選中R1中的2個客戶點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個客戶點i和j,交換這2個客戶點的位置。

2.5 信息素更新策略

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

(23)

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

(24)

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

2.6 擁堵規(guī)避策略

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

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

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

3)Ts

2.7 G-IEACO算法流程

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

算法2G-IEACO算法

輸入客戶點信息

輸出全局最優(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算法對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額外增加一個信息素獎勵值δ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.對SbestEver采用規(guī)避擁堵策略,調(diào)度車輛獲得全局最優(yōu)解Ssolution

3 實驗與結(jié)果分析

3.1 實驗設(shè)置

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

根據(jù)城市擁堵延時指數(shù),將1 d的工作時間劃分為5段。將06:30—07:00、09:00—17:00和19:00—22:30設(shè)置為正常時段,將07:00—09:00和17:00—19:00設(shè)為城市交通擁堵時段。在正常時段,車輛的行駛速度為在[50 km/h, 70 km/h]內(nèi)隨機(jī)產(chǎn)生;在擁堵時段,車輛的行駛速度在[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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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