計及分時電價及交通情況的電動汽車最優(yōu)出行路徑規(guī)劃算法

李永攀 魏恩偉 包賢祿 陳華鋒 鐘現(xiàn)成 陸軼祺 解大

1深圳供電局有限公司

2深圳市康拓普信息技術有限公司

3上海交通大學電子信息與電氣工程學院

0 引言

隨著新能源汽車的不斷普及，公共交通工具正大規(guī)模電動化，其中新能源汽車保有量在不斷上升，在相關政策的支持下，大量私人的電動汽車也走進了人們的日常生活[1]。在此大背景下，電動汽車配套的充電設施以及充電政策逐步完善。原困擾電動汽車車主的續(xù)航里程、無處充電等問題也逐步得到解決[2]。如何更好地使用電動汽車完成遠距離出行是當前研究的一項重點。

對于路徑規(guī)劃算法，應用最為廣泛的是A＊算法以及Dijkstra算法[3-4]，這些算法可以解決普通汽車的路徑搜索問題，但是無法滿足電動汽車車主對于出行時間以及充電費用的最優(yōu)需求。

事實上，在不同時間以及不同地區(qū)，充電電價也會不盡相同[5]。因此對于電動汽車的出行路徑規(guī)劃將轉(zhuǎn)變?yōu)橐粋€優(yōu)化問題[6]，優(yōu)化的目標就是最大程度地滿足用戶需求。

為了實現(xiàn)電動汽車的出行路徑規(guī)劃，有針對實時交通信息為用戶提供最優(yōu)路徑的研究，能在保證電量充足的情況下，實現(xiàn)出行的最短路徑[7]；有些研究同樣通過交通實時信息來實現(xiàn)動態(tài)的電動汽車路徑規(guī)劃[8]。這類算法雖然能夠在一定程度上滿足電動汽車的出行需要，以及對電動汽車負荷的合理分配，但是卻忽略了用戶的實際需求。

本文立足于電動汽車及配套設施發(fā)展現(xiàn)狀，提出了一種基于用戶實際需求的電動汽車出行最優(yōu)路徑規(guī)劃算法，包含對分時電價以及實時道路交通情況的分析。通過道路簡化模型，簡化規(guī)劃算法，能夠?qū)崿F(xiàn)在充電站密集或松散區(qū)域的路徑規(guī)劃，以滿足用戶的最大需求。

1 電動汽車出行路徑規(guī)劃影響因素

為了制定有實際應用價值的電動汽車出行路徑規(guī)劃方案，需要對其可能產(chǎn)生影響的所有因素進行分析。這些因素可以歸納為電動汽車因素、道路因素和充電站三大因素。

1.1 電動汽車因素

作為規(guī)劃主體，電動汽車本身的實時車況以及車主的主觀選擇將直接影響路徑的規(guī)劃結果。事實上，電動汽車本身的硬性條件是決定出行路徑規(guī)劃的主要因素。

（1）車主會確定本次出行的初始位置以及目的地。

（2）在保證車輛時刻有電的前提下，便需要根據(jù)用戶的實際需求，平衡充電費用與出行時間之間的優(yōu)先程度，達到“既節(jié)省時間又比較便宜”的模糊需求。

（3）在行駛過程中，電動汽車SOC值將隨著行駛的繼續(xù)而不斷變化，根據(jù)此條件限制電動汽車是否需要充電以及充電量的大小。

1.2 道路因素

道路因素實際上是目前車載導航主要考慮的方面。車載導航通過內(nèi)置的地圖匹配，即map matching功能，將實時定位的電動汽車位置與實際道路相匹配，便可獲取車輛當前行駛道路的信息，從而完成實時路徑規(guī)劃[9]。事實上，在對電動汽車出行路徑進行規(guī)劃時，道路實時條件是出行時間的一大組成部分。

（1）不同道路與不同充電站的連接布局構成了從出發(fā)點到目的地的道路網(wǎng)絡，最優(yōu)路徑規(guī)劃將在此基礎上展開。

（2）每條道路的實時交通情況及其長度，是評判在充電站間行駛時所要耗費時間的決定性條件。

道路交通信息在已有的導航中便可以獲取，通過綜合該信息與充電站的分布情況便能繪制出專用于電動汽車充電路徑規(guī)劃的道路簡化模型。此模型是實現(xiàn)最優(yōu)路徑規(guī)劃的基礎。

1.3 充電站因素

充電站是連接道路信息以及電動汽車需求的橋梁。充電站的位置信息與道路信息配合構成道路簡化模型，充電站的電氣信息與電動汽車的充電需求同樣需要相互滿足。影響電動汽車最優(yōu)路徑規(guī)劃的充電站因素有：

（1）充電站與道路的連接情況。車主必然會選擇充電費用低并且繞路盡可能少的出行方式。

（2）每個充電站容量以及對負荷的預測。這很大程度上決定了充電電價的高低，也同樣決定了電動汽車接入充電時是否會對電網(wǎng)工作產(chǎn)生壓力。當負荷特別高的時候，甚至可能禁止新的電動汽車接入充電。

（3）充電站的工作方式以及充電設施使用情況。私家車主一般均會選擇直流快充，目前大多數(shù)充電站也都已配備直流快充功能。而充電站的工作時間以及當前充電樁是否已經(jīng)滿載都是在進行路徑規(guī)劃時必須考慮的問題。在充電車位已滿的情況下，可以選擇等待空車位的出現(xiàn)或是提前預約車位。這將增加額外的出行時間或是費用。

2 電動汽車出行路徑規(guī)劃模型

2.1 道路簡化模型

城市交通網(wǎng)絡錯綜復雜，在尋找電動汽車出行路徑時，利用導航設備中可以獲取的每條道路實時交通情況及其長度信息，根據(jù)道路與充電站的連接布局信息，求得電動汽車在兩充電站間不同道路行駛所需要消耗的時間：

根據(jù)（1）式可求得實際的兩充電站間預期行駛時間。由于所選道路的不同，將產(chǎn)生很多種情況，如圖1所示。這里取其中的最短時間作為兩充電站間行駛的預期時間：

圖1 兩充電站間不同路徑耗時示意圖

圖2 小區(qū)域充電站與道路連接情況圖

取圖2所示小區(qū)域充電站分布情況為例，說明道路簡化模型的具體產(chǎn)生方式。

根據(jù)公式（2）對圖2中兩兩充電站間的預期最短行駛時間均能得到，由此便能繪制出如圖3所示的兩兩相連的線段（包括虛線和紅色線）。假設布局中共有n個充電站，則從每個充電站點出發(fā)均有條線段，其權值便以預期行駛時間表示，由此構成的充電道路模型將包含條線段。這樣的數(shù)量級其實已經(jīng)可以接受，然而根據(jù)實際應用需要，可以對該模型進一步簡化。記電動汽車正常使用時的最高連續(xù)行駛時間為，對模型可以繼續(xù)進行以下兩步的化簡：

（1）對預期行駛時間超過電動汽車續(xù)航時間的線段直接刪除，也即對：

例如：假設電動汽車持續(xù)行駛時間不超過15小時，則在圖3所示模型圖中，虛線段AC以及虛線段AF的預期時間為18小時，便對其進行刪除。

（2）對從邏輯上來看勢必不會選擇的道路直接刪除。在未完成的道路簡化模型上，會存在有一些線段的權值大于或等于連接其首位的多條線段構成的折線段權值之和，那么無論充電站的實際負荷情況如何，電動汽車的車主都將必然選擇那條折線段作為行駛路線，因為在保證了出行時間的最小化的同時，經(jīng)過了更多的充電站。

在圖3模型中，虛線段BF權重為14，而線段BD與線段DF權重之和同樣為14，因此同樣可以將虛線段BF直接刪除。

圖3 小區(qū)域充電道路簡化模型圖

至此，基于電動汽車出行充電道路的道路簡化模型便已經(jīng)完成。該模型通過實時交通信息，確定充電站間的預期行駛時間，將無限復雜的道路交通網(wǎng)絡化簡為由少數(shù)帶有權值的線段構成的道路簡化模型，并自動排除了擁堵路段。當不計充電站信息時，從B到F的最短路徑很明顯就是圖3中紅線所示路徑。在計及充電站時的路徑規(guī)劃也簡化了很多。

在應用道路簡化模型求解最優(yōu)路徑時，由于初始位置與終止位置并不一定是在某個充電站，而可能在任何地方。因此，在建立道路簡化模型時，要將初始位置與終止位置作為虛擬充電站同樣納入模型之中，這樣便能實現(xiàn)任意位置的路徑規(guī)劃。

2.2 聯(lián)合目標函數(shù)確定

在道路簡化模型的基礎上建立電動汽車出行的最優(yōu)路徑規(guī)劃目標函數(shù)。從用戶的實際需求出發(fā)，該目標函數(shù)將由兩部分構成：出行時間以及充電費用。

(1)出行時間

等待時間即為在不同充電站充電前等待的時間：

(2)充電費用

通過對充電站歷史負荷數(shù)據(jù)的大數(shù)據(jù)分析，可以對任意時刻的充電負荷進行預測，關于對電負荷的預測方法很多，包括人工神經(jīng)網(wǎng)絡、小波分析、支持向量機等，其相對誤差可以保證在20%以內(nèi)，能夠為分時電價的預測提供參考。

在已知分時電價制度的前提下，實現(xiàn)對電動汽車最優(yōu)路徑的規(guī)劃。則充電費用可以表示為：

(3)聯(lián)合目標函數(shù)

在引入了充電站的分時電價制度后，電動汽車的車主在對出行路徑進行規(guī)劃時除了考慮常規(guī)的出行時間，還會將充電費用也納入考慮范圍，因此規(guī)定目標函數(shù)為對出行時間與充電費用的組合：

2.3 約束條件確定

對于電動汽車出行的最優(yōu)路徑求解過程，實際上是在道路簡化模型的基礎上，選擇一條滿足最優(yōu)規(guī)劃目標且包含用戶所選起始位置和終止位置的線段組合?；谶@種思想，在初始條件已明確的情況下，可以列出最優(yōu)路徑規(guī)劃的約束條件如下：

至此電動汽車最優(yōu)出行的約束條件便已完成，配合聯(lián)合目標函數(shù)，共同構成了電動汽車最優(yōu)出行路徑的規(guī)劃模型。由此模型，便能求解出任意初始位置與終止位置的最優(yōu)路徑。

3 實時路徑規(guī)劃算法流程

圖4 電動汽車實時路徑規(guī)劃流程圖

能夠完成任意初始位置以及終止位置的最優(yōu)路徑規(guī)劃，便能夠進一步實現(xiàn)電動汽車出行的實時最優(yōu)路徑規(guī)劃，其流程圖如圖4所示。在進行實時規(guī)劃時，改變的僅僅是初始位置，而終止位置并不會改變，因此對道路簡化模型的修改量很小。

構建完最優(yōu)路徑規(guī)劃模型后，最優(yōu)路徑規(guī)劃便化為了簡單的混合整數(shù)非線性規(guī)劃問題。其求解方式很多，不再贅述。每次的規(guī)劃路徑輸出以后經(jīng)過一個小延時，便開始進行下一輪的規(guī)劃，由此便能實現(xiàn)實時路徑規(guī)劃。該流程能夠保證在充電站稀疏地區(qū)和密集地區(qū)，用戶的實際需求均能得到滿足。

4 仿真算例

對圖2所示區(qū)域進行多次不同目標、不同負荷情況下的電動汽車最優(yōu)出行路徑規(guī)劃結果進行對比。由于區(qū)域比較小，取電動汽車總?cè)萘繛檩^小的16kWh，

電動汽車行駛每小時耗電2kWh，充電站充電功率為10kW，效率為1。充電站A、C、D、E的預期電價以及目標函數(shù)α/β如表1中所示。分時電價制度按峰時每kWh為2.00元，谷時每度1.00元計算。

表1 電動汽車路徑規(guī)劃參數(shù)表

圖5 電動汽車實時路徑規(guī)劃流程圖

圖6 電動汽車實時路徑規(guī)劃流程圖

對該模型進行5次仿真計算，得出的規(guī)劃路徑如圖5和圖6所示。圖5中紅色線、藍色線、綠色線分別對應表1中編號1、2、3的參數(shù)，而圖6中的紫色線、橙色線分別對應表1中編號4、5的參數(shù)。經(jīng)檢驗，這些路徑確實是在不同場景下的最優(yōu)路徑。事實上，在輸出規(guī)劃結果的時候還包含了在不同充電站的充電量，這可以很好地由車主直接把控。

5 結論

在電動汽車大規(guī)模普及的當下，“充電難”已經(jīng)不再是困擾廣大車主駕駛電動汽車出行的問題。人們更多地考慮如何更好地出行。這就涉及充電費用和出行時間的問題。本文針對電動汽車用戶的實際需求，完成了以下工作：

（1）總結了與電動汽車出行路徑相關的影響因素，包括電動汽車本身、道路交通以及充電站三方面的因素，有利于對電動汽車出行方案的制定。

（2）提出了基于實時道路交通情況與充電站分布位置的道路簡化模型，充分地化簡了復雜交通網(wǎng)絡，為快速的最優(yōu)路徑規(guī)劃提供了基礎。

（3）建立了基于道路簡化模型的最優(yōu)路徑規(guī)劃模型，包括聯(lián)合目標函數(shù)以及相關約束條件，能夠準確實現(xiàn)不同目標、不同情況下的最優(yōu)路徑規(guī)劃。