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

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

?

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

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

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

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

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

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

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

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

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

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

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

node=[id,posX,posY,childs]

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

childs=[node,weight,mold]

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

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

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

1.2智能電動(dòng)汽車模型

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

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

pathTime,costElec,costLen,costTime,

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

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

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

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

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

capacity]

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

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

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

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

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

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

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

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

2.1初始化階段

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

2.2階段性分析

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

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

圖2　階段性分析流程

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

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

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

2.4智能充電

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

圖4　智能充電流程

3　仿真分析

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

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

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

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

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

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

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

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

3.3電動(dòng)汽車路徑規(guī)劃實(shí)時(shí)性分析

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

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

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

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

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

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

4　結(jié)束語

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

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

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

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

[1]歐雯要,葉瑞克,鮑健強(qiáng).電動(dòng)汽車(V2G技術(shù))的節(jié)能減碳價(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é)報(bào),2002,28(1):70-73.

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

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

[10]田佳榮,張昌華.一種電動(dòng)汽車用GPS導(dǎo)航系統(tǒng)的設(shè)計(jì)[J].電子測(cè)試,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]陳勇,孫逢春.電動(dòng)汽車?yán)m(xù)駛里程及其影響因素的研究[J].北京理工大學(xué)學(xué)報(bào),2009,21(5)：529-582.

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

[14]陳德兵,葉磊.低溫對(duì)純電動(dòng)汽車?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

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