計及分時電價及交通情況的電動汽車最優出行路徑規劃算法

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

1深圳供電局有限公司

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

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

0 引言

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

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

事實上，在不同時間以及不同地區，充電電價也會不盡相同[5]。因此對于電動汽車的出行路徑規劃將轉變為一個優化問題[6]，優化的目標就是最大程度地滿足用戶需求。

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

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

1 電動汽車出行路徑規劃影響因素

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

1.1 電動汽車因素

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

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

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

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

1.2 道路因素

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

（1）不同道路與不同充電站的連接布局構成了從出發點到目的地的道路網絡，最優路徑規劃將在此基礎上展開。

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

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

1.3 充電站因素

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

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

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

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

2 電動汽車出行路徑規劃模型

2.1 道路簡化模型

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

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

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

圖2 小區域充電站與道路連接情況圖

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

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

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

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

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

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

圖3 小區域充電道路簡化模型圖

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

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

2.2 聯合目標函數確定

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

(1)出行時間

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

(2)充電費用

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

在已知分時電價制度的前提下，實現對電動汽車最優路徑的規劃。則充電費用可以表示為：

(3)聯合目標函數

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

2.3 約束條件確定

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

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

3 實時路徑規劃算法流程

圖4 電動汽車實時路徑規劃流程圖

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

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

4 仿真算例

對圖2所示區域進行多次不同目標、不同負荷情況下的電動汽車最優出行路徑規劃結果進行對比。由于區域比較小，取電動汽車總容量為較小的16kWh，

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

表1 電動汽車路徑規劃參數表

圖5 電動汽車實時路徑規劃流程圖

圖6 電動汽車實時路徑規劃流程圖

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

5 結論

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

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

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

（3）建立了基于道路簡化模型的最優路徑規劃模型，包括聯合目標函數以及相關約束條件，能夠準確實現不同目標、不同情況下的最優路徑規劃。