基于時(shí)間窗的電動(dòng)汽車快速充電路徑規(guī)劃方法

何瑞輝 田東偉 汪映輝 石進(jìn)永

1(海南電網(wǎng)有限責(zé)任公司 海南 海口 571000) 2(國電南瑞科技股份有限公司 江蘇 南京 210061)

0 引 言

運(yùn)輸系統(tǒng)在全球能源消耗和二氧化碳排放中占有20%～25%的比重，對(duì)其具有重大影響。在中國，2014年溫室氣體(GHG)排放總量的26%來自使用化石燃料的交通運(yùn)輸系統(tǒng)[1]。此外，2012年74%的國內(nèi)貨運(yùn)由卡車運(yùn)輸，預(yù)計(jì)2040年貨運(yùn)量將增長39%，2050年貨運(yùn)量將增長約80%。未來運(yùn)輸仍將是溫室氣體的主要和不斷增長的來源，因此政府正在大力提倡和鼓勵(lì)使用電動(dòng)汽車。而電動(dòng)汽車的運(yùn)營也存在著缺點(diǎn)，例如行駛里程低、充電站數(shù)量有限、電池充電時(shí)間長[2-5]，這些限制使得電動(dòng)車隊(duì)的路線規(guī)劃成為極具挑戰(zhàn)性的組合優(yōu)化問題。

EVRP是傳統(tǒng)汽車路徑問題(CVRP)的延伸[6]，由于電動(dòng)汽車中電池容量有限，需要進(jìn)行充電才能完成所規(guī)劃的路線，且相比在加油站的加油過程，充電過程所需的時(shí)間較長，文獻(xiàn)[7]首次提出了帶有時(shí)間窗的EVRP，即EVRPTW。EVRPTW假設(shè)充電時(shí)間是傳輸能量的線性函數(shù)，電池充滿電。文獻(xiàn)[8-9]放寬了完全充電限制，允許以任何數(shù)量的電池容量進(jìn)行部分充電，這是當(dāng)前現(xiàn)實(shí)中廣泛采用的做法。文獻(xiàn)[10]通過考慮不同的收費(fèi)策略并開發(fā)了分支價(jià)格和切割算法來解決優(yōu)化問題。文獻(xiàn)[11]將EVRPTW擴(kuò)展到包括EV和ICEV的混合車隊(duì)，目標(biāo)是最小化定義為速度和貨物載荷的總成本。文獻(xiàn)[12]解決了車隊(duì)規(guī)模和混合汽車路線問題與時(shí)間窗口，其中車隊(duì)僅由EV組成，它們最大限度地降低了汽車獲取和行駛距離的總成本，兩項(xiàng)研究都使用ALNS作為解決方案。文獻(xiàn)[13]通過允許使用多種技術(shù)進(jìn)行部分充電來解決EVRP問題。他們限制了總路線持續(xù)時(shí)間，但沒有考慮時(shí)間窗口。他們提出了局部搜索算法和基于模擬退火(SA)的元啟發(fā)式方法。文獻(xiàn)[14]研究了在時(shí)間窗存在的情況下快速充電選擇的影響。文獻(xiàn)[15]是第一項(xiàng)將EVRP擴(kuò)展到考慮非線性充電功能的研究，目標(biāo)函數(shù)最小化將包括行程時(shí)間和充電時(shí)間在內(nèi)的總時(shí)間。在目前的研究中，尚未出現(xiàn)以降低總成本為目標(biāo)來進(jìn)行具有時(shí)間窗和快充站的電動(dòng)汽車路徑規(guī)劃研究。

本文通過引入快速充電選項(xiàng)來擴(kuò)展不完全充電，并將此問題稱為EVRPTW和快速充電(EVRPTW-FC)。本文假設(shè)這些快充站配備了多種充電樁類型，將此問題表述為0-1混合線性程序，并提出一種有效解決它的算法。該算法將自適應(yīng)大型鄰域搜索(ALNS)與精確方法相結(jié)合，在ALNS的每次迭代中，通過從其路線中移除某些客戶和站點(diǎn)來排除可行解決方案，然后通過在需要充電時(shí)將移除的客戶與站點(diǎn)一起插回到解決方案中進(jìn)行修復(fù)。插入充電站時(shí)，還會(huì)確定充電樁類型和充電量。然后通過求解混合線性整數(shù)程序來定期改進(jìn)ALNS計(jì)算出的解決方案。

1 電動(dòng)汽車充電模型

(1)

式(2)-式(4)確保每個(gè)用戶只需進(jìn)站充電一次且每個(gè)充電站最多可進(jìn)一次。

(2)

(3)

(4)

式中：若車輛通過路徑(i，j)，則xij為1，否則其值為0。

式(5)和式(6)表明電動(dòng)汽車到達(dá)和離開充電站。

(5)

(6)

式(7)保證所有離開的電動(dòng)汽車在規(guī)劃路徑結(jié)束時(shí)回到充電站。

(7)

服務(wù)時(shí)間由式(8)-式(10)決定。

τi+(tij+si)xij-l0(1-xij)≤τj

(8)

?i∈F′,?j∈VAD

(9)

(10)

式中：τi表示在i點(diǎn)服務(wù)開始時(shí)間；ei、li表示客戶i的服務(wù)時(shí)間窗；Q表示電動(dòng)汽車的電池容量。

式(11)和式(12)約束汽車的載荷并確保總載荷不超過貨物容量：

(11)

0≤ui≤C?i∈DD

(12)

式中：C表示車輛載貨量；ui表示在i點(diǎn)的剩余貨物水平。

式(13)和式(14)分別表示離開客戶和站點(diǎn)時(shí)的電池SOC。

0≤yj≤yi-(hdij)xij+Q(1-xij)

(13)

式中：dij表示路徑(i，j)距離；h表示單位距離所需電量。

0≤yj≤yi-(hdij)xij+Q(1-xij)

(14)

式(15)確定變量yi和Yi的界限，式(16)確保EV完全充滿電后離開充電站。

(15)

Yi=Q?i∈DD

(16)

式(17)確定傳遞的能量的值，式(18)-式(20)決定用哪種類型的充電樁進(jìn)行充電。

(17)

(18)

(19)

(20)

最后，式(21)和式(22)定義二元決策變量。

ai,bi∈{0,1} ?i∈F′

(21)

xij∈{0,1} ?(i,j)∈A

(22)

2 模型求解

式(23)為最小化路線的總成本。

(23)

第一項(xiàng)代表路線的充電成本；第二項(xiàng)是能源成本，根據(jù)離開和到達(dá)之間的SOC差異計(jì)算得出。

式(24)-式(25)滿足客戶和充電站的時(shí)間窗可行性。

(24)

(25)

式中：si表示服務(wù)客戶i的時(shí)間要求。

式(26)表征電池SOC：如果EV在離開客戶i后沒有進(jìn)入充電站，那么通過減去沿曲線消耗的能量來計(jì)算到達(dá)客戶i+1時(shí)的SOC(i，i+1)來自客戶i的SOC。如果它進(jìn)入了充電站，則在站j處充電的能量被添加到客戶i處的SOC，并且減去沿著曲線(i，j)和(j，i+1)消耗的能量。

(26)

式(27)確保如果EV已進(jìn)入充電站i，則到達(dá)站j的SOC是非負(fù)的。

(27)

(28)

式(29)確保充電后的SOC不超過電池容量。如果EV在i和i+1之間充電，則充電樁類型由式(30)-式(32)確定。

(29)

(30)

(31)

(32)

式(33)確保汽車在充滿電的情況下離開充電站。式(34)-式(35)確定二元決策變量。

y0=Q

(33)

(34)

(35)

同時(shí)引入一個(gè)預(yù)處理過程，假設(shè)i和i+1為路線中的兩個(gè)連續(xù)客戶，F(xiàn)i,i+1是EV的充電站集合，從客戶i到i+1路程中可以進(jìn)站。最初，F(xiàn)i,i+1=F。然后，本文對(duì)站點(diǎn)與客戶i和i+1的距離進(jìn)行比較。例如，考慮兩個(gè)站點(diǎn)j,j′∈Fi,i+1。如果dij′>dij即j更接近i和i+1，則j就從最優(yōu)解中排除。為Fi,i+1中的所有站對(duì)重復(fù)該過程，以減小可行解個(gè)數(shù)。相同的過程適用于路徑中的所有客戶對(duì)(i，i+1)。

圖1顯示了四個(gè)充電站j、j′、j″和j?的情況，其可以在客戶i和i+1之間進(jìn)站充電。如上所述，可以清楚地看出j′受j影響。然而j、j″和j?中的任何一個(gè)都不影響另一個(gè)，因?yàn)閮蓚€(gè)條件都不滿足。因此，F(xiàn)i,i+1中包含j、j″和j?。

圖1 客戶i和i+1之間的充電站集合

在圖2中，使用由三個(gè)客戶變量組成的模型來說明固定路線問題的結(jié)構(gòu)。由于預(yù)處理可以排除一對(duì)客戶之間可以充電的充電站，因此每條曲線與不同的充電站組相關(guān)聯(lián)。于是，本文不需要?jiǎng)?chuàng)建工作站的副本在算法過程進(jìn)行計(jì)算，這大大減少了決策變量的數(shù)量。

圖2 兩個(gè)節(jié)點(diǎn)之間的充電站

3 算例分析

本文構(gòu)造了一個(gè)包括100個(gè)客戶和21個(gè)充電站的大規(guī)模實(shí)例，數(shù)據(jù)在100×100網(wǎng)格上聚類和隨機(jī)分布。其中根據(jù)時(shí)間窗口的長度、汽車負(fù)載和電池容量的不同將客戶分為窄時(shí)間窗口(1類)和寬時(shí)間窗口(2類)兩類，通過隨機(jī)選擇大規(guī)模實(shí)例中的客戶和充電站子集生成小規(guī)模實(shí)例。本文在Window 10下搭建Visual Studio 2017+CUDA10.1+CPLEX12.9開發(fā)環(huán)境，采用C++調(diào)用CPLEX。本文配置完全依照CPLEX官方安裝文檔以及安裝CPLEX后的c_cpp.html文件；電腦的系統(tǒng)環(huán)境變量配置參考CPLEX官方安裝文檔中的Setting up CPLEX on Windows一節(jié)中的設(shè)置。

3.1 大規(guī)模算例

本文從車隊(duì)規(guī)模和能源成本兩方面進(jìn)行優(yōu)化并驗(yàn)證使用快速充電的優(yōu)勢(shì)。在每過一定次數(shù)的迭代后都要對(duì)充電決策進(jìn)行優(yōu)化，這個(gè)次數(shù)稱為CPLEX的調(diào)用頻率，數(shù)值太小可能會(huì)增加運(yùn)行時(shí)間，而太大會(huì)降低解決方案的質(zhì)量。初步實(shí)驗(yàn)表明，當(dāng)CPLEX的調(diào)用頻率在200左右時(shí)，可在運(yùn)行時(shí)間和方案質(zhì)量兩者間達(dá)到平衡，所得結(jié)果最優(yōu)，因此本文的算例仿真中將迭代次數(shù)定為200。

具體調(diào)用CPLEX時(shí)，首先在Visual Studio 2017中將Visual Studio調(diào)試環(huán)境修改為release.x64，在Visual Studio 2017中選中解決方案“CPLEX”從而進(jìn)行環(huán)境配置。在Testcplex屬性頁中依次選擇“C/C++”-“代碼生成”-“運(yùn)行庫”設(shè)置為多線程，將時(shí)間限制設(shè)置為7 200 s。將本文算法運(yùn)行結(jié)果與在ALNS下只具備正常充電樁的運(yùn)行結(jié)果進(jìn)行比較，最優(yōu)解用粗體表示，結(jié)果如表1所示，其中：N11表示1類客戶的第一個(gè)實(shí)例；N21表示2類客戶的第一個(gè)實(shí)例。

表1 大規(guī)模客戶算例分析

續(xù)表1

從結(jié)果中可以看出當(dāng)客戶的時(shí)間窗口較窄(即1類客戶)時(shí)，由于使用快速充電可以明顯減少EV充電所花費(fèi)的時(shí)間，且汽車可能能夠沿著其路線服務(wù)其他客戶，包括由于嚴(yán)格的時(shí)間窗口限制而無法提供服務(wù)的客戶，因此快速充電更有利。EV可以沿其路線服務(wù)更多的客戶，由此可以構(gòu)建更有效的解決方案，可以減少車隊(duì)的規(guī)模或是縮短行程，從而降低總的能源成本。而在時(shí)間窗口較寬的2類客戶的結(jié)果中，快速充電僅在兩個(gè)實(shí)例中減少了車隊(duì)規(guī)模降低了成本。由于在這類問題中，時(shí)間窗口很容易滿足，汽車可以在其路線上為更多的客戶提供服務(wù)并且車隊(duì)規(guī)模已經(jīng)很少(在2到4輛之間)，因此通常不可能減少車隊(duì)規(guī)模。

3.2 小規(guī)模算例

將本文算法的結(jié)果與CPLEX中給出的最佳邊界比較，在Testcplex屬性頁中設(shè)置為單線程并將時(shí)間限制設(shè)置為7 200 s，結(jié)果如表2所示。在“時(shí)間”列中報(bào)告的計(jì)算時(shí)間以s為單位。實(shí)例名稱中“c”和“s”后面給出的值分別代表客戶和充電站的數(shù)量，如“N11c5s2”表示第一個(gè)實(shí)例包括5個(gè)類型1客戶和2個(gè)電動(dòng)汽車充電站，粗體表明在減少車隊(duì)規(guī)模、能源成本或是運(yùn)算時(shí)間上本文算法優(yōu)于CPLEX計(jì)算的部分。

表2 小規(guī)模客戶算例分析

續(xù)表2

結(jié)果中的運(yùn)行時(shí)間為7 200 s的CPLEX結(jié)果顯示在給定時(shí)間限制內(nèi)找到的最佳上限，并不一定是最佳解決方案。CPLEX可以將客戶數(shù)在10以下的算例進(jìn)行優(yōu)化，本文算法也可以找出最優(yōu)解，但需要的時(shí)間更長。而客戶數(shù)在10到15個(gè)的算例中，本文算法在尋找最優(yōu)解和運(yùn)行時(shí)間方面表現(xiàn)均優(yōu)于CPLEX。結(jié)果表明了本文算法在解決小規(guī)模客戶的實(shí)例中同樣具有可行性和高效性。

4 結(jié) 語

本文解決了具有時(shí)間窗和快速充電樁的電動(dòng)汽車路徑規(guī)劃問題。在EVRPTW-FC中，充電站配備了多個(gè)充電樁，文中考慮了三種充電樁類型，即正常、快速和超快速。由于中型和大型問題難以處理，本文提出一種有效解決問題的算法，將ALNS與精確方法相結(jié)合。在ALNS中，引入了針對(duì)問題性質(zhì)的新機(jī)制；在精確方法中，在ALNS提供的解決方案中修復(fù)了每輛車所相連的客戶的順序，并利用CPLEX來優(yōu)化充電決策。本文對(duì)小型和大型實(shí)例測(cè)試了算法的性能。在小實(shí)例中的結(jié)果表明，本文方法在解決方案質(zhì)量和運(yùn)行時(shí)間方面都優(yōu)于CPLEX。在大型實(shí)例中，結(jié)果表明了在車隊(duì)規(guī)模和能耗方面使用快速充電的優(yōu)勢(shì)。當(dāng)時(shí)間窗比較窄時(shí)，能夠獲取需要較少EV且降低能源成本的路徑規(guī)劃；而當(dāng)時(shí)間窗寬時(shí)，快速充電樁的影響相對(duì)較小。

在本次實(shí)驗(yàn)中，本文假設(shè)所有充電站都已經(jīng)配備了所有類型的充電樁，但是考慮到高昂的安裝成本和缺乏基礎(chǔ)設(shè)施，實(shí)際情況可能并非如此，因此實(shí)際中還需考慮充電站的選址問題。進(jìn)一步的工作還需要解決異構(gòu)車隊(duì)案例，其中汽車根據(jù)其貨物容量、電池條件和車齡進(jìn)行分類，這會(huì)影響到其路徑范圍和放電/充電時(shí)間。此外，本文假設(shè)充電站和充電樁始終可用，而在現(xiàn)實(shí)生活中，車站中可能存在排隊(duì)現(xiàn)象，并且EV可能需要等待服務(wù)。因此，可以在隨機(jī)背景下研究充電時(shí)間的可變性，從而使得結(jié)果更加準(zhǔn)確。