基于兩階段求解策略的動態(tài)電動車輛路徑優(yōu)化研究

葛顯龍, 竹自強(qiáng), 金淵智

(1.重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院,重慶 400074; 2.重慶交通大學(xué) 智能物流網(wǎng)絡(luò)重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400074; 3.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院,四川 成都 610031; 4.三門峽職業(yè)技術(shù)學(xué)院 信息傳媒學(xué)院,河南 三門峽 472000)

0 引言

電動車具有節(jié)能、清潔以及低噪音的特點(diǎn)。近年來，一些物流企業(yè)開始使用電動車進(jìn)行配送，比如，京東、中國郵政以及菜鳥物流。但是，與傳統(tǒng)燃油車不同，電動車由于其續(xù)航限制，往往需要進(jìn)行途中充電或者換電，在一定程度上增加時間成本及路徑成本，因此需要制定合理的充/換電策略，以保證配送成本最小化。此外，還有一些現(xiàn)實(shí)因素應(yīng)該被考慮，(1)客戶的動態(tài)需求，在實(shí)際配送過程中，客戶的訂單需求可能發(fā)生變化，此時企業(yè)能否在保證經(jīng)濟(jì)性的基礎(chǔ)上做出快速響應(yīng)以提升客戶體驗(yàn)將變得至關(guān)重要。(2)充/換電站的擁堵情況，由于目前公共充/換電設(shè)施的數(shù)量和密度較小，易引發(fā)擁堵而提高時間成本，因此如何結(jié)合當(dāng)前充/換電站設(shè)施制定合理的配送計劃是電動汽車在物流配送作業(yè)中的關(guān)鍵。

動態(tài)車輛路徑問題[1](Dynamic Vehicle Routing Problem，DVRP)的研究主要集中在新增客戶的動態(tài)問題。此類問題的研究已比較成熟，Kuo等[2]將服務(wù)客戶數(shù)量最大化和客戶平均等待時間最小化作為優(yōu)化目標(biāo)建立了DVRP模型。Okulewicz和Madziuk[3]將DVRP擴(kuò)展為多配送中心的動態(tài)車輛路徑問題，建立帶容量和工作時間約束的數(shù)學(xué)模型。Ghannadpour等[4]針對帶模糊時間窗的DVRP建立了一種最小化車隊(duì)規(guī)模、路徑成本及等待時間的多目標(biāo)模型。Huang等[5]研究了確定性和隨機(jī)流量條件下建立了TDVRP-PF模型；?imen和Soysal[6]研究了具有隨機(jī)車速的時變車輛路徑問題。動態(tài)需求的車輛路徑問題常常采用定期更新策略，將每個工作日劃分為若干時間周期，按時間周期將動態(tài)需求問題轉(zhuǎn)化成一系列靜態(tài)需求問題[2～4]，從而將動態(tài)問題靜態(tài)化。為了保證問題求解的高效性，已有文獻(xiàn)多采用遺傳算法[7,8]、粒子群算法、蟻群算法[9,10]等啟發(fā)式算法求解此類問題。

關(guān)于電動車輛路徑問題(Electric Vehicle Routing Problem，EVRP)的研究主要集中在非線性能耗、充電策略以及考慮換電站選址的EVRP，Lin等[11]建立了最小化旅行時間、能耗成本以及車輛使用成本為目標(biāo)函數(shù)的EVRP模型。Desaulniers等[12]研究了四種充電策略。Goeke和Schneider[13]提出了一種非線性放電模型，并考慮了車輛速度、裝載量等對電池放電的影響。Yang和Sun[14]建立了最小化路徑成本和選址成本的BSS-EV-LRP模型。Hof等[15]設(shè)計了改進(jìn)的自適應(yīng)變鄰域搜索(AVNS)算法來求解BSS-EV-LRP模型，并發(fā)現(xiàn)AVNS平均解的質(zhì)量具有較強(qiáng)的魯棒性，能夠較好地減少解中構(gòu)造的BSSs的數(shù)量。Zhang等[16]提出了基于隨機(jī)需求的BSS-EV-LRP模型。

綜上，大部分動態(tài)車輛路徑問題的研究集中在傳統(tǒng)燃油車輛，而在電動車輛路徑問題忽視了客戶需求的動態(tài)性、電池續(xù)航以及充/換電設(shè)施的擁堵成本等現(xiàn)實(shí)因素。為此，提出了基于分階段求解策略，并建立兩階段的EVRP模型，其中第一階段針對靜態(tài)客戶建立了靜態(tài)EVRP模型，第二階段建立DEVRP模型以更新路徑。提出了換電站及動態(tài)客戶插入成本公式，并設(shè)計CW-TS混合啟發(fā)式算法來求解靜態(tài)模型，貪婪算法求解動態(tài)模型。最后，通過算例驗(yàn)證了模型與算法的可行性與有效性。

1 問題描述

基于分階段求解策略的DEVRP，可以描述如下：第一階段靜態(tài)調(diào)度，根據(jù)初始的靜態(tài)客戶訂單，規(guī)劃出初始配送方案，0時刻車輛從配送中心出發(fā)按此路徑依次訪問客戶點(diǎn)并開始接收新訂單，接收時長為t(即信息中心會在時間窗[0,t]接收新的客戶需求)。第二階段動態(tài)調(diào)度，在t時刻由于所有的動態(tài)客戶信息已知，可將動態(tài)網(wǎng)絡(luò)轉(zhuǎn)換成靜態(tài)網(wǎng)絡(luò)，此時根據(jù)車輛當(dāng)前的狀態(tài)插入相應(yīng)的動態(tài)客戶從而完成路徑更新。為了體現(xiàn)客戶信息隨時間的變化，引入時間軸的概念，如圖1(a)～(b)，圖1(a)表示第一階段，系統(tǒng)在0時刻根據(jù)靜態(tài)客戶需求規(guī)劃了初始路徑，同時開始接受新的客戶請求。圖1(b)表示t時刻車輛的狀態(tài)以及新增的所有動態(tài)客戶，此時網(wǎng)絡(luò)的所有信息均已知，因此動態(tài)網(wǎng)絡(luò)坍縮成靜態(tài)網(wǎng)絡(luò)，并將t時刻車輛即將達(dá)到或正好位于的那些客戶點(diǎn)、換電站、配送中心稱為關(guān)鍵點(diǎn)，如圖1(b)中的客戶點(diǎn)9、3、6。第二階段將關(guān)鍵點(diǎn)作為新的起點(diǎn)，將剩余的未服務(wù)的靜態(tài)客戶以及動態(tài)客戶作為新的客戶集合，重新規(guī)劃路徑，得到結(jié)果如圖1(c)。由于動態(tài)客戶2距離路徑r2較遠(yuǎn)使得其插入會引起新增換電次數(shù)至少兩次，因此路徑2在該服務(wù)日內(nèi)拒絕服務(wù)該動態(tài)客戶點(diǎn)，而將服務(wù)時間推遲到下一服務(wù)日。對于路徑1和路徑3，都接受了新增動態(tài)需求客戶，結(jié)果如圖1(d)。

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

2.1 符號說明

2.2 建立靜態(tài)電動車輛路徑問題模型

現(xiàn)以最小化路徑成本及車輛使用成本為目標(biāo)函數(shù)，建立EVRP混合整數(shù)規(guī)劃模型如下:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

xijk,yki,xok∈{0,1},?i,j,o∈V,?k∈K

(15)

式(1)為目標(biāo)函數(shù)；式(2)保證節(jié)點(diǎn)流入等于流出；式(3)限制車輛使用數(shù)量，保證派出的車輛數(shù)不大于配送中心擁有量；式(4)車輛服務(wù)的客戶數(shù)不大于總客戶數(shù)；式(5)保證每條路線上客戶的總需求不大于車輛的最大裝載；式(6)閉環(huán)約束，保證車輛從配送中心出發(fā)且最終回到配送中心；式(7)每個客戶只能被訪問一次；式(8)當(dāng)電動車離開配送中心時為滿裝載；式(9)表示電動車離開i點(diǎn)時的剩余裝載；式(10)表示電動車到達(dá)i點(diǎn)時的剩余裝載；式(11)電動車在客戶點(diǎn)停留時不損耗電量；式(12)保證車輛離開配送中心和換電站時電池為滿電；式(13)和(14)表示車輛在個節(jié)點(diǎn)之間的電量約束；式(15)為0-1變量。

2.3 建立動態(tài)EVRP數(shù)學(xué)模型

以配送成本最小化為目標(biāo)，建立t時刻配送優(yōu)化的混合整數(shù)規(guī)劃模型，具體如下：

(16)

式(16)表示目標(biāo)函數(shù)，即使得插入路徑成本最小化。式(17)表示對動態(tài)距離屬性的約束，即單獨(dú)插入某個動態(tài)客戶時不能引起新的換電次數(shù)超過一次。式(18)和(19)表示關(guān)鍵點(diǎn)只能發(fā)出車輛并最后回到配送中心。式(20)表示需求約束，即插入的動態(tài)客戶的需求不能超過該條路徑車輛的剩余裝載。式(21)表示未服務(wù)的靜態(tài)客戶及動態(tài)客戶的流平衡。式(22)電動車離開換電站時處于滿電。式(23)和(24)表示車輛在個節(jié)點(diǎn)之間的電量約束。式(25)每個動態(tài)客戶或者未服務(wù)靜態(tài)客戶只能被訪問一次。式(26)表示電動車離開i點(diǎn)時的剩余裝載。式(27)表示電動車到達(dá)i點(diǎn)時的剩余裝載。

3 求解算法設(shè)計

針對靜態(tài)EVRP模型，設(shè)計了改進(jìn)的節(jié)約里程算法與禁忌搜索算法(CW-TS)的兩階段混合啟發(fā)式算法，其中由CW得到靜態(tài)階段初始解，再通過TS優(yōu)化初始解，從而獲得靜態(tài)階段的最優(yōu)解。第二階段由貪婪算法來插入動態(tài)客戶，生成動態(tài)EVRP模型的最優(yōu)解。

3.1 第一階段模型求解算法

(1)節(jié)約里程算法生成初始解

為了方便矩陣運(yùn)算采用自然數(shù)編碼，如：[0-1-2-3-4-12-0-5-6-7-8-11-0-9-10-0]，表示第一階段的一個可行解，其中0為配送中心，1-10為靜態(tài)客戶，11-12為換電站，而[0-1-2-3-12-4-13-0-5-6-7-11-8-14-0-9-15-10-0]表示第二階段的一個可行解，13-15表示動態(tài)客戶。利用CW算法在不考慮裝載約束、需求約束及車輛里程約束的條件下得到配送中心與所有靜態(tài)客戶點(diǎn)的旅行商問題(TSP)解，與傳統(tǒng)的節(jié)約里程算法不同，我們在得到TSP解后還需采用兩邊逐次修正算子對其進(jìn)行再優(yōu)化；設(shè)計一種分車算子將TSP轉(zhuǎn)化為傳統(tǒng)車輛路徑問題的解(VRP)，此時在不考慮車輛里程約束的條件下得到了配送中心與所有靜態(tài)客戶點(diǎn)的VRP解，對于每條子路徑采用兩邊逐次修正算子對其進(jìn)行再優(yōu)化。

(2)TS算法輸出第一階段的解

將由CW得到的VRP解記為S，通過換電站插入規(guī)則將S變?yōu)榭尚薪夂笥嬎闫淠繕?biāo)函數(shù)值并賦值給初始解SS，當(dāng)前解DS和最優(yōu)解BS；設(shè)定最大迭代次數(shù)L和最優(yōu)解連續(xù)未變化次數(shù)P；給出禁忌表長度TL；每一代產(chǎn)生的鄰域候選解個數(shù)N。

采用了新的鄰域產(chǎn)生方法，每一次迭代隨機(jī)選擇四種鄰域交換算子(逆序鄰域交換算子、1-opt、2-opt、3-opt)中的一種對S做鄰域變換產(chǎn)生N個候選解，對每一個候選解用換電站插入規(guī)則使其變得可行并計算其目標(biāo)函數(shù)，選擇其中的最小值與BS對比，若其小于BS則觸發(fā)特赦準(zhǔn)則，并更新S，DS及BS，否則將產(chǎn)生該解的移動加入禁忌表，并更新S和DS，開始下一次迭代。迭代次數(shù)達(dá)到L或最優(yōu)解連續(xù)未變化次數(shù)達(dá)到P，終止程序輸出最優(yōu)解。

3.2 貪婪算法求解第二階段模型

在第二階段的T0時刻，識別出每條子路徑rk的關(guān)鍵點(diǎn)pk，記錄每個pk的剩余載量及剩余電量。剔除關(guān)鍵點(diǎn)后的換電站并識別出潛在的動態(tài)客戶插入位置，根據(jù)信息中心在時間窗[0,T0]內(nèi)接收的動態(tài)需求先后順序，依次嘗試將動態(tài)客戶插入到當(dāng)前各子路徑。

在T0時刻，首先將每條子路徑rk中關(guān)鍵點(diǎn)Pk之后的換電站剔除，將剔除換電站后的路徑稱為krouting，對于krouting，關(guān)鍵點(diǎn)、未服務(wù)客戶點(diǎn)以及配送中心之間形成動態(tài)客戶潛在插入集M。將動態(tài)客戶點(diǎn)i依次插入到這些潛在位置，并選取插入成本最小的位置為動態(tài)客戶的插入點(diǎn)，每成功接受一個動態(tài)客戶則相應(yīng)的krouting會被更新，定義每條krouting的初始路徑長度為L，L也會隨之更新。

(28)

其中β1+β2+β3=1,β1,β1,β3≥0

(29)

(30)

(31)

4 算例分析

本節(jié)包括一個仿真實(shí)驗(yàn)及其結(jié)果分析。實(shí)驗(yàn)環(huán)境基于MATLAB R2013a平臺。隨機(jī)生成一個包含25個靜態(tài)客戶(編號1～25)、10個動態(tài)客戶(編號32～41)以及6個換電站(編號26～31)的算例，來對比單獨(dú)使用CW和TS得到的結(jié)果，與使用CW-TS混合啟發(fā)式算法得到的結(jié)果。算法使用的具體參數(shù)見表1，客戶詳細(xì)信息見附表1。

表1 算法參數(shù)

針對每種算法運(yùn)行10次程序得到結(jié)果如表1。路徑長度用L表示，車輛數(shù)用K表示，總成本用C表示，計算時間用T(S)表示。

表2 算法對比分析

由表1，三種算法得到的最優(yōu)解均用黑體突出。對于L，CW-TS算法給出解的路徑長度最短，其解的平均值較CW結(jié)果降低了19.6%，較TS結(jié)果降低了17.4%；對于K，CW-TS與TS得到的結(jié)果均為4輛車，而CW得到的結(jié)果均為5輛車；對于C，CW-TS算法求得了最小值并且其解的平均值較CW結(jié)果降低了19.6%，較TS結(jié)果降低了16.7%；而計算時間，由于CW沒有領(lǐng)域搜索的過程其計算時間最短且結(jié)果穩(wěn)定，TS由于有禁忌搜索過程且初始解隨機(jī)產(chǎn)生，造成其計算時間最長，CW-TS雖然也具有禁忌搜索過程，但是其初始解質(zhì)量較好，使得其計算時間能保持在可行的范圍。綜上，CW-TS算法較CW、TS算法得到的結(jié)果在各方面都有明顯優(yōu)勢，因此驗(yàn)證了CW-TS算法的可行性與有效性。動態(tài)客戶加入前路徑軌跡見圖2(a)，動態(tài)客戶加入后的最終路徑軌跡見圖2(b)，0表示配送中心，1～25表示靜態(tài)客戶，26～31表示換電站，32～41表示動態(tài)客戶。

加入動態(tài)客戶前的路徑總長度為：655，總成本為：6953；加入動態(tài)客戶后的最終路徑長度為：747，總成本為：7872。如圖所示，15、19、20、23為關(guān)鍵點(diǎn)，還存在26、27、29換電站未被使用，說明換電站插入策略是有效的。

5 總結(jié)

針對基于分階段求解策略的動態(tài)電動車輛路徑優(yōu)化問題，建立了以最小化路徑成本及車輛使用成本為目標(biāo)函數(shù)的靜態(tài)EVRP數(shù)學(xué)模型和動態(tài)EVRP數(shù)學(xué)模型，并設(shè)計了改進(jìn)的CW-TS混合啟發(fā)式算法以及貪婪算法對兩階段的模型進(jìn)行求解。為了驗(yàn)證算法的有效性與可行性，首先通過中等規(guī)模的算例，并單獨(dú)使用CW和TS得到的結(jié)果，與使用CW-TS混合啟發(fā)式算法得到的結(jié)果進(jìn)行對比，結(jié)果顯示本文設(shè)計的算法獲得了較優(yōu)結(jié)果。