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

何瑞輝 田東偉 汪映輝 石進永

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

0 引 言

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

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

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

1 電動汽車充電模型

(1)

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

(2)

(3)

(4)

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

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

(5)

(6)

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

(7)

服務時間由式(8)-式(10)決定。

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

(8)

?i∈F′,?j∈VAD

(9)

(10)

式中：τi表示在i點服務開始時間；ei、li表示客戶i的服務時間窗；Q表示電動汽車的電池容量。

式(11)和式(12)約束汽車的載荷并確?？傒d荷不超過貨物容量：

(11)

0≤ui≤C?i∈DD

(12)

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

式(13)和式(14)分別表示離開客戶和站點時的電池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)決定用哪種類型的充電樁進行充電。

(17)

(18)

(19)

(20)

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

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

(21)

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

(22)

2 模型求解

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

(23)

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

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

(24)

(25)

式中：si表示服務客戶i的時間要求。

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

(26)

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

(27)

(28)

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

(29)

(30)

(31)

(32)

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

y0=Q

(33)

(34)

(35)

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

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

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

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

圖2 兩個節(jié)點之間的充電站

3 算例分析

本文構(gòu)造了一個包括100個客戶和21個充電站的大規(guī)模實例，數(shù)據(jù)在100×100網(wǎng)格上聚類和隨機分布。其中根據(jù)時間窗口的長度、汽車負載和電池容量的不同將客戶分為窄時間窗口(1類)和寬時間窗口(2類)兩類，通過隨機選擇大規(guī)模實例中的客戶和充電站子集生成小規(guī)模實例。本文在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é)中的設置。

3.1 大規(guī)模算例

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

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

表1 大規(guī)?？蛻羲憷治?/p>

續(xù)表1

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

3.2 小規(guī)模算例

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

表2 小規(guī)?？蛻羲憷治?/p>

續(xù)表2

結(jié)果中的運行時間為7 200 s的CPLEX結(jié)果顯示在給定時間限制內(nèi)找到的最佳上限，并不一定是最佳解決方案。CPLEX可以將客戶數(shù)在10以下的算例進行優(yōu)化，本文算法也可以找出最優(yōu)解，但需要的時間更長。而客戶數(shù)在10到15個的算例中，本文算法在尋找最優(yōu)解和運行時間方面表現(xiàn)均優(yōu)于CPLEX。結(jié)果表明了本文算法在解決小規(guī)?？蛻舻膶嵗型瑯泳哂锌尚行院透咝?。

4 結(jié) 語

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

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