王 勇,李慧星,羅思妤,周景欣,許茂增

(重慶交通大學(xué)經(jīng)濟(jì)與管理學(xué)院,重慶 400074)

隨著低碳經(jīng)濟(jì)發(fā)展模式的進(jìn)一步推廣,綠色低碳和智慧物流成為物流行業(yè)發(fā)展的新趨勢(shì)[1]。相較于傳統(tǒng)燃油車(chē)造成環(huán)境污染的問(wèn)題,電動(dòng)車(chē)具有節(jié)能環(huán)保、噪聲低等良好的綠色效益[2],更符合新時(shí)代低碳環(huán)保的發(fā)展需求,且電動(dòng)物流配送車(chē)相對(duì)于傳統(tǒng)燃油車(chē)具有更高的道路通行權(quán),并可有效降低物流企業(yè)運(yùn)營(yíng)成本,將逐步取代燃油車(chē)成為城市物流配送“最后一公里”的重要工具。據(jù)公安部交通管理局統(tǒng)計(jì)數(shù)據(jù)顯示1)https://www.mps.gov.cn/n2254098/n4904352/c8719719/content.html,2022年我國(guó)電動(dòng)車(chē)突破900萬(wàn)輛,相比于2010年增長(zhǎng)近900倍,而全國(guó)公共充電站的數(shù)量為163.6 萬(wàn)座,僅有電動(dòng)車(chē)數(shù)量的1/5。不斷增加的電動(dòng)車(chē)數(shù)量和有限的充電資源間的矛盾日益突出,電動(dòng)車(chē)配送對(duì)充電資源協(xié)同性與物流配送及時(shí)性提出了更高的要求。共享信息平臺(tái)、共同配送模式等新型城市物流配送模式的出現(xiàn),在整合電動(dòng)車(chē)充電資源、提升電動(dòng)車(chē)配送效率等方面提供了良好助益。針對(duì)電動(dòng)車(chē)配送行業(yè)發(fā)展的挑戰(zhàn)與機(jī)遇,國(guó)內(nèi)外學(xué)者從電動(dòng)車(chē)輛路徑問(wèn)題、多中心共同配送問(wèn)題和運(yùn)輸資源共享調(diào)度3個(gè)方面開(kāi)展了一系列研究工作。

在電動(dòng)車(chē)輛路徑問(wèn)題研究方面,揭婉晨等[3]研究了以電動(dòng)車(chē)總行駛距離最小化為目標(biāo)的帶時(shí)間窗電動(dòng)車(chē)輛路徑問(wèn)題,并提出了一種分支定價(jià)算法進(jìn)行問(wèn)題求解。Zhang 等[4]考慮了電動(dòng)車(chē)的行駛距離、車(chē)輛重量、速度和發(fā)動(dòng)機(jī)效率等因素對(duì)電量消耗的影響,構(gòu)建了以電動(dòng)車(chē)能耗最小為目標(biāo)函數(shù)的電動(dòng)車(chē)輛路徑優(yōu)化模型,并設(shè)計(jì)了一種改進(jìn)的蟻群算法求解模型。Lu等[5]結(jié)合電動(dòng)車(chē)的速度、重量、行駛距離等因素構(gòu)建了電動(dòng)車(chē)能耗計(jì)算模型,研究了具有時(shí)間依賴的電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題。李英等[6]考慮了充電設(shè)施對(duì)電動(dòng)車(chē)的影響,以配送總成本最小化為目標(biāo)函數(shù),研究了電動(dòng)車(chē)與傳統(tǒng)車(chē)輛混合配置的路徑優(yōu)化模型。趙志學(xué)等[7]在生鮮配送電動(dòng)車(chē)輛路徑問(wèn)題中考慮了電動(dòng)車(chē)運(yùn)行功率對(duì)能耗的影響,建立了配送總成本最小化的數(shù)學(xué)模型,并設(shè)計(jì)了一種改進(jìn)自適應(yīng)蟻群算法進(jìn)行模型求解。Cortés-Murcia等[8]指出電動(dòng)車(chē)能耗受運(yùn)輸距離和充電時(shí)間影響,以電動(dòng)車(chē)使用時(shí)間最短為目標(biāo)函數(shù),構(gòu)建了電動(dòng)車(chē)輛路徑優(yōu)化模型,并設(shè)計(jì)了一種大鄰域搜索算法研究電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題。由上述文獻(xiàn)可知,電動(dòng)車(chē)的重量、速度、行駛距離、發(fā)動(dòng)機(jī)效率等因素常被用于電動(dòng)車(chē)電量消耗計(jì)算模型構(gòu)建,而最小化配送成本的電動(dòng)車(chē)輛路徑優(yōu)化模型構(gòu)建與智能優(yōu)化算法設(shè)計(jì)為資源共享模式下的多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題研究提供了技術(shù)支持和理論支撐。

在多中心共同配送問(wèn)題研究方面,徐小峰等[9]應(yīng)用多目標(biāo)免疫遺傳算法研究了多中心共同配送的逆向物流問(wèn)題,提出了客戶和配送中心協(xié)同配送的動(dòng)態(tài)路徑優(yōu)化策略以降低配送網(wǎng)絡(luò)的總運(yùn)營(yíng)成本。范厚明等[10]探討了客戶需求拆分策略對(duì)多中心共同配送的影響,建立了一個(gè)多中心開(kāi)放車(chē)輛路徑優(yōu)化模型以提高車(chē)輛的裝載率。Wang等[11]設(shè)計(jì)了多目標(biāo)粒子群優(yōu)化(MOPSO)算法研究多中心間車(chē)輛協(xié)同運(yùn)輸問(wèn)題,有效提高了車(chē)輛利用率,降低了物流運(yùn)營(yíng)成本。楊翔等[12]研究了基于模糊需求的多中心開(kāi)放路徑優(yōu)化問(wèn)題,并設(shè)計(jì)了一種兩階段禁忌搜索算法求解問(wèn)題。Soeanu等[13]針對(duì)配送過(guò)程中的不確定性,提出優(yōu)先交付策略研究了以車(chē)輛行駛距離最小化為優(yōu)化目標(biāo)的多中心共同配送問(wèn)題,有效緩解了因車(chē)輛故障或損失等不確定因素造成的風(fēng)險(xiǎn)。徐小峰等[14]研究了多油品供給受限下多油庫(kù)被動(dòng)配送車(chē)輛路徑問(wèn)題,并構(gòu)建了多油品多油庫(kù)車(chē)輛路徑規(guī)劃的多目標(biāo)優(yōu)化模型,應(yīng)用MOPSO 算法進(jìn)行了模型求解。由上述文獻(xiàn)可知,當(dāng)前關(guān)于多中心共同配送問(wèn)題的研究主要集中在優(yōu)化模型構(gòu)建、混合多目標(biāo)算法設(shè)計(jì)與協(xié)同策略提出等方面,而多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化以及多中心間電動(dòng)車(chē)協(xié)同策略等方面還有待進(jìn)一步拓展。

在運(yùn)輸資源共享調(diào)度問(wèn)題研究方面,劉家利等[15]引入車(chē)輛租賃和共享機(jī)制研究了多中心開(kāi)環(huán)車(chē)輛路徑問(wèn)題,并設(shè)計(jì)了兩階段自適應(yīng)遺傳算法有效降低了物流運(yùn)營(yíng)成本。王勇等[16]針對(duì)多中心共同配送問(wèn)題,提出了多周期運(yùn)營(yíng)的車(chē)輛共享模式,設(shè)計(jì)了基于K-means時(shí)空聚類(lèi)算法的多目標(biāo)混合遺傳算法對(duì)問(wèn)題進(jìn)行求解,有效降低了車(chē)輛使用數(shù)量,實(shí)現(xiàn)了配送資源的合理化配置。Li等[17]提出了共享運(yùn)輸路徑和倉(cāng)庫(kù)資源策略,并設(shè)計(jì)了一種自適應(yīng)局部搜索混合遺傳算法研究多中心資源共享的車(chē)輛路徑問(wèn)題。Fan等[18]為提高企業(yè)的配送效率,提出了共享運(yùn)輸資源和客戶的運(yùn)營(yíng)機(jī)制,構(gòu)建了以運(yùn)營(yíng)成本最小化為目標(biāo)函數(shù)的整數(shù)規(guī)劃模型研究多中心配送問(wèn)題。Los等[19]以物流企業(yè)總利潤(rùn)最大化為目標(biāo)函數(shù),研究了客戶信息共享的多中心協(xié)同車(chē)輛路徑問(wèn)題,并分析了不同信息共享策略下物流企業(yè)服務(wù)水平和利潤(rùn)等的變化情況。Zhang 等[20]研究了承運(yùn)人和倉(cāng)庫(kù)資源共享的多中心協(xié)同車(chē)輛路徑問(wèn)題,并設(shè)計(jì)了一種擴(kuò)展變鄰域搜索算法進(jìn)行求解。由上述文獻(xiàn)可知,運(yùn)輸資源共享調(diào)度研究主要集中在多中心配送網(wǎng)絡(luò)中的車(chē)輛共享、物流設(shè)施共享以及運(yùn)輸路線共享等方面。然而,不同配送中心之間的充電站資源和電動(dòng)配送車(chē)輛的共享問(wèn)題,以及多中心配送網(wǎng)絡(luò)中的資源共享模式與電動(dòng)車(chē)配送相結(jié)合的問(wèn)題還有待進(jìn)一步研究。

本研究在優(yōu)化多中心共同配送電動(dòng)車(chē)輛路徑問(wèn)題過(guò)程中,提出了運(yùn)輸資源共享策略和充電站共享策略,構(gòu)建了運(yùn)營(yíng)成本最小化和電動(dòng)車(chē)使用數(shù)最小化的雙目標(biāo)優(yōu)化模型,設(shè)計(jì)了一種包含3D-Kmeans時(shí)空聚類(lèi)算法、Clarke-Wright(CW)節(jié)約算法以及MOPSO 算法的混合啟發(fā)式算法對(duì)優(yōu)化模型進(jìn)行求解,研究了資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題。結(jié)合實(shí)例進(jìn)行了算法消融實(shí)驗(yàn)、考慮充電站排隊(duì)等待時(shí)間不確定性的優(yōu)化結(jié)果對(duì)比,以及考慮電動(dòng)車(chē)電量消耗和速度呈階梯性關(guān)系的優(yōu)化結(jié)果對(duì)比研究,探討了資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前后變化,以及不同資源共享模式下的運(yùn)營(yíng)成本、電動(dòng)車(chē)使用數(shù)等的變化情況,進(jìn)而對(duì)比分析了5種資源共享模式下運(yùn)營(yíng)成本、電動(dòng)車(chē)使用數(shù)和充電站使用次數(shù)等的變化情況。本研究可為資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑問(wèn)題提供新的研究思路。

1 問(wèn)題描述

與傳統(tǒng)燃油車(chē)輛配送不同,電動(dòng)車(chē)在配送過(guò)程中受到電池容量限制,不得不前往充電站補(bǔ)充電量。然而,充電基礎(chǔ)設(shè)施不完善與充電站建設(shè)存在時(shí)序性差異等問(wèn)題,使得部分配送區(qū)域充電站配套不齊全、地理位置分布不均勻、使用頻次低等現(xiàn)象凸顯,進(jìn)而導(dǎo)致遠(yuǎn)距離充電的電動(dòng)車(chē)存在配送路徑長(zhǎng)、配送效率低下和運(yùn)營(yíng)成本高等問(wèn)題。在保障電動(dòng)配送車(chē)輛充電需求的前提下,有效整合充電站資源與電動(dòng)車(chē)資源,開(kāi)展配送中心間合作運(yùn)營(yíng),并合理規(guī)劃配送與充電路徑,能夠有效降低運(yùn)營(yíng)成本,進(jìn)而提高多中心共同配送網(wǎng)絡(luò)的資源利用率。此外,電動(dòng)車(chē)相較于燃油車(chē),不僅在物流配送方面具有更大的道路時(shí)空通行權(quán),而且還具有更多的時(shí)空配送路徑選擇方案,因此,在資源共享環(huán)境下電動(dòng)物流配送車(chē)更有利于滿足客戶多樣化的服務(wù)需求。圖1所示為資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前后對(duì)比。

圖1 資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前后對(duì)比Fig.1 Comparison before and after optimization of electric vehicle routing for multi-center joint distribution with resource sharing modes

圖1(a)表示多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前,由于電動(dòng)車(chē)的電池續(xù)航能力不足限制了電動(dòng)車(chē)的配送范圍,而充電需求迫使電動(dòng)車(chē)在配送過(guò)程中偏離原計(jì)劃路線選擇距離較遠(yuǎn)的充電站補(bǔ)充電量,降低了電動(dòng)車(chē)配送效率,且各配送中心獨(dú)立運(yùn)營(yíng),導(dǎo)致某些配送服務(wù)區(qū)域內(nèi)充電站使用頻次過(guò)低,加劇了電動(dòng)車(chē)配送路線迂回交錯(cuò)、違反客戶服務(wù)時(shí)間窗等現(xiàn)象。圖1(b)表示多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化后,多個(gè)配送中心進(jìn)行合作使配送區(qū)域得到合理劃分,縮小了電動(dòng)車(chē)的配送范圍。根據(jù)客戶服務(wù)時(shí)間窗,將配送中心的服務(wù)時(shí)間劃分為多個(gè)服務(wù)時(shí)間段,并結(jié)合客戶需求與位置、電動(dòng)車(chē)充電需求與充電站位置,對(duì)電動(dòng)車(chē)充電與配送路徑進(jìn)行合理優(yōu)化,實(shí)現(xiàn)充電站的共享利用與電動(dòng)車(chē)的共享調(diào)度,提高充電站使用效率、減少電動(dòng)車(chē)的使用數(shù)量,有效緩解了路徑交叉與違反客戶時(shí)間窗的現(xiàn)象。例如:E1、E3和E5這3個(gè)充電站實(shí)現(xiàn)了共享使用,為多中心共同配送網(wǎng)絡(luò)中所有電動(dòng)車(chē)提供充電服務(wù);電動(dòng)車(chē)EV1 實(shí)現(xiàn)了在路徑DC1→C3→C4→C5→DC1和路徑DC3→C18→C19→C16→C28→DC3上的車(chē)輛共享調(diào)度。

圖1中,路線上的數(shù)值表示電動(dòng)車(chē)的行駛時(shí)間。假設(shè)每輛電動(dòng)車(chē)單位時(shí)間內(nèi)電量消耗為15 k W·h,電量消耗成本為2元/k W·h,司機(jī)單位時(shí)間服務(wù)成本為15元/h,電動(dòng)車(chē)早到的單位時(shí)間懲罰成本為10元,晚到的單位時(shí)間懲罰成本為30元,進(jìn)行配送服務(wù)的電動(dòng)車(chē)租賃成本為100元/輛,進(jìn)行集中運(yùn)輸?shù)碾妱?dòng)車(chē)租賃成本為200元/輛。表1所示為資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前后相關(guān)指標(biāo)的對(duì)比結(jié)果。由表1可知,通過(guò)資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化,運(yùn)營(yíng)成本從6 885元降至3 615元,電量消耗從1 050 k W·h降至825 k W·h,電動(dòng)車(chē)使用數(shù)從10輛減少至4輛,充電站使用數(shù)從6個(gè)減少至3個(gè)。結(jié)果表明,多服務(wù)時(shí)間段內(nèi)的車(chē)輛共享與充電站共享策略能夠有效降低配送物流網(wǎng)絡(luò)運(yùn)營(yíng)成本,并減少電動(dòng)配送車(chē)使用數(shù)、提高充電站的利用率。

表1 資源共享模式下多中心電動(dòng)車(chē)共同配送優(yōu)化前后對(duì)比Tab.1 Comparison before and after optimization of multi-center electric vehicle joint distribution with resource sharing modes

2 模型建立

2.1 模型假設(shè)

多中心共同配送網(wǎng)絡(luò)中存在多個(gè)充電站,在電動(dòng)車(chē)配送過(guò)程中,當(dāng)電動(dòng)車(chē)電量不足時(shí),就近選擇充電站充電,充電完成后繼續(xù)進(jìn)行配送服務(wù),直到配送任務(wù)完成后才返回配送中心[21]。

模型假設(shè)如下:

(1)配送網(wǎng)絡(luò)中的充電站向所有電動(dòng)配送車(chē)開(kāi)放,電動(dòng)配送車(chē)的充電速度恒定[4,22],且考慮到電動(dòng)配送車(chē)在充電站的排隊(duì)等待時(shí)間存在不確定性,故本研究?jī)H考慮電動(dòng)車(chē)的充電時(shí)間,而不考慮電動(dòng)車(chē)在充電站的排隊(duì)等待時(shí)間。

(2)電動(dòng)配送車(chē)的類(lèi)型相同,且在配送過(guò)程中會(huì)選擇距離較近的充電站充電。

(3)每輛電動(dòng)配送車(chē)從配送中心出發(fā),完成配送服務(wù)后返回該配送中心。

(4)電動(dòng)配送車(chē)從配送中心或充電站出發(fā)時(shí)的電量為滿電狀態(tài)。

(5)配送中心的服務(wù)時(shí)間可以劃分為多個(gè)服務(wù)時(shí)間段,電動(dòng)配送車(chē)能夠在不同服務(wù)時(shí)間段為不同配送中心的配送線路提供服務(wù),從而實(shí)現(xiàn)車(chē)輛共享。本研究不考慮跨服務(wù)時(shí)間段配送線路的電動(dòng)配送車(chē)輛共享問(wèn)題。

2.2 符號(hào)定義

資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化研究的變量定義如下:

集合

D——配送中心集合,d∈D

C——客戶點(diǎn)集合,c∈C

F——充電站集合,f∈F

K——電動(dòng)運(yùn)輸車(chē)集合,k∈K

V——電動(dòng)配送車(chē)集合,v∈V

G——所有節(jié)點(diǎn)集合,G=D∪C∪F,g∈G

S——服務(wù)時(shí)間段集合,s∈S

參數(shù)

aij——電動(dòng)配送車(chē)從節(jié)點(diǎn)i～j的特定系數(shù),i,j∈G,i≠j

ov——電動(dòng)配送車(chē)v最大載重量,v∈V

Ok——電動(dòng)運(yùn)輸車(chē)k最大載重量,k∈K

φf(shuō)——電動(dòng)配送車(chē)的電量消耗成本(元/k W·h)

evf——電動(dòng)配送車(chē)的發(fā)動(dòng)機(jī)效率

Qk——電動(dòng)運(yùn)輸車(chē)k的電池容量,k∈K

qv——電動(dòng)配送車(chē)v的電池容量,v∈V

W——電動(dòng)配送車(chē)自重(kg)

A——電動(dòng)配送車(chē)的加速度(m/s2)

G——重力加速度(m/s2)

θij——節(jié)點(diǎn)i～j的道路坡度,i,j∈G,i≠j

λ——電動(dòng)配送車(chē)的迎風(fēng)面積(m2)

βs——電動(dòng)配送車(chē)在服務(wù)時(shí)間段s內(nèi)的特定系數(shù),s∈S

Γs——在服務(wù)時(shí)間段s內(nèi)電動(dòng)車(chē)電量消耗對(duì)速度的敏感系數(shù),s∈S

σ——電動(dòng)配送車(chē)的充電速度(k W/h)

CR——滾動(dòng)阻力系數(shù)

CD——空氣阻力系數(shù)

ρ——空氣密度

M——一個(gè)極大的正數(shù)

[ei,li]——客戶時(shí)間窗,i∈C

P1——電動(dòng)車(chē)早到懲罰成本(元/h)

P2——電動(dòng)車(chē)晚到懲罰成本(元/h)

Hk——電動(dòng)運(yùn)輸車(chē)k的租賃費(fèi)用(元/輛),k∈K

hv——電動(dòng)配送車(chē)v的租賃費(fèi)用(元/輛),v∈V

CY——單位時(shí)間內(nèi)電動(dòng)運(yùn)輸車(chē)司機(jī)服務(wù)成本(元/h)

CP——單位時(shí)間內(nèi)電動(dòng)配送車(chē)司機(jī)服務(wù)成本(元/h)

η——充電站可容納的最大電動(dòng)車(chē)充電數(shù)量

決策變量

2.3 模型構(gòu)建

電動(dòng)車(chē)在使用過(guò)程中的電量消耗受行駛的路況、速度、距離以及車(chē)輛自重等因素影響[4-5]。為準(zhǔn)確計(jì)算電動(dòng)車(chē)的電量消耗情況,基于現(xiàn)有研究,引入結(jié)合上述影響因素的電動(dòng)車(chē)非線性電量消耗函數(shù)模型,即:

式(1)計(jì)算了電動(dòng)車(chē)在服務(wù)時(shí)間段s內(nèi)從節(jié)點(diǎn)i行駛至j的電量消耗,式(2)中的aij為從節(jié)點(diǎn)i～j的特定系數(shù),式(3)中的βs為電動(dòng)配送車(chē)在服務(wù)時(shí)間段s內(nèi)的特定系數(shù)。

由于資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化研究涉及電動(dòng)配送車(chē)輛在不同配送線路間的共享設(shè)計(jì)以及充電站在不同線路上被電動(dòng)配送車(chē)輛共同使用的問(wèn)題,所以物流運(yùn)營(yíng)成本一直是物流配送企業(yè)考慮的重要指標(biāo),因此,物流運(yùn)營(yíng)成本最小化和電動(dòng)配送車(chē)輛使用數(shù)最小化是資源共享模式下多中心共同配送網(wǎng)絡(luò)優(yōu)化需要重點(diǎn)考慮的優(yōu)化目標(biāo)。本研究以多中心共同配送網(wǎng)絡(luò)運(yùn)營(yíng)成本W(wǎng)1最小化和電動(dòng)車(chē)使用數(shù)W2最小化為目標(biāo),建立資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題的雙目標(biāo)優(yōu)化模型,即:

Z1包括電動(dòng)運(yùn)輸車(chē)和電動(dòng)配送車(chē)的電量消耗成本,即

Z2包括電動(dòng)運(yùn)輸車(chē)和電動(dòng)配送車(chē)的租賃成本,即

Z3包括電動(dòng)運(yùn)輸車(chē)和電動(dòng)配送車(chē)的司機(jī)服務(wù)成本,即

Z4包括電動(dòng)運(yùn)輸車(chē)和電動(dòng)配送車(chē)未按客戶要求時(shí)間服務(wù)所產(chǎn)生的懲罰成本,即

其中:式(10)表示每個(gè)客戶在任意服務(wù)時(shí)間段內(nèi)只能被電動(dòng)車(chē)訪問(wèn)1次;式(11)表示流量守恒準(zhǔn)則,電動(dòng)車(chē)到達(dá)某節(jié)點(diǎn)后再?gòu)脑摴?jié)點(diǎn)離開(kāi);式(12)表示在任意服務(wù)時(shí)間段內(nèi)配送中心間電動(dòng)運(yùn)輸車(chē)運(yùn)載貨物的載重量小于其最大裝載量;式(13)表示在任意服務(wù)時(shí)間段內(nèi)每條路徑上電動(dòng)配送車(chē)載重量不會(huì)超出其最大裝載量;式(14)表示在任意服務(wù)時(shí)間段內(nèi)電動(dòng)運(yùn)輸車(chē)的運(yùn)輸量等于該服務(wù)時(shí)間段內(nèi)重新分配客戶的總需求;式(15)表示消除多中心共同配送網(wǎng)絡(luò)中的子回路;式(16)表示任意服務(wù)時(shí)間段內(nèi)在充電站進(jìn)行充電的電動(dòng)車(chē)數(shù)量不超過(guò)充電站可以容納的最大充電車(chē)輛數(shù)量;式(17)表示任意服務(wù)時(shí)間段內(nèi)電動(dòng)配送車(chē)配送路線總數(shù);式(18)表示任意服務(wù)時(shí)間段內(nèi)電動(dòng)配送車(chē)的配送路線順序;式(19)和(20)表示電動(dòng)配送車(chē)的出發(fā)時(shí)間與離開(kāi)時(shí)間都在配送中心的服務(wù)時(shí)間范圍內(nèi);式(21)表示服務(wù)時(shí)間段s內(nèi)電動(dòng)配送車(chē)的充電時(shí)間;式(22)和(23)表示配送時(shí)間的連續(xù)性;式(24)和(25)表示電動(dòng)運(yùn)輸車(chē)與電動(dòng)配送車(chē)從配送中心出發(fā)時(shí)初始電量為滿電;式(26)和(27)表示在任意服務(wù)時(shí)間段內(nèi)電動(dòng)運(yùn)輸車(chē)與電動(dòng)配送車(chē)在配送途中剩余電量不小于零;式(28)表示電動(dòng)車(chē)電量連續(xù)性約束;式(29)表示在任意服務(wù)時(shí)間段內(nèi)電動(dòng)車(chē)在充電站補(bǔ)充電量至額定電量;式(30)表示在任意服務(wù)時(shí)間段內(nèi)電動(dòng)車(chē)服務(wù)客戶時(shí)不消耗電量;式(31)～(36)為0-1變量。

3 基于3D-K-means時(shí)空聚類(lèi)的CWMOPSO 混合算法

本研究提出了基于3D-K-means時(shí)空聚類(lèi)的CW-MOPSO混合算法用于求解資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化模型。首先,將客戶時(shí)間窗分類(lèi),確定配送中心的服務(wù)時(shí)間段;其次,在各服務(wù)時(shí)間段內(nèi)根據(jù)配送中心、客戶的地理位置與時(shí)間要求,應(yīng)用3D-K-means時(shí)空聚類(lèi)算法[23],實(shí)現(xiàn)了客戶資源在時(shí)間與空間組成的三維空間內(nèi)的重新分配;再次,應(yīng)用CW 節(jié)約算法[16]在各聚類(lèi)單元內(nèi)生成新的初始路徑,進(jìn)而應(yīng)用MOPSO 算法進(jìn)行路徑優(yōu)化[14,25-26],并在算法過(guò)程中設(shè)計(jì)了充電站插入策略,進(jìn)行合適位置的充電站插入;最后,生成多中心共同配送電動(dòng)車(chē)輛優(yōu)化路徑。基于3D-K-means時(shí)空聚類(lèi)的CW-MOPSO混合算法流程如圖2所示。

圖2 混合算法流程Fig.2 Flow chart of hybrid algorithm

混合算法的具體流程如下:

步驟1輸入d個(gè)配送中心與c個(gè)客戶的時(shí)間窗、經(jīng)緯度和時(shí)空轉(zhuǎn)換系數(shù)α,構(gòu)造時(shí)間-空間三維坐標(biāo)系。令τ=1,并根據(jù)客戶時(shí)間窗特征劃分S個(gè)服務(wù)時(shí)間段。

步驟2在每個(gè)服務(wù)時(shí)間段內(nèi)設(shè)置z個(gè)聚類(lèi)單元,并使z=d在每個(gè)聚類(lèi)單元內(nèi)隨機(jī)選取一個(gè)聚類(lèi)中心。

步驟3計(jì)算客戶與聚類(lèi)中心間的時(shí)空距離dij,其中,

(mi,mi)和(mj,mj)分別為客戶ci和cj地理位置坐標(biāo),(ei,li)和(ej,lj)分別為客戶ci和cj服務(wù)時(shí)間窗。

步驟4將每個(gè)客戶分配到與其時(shí)空距離最近的聚類(lèi)中心,并更新聚類(lèi)結(jié)果。

步驟5重復(fù)步驟2～4,直至聚類(lèi)結(jié)果不再發(fā)生變化。

步驟6計(jì)算每個(gè)配送中心與z個(gè)聚類(lèi)中心間的距離,將每個(gè)聚類(lèi)中心的聚類(lèi)單元指派給離其最近的配送中心,輸出聚類(lèi)結(jié)果。

步驟7判斷τ大小,若τ≤1,將聚類(lèi)結(jié)果導(dǎo)入CW-MOPSO 混合算法中,執(zhí)行步驟8;若τ>1,則跳轉(zhuǎn)至步驟10。

步驟8初始化相應(yīng)參數(shù),確定個(gè)體加速度權(quán)重c1,種群加速度權(quán)重c2,慣性重量ω,最大運(yùn)行次數(shù)max_Run,最大迭代次數(shù)max_τ,種群規(guī)模popsize,存檔文件內(nèi)存最大值max_N。

步驟9在每個(gè)聚類(lèi)單元內(nèi),應(yīng)用CW 節(jié)約算法生成客戶間、客戶與配送中心間的節(jié)約距離矩陣,并根據(jù)排序后的節(jié)約距離生成初始路徑,構(gòu)造初始種群。

步驟10賦予初始種群中每個(gè)粒子的初始速度vi與初始位置xi,構(gòu)建初始存檔A并設(shè)置Run=1。

步驟11計(jì)算粒子i的適應(yīng)度值,對(duì)粒子i進(jìn)行非支配排序,選擇Xpbest,計(jì)算擁擠距離,并根據(jù)擁擠度距離值在存檔文件中選擇Xgbest。更新粒子速度和位置,更新存檔A。

步驟12判斷電動(dòng)車(chē)電量是否滿足訪問(wèn)所有客戶,若滿足則輸出路徑,若不滿足則選擇最優(yōu)的充電站插入點(diǎn),將充電站插入路徑,并計(jì)算插入成本。更新路徑電量,直至判定電動(dòng)配送車(chē)能訪問(wèn)路徑上所有客戶,并結(jié)合資源共享策略輸出電動(dòng)車(chē)的配送路徑。

步驟13評(píng)價(jià)粒子i的適應(yīng)度值,更新存檔并控制存檔大小使其不超過(guò)max_N。

步驟14令Run=Run+1,判斷Run是否達(dá)到max_Run。若Run>max_Run,則返回步驟4;若Run≤max_Run,則進(jìn)入下一步。

步驟15令τ=τ+1,判斷τ是否達(dá)到max_τ。若τ≤max_τ,則返回步驟10;若τ>max_τ,則結(jié)束循環(huán)操作,選擇帕累托優(yōu)化解,進(jìn)而輸出電動(dòng)配送車(chē)的最優(yōu)路徑。

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

3.1.1充電站插入策略 本研究將電動(dòng)車(chē)在配送路徑中由于電量限制不能到達(dá)的節(jié)點(diǎn)稱為斷點(diǎn)[24]。在生成電動(dòng)車(chē)配送路徑時(shí):①計(jì)算配送路徑rp所需電量Qp,并與電動(dòng)車(chē)額定電量qv進(jìn)行對(duì)比,若Qp>qv,則表示路徑rp存在斷點(diǎn);②計(jì)算電動(dòng)車(chē)v到達(dá)路徑rp中每個(gè)節(jié)點(diǎn)cm所需電量Qpc,當(dāng)Qpc>qv時(shí),則判定cm為rp的斷點(diǎn);③依次確定電動(dòng)車(chē)在cm前所有節(jié)點(diǎn)剩余電量的行駛范圍,在剩余電量的行駛范圍內(nèi)就近選擇充電站插入路徑,并計(jì)算插入成本;④更新路徑電量并重新對(duì)rp所需電量Qpc進(jìn)行對(duì)比,判斷是否存在斷點(diǎn),若仍存在斷點(diǎn)則重新選擇充電站插入路徑,直至該路徑不存在斷點(diǎn)為止。充電站插入位置如圖3所示。

圖3 充電站插入路徑示意圖Fig.3 Schematic diagram of charging station insertion path

由圖3可以看出,在一個(gè)擁有6個(gè)客戶、3個(gè)充電站的配送網(wǎng)絡(luò)中存在兩條配送路徑r1和r2,假設(shè)電動(dòng)車(chē)的額定電量為100 k W·h。在配送路徑中插入充電站生成電動(dòng)車(chē)輛配送路徑的過(guò)程如下:①計(jì)算配送路徑r1和r2所需電量。r1所需電量為53 k W·h,小于電動(dòng)車(chē)額定電量100 k W·h,則輸出路徑r1;r2所需電量為174 k W·h,大于電動(dòng)車(chē)額定電量100 k W·h,則r2存在斷點(diǎn)。②計(jì)算電動(dòng)車(chē)到達(dá)路徑r2每個(gè)節(jié)點(diǎn)所需電量,得到電動(dòng)車(chē)到達(dá)節(jié)點(diǎn)c5所需電量為110 k W·h,大于電動(dòng)車(chē)額定電量100 k W·h,則判定c5為r2的斷點(diǎn)。③依次計(jì)算電動(dòng)車(chē)在斷點(diǎn)c5前所有節(jié)點(diǎn)的剩余電量可行駛范圍,在可行駛范圍內(nèi)就近選擇充電站插入路徑,即電動(dòng)車(chē)在c4的剩余電量可行駛范圍內(nèi)存在充電站E2,則就近選擇充電站E2插入路徑r2,并計(jì)算插入成本。④更新路徑r2并對(duì)r2所需電量和斷點(diǎn)進(jìn)行判斷,若電量能夠滿足r2配送需求且不存在斷點(diǎn),則輸出電動(dòng)車(chē)輛路徑r2。

3.1.2粒子群更新 粒子的速度和位置是MOPSO 算法尋優(yōu)過(guò)程的關(guān)鍵因素,而粒子群更新則是通過(guò)粒子間的信息交互不斷更新粒子的速度和位置,從而尋求全局優(yōu)化解的過(guò)程[26]。假設(shè)種群中存在多個(gè)粒子,每個(gè)粒子i均包含一個(gè)位置向量xi和速度向量vi,則每個(gè)粒子的vi和xi用下式更新:

式中:Xpbest表示粒子自身的最佳位置,Xgbest表示種群中所有粒子中的最佳位置;ω為慣性權(quán)重;c1和c2分別為粒子朝向Xpbest和Xgbest運(yùn)動(dòng)的加速度權(quán)重;r1和r2為[0,1]內(nèi)的隨機(jī)值。

圖4所示為MOPSO 中粒子的更新過(guò)程。

圖4 MOPSO 中粒子位置更新Fig.4 Particle position update in MOPSO

在圖4(a)中,與單目標(biāo)的粒子群優(yōu)化不同,所有粒子的運(yùn)動(dòng)不是單向的,而是朝著帕累托前沿運(yùn)動(dòng);在圖4(b)中,每個(gè)粒子的運(yùn)動(dòng)受其當(dāng)前Xpbest和Xgbest的影響。

3.1.3外部存檔更新機(jī)制 在MOPSO 算法中,外部存檔主要用于儲(chǔ)存更新過(guò)程中的優(yōu)質(zhì)非支配粒子[26],而設(shè)計(jì)外部存檔更新機(jī)制能夠有效解決由于外部存檔大小有限導(dǎo)致的優(yōu)質(zhì)非支配粒子丟失的問(wèn)題[27]。本研究基于個(gè)體間支配關(guān)系和擁擠距離對(duì)外部存檔進(jìn)行更新,在選擇放入存檔的粒子時(shí),若新粒子被存檔原有粒子支配,則保留原有粒子;若原有粒子被即將放入存檔的新粒子支配,則刪除原有粒子并將新粒子加入存檔中;若新粒子和原有粒子彼此均不被支配,則直接將新粒子加入存檔中。為了提高算法運(yùn)行速度,在迭代過(guò)程中對(duì)外部存檔內(nèi)存進(jìn)行設(shè)置,利用粒子間的擁擠距離刪除多余的優(yōu)質(zhì)粒子,維持優(yōu)質(zhì)粒子多樣性,提高算法搜索能力。外部存檔更新過(guò)程的偽代碼如下所示:

輸入外部存檔A,存檔文件內(nèi)存最大值max_N

輸出更新存檔A

3.1.4資源共享策略設(shè)計(jì) 本文涉及的資源共享主要包括多配送中心間充電站資源和電動(dòng)配送車(chē)輛資源的共享。在結(jié)合時(shí)空聚類(lèi)和CW-MOPSO 混合算法生成配送路徑的過(guò)程中,結(jié)合電動(dòng)配送車(chē)輛到達(dá)充電站的時(shí)間和充電服務(wù)時(shí)間[28-29],確定充電站是否可被配送線路共享使用。此外,根據(jù)每條配送路徑的開(kāi)始和結(jié)束時(shí)間,將不同配送路徑的服務(wù)時(shí)間窗劃歸到不同的服務(wù)時(shí)間段內(nèi),并根據(jù)服務(wù)時(shí)間窗中值[30-31],按照不同服務(wù)時(shí)間段內(nèi)配送路徑服務(wù)時(shí)間窗中值的差值由小至大順序安排電動(dòng)配送車(chē)輛在不同配送線路上實(shí)現(xiàn)共享,且本研究不考慮跨服務(wù)時(shí)間段配送線路的電動(dòng)配送車(chē)輛資源共享問(wèn)題。充電站和電動(dòng)配送車(chē)輛資源共享過(guò)程如圖5所示。

圖5 充電站和電動(dòng)配送車(chē)輛資源共享過(guò)程Fig.5 Charging station and electric delivery vehicle resource sharing process

圖5是由DC1、DC2和2個(gè)共享充電站、16個(gè)客戶組成的配送網(wǎng)絡(luò),通過(guò)路徑優(yōu)化過(guò)程,共生成6條配送路徑。首先,根據(jù)每條路徑的開(kāi)始與結(jié)束時(shí)間以及服務(wù)時(shí)長(zhǎng)的特點(diǎn),將r1劃歸到s1的時(shí)間段內(nèi),將r2與r4劃歸到s2的時(shí)間段內(nèi),將r3與r5劃歸到s3的時(shí)間段內(nèi)。其次,計(jì)算每條路徑的時(shí)間中值以獲取時(shí)間中值差的序列,即r1

3.1.5帕累托優(yōu)化解選擇 本研究是基于非支配排序[32]與擁擠度距離[33]選擇帕累托優(yōu)化解。通過(guò)判斷粒子間的相互支配關(guān)系,將非支配的粒子儲(chǔ)存在帕累托前沿中,再計(jì)算帕累托前沿中粒子間的擁擠度距離,選擇擁擠度距離較大的粒子,輸出帕累托優(yōu)化解?；趽頂D度距離在帕累托前沿中選擇粒子的過(guò)程如圖6所示。

圖6 基于擁擠度距離選擇帕累托優(yōu)化解Fig.6 Pareto optimization solution selection based on crowding degree distance

由圖6 可知,帕累托優(yōu)化解選擇過(guò)程如下:①基于目標(biāo)函數(shù)f1與f2評(píng)估粒子i,并計(jì)算種群中支配粒子i的數(shù)量n(i)和i支配的粒子集合ui(j),找出所有n(i)=0的粒子保留在Rank1中。②對(duì)于Rank1中每個(gè)粒子所支配的集合ui(j)中的每個(gè)粒子j,計(jì)算出n(j)-1=0的粒子并保留在Rank2中。同理,對(duì)于Rank2 中每個(gè)粒子所支配集合uj(k)中的每個(gè)粒子k,計(jì)算出n(k)-2=0的粒子并保留在Rank3中。重復(fù)此過(guò)程,直至確定種群中所有粒子的非支配等級(jí)。③基于下式計(jì)算粒子i與兩個(gè)相鄰粒子的擁擠度距離:

3.2 算法檢驗(yàn)

3.2.1小規(guī)模算例驗(yàn)證 為了測(cè)試CW-MOPSO混合算法的計(jì)算性能,在Solomon數(shù)據(jù)集[34]C101、R101和RC101 中分別隨機(jī)選取5 組數(shù)據(jù),1～5組數(shù)據(jù)在Solomon數(shù)據(jù)集C101中隨機(jī)選擇,每組數(shù)據(jù)包含20個(gè)客戶點(diǎn)、2 個(gè)配送中心和2 個(gè)充電站,車(chē)輛容量為100;6～10 組數(shù)據(jù)在Solomon數(shù)據(jù)集R101中隨機(jī)選擇,包含30個(gè)客戶點(diǎn)、3個(gè)配送中心和3個(gè)充電站,車(chē)輛容量為100;11～15組數(shù)據(jù)在Solomon數(shù)據(jù)集RC101 中隨機(jī)選擇,包含40個(gè)客戶點(diǎn)、4個(gè)配送中心和3個(gè)充電站,車(chē)輛容量為100。此外,為了有效驗(yàn)證本文提出的混合算法的計(jì)算性能,在小規(guī)模算例計(jì)算中,充電站沒(méi)有時(shí)間窗約束,且不考慮配送中心之間的運(yùn)輸成本、配送車(chē)輛的租賃成本和司機(jī)服務(wù)成本。選取ILOG CPLEX 12.10軟件與本文提出的CWMOPSO 混合算法求解上述15組算例。其中,1～5組、6～10組和11～15組算例的CPLEX 軟件最長(zhǎng)求解時(shí)間分別設(shè)置為1 800 s、3 600 s和5 000 s,而CW-MOPSO 混合算法求解每個(gè)算例15次并選擇已知的最優(yōu)解,CW-MOPSO 混合算法的參數(shù)設(shè)置見(jiàn)表2。

表2 小規(guī)模算例的計(jì)算結(jié)果對(duì)比Tab.2 Comparison of calculation results for small-scale examples

由表2可知,在不同數(shù)據(jù)規(guī)模的15組算例計(jì)算結(jié)果對(duì)比中,CPLEX 需要花費(fèi)較長(zhǎng)時(shí)間獲得優(yōu)化解,而CW-MOPSO 混合算法能夠在較短時(shí)間內(nèi)獲得最優(yōu)解或近似最優(yōu)解。在算例1～5中,CPLEX和CW-MOPSO 混合算法均可獲得最優(yōu)解,但CW-MOPSO 混合算法獲得最優(yōu)解的計(jì)算時(shí)間遠(yuǎn)低于CPLEX 的計(jì)算時(shí)間。在算例6～10 中,CW-MOPSO 混合算法可以獲得算例6～9的最優(yōu)解,而求得算例10的優(yōu)化解與CPLEX 求得最優(yōu)解的成本差值比例為0.7%。在算例11～15中,CWMOPSO 混合算法可以獲得算例11、12和14的最優(yōu)解,而求得算例13和15的優(yōu)化解與CPLEX 求得最優(yōu)解的成本差值比例分別為0.9%和1.3%。此外,CPLEX 和CW-MOPSO 混合算法求解15組算例的平均物流運(yùn)營(yíng)成本和平均車(chē)輛使用數(shù)分別為1 070.2元和5.5輛以及1 073.1元和5.5輛,運(yùn)營(yíng)成本差值的均值為0.19%,且在15組算例中,CWMOPSO 混合算法獲得優(yōu)化解的平均計(jì)算時(shí)間為35.3 s,遠(yuǎn)低于CPLEX 獲得最優(yōu)解的平均計(jì)算時(shí)間2 433.2 s。因此,本文提出的CW-MOPSO混合算法計(jì)算結(jié)果具有較高的可靠性,且在獲得最優(yōu)解或近似優(yōu)化解方面具有明顯的時(shí)間優(yōu)勢(shì)。

3.2.2算法比較驗(yàn)證 為了進(jìn)一步驗(yàn)證本研究所提出算法的有效性,將CW-MOPSO 混合算法與非支配排序遺傳算法(NSGA-II)[23]、多目標(biāo)遺傳算法(MOGA)[35]和多目標(biāo)梯度進(jìn)化算法(MOGEA)[36]進(jìn)行對(duì)比分析。本文將Cordeau所設(shè)計(jì)的帶時(shí)間窗的多中心車(chē)輛路徑算例數(shù)據(jù)2)https://neo.lcc.uma.es/vrp/vrp-instances/multiple-depotvrp-with-time-windows-instances/進(jìn)行改進(jìn),增加充電站的數(shù)量并隨機(jī)選取客戶地理位置作為充電站地理數(shù)據(jù),改進(jìn)后的30組數(shù)據(jù)集3)https://github.com/WY983/Experimental-Data/issues/1的數(shù)據(jù)特征如表3所示。根據(jù)已有文獻(xiàn)[24,36-37]設(shè)置主要參數(shù)如表4 所示。每組算例運(yùn)算10次,選取最優(yōu)運(yùn)營(yíng)成本、車(chē)輛使用數(shù)和充電站使用次數(shù)進(jìn)行對(duì)比,具體結(jié)果如表5所示。

表3 數(shù)據(jù)集特征Tab.3 Dataset characteristics

表4 算法參數(shù)設(shè)置Tab.4 Algorithm parameter settings

表5 不同算法優(yōu)化結(jié)果對(duì)比Tab.5 Comparison of optimization results of different algorithms

將CW-MOPSO 混合算法與NGSA-II、MOGA和MOGEA 等3種算法求解出的運(yùn)營(yíng)成本進(jìn)行t檢驗(yàn)和p值比較,表5結(jié)果表明,CW-MOPSO 混合算法與其他3 種算法計(jì)算結(jié)果存在明顯差異。此外,CW-MOPSO 混合算法求解出的運(yùn)營(yíng)成本平均值分別比NGSA-II、MOGA 和MOGEA 算法降低了230.5元、296.5元和232.8元,充電站平均使用次 數(shù) 均少于NGSA-II、MOGA 和MOGEA 算法,平均車(chē)輛使用數(shù)均比NGSA-II、MOGA 和MOGEA算法計(jì)算的平均車(chē)輛數(shù)減少1輛。因此,本研究提出的CW-MOPSO 混合算法相比于其他3種算法,在求解多中心共同配送的電動(dòng)車(chē)輛路徑問(wèn)題方面更具優(yōu)越性。

4 實(shí)例分析

4.1 實(shí)例數(shù)據(jù)

以重慶市主城區(qū)范圍內(nèi)的4 個(gè)配送中心(DC1～DC4)、146 個(gè)客戶(C1～C146)以及在選定區(qū)域內(nèi)的12個(gè)充電站(E1～E12)為例進(jìn)行研究,物流設(shè)施和客戶點(diǎn)的分布情況如圖7所示。

圖7 配送中心、客戶與充電站地理分布Fig.7 Geographic distribution of distribution centers,customers,and charging stations

4.2 優(yōu)化結(jié)果及分析

4.2.1聚類(lèi)結(jié)果 根據(jù)實(shí)例的數(shù)據(jù)規(guī)模和相關(guān)文獻(xiàn)[11,26-27],相應(yīng)的參數(shù)設(shè)置如表6 所示。應(yīng)用3DK-means時(shí)空聚類(lèi)算法對(duì)客戶進(jìn)行分配,3D-Kmeans時(shí)空聚類(lèi)的前后對(duì)比如圖8所示,經(jīng)過(guò)時(shí)空聚類(lèi)后各配送中心服務(wù)時(shí)間段內(nèi)的客戶位置分布更加聚集,實(shí)現(xiàn)了多中心共同配送網(wǎng)絡(luò)中客戶資源的優(yōu)化配置。表7所示為3D-K-means時(shí)空聚類(lèi)后各配送中心服務(wù)的客戶,聚類(lèi)后DC1、DC2、DC3 和DC4分別服務(wù)33、33、42和38個(gè)客戶。其中,300～600時(shí)間段、600～900時(shí)間段和900～1 200時(shí)間段的客戶數(shù)量分別為36、82和28個(gè)。

表6 CW-MOPSO混合算法參數(shù)設(shè)置Tab.6 Parameter settings for CW-MOPSO hybrid algorithm

圖8 3D-K-means時(shí)空聚類(lèi)前后對(duì)比Fig.8 Comparison of 3D-K-means before and after time-space clustering

4.2.2優(yōu)化結(jié)果 針對(duì)資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題,以多中心共同配送網(wǎng)絡(luò)中運(yùn)營(yíng)成本最小與電動(dòng)車(chē)輛使用數(shù)最小為目標(biāo)函數(shù),應(yīng)用基于3D-K-means 時(shí)空聚類(lèi)的CWMOPSO 混合算法對(duì)優(yōu)化模型進(jìn)行求解,得到資源共享下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前后運(yùn)營(yíng)成本、電動(dòng)車(chē)使用數(shù)以及電量消耗等的變化情況。具體如表8所示。

由表8可知,應(yīng)用充電站共享策略使充電站使用數(shù)減少了1個(gè),使用次數(shù)增加了50.0%,有效提高了充電站的使用效率。通過(guò)多中心間資源共享使電動(dòng)車(chē)使用數(shù)減少了56.0%,電量消耗降低了24.1%,運(yùn)營(yíng)成本降低了43.2%,行駛距離減少了22.7%。此外,根據(jù)客戶時(shí)間窗的特點(diǎn)劃分了3個(gè)服務(wù)時(shí)間段,表9所示為多個(gè)時(shí)間段內(nèi)資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化方案。

表9 資源共享模式下多中心共同配送電動(dòng)車(chē)輛優(yōu)化路線Tab.9 Electric vehicle optimization routes for multi-center joint delivery with resource sharing modes

由表9可知,優(yōu)化后的配送方案中規(guī)劃了22條配送路徑,僅需要11輛電動(dòng)車(chē)就能完成配送服務(wù)。不同服務(wù)時(shí)間段內(nèi)DC1與DC2的車(chē)輛路徑見(jiàn)圖9,EV1～EV4分別在不同時(shí)段內(nèi)為DC1和DC2的客戶提供服務(wù),實(shí)現(xiàn)了電動(dòng)車(chē)在多中心間的共享。例如,EV1在600～900服務(wù)時(shí)間段內(nèi)服務(wù)了DC2的客戶后,又在900～1 200服務(wù)時(shí)間段內(nèi)服務(wù)了DC1的客戶。此外,應(yīng)用充電站共享策略合理化配置了充電資源,與優(yōu)化前相比減少了E12的使用,提高了其他充電站的使用次數(shù),實(shí)現(xiàn)了充電站在配送中心內(nèi)部與配送中心間的共享。由圖7可見(jiàn):E4分別為EV1和EV10 提供充電服務(wù),實(shí)現(xiàn)了在DC2 內(nèi)部共享;E9為EV5和EV6提供充電服務(wù),在DC1和DC2間實(shí)現(xiàn)了共享;E7既為EV3和EV4提供充電服務(wù),實(shí)現(xiàn)了在DC2內(nèi)部共享,又為EV1提供充電服務(wù),在DC1與DC2之間實(shí)現(xiàn)了共享。

圖9 不同時(shí)間段內(nèi)DC1與DC2的電動(dòng)車(chē)輛路徑Fig.9 Electric vehicle routes of DC1 and DC2 during different time periods

4.3 分析與討論

4.3.1算法消融實(shí)驗(yàn)對(duì)比 為從實(shí)例計(jì)算的角度進(jìn)一步驗(yàn)證本文提出算法的有效性,對(duì)CWMOPSO 算法進(jìn)行消融實(shí)驗(yàn)驗(yàn)證研究。本文設(shè)計(jì)了3 種算法消融方案:僅應(yīng)用充電站插入策略,而不應(yīng)用外部存檔更新策略(S1);僅應(yīng)用外部存檔更新策略,而不應(yīng)用充電站插入策略(S2);既應(yīng)用充電站插入策略,又應(yīng)用外部存檔更新策略(S3)。3種算法策略下的計(jì)算結(jié)果如表10 和圖10所示。

表10 3種算法策略下的優(yōu)化結(jié)果對(duì)比Tab.10 Comparison of optimization results under three algorithm strategies

圖10 3種算法策略下的優(yōu)化結(jié)果對(duì)比Fig.10 Comparison of optimization results under three algorithm strategies

由表10與圖10可知,在同時(shí)應(yīng)用充電站插入策略和外部存檔更新策略(S3)時(shí),算法的計(jì)算結(jié)果為運(yùn)營(yíng)成本6 240.5元,低于僅使用充電站插入策略(S1)的運(yùn)營(yíng)成本8 439.5元和僅采用外部存檔更新策略(S2)的運(yùn)營(yíng)成本9 488.0元。在電動(dòng)車(chē)使用方面,多中心配送網(wǎng)絡(luò)中僅使用了11輛電動(dòng)車(chē),總行駛距離和電量消耗分別降至3 337.4 km 和1 193.6 k W·h,有效提高了電動(dòng)配送車(chē)的使用效率;同時(shí),通過(guò)在CW-MOPSO 算法中應(yīng)用充電站插入策略和外部存檔更新,可以有效提高多中心配送網(wǎng)絡(luò)中充電站的使用頻率,進(jìn)而實(shí)現(xiàn)充電資源的集約化使用。因此,在CW-MOPSO 算法中加入充電站插入策略和外部存檔更新策略可以有效提高算法本身的計(jì)算性能,并可得到良好的優(yōu)化計(jì)算結(jié)果。

4.3.2考慮充電站排隊(duì)等待時(shí)間不確定性的優(yōu)化結(jié)果對(duì)比 為了進(jìn)一步探討電動(dòng)車(chē)在各充電站存在不確定的排隊(duì)等待時(shí)間,進(jìn)而導(dǎo)致最終服務(wù)客戶存在送達(dá)延遲不確定性的問(wèn)題,將假設(shè)1中“僅考慮電動(dòng)車(chē)的充電時(shí)間,不考慮電動(dòng)車(chē)在充電站的排隊(duì)

等待時(shí)間”的條件進(jìn)行松弛化處理,用以驗(yàn)證該假設(shè)的合理性和優(yōu)化結(jié)果的魯棒性。

考慮電動(dòng)車(chē)在充電站的排隊(duì)等待情況,將電動(dòng)車(chē)在充電站的排隊(duì)情況劃分為全部充電站不排隊(duì)(Case1)、全部充電站排隊(duì)且排隊(duì)時(shí)間固定(Case2)以及部分充電站排隊(duì)、其余充電站不排隊(duì)(Case3)3種場(chǎng)景。其中,Case3 場(chǎng)景下多中心共同配送網(wǎng)絡(luò)中需要排隊(duì)等待的充電站為E4、E5、E7、E8和E9,并設(shè)定存在排隊(duì)場(chǎng)景的充電站的排隊(duì)等待時(shí)間為1.5 h,單位時(shí)間的排隊(duì)等待成本為15元/h。不同充電站排隊(duì)等待情景下的多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化結(jié)果如表11所示。

表11 不同充電站排隊(duì)等待情景下的多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化結(jié)果對(duì)比Tab.11 Result comparison of multi-center joint distribution electric vehicle routing optimization under different queuing waiting scenarios at charging stations

由表11可知,在考慮電動(dòng)車(chē)的充電排隊(duì)等待時(shí)間的Case2和Case3中,配送中心需要分別增派5輛和3輛電動(dòng)車(chē)為客戶提供服務(wù)。此外,Case3 中部分電動(dòng)配送車(chē)為了減少排隊(duì)等待時(shí)間會(huì)選擇較遠(yuǎn)距離的充電站進(jìn)行充電,行駛距離相比于Case1和Case2分別增加了694.2 km 和507.5 km,且存在較高的延遲服務(wù)懲罰成本。在不考慮充電站排隊(duì)等待時(shí)間(Case1)的情況下,電動(dòng)車(chē)在充電站的選擇上更為靈活,充電站的總使用次數(shù)高達(dá)18次,而電動(dòng)車(chē)行駛距離和電量消耗均達(dá)到3種場(chǎng)景中的最小值,且多中心共同配送網(wǎng)絡(luò)的總運(yùn)營(yíng)成本分別比Case2和Case3降低了19.4%和15.7%。因此,不考慮充電站排隊(duì)等待時(shí)間的優(yōu)化結(jié)果具有更高的魯棒性,進(jìn)一步驗(yàn)證了本研究假設(shè)條件提出的合理性。

4.3.3考慮電動(dòng)車(chē)電量消耗和速度呈階梯性關(guān)系的優(yōu)化結(jié)果對(duì)比 由于電動(dòng)車(chē)在實(shí)際物流配送過(guò)程中電量消耗和速度可能存在階梯性的相關(guān)關(guān)系[37-38],即在加速階段、勻速階段以及減速階段,其電量消耗對(duì)速度的敏感系數(shù)是不同的。因此,本研究將進(jìn)一步研究不同時(shí)間階段電動(dòng)車(chē)存在加速、減速和勻速狀態(tài)下的多中心共同配送優(yōu)化結(jié)果,并進(jìn)行對(duì)比分析。

根據(jù)電動(dòng)車(chē)物流配送過(guò)程中電量消耗與速度的關(guān)系模型,進(jìn)一步探討不同服務(wù)時(shí)間段電動(dòng)車(chē)具有不同速度狀態(tài)(加速、減速和勻速)時(shí),電動(dòng)車(chē)電量消耗的敏感系數(shù)變化對(duì)優(yōu)化結(jié)果的影響,分別設(shè)定電動(dòng)物流配送車(chē)在不同服務(wù)時(shí)間段具有勻速(Scenario1)、加速-勻速(Scenario2)以及加速-減速-勻速(Scenario3)3種場(chǎng)景,進(jìn)而比較分析電動(dòng)車(chē)使用數(shù)、充電站使用次數(shù)、行駛距離、電量消耗和運(yùn)營(yíng)成本的變化情況。具體參數(shù)設(shè)置與計(jì)算結(jié)果如表12所示。

表12 不同速度情景下的多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化結(jié)果對(duì)比Tab.12 Result comparison of multi-center joint distribution electric vehicle routing optimization under different speed scenarios

由表12可知,不同服務(wù)時(shí)間段的加速、減速和勻速狀態(tài)對(duì)電動(dòng)物流配送車(chē)的使用數(shù)、充電站使用次數(shù)、行駛距離、電量消耗以及多中心共同配送網(wǎng)絡(luò)運(yùn)營(yíng)成本的影響不同。當(dāng)電動(dòng)車(chē)處于加速-減速-勻速狀態(tài)(Scenario3)時(shí),電動(dòng)車(chē)使用數(shù)為12輛,充電站使用次數(shù)為19次,行駛距離為3 476.6 km,電量消耗為1 264.1 k W·h,運(yùn)營(yíng)成本為6 781.5元,上述指標(biāo)均為3種場(chǎng)景中的最高值。當(dāng)電動(dòng)車(chē)處于勻速行駛狀態(tài)(Scenario1)時(shí),電動(dòng)車(chē)使用數(shù)、充電站使用次數(shù)、行駛距離、電量消耗和總運(yùn)營(yíng)成本分別為11輛、18次、3 337.4 km、1 193.6 k W·h和6 240.5元,且運(yùn)營(yíng)成本為3種場(chǎng)景中的最小值。此外,相較于Scenario1和Scenario2的行駛距離略小,但電量消耗和運(yùn)營(yíng)成本卻較高,而Scenario3 的電動(dòng)車(chē)使用數(shù)、充電站使用次數(shù)、行駛距離、電量消耗和運(yùn)營(yíng)成本均高于Scenario1。綜上可知,電動(dòng)車(chē)的電量消耗在長(zhǎng)距離勻速行駛過(guò)程中比多次不同速度狀態(tài)短距離行駛的電量消耗更少,且電動(dòng)車(chē)的速度變化會(huì)影響電動(dòng)車(chē)使用數(shù)、充電站使用次數(shù)、電量消耗、行駛距離和運(yùn)營(yíng)成本等。因此,在物流配送過(guò)程中,合理地減少速度變化狀態(tài)可以有效均衡電動(dòng)車(chē)使用數(shù)、行駛距離、電量消耗和運(yùn)營(yíng)成本等的變化情況。

4.3.4不同資源共享模式下的優(yōu)化結(jié)果對(duì)比 為了進(jìn)一步探討不同資源共享模式對(duì)運(yùn)營(yíng)成本、充電站使用數(shù)、充電站使用次數(shù)、行駛距離和電量消耗等指標(biāo)的影響,考慮了5種資源共享模式:電動(dòng)車(chē)與充電站均不共享模式(Case1)、電動(dòng)車(chē)內(nèi)部共享而充電站不共享模式(Case2)、電動(dòng)車(chē)內(nèi)部共享且充電站共享模式(Case3)、電動(dòng)車(chē)全局共享而充電站不共享模式(Case4)、電動(dòng)車(chē)全局共享且充電站共享模式(Case5)。不同資源共享模式下運(yùn)營(yíng)成本、車(chē)輛使用數(shù)以及充電站使用數(shù)等的對(duì)比結(jié)果如表13和圖11所示。

表13 不同資源共享程度模式下多中心配送的優(yōu)化結(jié)果對(duì)比Tab.13 Comparison of optimization results of multi-center distribution under different resource sharing degree modes

圖11 不同資源共享模式下的優(yōu)化結(jié)果對(duì)比Fig.11 Comparison of optimization results under different resource sharing modes

由表13和圖11可知,不同的資源共享模式會(huì)導(dǎo)致多中心共同配送網(wǎng)絡(luò)的運(yùn)營(yíng)成本、電動(dòng)車(chē)使用數(shù)、電量消耗、行駛距離、充電站使用數(shù)和充電站使用次數(shù)發(fā)生變化。在電動(dòng)車(chē)與充電站均不共享模式(Case1)下,多中心共同配送網(wǎng)絡(luò)中電動(dòng)車(chē)使用數(shù)(25輛)、行駛距離(4 318.8 km)、電量消耗(1 718.3 k W·h)和運(yùn)營(yíng)成本(10 992.7元)均高于其他模式;而電動(dòng)車(chē)全局共享且充電站共享模式(Case5)下的電動(dòng)車(chē)輛使用數(shù)(11輛)、行駛距離(3 337.4 km)、電量消耗(1 193.6 k W·h)和運(yùn)營(yíng)成本(6 240.5元)均低于其他模式。由5種模式對(duì)比結(jié)果分析可知,電動(dòng)車(chē)全局共享且充電站共享模式(Case5)下的多中心共同配送網(wǎng)絡(luò)的電動(dòng)車(chē)使用數(shù)最少、行駛距離最短、電量消耗最小,且僅需要11個(gè)充電站就能滿足所有配送車(chē)輛的充電需求。為進(jìn)一步研究充電站共享與不共享對(duì)車(chē)輛路徑和車(chē)輛使用數(shù)的影響,圖12出示了全局車(chē)輛共享下DC3與DC4充電站不共享(Case4)與共享模式(Case5)的配送車(chē)輛路徑。

圖12 全局車(chē)輛共享下DC3與DC4充電站不共享與共享模式的車(chē)輛路徑對(duì)比Fig.12 Comparison of vehicle routes between unshared and shared modes of DC3 and DC4 charging stations under global vehicle sharing

由圖12可見(jiàn),在電動(dòng)車(chē)全局共享且充電站共享模式(Case5)下,DC3與DC4充電站使用數(shù)為6個(gè),使用次數(shù)為9次;在電動(dòng)車(chē)全局共享且充電站不共享模式(Case4)下,充電站的使用數(shù)為7個(gè),使用次數(shù)為7次。在充電站共享下的DC4的配送路徑中,僅使用E3、E5和E8等3個(gè)充電站為DC4所有電動(dòng)車(chē)提供充電服務(wù),相較于充電站不共享模式(Case4)下減少了充電站E12 的使用。此外,在電動(dòng)車(chē)全局共享且充電站不共享模式(Case4)下,DC3與DC4 的配送路徑有14 條,比充電站共享模式(Case5)下的配送路徑增加了2條。充電站共享策略延長(zhǎng)了電動(dòng)車(chē)行駛距離,如在DC3的路徑中通過(guò)共享充電站E8,使得電動(dòng)車(chē)從DC3出發(fā)依次服務(wù)客戶C145、C111、C104、C126和C97后能夠繼續(xù)服務(wù)客戶C98、C142再返回DC3,進(jìn)而減少了電動(dòng)配送車(chē)的使用數(shù)量。

5 結(jié)論

本研究基于電動(dòng)配送車(chē)輛和充電站共享,研究了多中心共同配送車(chē)輛路徑優(yōu)化問(wèn)題。首先,以多個(gè)服務(wù)時(shí)間段運(yùn)營(yíng)成本最小化和電動(dòng)車(chē)輛使用數(shù)最小化為雙目標(biāo)函數(shù),構(gòu)建了多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化模型;其次,設(shè)計(jì)了基于3D-K-means時(shí)空聚類(lèi)的CW-MOPSO 混合算法求解模型,提出了充電站插入策略用于生成在途充電的電動(dòng)車(chē)輛路徑,并在循環(huán)迭代過(guò)程中引入外部存檔更新策略和資源共享策略,提高了算法搜索能力從而求解得到高質(zhì)量的帕累托優(yōu)化解;最后,將CW-MOPSO 混合算法與NSGA-II、MOGA 和MOGEA 算法求解的運(yùn)營(yíng)成本、車(chē)輛使用數(shù)、充電站使用次數(shù)等結(jié)果進(jìn)行對(duì)比分析,驗(yàn)證了CW-MOPSO 混合算法求解多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題的優(yōu)越性。

以重慶市某物流企業(yè)實(shí)際數(shù)據(jù)為例,對(duì)比分析了多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化前后運(yùn)營(yíng)成本和電動(dòng)車(chē)使用數(shù)等的變化情況。研究結(jié)果表明,資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化方案的物流運(yùn)營(yíng)總成本降低了43.2%,車(chē)輛使用數(shù)減少了56.0%,充電站使用數(shù)量減少了8.3%。此外,本研究進(jìn)行了算法消融實(shí)驗(yàn)對(duì)比、考慮充電站排隊(duì)等待時(shí)間不確定性的優(yōu)化結(jié)果對(duì)比,以及考慮電動(dòng)車(chē)電量消耗和速度呈階梯性關(guān)系的優(yōu)化結(jié)果對(duì)比研究,并進(jìn)一步對(duì)比分析了不同資源共享模式下的運(yùn)營(yíng)成本、電動(dòng)車(chē)使用數(shù)、電量消耗、行駛距離以及充電站使用數(shù)的變化情況。由上述分析可知,充電站插入策略和外部存檔更新策略可以有效提高算法本身的計(jì)算性能;部分充電站排隊(duì)、其余充電站不排隊(duì)的場(chǎng)景將增加電動(dòng)車(chē)的總行駛距離且存在較高的客戶延遲服務(wù)懲罰成本;電動(dòng)車(chē)的電量消耗在長(zhǎng)距離勻速行駛過(guò)程中比多次不同速度狀態(tài)短距離行駛的電量消耗更少,且電動(dòng)車(chē)的速度變化會(huì)影響電動(dòng)車(chē)使用數(shù)、充電站使用次數(shù)、電量消耗、行駛距離和運(yùn)營(yíng)成本等。此外,車(chē)輛全局共享且充電站共享的資源共享模式能夠有效降低多中心共同配送網(wǎng)絡(luò)中電動(dòng)車(chē)使用數(shù)和充電站使用數(shù),優(yōu)化網(wǎng)絡(luò)資源配置,提高配送效率,進(jìn)而降低運(yùn)營(yíng)成本。本研究為資源共享模式下多中心共同配送電動(dòng)車(chē)輛路徑優(yōu)化問(wèn)題提供了新思路,這將有利于完善城市綠色物流配送體系的構(gòu)建,推動(dòng)新能源物流配送行業(yè)的健康可持續(xù)發(fā)展。