楊森炎，寧連舉，商攀

(1.北京郵電大學(xué)，a.現(xiàn)代郵政學(xué)院(自動(dòng)化學(xué)院)，b.經(jīng)濟(jì)管理學(xué)院，北京100876；2.北京交通大學(xué)，交通運(yùn)輸學(xué)院，北京100044)

0 引言

電動(dòng)車(chē)輛具備低能耗、低排放、低噪聲等優(yōu)勢(shì)，已廣泛用于城市“最后一公里”物流配送過(guò)程。由于電池續(xù)航里程有限，電動(dòng)車(chē)輛需要在途中補(bǔ)充電量。充電設(shè)施不足導(dǎo)致車(chē)輛繞路或排隊(duì)充電現(xiàn)象[1]。為提高電動(dòng)物流車(chē)輛服務(wù)效率，學(xué)者們基于經(jīng)典的車(chē)輛路徑問(wèn)題，考慮充耗電過(guò)程、電池容量等限制條件，提出電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題(EVRP)。Schneider 等[2]假設(shè)充電量與充電時(shí)間呈線性關(guān)系，研究帶時(shí)間窗的EVRP問(wèn)題(EVRPTW)，設(shè)計(jì)了可變鄰域搜索算法與禁忌搜索結(jié)合的混合啟發(fā)式求解算法。Montoya等[3]提出分段線性逼近方法，研究非線性充電過(guò)程的EVRPTW 問(wèn)題。Goeke 等[4]研究電動(dòng)車(chē)輛和內(nèi)燃機(jī)車(chē)混合下的EVRPTW問(wèn)題。Felipe等[5]研究部分充電策略和不同充電技術(shù)下的電動(dòng)車(chē)輛路徑規(guī)劃和充電決策優(yōu)化方法。Keskin等[6]對(duì)比了部分充電和完全充電策略下的路徑優(yōu)化方案。Hiermann 等[7]研究考慮不同車(chē)輛配置的EVRPTW 問(wèn)題，提出基于自適應(yīng)大鄰域搜索的混合啟發(fā)式算法，通過(guò)智能局部搜索改進(jìn)路線。

既有關(guān)于EVRPTW 問(wèn)題的研究在車(chē)輛行駛、充耗電過(guò)程、充電站能力等方面考慮的約束條件較為復(fù)雜。傳統(tǒng)的基于物理運(yùn)輸網(wǎng)絡(luò)的建模方法難以充分考慮客戶(hù)需求和電動(dòng)車(chē)輛運(yùn)行狀態(tài)的時(shí)空特性，需要設(shè)置時(shí)間、空間、載重狀態(tài)、電量狀態(tài)等多種類(lèi)變量，建立大量的復(fù)雜約束條件以描述變量之間的相互關(guān)系，因此模型結(jié)構(gòu)較為復(fù)雜。常采用的智能算法雖然通用性強(qiáng)，時(shí)效性較高，但難以從理論上保證解的質(zhì)量。

近年來(lái)學(xué)者們提出采用時(shí)空網(wǎng)絡(luò)的建模方法求解車(chē)輛路徑優(yōu)化問(wèn)題，通過(guò)系統(tǒng)離散化方法處理復(fù)雜約束，可以有效簡(jiǎn)化模型，降低問(wèn)題的求解難度。Mahmoudi等[8]提出時(shí)空網(wǎng)絡(luò)的建?？蚣埽蠼獬鞘薪煌▓?chǎng)景下接送乘客的車(chē)輛路徑問(wèn)題。Yang等[9]基于離散的時(shí)空狀態(tài)網(wǎng)絡(luò)表示方法，對(duì)考慮混合取送的物流車(chē)輛路徑優(yōu)化問(wèn)題進(jìn)行建模和求解。

本文運(yùn)用離散的時(shí)空狀態(tài)網(wǎng)絡(luò)方法，研究考慮充電策略的電動(dòng)物流車(chē)輛路徑優(yōu)化問(wèn)題，對(duì)電動(dòng)物流車(chē)輛路徑規(guī)劃和充耗電過(guò)程進(jìn)行離散化表示，建立多商品網(wǎng)絡(luò)流優(yōu)化模型，在時(shí)間、空間和狀態(tài)維度上對(duì)電動(dòng)物流車(chē)輛路徑以及充電策略實(shí)現(xiàn)同步優(yōu)化，并設(shè)計(jì)基于增廣拉格朗日松弛技術(shù)的求解算法，將原問(wèn)題分解為一系列規(guī)模較小的最短路徑子問(wèn)題，可以快速找到可行解。

1 模型構(gòu)建

1.1 問(wèn)題描述

本文采用部分充電策略，即車(chē)輛中途只需補(bǔ)充支撐其完成剩余配送任務(wù)的部分電量，可以減少不必要的充電等待時(shí)間。考慮電池容量、車(chē)輛承載能力、充電站能力、客戶(hù)服務(wù)時(shí)間窗、路網(wǎng)空間結(jié)構(gòu)等約束，優(yōu)化客戶(hù)的服務(wù)順序、充電站點(diǎn)選擇及單次充電時(shí)間。模型假設(shè)如下：

(1)配送中心車(chē)輛充足，車(chē)輛出發(fā)時(shí)處于滿電狀態(tài)，完成配送后返回到原配送中心；

(2)車(chē)輛的耗電量與行駛時(shí)間成正比，當(dāng)剩余電池容量低于最小閾值時(shí)需補(bǔ)充電量；

(3)充電速率固定，充電量與充電時(shí)間滿足線性關(guān)系；

(4)不考慮路網(wǎng)交通狀態(tài)的影響，車(chē)輛保持勻速行駛。

1.2 符號(hào)定義

(1)集合和元素

N——物理網(wǎng)絡(luò)節(jié)點(diǎn)集合；

T——時(shí)間點(diǎn)集合；

V——電動(dòng)車(chē)輛集合；

P——客戶(hù)集合；

S——充電站點(diǎn)集合；

W——車(chē)輛剩余載貨量狀態(tài)值集合；

L——空間路段集合，L={(i,j)|i∈N,j∈N}

Av——車(chē)輛v對(duì)應(yīng)的時(shí)空狀態(tài)弧集合，Av={(i,j,t,t′,w,w′,e,e′)|i∈N,j∈N}；

ψp,v——車(chē)輛v服務(wù)客戶(hù)配送需求的弧集合，ψp,v?Av；

ψs,v——車(chē)輛v在充電站充電的弧集合，ψs,v?Av；

i,j,j′,j″——節(jié)點(diǎn)編號(hào)，i,j,j′,j″∈N；

t,t′,t″——時(shí)間編號(hào)，t,t′,t″∈T；

v,v′——車(chē)輛編號(hào)，v,v′∈V；

p——客戶(hù)編號(hào)，p∈P；

s——充電站編號(hào)，s∈S；

w,w′,w″——剩余載貨量狀態(tài)值，w,w′,w″∈W；

e,e′,e″——剩余電量狀態(tài)；

(i,t,w,e)——時(shí)空狀態(tài)點(diǎn)；

(i,j,t,t′,w,w′,e,e′)——時(shí)空狀態(tài)??；

o——配送中心節(jié)點(diǎn)；

to,v——車(chē)輛v離開(kāi)配送中心o的時(shí)間；

t′o,v——車(chē)輛v返回配送中心o的時(shí)間；

wo,v——車(chē)輛v離開(kāi)配送中心o的剩余載貨量；

w′o,v——車(chē)輛v返回配送中心o的剩余載貨量；

evo——車(chē)輛v離開(kāi)配送中心o的剩余電量；

e′o,v——車(chē)輛v返回配送中心o的剩余電量。

(2)參數(shù)

Emin——最小剩余電量閾值；

Emax——電池容量；

ξs——充電站s的充電能力，即最多可允許同時(shí)充電的車(chē)輛數(shù)量；

γs——充電站s的充電速率；

κv——車(chē)輛v的耗電速率；

χv——車(chē)輛v的最大承載能力；

[te,p,tl,p]——客戶(hù)p的服務(wù)時(shí)間窗，其中，te,p為可服務(wù)p的最早時(shí)間，tl,p為可服務(wù)p的最晚時(shí)刻；

c(i,j,t,t′,w,w′,e,e′)——時(shí)空狀態(tài)弧(i,j,t,t′,w,w′,e,e′)的配送成本。

(3)決策變量

y(i,j,t,t′,w,w′,e,e′),v——若車(chē)輛v經(jīng)過(guò)弧(i,j,t,t′,w,w′,e,e′)則為1，否則為0。

1.3 構(gòu)建離散時(shí)空狀態(tài)網(wǎng)絡(luò)

時(shí)空狀態(tài)網(wǎng)絡(luò)具有時(shí)間、空間和狀態(tài)3 個(gè)維度。考慮到配送過(guò)程同時(shí)受車(chē)輛承載能力和電池續(xù)航能力限制，對(duì)狀態(tài)維度進(jìn)行擴(kuò)展，用狀態(tài)向量[w,e] 表示車(chē)輛的載貨量狀態(tài)和剩余電量狀態(tài)。車(chē)輛經(jīng)過(guò)節(jié)點(diǎn)i的時(shí)空狀態(tài)可以用[i,t,w,e] 表示，即車(chē)輛在t時(shí)刻行駛到節(jié)點(diǎn)i，載貨量w，剩余可用電量e。時(shí)空狀態(tài)網(wǎng)絡(luò)中任意兩個(gè)相鄰節(jié)點(diǎn)[i,t,w,e]和 [j,t′,w′,e′]之間存在一條時(shí)空狀態(tài)弧(i,j,t,t′,w,w′,e,e′)，共有4種不同類(lèi)型的時(shí)空狀態(tài)弧，分別是運(yùn)輸弧、充電弧、配送弧及等待弧。需要根據(jù)以下規(guī)則構(gòu)建時(shí)空狀態(tài)網(wǎng)絡(luò)。

(1)針對(duì)EVRPTW 問(wèn)題，對(duì)時(shí)間和車(chē)輛載貨狀態(tài)維度進(jìn)行離散化，構(gòu)建時(shí)空狀態(tài)點(diǎn)集合。

(2)基于物理空間網(wǎng)絡(luò)節(jié)點(diǎn)之間的鄰接關(guān)系，增加離散的時(shí)間和狀態(tài)維度，建立時(shí)空狀態(tài)弧集合A，包括運(yùn)輸弧集合ψT、充電弧集合ψS、配送弧集合ψP和等待弧集合ψW，即A=ψT?ψS?ψP?ψW，具體如下：

添加運(yùn)輸弧，對(duì)于任意i,j∈N，t∈T，Ti,j,t為t時(shí)刻路段(i,j)的運(yùn)輸時(shí)間，車(chē)輛耗電速率是κv，添加 (i,j,t,t′,w,w′,e,e′)到ψT，且滿足關(guān)系：t′=t+Ti,j,t,w′=w,e′=e-κv·Ti,j,t。

添加充電弧，對(duì)于任意s∈S,t∈T，充電站s的充電速率為γs，添加(s,s,t,t+1,w,w′,e,e′)到ψS，且滿足關(guān)系：w′=w,e′=e+γs×1。

添加配送弧，對(duì)于任意t∈T，p∈P，客戶(hù)p位于弧(ip,jp)上，其配送需求為np，Tp,t為t時(shí)刻服務(wù)客戶(hù)p所需的時(shí)間，車(chē)輛耗電速率為κ′v，添加(ip,jp,t,t′,w,w′,e,e′)到ψP，且滿足關(guān)系 ：t′=t+Tp,t,w′=w-np,e′=e-κ′v·Tp,t。

添加等待弧，對(duì)于任意i∈N，t∈T，添加(i,i,t,t+1,w,w′,e,e′)到ψW，且滿足關(guān)系：w′=w,e′=e。

(3)對(duì)于任意一條時(shí)空狀態(tài)弧a∈A，設(shè)置對(duì)應(yīng)的成本ca。

以8點(diǎn)配送網(wǎng)絡(luò)為例，客戶(hù)位于空間網(wǎng)絡(luò)上相鄰兩個(gè)節(jié)點(diǎn)之間，如圖1所示，假設(shè)電池最大容量Emax=10，最小電量閾值Emin=2。電動(dòng)車(chē)輛從配送中心出發(fā)時(shí)處于滿載和滿電狀態(tài)，為5位客戶(hù)配送貨物，當(dāng)e低于Emin時(shí)，需要選擇充電站進(jìn)行充電。最優(yōu)路徑節(jié)點(diǎn)順序是“1→2→4→5→7→3→1”，剩余載貨量和電量的時(shí)空變化過(guò)程如圖2所示。車(chē)輛在節(jié)點(diǎn)7 完成充電的過(guò)程可以用兩個(gè)充電弧(7,7,4,5,3,3,2,6)和(7,7,5,6,3,3,6,10)表示。車(chē)輛完成對(duì)客戶(hù)1 的配送服務(wù)過(guò)程可以用配送弧(2,4,1,2,8,7,8,6)表示。車(chē)輛在完成客戶(hù)的配送服務(wù)之后載貨量和剩余電量均降低。

圖1 配送網(wǎng)絡(luò)示意圖Fig.1 Diagram of distribution network

圖2 電動(dòng)物流車(chē)行駛過(guò)程中的時(shí)空狀態(tài)變化Fig.2 Spatial-temporal state changes during electric logistics vehicle driving

客戶(hù)服務(wù)時(shí)間窗口、車(chē)輛承載能力和電池容量等實(shí)際約束條件以及時(shí)間、載貨量和電量狀態(tài)的更新直接嵌入時(shí)空狀態(tài)網(wǎng)絡(luò)的構(gòu)建過(guò)程，縮減算法的搜索空間，提高計(jì)算效率。具體如下：

①客戶(hù)配送服務(wù)時(shí)間窗約束，車(chē)輛需要在客戶(hù)p的服務(wù)時(shí)間窗[te,p,tl,p] 內(nèi)配送貨物，即配送時(shí)間范圍是te,p≤t≤tl,p。

②車(chē)輛承載能力約束，任意車(chē)輛v在任意時(shí)刻t的剩余載貨量wv,t不能超過(guò)其承載能力χv，即0 ≤wv,t≤χv。

③電池容量約束，任意車(chē)輛v在任意時(shí)刻t的剩余可用電量狀態(tài)ev,t不小于閾值Emin，且不超過(guò)電池容量Emax，即Emin≤ev,t≤Emax。

④時(shí)間更新規(guī)則，對(duì)于任意時(shí)空狀態(tài)弧(i,j,t,t′,w,w′,e,e′)，車(chē)輛經(jīng)過(guò)相鄰節(jié)點(diǎn)的時(shí)間關(guān)系滿足t′=t+Ti,j,t。

⑤電量消耗過(guò)程，對(duì)于任意運(yùn)輸弧(i,j,t,t′,w,w′,e,e′)，車(chē)輛經(jīng)過(guò)相鄰節(jié)點(diǎn)的能量更新規(guī)則為e′=e-κv·Ti,j,t。

⑥充電過(guò)程，對(duì)于任意充電弧(i,i,t,t+1w,w′,e,e′)，車(chē)輛的能量更新規(guī)則為e′=e+γs×1。

1.4 多商品網(wǎng)絡(luò)流優(yōu)化模型

以最小化總配送成本為目標(biāo)，針對(duì)EVRPTW問(wèn)題，構(gòu)建多商品網(wǎng)絡(luò)流優(yōu)化模型為

式(1)為目標(biāo)函數(shù)，最小化總配送成本；式(2)～式(4)為流量平衡約束，式(2)保證車(chē)輛從配送中心出發(fā)，式(3)保證車(chē)輛最后返回配送中心，式(4)保證每條路徑任意中間節(jié)點(diǎn)的輸入流和輸出流平衡；式(5)確保每位客戶(hù)的配送需求被服務(wù)；式(6)保證每個(gè)充電站同時(shí)充電的車(chē)輛數(shù)不超過(guò)其充電站能力；式(7)為決策變量。

為保證使用盡可能少的電動(dòng)車(chē)輛，設(shè)置從配送中心直接返回到配送中心的虛擬弧，虛擬弧的成本為0。對(duì)于無(wú)需完成配送任務(wù)的車(chē)輛，直接通過(guò)虛擬弧返回配送中心，不會(huì)進(jìn)入正常的服務(wù)網(wǎng)絡(luò)。

時(shí)空狀態(tài)網(wǎng)絡(luò)建模方法是在傳統(tǒng)物理網(wǎng)絡(luò)上增加了時(shí)間和狀態(tài)維度，可以清晰地刻畫(huà)車(chē)輛運(yùn)行過(guò)程中時(shí)間變化、空間變化及狀態(tài)轉(zhuǎn)移之間的耦合關(guān)系，構(gòu)建復(fù)雜場(chǎng)景下的網(wǎng)絡(luò)流優(yōu)化模型，適用于解決帶有時(shí)間窗約束或者時(shí)變運(yùn)輸網(wǎng)絡(luò)優(yōu)化問(wèn)題。雖然該方法可以顯著減少EVRPTW 問(wèn)題的變量種類(lèi)和約束數(shù)量，但是求解上述0-1 整數(shù)規(guī)劃模型仍然屬于NP-hard，時(shí)間和狀態(tài)維度的離散化導(dǎo)致搜索空間增大，在計(jì)算復(fù)雜度上存在較大的挑戰(zhàn)。

2 算法設(shè)計(jì)

2.1 模型分解

為使模型簡(jiǎn)潔，用a表示時(shí)空狀態(tài)弧(i,j,t,t′,w,w′,e,e′)。采用拉格朗日松弛方法，把上述整數(shù)規(guī)劃模型的式(5)和式(6)松弛到目標(biāo)函數(shù)式(1)中，得到拉格朗日松弛模型(LR)為

保留約束條件式(2)～式(4)和式(7)。

分解可得單輛車(chē)的LR子模型為

化簡(jiǎn)為

成本為

該問(wèn)題是標(biāo)準(zhǔn)最短路徑子問(wèn)題，具有相同的拉格朗日乘子λp和λs,t。每次迭代，相同車(chē)輛會(huì)傾向于選擇服務(wù)同一客戶(hù)，導(dǎo)致解的對(duì)稱(chēng)性問(wèn)題，影響求解效率。為克服對(duì)稱(chēng)性問(wèn)題，在LR 模型的基礎(chǔ)上增加一個(gè)增廣二次項(xiàng)，構(gòu)建增廣拉格朗日松弛模型(ALR)為

式中：θp和θs為懲罰參數(shù)。二次懲罰項(xiàng)的引入導(dǎo)致ALR模型難以分解。為把ALR模型分解為易求解的子模型，對(duì)模型進(jìn)行線性化處理。定義αp,v和βs,t,v為

式中：αp,v為客戶(hù)p除了車(chē)輛v之外被其他車(chē)輛服務(wù)的總次數(shù)；βs,t,v為除了車(chē)輛v之外在充電站s充電的總車(chē)輛數(shù)。車(chē)輛v對(duì)應(yīng)的子問(wèn)題目標(biāo)函數(shù)為

由于ya,v是0-1 變量，二次項(xiàng)等價(jià)于，進(jìn)一步化簡(jiǎn)為

根據(jù)式(16)和式(19)，式(15)可進(jìn)一步化簡(jiǎn)為

式中：?為常數(shù)項(xiàng)。

2.2 求解算法

采用塊坐標(biāo)下降法(BCD)的分解優(yōu)化框架，嵌入前向動(dòng)態(tài)規(guī)劃(DP)算法，對(duì)ALR 模型分解得到的最短路徑子模型進(jìn)行循環(huán)迭代求解。在BCD框架中，變量和約束條件按車(chē)輛被分為若干個(gè)模塊，針對(duì)每個(gè)模塊依次最小化目標(biāo)函數(shù)[10]。假設(shè)配送中心有M輛電動(dòng)車(chē)，編號(hào)m=1,2,…,M，任意車(chē)輛vm對(duì)應(yīng)的時(shí)空狀態(tài)弧變量集合設(shè)為Ym，M輛電動(dòng)車(chē)的時(shí)空狀態(tài)弧變量總集合設(shè)為Y。ALR 模型的目標(biāo)函數(shù)為

式中：y∈Y=Y1×Y2×…×Ym?Rn，Ym?Rnm，變量y1,y2,…,yM依次更新公式為

在第k+1 次迭代，為了優(yōu)化第m輛電動(dòng)車(chē)的路徑，完成前i-1 輛電動(dòng)車(chē)的時(shí)空狀態(tài)路徑優(yōu)化后，更新車(chē)輛路徑方案，后M-m輛車(chē)的路徑仍然保持第k次迭代的優(yōu)化方案懲罰參數(shù)θp和θs分別是拉格朗日乘子和的更新步長(zhǎng)，即

基于ALR 的方法可以通過(guò)增設(shè)二次懲罰項(xiàng)，克服LR 方法存在的對(duì)稱(chēng)性問(wèn)題，提高算法的收斂速率；另一方面，每次迭代計(jì)算最優(yōu)上界和下界的間隙GGAP，可以從理論上評(píng)估可行解的質(zhì)量，具體步驟如下。

Step 1 初始化

Step 2 計(jì)算ALR模型的下界解

Step 2.1 求解子模型

按式(21)更新成本c^a,v，不考慮充電站的充電能力約束，使用DP 算法，按式(23)的迭代方式，依次優(yōu)化單輛車(chē)的配送路徑。

Step 2.2 計(jì)算下界解，更新最優(yōu)下界值

根據(jù)Step 2.1 得到的車(chē)貨分配方案，計(jì)算下界解，規(guī)則為：若某些客戶(hù)被多輛車(chē)服務(wù)，則僅指派一輛車(chē)配送即可；若存在部分服務(wù)需求沒(méi)有被滿足，則重新指派一輛車(chē)完成服務(wù)。

計(jì)算下界值，并按更新最優(yōu)下界B*LB。

Step 3 計(jì)算ALR模型的上界解

Step 3.1 求解子模型

Step 3.2 計(jì)算上界解，更新最優(yōu)上界值

根據(jù)Step 3.1 得到的車(chē)貨分配方案，計(jì)算上界解，規(guī)則同Step 2.2。

計(jì)算上界值，并按更新最優(yōu)上界B*UB。

Step 4 評(píng)估解的質(zhì)量

計(jì)算B*UB和B*LB之間的最優(yōu)間隙GGAP為

GGAP值越小，解的質(zhì)量越好。

Step 5 更新拉格朗日乘子

采用次梯度方法，按式(24)和式(25)更新拉格朗日乘子λp,λs,t。

Step 6 結(jié)束終止條件

若k到達(dá)最大迭代次數(shù)K，終止算法，并輸出，B*UB，GGAP和最優(yōu)上界解；否則，返回Step 2，k=k+1，繼續(xù)迭代。

Step 2.1和Step 3.1的DP算法采用了隱枚舉的思想，盡早去除不滿足約束條件的變量取值組合，直至找到一個(gè)滿足條件的可行解，并記為當(dāng)前最優(yōu)的可行解，計(jì)算其目標(biāo)函數(shù)值。后續(xù)迭代得到的可行解的目標(biāo)函數(shù)值與當(dāng)前最優(yōu)值進(jìn)行比較，對(duì)可行解的質(zhì)量進(jìn)行改進(jìn)。

求解最短路徑子問(wèn)題的過(guò)程是上述ALR 算法最耗時(shí)的環(huán)節(jié)。 整個(gè)算法的復(fù)雜度是O(K×nV×nL×nT×nW)，其中，K為迭代次數(shù)，nV為電動(dòng)車(chē)輛數(shù)，nL為空間路段數(shù)，nT為離散的時(shí)間點(diǎn)數(shù)，nW為車(chē)輛承載能力。采用時(shí)空狀態(tài)網(wǎng)絡(luò)的建模方法需要確定合適的離散精度，若離散的時(shí)間、空間及狀態(tài)精度過(guò)高，時(shí)空狀態(tài)網(wǎng)絡(luò)規(guī)模過(guò)大，會(huì)影響算法的計(jì)算效率；若離散精度設(shè)置過(guò)小，會(huì)影響模型的精確性。

3 算例分析

算法執(zhí)行的硬件環(huán)境為Intel(R)CPU(TM)i7-7700 CPU @ 3.60 GHz，內(nèi)存為16 GB。軟件環(huán)境為Windows 10系統(tǒng)，使用Python編寫(xiě)求解算法。

3.1 算法分析

基于Sioux Falls 網(wǎng)絡(luò)構(gòu)建測(cè)試算例，如圖3所示，共有24個(gè)節(jié)點(diǎn)和76條路段，其中，節(jié)點(diǎn)11設(shè)為配送中心，節(jié)點(diǎn)1、2、8、13、15、18、23分別設(shè)為充電站s1,s2,s8,s13,s15,s18,s23，每條路段上標(biāo)記的是行程時(shí)間。電動(dòng)車(chē)輛從配送中心出發(fā)時(shí)均處于滿載(w0=8)和滿電狀態(tài)(e0=30)。充耗電過(guò)程的相關(guān)參數(shù)設(shè)置為：最小剩余電量閾值Emin=3，最大電池容量Emax=30，充電速率γ=10，耗電速率κ=1，充電站能力ξ=2。

圖3 Sioux Falls網(wǎng)絡(luò)Fig.3 Sioux Falls network

為測(cè)試算法求解不同規(guī)模算例的性能，設(shè)置兩組實(shí)驗(yàn)，分別為24位客戶(hù)和50位客戶(hù)，得到電動(dòng)車(chē)輛和充電站使用方案如表1所示。24 個(gè)客戶(hù)的算例需使用6 輛車(chē)和4 個(gè)充電站(s8,s13,s15,s23)，其余充電站均未有車(chē)輛充電。50 個(gè)客戶(hù)的算例需使用10 輛車(chē)和6 個(gè)充電站(s2,s8,s13,s15,s18,s23)?？蛻?hù)數(shù)量增大需要調(diào)用更多的電動(dòng)車(chē)輛完成配送任務(wù)，也會(huì)提高充電站的利用率。

表1 優(yōu)化方案Table 1 Optimization scheme

兩組不同規(guī)模算例的實(shí)驗(yàn)結(jié)果如表2所示，可以看出，算法能夠在有限的迭代次數(shù)內(nèi)收斂，計(jì)算效率較高。最優(yōu)上界值與最優(yōu)下界值之間的GGAP較小，表明計(jì)算得到的可行解已接近最優(yōu)解，質(zhì)量較高。客戶(hù)數(shù)量越多，服務(wù)客戶(hù)需要的電動(dòng)車(chē)輛越多，算法收斂需要迭代的次數(shù)越多，計(jì)算效率有所降低，但仍然可以較快地找到可行解。在24 個(gè)客戶(hù)算例中，算法迭代次數(shù)K設(shè)為100，ALR 算法每次迭代得到的最優(yōu)上界和下界變化如圖4所示，迭代43次后，最優(yōu)上界值、最優(yōu)下界值以及兩者之間的GGAP均保持不變，即算法收斂到較優(yōu)的解。

表2 不同規(guī)模算例的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of different-scale instances

圖4 ALR最優(yōu)上界和下界變化Fig.4 Variations of ALR best upper and lower bounds

3.2 參數(shù)靈敏度分析

(1)充電速率

把24 個(gè)客戶(hù)算例設(shè)為基準(zhǔn)算例，充電速率γ調(diào)為5，其余參數(shù)保持不變。算法迭代63 次后收斂，CPU計(jì)算時(shí)間為79.51 s。充電速率降低使電動(dòng)車(chē)輛在充電站的充電時(shí)間變長(zhǎng)，由于客戶(hù)服務(wù)時(shí)間窗是固定的，導(dǎo)致車(chē)輛路徑和充電優(yōu)化方案整體上發(fā)生較大變化。如表3所示，與基準(zhǔn)算例(γ=10)相比，總時(shí)間成本增大7.9%，總充電量提高14.3%，總充電時(shí)長(zhǎng)顯著增大。

表3 充電速率的影響Table 3 Influence of recharge rate

(2)充電站能力

在基準(zhǔn)算例的基礎(chǔ)上，充電站能力ξ調(diào)為1。算法迭代62 次后收斂，CPU 計(jì)算時(shí)間為74.93 s。如表4所示，與基準(zhǔn)算例(ξ=2)相比，總時(shí)間成本有所降低，總剩余電量增大，故充電站能力參數(shù)也會(huì)影響車(chē)輛整體的路徑規(guī)劃和充電決策。

表4 充電站能力的影響Table 4 Influence of recharging station capacity

4 結(jié)論

本文綜合考慮了電動(dòng)物流車(chē)輛路徑規(guī)劃、客戶(hù)配送服務(wù)需求及充耗電過(guò)程，基于高維的離散時(shí)空狀態(tài)網(wǎng)絡(luò)，構(gòu)建了多商品網(wǎng)絡(luò)流優(yōu)化模型，設(shè)計(jì)了基于ALR 和BCD 技術(shù)的分布式優(yōu)化算法，基于Sioux Falls 網(wǎng)絡(luò)測(cè)試算例，驗(yàn)證了算法的時(shí)效性和可靠性，并得出以下結(jié)論：

(1)時(shí)空狀態(tài)網(wǎng)絡(luò)建模框架可以有效減少變量類(lèi)型和耦合約束，簡(jiǎn)化模型結(jié)構(gòu)；

(2)ALR 模型中懲罰項(xiàng)的引入可以克服LR 解的對(duì)稱(chēng)性問(wèn)題，加快算法的收斂速率，且最優(yōu)上下界的計(jì)算可以評(píng)估可行解的質(zhì)量。

(3)考慮部分充電策略的電動(dòng)車(chē)輛路徑規(guī)劃可以降低能源消耗和運(yùn)營(yíng)成本，在時(shí)間、空間和狀態(tài)維度上實(shí)現(xiàn)電動(dòng)物流資源的優(yōu)化配置。