趙薪智,李盤靖,張　歡,任珈漪,張榮磊

(山東理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255049)

?

電動汽車智能充電路徑規(guī)劃研究

趙薪智,李盤靖,張歡,任珈漪,張榮磊

(山東理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255049)

針對電動汽車存在的”充電焦慮”問題，建立了智能電動汽車動態(tài)網(wǎng)絡(luò)系統(tǒng)模型，當(dāng)存在多目標(biāo)時，在原有路徑規(guī)劃算法的基礎(chǔ)上，提出了”Dijkstra算法+最近鄰點法”的最優(yōu)路徑規(guī)劃算法。該算法可對電動汽車的剩余電量進(jìn)行智能預(yù)判，并能實現(xiàn)電動汽車在充電樁的智能充電，有效地緩解了電動汽車“充電焦慮”問題。

智能電動汽車；動態(tài)充電路徑規(guī)劃；智能充電樁;充電網(wǎng)絡(luò)

隨著汽車工業(yè)的高速發(fā)展，全球汽車的保有量不斷增加。以燃油發(fā)動機(jī)為動力的傳統(tǒng)汽車帶來的環(huán)境污染與能源短缺問題日漸凸顯，新能源汽車成為未來汽車技術(shù)的主要發(fā)展方向[1-5]。然而,電動汽車充電時間較長,一般為5～8 h[6]，勢必會對充電樁的負(fù)荷、充電排隊時間造成很大影響。因此，在多個充電樁可選的情況下，存在著在什么時間前往哪個充電樁的路徑規(guī)劃問題。

目前有關(guān)電動汽車充電路徑規(guī)劃的研究仍側(cè)重于單一路徑規(guī)劃算法。彭飛等[7]引入基數(shù)堆結(jié)構(gòu)減少路徑搜索算法的時間復(fù)雜度。樊月珍等[8]采用對弧段而不是標(biāo)點標(biāo)號，節(jié)省了大量存儲空間。劉智清等[9]建立了最優(yōu)路徑規(guī)劃問題的線性規(guī)劃模型，以期提高運(yùn)算速度。但這些算法和模型并不能完全應(yīng)用到實際中，這是因為一般電動汽車存在多個目標(biāo)遍歷，單一的路徑規(guī)劃算法效率相對較低。此外，還忽略了對能耗模型的研究。電動汽車在特定路段的能耗并非基于實時的交通信息估算，而是賦予常量，或者是單方面對電動汽車的能耗進(jìn)行估算[10-11]。陳勇等[12]通過等速法來計算電動汽車的續(xù)駛里程。徐寶貴等[13]分析了影響車載電池工作性能以及汽車?yán)m(xù)駛里程的因素。陳德兵[14]分析了電動汽車動力電池在不同溫度下的充放電情況?？v觀目前的研究，大多局限于充電路徑規(guī)劃和續(xù)航里程單方面的研究。本文對電動汽車的能耗建模，將該模型作為電動汽車?yán)m(xù)駛里程估算和路徑規(guī)劃的基礎(chǔ)，對實際道路交通條件下的電動汽車進(jìn)行路徑規(guī)劃，評估電動汽車的節(jié)能效果。

1　電動汽車動態(tài)網(wǎng)絡(luò)模型

智能電動汽車動態(tài)交通網(wǎng)絡(luò)模型主要由智能路網(wǎng)模型、智能電動汽車模型和智能充電樁網(wǎng)絡(luò)模型3部分組成。

1.1智能路網(wǎng)模型

虛擬智能路網(wǎng)是將實際的道路交通網(wǎng)絡(luò)抽象為有向網(wǎng)絡(luò)，其中節(jié)點表示電動汽車、充電樁位置以及交叉路口，弧段表示道路，弧段權(quán)值表示道路距離、所花費時間、所消耗電能。

node=[id,posX,posY,childs]

其中： id為節(jié)點編號，表征電動汽車、充電樁所在位置，為實際位置的抽象表示；posx指節(jié)點所在實際位置的精度；posy指節(jié)點所在實際位置的維度； childs指當(dāng)前節(jié)點的后續(xù)子節(jié)點。childs采用map類型，即

childs=[node,weight,mold]

其中：node為指向的下一個節(jié)點；weight指的是當(dāng)前節(jié)點到下一個節(jié)點的權(quán)值；mold表示交通權(quán)值類型。

當(dāng)電動汽車在不同工況(啟動、加速等6種狀態(tài))時，行駛同樣的路段，所耗費的電量是不同的。當(dāng)電動汽車處在加速或減速工況時，耗電量相對增多。因此，當(dāng)交通狀況越擁堵時，電動汽車加速和減速次數(shù)也就越多，耗電量也就越多。

本文以淄博市2014年發(fā)布的交通狀況為例，采用交通擁堵指數(shù)動態(tài)模擬交通狀況。交通擁堵指數(shù)是通過獲得分布在道路中的動態(tài)車輛位置信息，得到不同等級的道路運(yùn)行速度，進(jìn)而得到0～10的指數(shù)指標(biāo)值。交通狀況擁堵程度越高，該路段所消耗的時間就越多。

1.2智能電動汽車模型

智能電動汽車模型需要實現(xiàn)的功能有SOC(剩余電量)的預(yù)警、自動尋路、尋找最近充電樁、充電等。因此，電動汽車模型為：

cars=[id,speed,SOC,waitTime,chargeTime,

pathTime,costElec,costLen,costTime,

pos,goal,mold,path,pathInfo,trace,sf,gl]

其中：id為電動汽車編號；speed為電動汽車行駛速度；SOC為剩余電量；waitTime表示當(dāng)電動汽車已經(jīng)到達(dá)充電樁到充電前的等待時間，當(dāng)開始充電時，waitTime=0；chargeTime表示充電時間，當(dāng)chargeTime=0時，電動汽車離開充電樁；pathTime表示到達(dá)充電樁路上所耗費時間，當(dāng)pathTime=0時，表示已經(jīng)到達(dá)充電樁；costElec，costLen和costTime分別表示從初始狀態(tài)到達(dá)目的地總共耗費的電能、總共走過距離、總共花費的時間(包括電動汽車充電時間)；pos為所在位置，即節(jié)點node編號；goal表示所要前往位置，當(dāng)電動汽車需要充電時，此時目的地為充電樁位置，否則目的地為最后終點；mold為優(yōu)化方式；path記錄到達(dá)每個節(jié)點最短路徑權(quán)值；pathInfo記錄到達(dá)每個節(jié)點的最短路徑；trace記錄車走過的節(jié)點；sf為安全系數(shù)，確保SOC在安全電量內(nèi)；gl為到達(dá)最近充電樁的預(yù)估值。

1.3智能充電樁網(wǎng)絡(luò)模型

智能充電樁網(wǎng)絡(luò)能使智能電動汽車根據(jù)實時的充電樁信息做出智能充電決策，因此智能充電樁網(wǎng)絡(luò)模型為

elecs=[id,pos,sequene,count,totalTime,

capacity]

其中：id表示充電樁編號；pos表示所在節(jié)點位置；sequene表示當(dāng)前充電隊列；count表示當(dāng)前充電的電動汽車數(shù)量；totalTime 表示當(dāng)前充電所需要總時間；capacity表示充電樁車輛容納數(shù)。

1.4模型間的交互聯(lián)系

智能路網(wǎng)將實際的交通網(wǎng)抽象為有向圖網(wǎng)絡(luò)，為電動汽車提供了位置信息，同時還提供了各路段的權(quán)值信息。智能充電樁向智能電動汽車提供當(dāng)前充電樁位置、當(dāng)前隊列以及所需充電的時間等。智能電動汽車根據(jù)優(yōu)化目標(biāo)來做出選擇。智能電動汽車的速度、SOC等均與智能路網(wǎng)路段權(quán)值有關(guān)，同時智能電動汽車的排隊時間、充電時間、SOC的變化量等與智能充電樁的狀態(tài)信息也是密不可分的。

2　電動汽車充電路徑規(guī)劃

在建立電動汽車動態(tài)網(wǎng)絡(luò)模型的基礎(chǔ)上，提出一種最優(yōu)的充電路徑規(guī)劃方法，即當(dāng)電動汽車有多目標(biāo)需要遍歷時，采用基于”Dijkestra算法+最近鄰點法”的靜態(tài)最優(yōu)路徑規(guī)劃方法，但是由于各路段上的交通狀態(tài)是動態(tài)波動的，難以得到準(zhǔn)確的可行駛時間隨時間變化的關(guān)系式。將時間離散化，即在單位時間內(nèi)交通狀況是穩(wěn)定的?；诮煌窙r的動態(tài)路徑規(guī)劃可以認(rèn)為在多個離散的時間點上做出靜態(tài)的路徑規(guī)劃，也就減少了路徑規(guī)劃次數(shù)。同時，當(dāng)有突發(fā)情況發(fā)生時，例如有其他電動汽車改變行駛狀態(tài)、改變行駛路徑時，可做出新的路徑規(guī)劃，增大了路徑規(guī)劃的準(zhǔn)確率。

首先進(jìn)行初始化。然后在間隔時間段內(nèi)初始時刻或有事件發(fā)生時進(jìn)行階段性分析。對電動汽車的SOC進(jìn)行智能預(yù)警分析。當(dāng)電動汽車不在充電樁充電時，返回階段性分析；當(dāng)電動汽車在充電樁充電時，無需進(jìn)行階段性分析；當(dāng)電動汽車充滿電時，回到動態(tài)交通中，此時返回階段性分析。

動態(tài)路徑規(guī)劃流程主要由初始化階段、智能充電樁競爭關(guān)系分析、SOC智能預(yù)警控制分析以及階段性分析4部分組成，如圖1所示。

圖1　動態(tài)路徑規(guī)劃流程

2.1初始化階段

在初始化階段中， 初始化虛擬場景中的電動汽車、充電樁、路網(wǎng)、時間器等部分，并根據(jù)電動汽車的多目的地做出第1次優(yōu)化。采用Dijkstra算法為基礎(chǔ)算法，即各目標(biāo)點之間使用Dijkstra算法，確保目標(biāo)之間的路徑為最短路徑。由于電動汽車一般有多個目的地，因此采用最近鄰點法，使電動汽車確定一條遍歷所有目標(biāo)點的最短路徑。

2.2階段性分析

為了增大動態(tài)路徑規(guī)劃的準(zhǔn)確率并且減少重復(fù)路徑規(guī)劃的執(zhí)行次數(shù)，設(shè)定間隔的離散時間點和事件集。間隔的離散時間點是將時間離散化，假定在單位時間段內(nèi)的交通狀況不會發(fā)生變化，在每個時間段初做出分析。事件集為存儲與動態(tài)路徑規(guī)劃有關(guān)的一系列事件集，包括各類的突發(fā)狀況、電動汽車狀態(tài)的改變等。

當(dāng)time%inte==0||eventGroup.has(e)(系統(tǒng)時間在間隔時間段的初始時刻或事件集中有事件發(fā)生)時，場景會發(fā)生變化，需要重新進(jìn)行路徑規(guī)劃。當(dāng)事件結(jié)束時，清除事件。階段性分析流程見圖2。

圖2　階段性分析流程

2.3SOC智能預(yù)警控制分析

當(dāng)電動汽車的SOC

圖3　SOC智能預(yù)警控制流程

2.4智能充電

當(dāng)cars0需要去充電樁充電時，分別計算cars0的pathTime，waitTime，chargeTime。當(dāng)pathTime=0時，說明電動汽車已經(jīng)在充電樁隊列中，充電樁的隊列數(shù)加1，將car推入sequene末尾處，并且totalTime+=car.chargeTime；當(dāng)waitTime=0時，電動汽車已經(jīng)開始充電；當(dāng)chargeTime=0時，電動汽車已經(jīng)充滿電，準(zhǔn)備離開充電樁，此時將sequence移除car，同時隊列數(shù)減1。智能充電流程見圖4。

圖4　智能充電流程

3　仿真分析

以百度地圖為基礎(chǔ)，在淄博市城區(qū)范圍內(nèi)對電動汽車智能最優(yōu)充電路徑規(guī)劃進(jìn)行仿真分析。采用節(jié)點表示充電樁、電動汽車等相對位置，建立了包含1 800個節(jié)點、10個充電樁以及50輛電動汽車的模型。仿真系統(tǒng)界面如圖5所示。

圖5　仿真系統(tǒng)界面

3.1充電樁智能充電仿真分析

假定主車(cars0)要去9號充電樁充電，到達(dá)充電樁時間為20 min，9號充電樁位置是1050。此時在充電樁有2輛車(分別為cars1和cars2)在充電，cars3，cars4，cars5在去9號充電樁充電的路上，各電動汽車的初始狀態(tài)如表1所示。假定每走1單位路程耗費1單位電量,每分鐘充1單位電量，充滿電后電動汽車離開。9號充電樁狀態(tài)變化如表2所示。

表1　電動汽車初始狀態(tài)

表2　充電樁狀態(tài)變化

3.2電動汽車多目標(biāo)路徑規(guī)劃仿真

電動汽車所在位置為node532，需要去往5個目的地，分別為：dest1，dest2，dest3，dest4，dest5(node432，node333，node233，node1132，node121)。同時，假定在電動汽車電量<50時自動尋找最優(yōu)充電樁充電。仿真結(jié)果如表3所示。

3.3電動汽車路徑規(guī)劃實時性分析

當(dāng)電動汽車路徑規(guī)劃時，需要對路徑規(guī)劃的實時性進(jìn)行分析，能否及時給出路徑規(guī)劃方案。主要分為2種情況:① 當(dāng)有突發(fā)狀況發(fā)生時無需重新計算，可從原有的存儲的最短路徑重新取出從當(dāng)前位置到第1個目標(biāo)節(jié)點的最短路徑。② 當(dāng)電動汽車電量不足時需找到一個最近充電樁，使得當(dāng)前位置到達(dá)充電樁的距離與充電樁到達(dá)下一個充電樁距離之和最短，即需計算2段最短距離，因此需要保證其準(zhǔn)確性，縮小充電樁搜索范圍并及時做出路徑規(guī)劃。

表3　路徑規(guī)劃對比

現(xiàn)對電動汽車電量不足情況進(jìn)行實時性分析。對當(dāng)前范圍內(nèi)100個節(jié)點進(jìn)行搜索，對充電樁個數(shù)進(jìn)行分析，結(jié)果如表4所示。

表4充電樁個數(shù)與搜索速度關(guān)系

充電樁個數(shù)搜索速度/s1<12<1314252641015

當(dāng)充電樁數(shù)量較少時運(yùn)行時間很短；當(dāng)充電樁數(shù)量較多時運(yùn)行時間雖相對較長，但仍在可接受范圍之內(nèi)。

4　結(jié)束語

本文在建立多目標(biāo)電動汽車智能充電路徑規(guī)劃模型上進(jìn)行如下改進(jìn)：

1) 將時間離散化，并且添加了事件集，優(yōu)化了電動汽車動態(tài)路徑規(guī)劃。

2) 對SOC做出智能預(yù)警，緩解了電動汽車的“充電焦慮”問題。

3) 在原有算法的基礎(chǔ)上提出了”最近鄰點法+Dijkstra算法”，大大優(yōu)化了電動汽車的路徑規(guī)劃。同時根據(jù)實時的交通信息，動態(tài)模擬了電動汽車的智能充電過程。

[1]歐雯要,葉瑞克,鮑健強(qiáng).電動汽車(V2G技術(shù))的節(jié)能減碳價值研究[J].未來與發(fā)展,2012(5):36-40.

[2]KIM H,LEE J,PARK G,et al.An efficient scheduling scheme on charging stations for smart transportation [M].Berlin Heidelberg:Springer,2010:274-278.

[3]KIM B,JO J,KIM J,et al.Optimal route search in car navigation systems by multi-objective genetic algorithms [J].International Journal of Information Systems for Logistics and Management,2009,4(2):9-18.

[4]MARIYASAGAYAM M N,KOBAYASHI Y.Electric vehicle route assistance using forecast on charging station [C]//Lisbon,Portugal:Proceedings of 3th International Conference on Smart Grids,Green Communications and IT Energy-aware Technologies.2013:134-142.

[5]KOBAYASHI Y,KIYAMA N,AOSHIMA H,et al.A route search method for electric vehicles in consideration of range and locations of charging stations [C]//Baden-Baden,Germany:Proceedings of 2011 IEEE Intelligent Vehicles Symposium (FV).[S.l.]:IEEE,2011:920-925.

[6]SEDANO J,CHIRA C,VILLAR J R,et al.An intelligent route management system for electric vehicle charging[J].Integrated Computer-Aided Engineering,2013,20(4):321-333.

[7]彭飛,柳重堪,張其善.車輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J].北京航空航天大學(xué)學(xué)報,2002,28(1):70-73.

[8]樊月珍,江發(fā)潮,毛恩榮.車輛行駛最優(yōu)路徑優(yōu)化算法設(shè)計[J]計算機(jī)工程與設(shè)計,2007,28(23):5758-5761.

[9]劉智請,李春貴.城市交通最優(yōu)路徑規(guī)劃仿真研究[J].計算機(jī)仿真,2011,28(7):349-352.

[10]田佳榮,張昌華.一種電動汽車用GPS導(dǎo)航系統(tǒng)的設(shè)計[J].電子測試,2011(1):54-57.

[11]KRAUSE K R,GAULT T A,PEBBLES P H,et al.Charge notification method for extended range electric vehicles[P].American patents,2012-1-19.

[12]陳勇,孫逢春.電動汽車?yán)m(xù)駛里程及其影響因素的研究[J].北京理工大學(xué)學(xué)報,2009,21(5)：529-582.

[13]徐貴寶,王震坡.電動汽車?yán)m(xù)駛里程能量計算和影響因素分析[J].車輛與動力技術(shù),2008(2):53-56,61.

[14]陳德兵,葉磊.低溫對純電動汽車?yán)m(xù)駛離成的影響分析[J].客車技術(shù)與研究,2012(2):49-51,57.

(責(zé)任編輯劉舸)

Research on Intelligent Path Planning Charging for Electric Vehicle

ZHAO Xin-zhi, LI Pan-jing, ZHANG Huan, REN Jia-yi, ZHANG Rong-lei

(College of Computer Science and Technology,Shandong University of Technology, Zibo 255049, China)

Intelligent electric vehicle dynamic network system model was established for solving the “battery charging anxiety” problem of electromobile, and when multiple targets exist, the optimal path planning algorithm of “Dijkstra algorithm plus the nearest neighbor point method” was put forward based on the original path planning algorithm. The intelligent pre-sentence of remaining power of electric vehicles was made, and the intelligent charging of electric vehicles in the charging pile was achieved, which effectively eases the electric car charging anxiety problem.

intelligent electric vehicle; dynamic charging path planning; intelligent charging pile; charging network

2016-05-12

趙薪智(1992—)，男，主要從事軟件工程研究，E-mail:530143256@163.com。

format：ZHAO Xin-zhi, LI Pan-jing, ZHANG Huan, et al.Research on Intelligent Path Planning Charging for Electric Vehicle[J].Journal of Chongqing University of Technology(Natural Science)，2016(10):34-39.

10.3969/j.issn.1674-8425(z).2016.10.005

TP301

A

1674-8425(2016)10-0034-06

引用格式：趙薪智,李盤靖,張歡,等.電動汽車智能充電路徑規(guī)劃研究[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，2016(10):34-39.