基于實(shí)時(shí)路況的電動(dòng)汽車充電調(diào)度算法①

李紅章,楊金輝,朱家偉,安毅生

1(長(zhǎng)安大學(xué) 信息工程學(xué)院,西安 710054)

2(中興通訊股份有限公司長(zhǎng)沙分公司,長(zhǎng)沙 410005)

隨著我國(guó)社會(huì)經(jīng)濟(jì)的發(fā)展,道路上的車輛數(shù)不斷增加.然而,傳統(tǒng)汽車過(guò)度依賴化石能源,長(zhǎng)遠(yuǎn)看,不但會(huì)造成資源枯竭,還會(huì)導(dǎo)致嚴(yán)重的環(huán)境污染.電動(dòng)汽車的出現(xiàn)較好地解決了上述問(wèn)題.電動(dòng)汽車使用可再生的電能作為動(dòng)力,并且在使用過(guò)程中不產(chǎn)生尾氣等污染物.由于有著諸多優(yōu)點(diǎn),電動(dòng)汽車行業(yè)得到了國(guó)家的重點(diǎn)扶持,近年來(lái)發(fā)展迅猛.然而,電動(dòng)汽車有著充電時(shí)間長(zhǎng)、續(xù)航短的特點(diǎn),并且當(dāng)下城市充電設(shè)施不完善,充電站分布不均衡,直接導(dǎo)致電動(dòng)汽車補(bǔ)充能源較燃油車?yán)щy,已經(jīng)成為其進(jìn)一步推廣發(fā)展的障礙.解決電動(dòng)汽車的續(xù)航問(wèn)題較為直接的方式有兩種:一是提升電池容量;二是大量建設(shè)充電樁并提升充電速度.但當(dāng)下電池技術(shù)短期內(nèi)難以取得較大突破,電池容量及充電速度提升潛力有限.此外,現(xiàn)代城市人口密集,城市規(guī)劃缺乏前瞻性,改造成本高昂等原因?qū)е鲁潆姌?、充電站難以大規(guī)模鋪開建設(shè).在充電資源較為緊張的情況下,我們發(fā)現(xiàn)公共充電樁的使用率依然較為低下.據(jù)北京市發(fā)布的2018年10月的數(shù)據(jù)表明,北京市公共充電樁的利用率僅為7%左右.據(jù)一份歐洲的研究報(bào)告顯示僅有5%的電動(dòng)車輛長(zhǎng)期使用公共充電樁[1].美國(guó)愛荷華州國(guó)家實(shí)驗(yàn)室對(duì)5000 余充電樁的使用情況進(jìn)行統(tǒng)計(jì).結(jié)果表明交通便利的充電樁每周約有7 次的充電行為,與之對(duì)應(yīng)的是位置偏僻的充電樁每周只有約1.4 次的充電行為[2],大量的充電資源得不到有效利用.

隨著車聯(lián)網(wǎng)技術(shù)的發(fā)展[3],如何調(diào)度電動(dòng)汽車合理充電,成為近年來(lái)研究的熱點(diǎn).通過(guò)研究電動(dòng)汽車的歷史出行數(shù)據(jù),對(duì)區(qū)域內(nèi)的充電負(fù)荷進(jìn)行預(yù)測(cè),可以對(duì)當(dāng)前車輛的充電行為進(jìn)行合理調(diào)度.有學(xué)者提出基于空間負(fù)荷分布的車輛充電調(diào)度策略,通過(guò)對(duì)行駛過(guò)程的動(dòng)態(tài)分析,結(jié)合電網(wǎng)負(fù)荷狀態(tài)、交通數(shù)據(jù),可以將充電車輛匹配到合適的充電站[4].有研究學(xué)者使用了馬爾可夫決策過(guò)程和汽車隨機(jī)出行鏈建立了車輛充電需求的時(shí)空模型,得到了不同場(chǎng)景下的預(yù)測(cè)充電需求模型[5].此外,通過(guò)調(diào)節(jié)電價(jià)也可以有效的引導(dǎo)車輛充電行為,該方法客觀上能夠避免單點(diǎn)充電負(fù)荷過(guò)高,從而提高了充電站的使用率.基于此有學(xué)者將蟻群算法與合理調(diào)整電價(jià)相結(jié)合,提出了一種任務(wù)調(diào)度算法,能夠較好地降低用戶成本和充電站負(fù)荷[6].Masoum 等人提出了一種充電定價(jià)與優(yōu)先級(jí)方案,通過(guò)控制電動(dòng)汽車的充電時(shí)段,來(lái)緩解局部區(qū)域的供電壓力[7].還有部分學(xué)者從電網(wǎng)側(cè)的供電安全出發(fā)[8],設(shè)計(jì)了電動(dòng)汽車充電調(diào)度算法.Zhao 等人提出的基于ZigBee和GPRS 無(wú)線通信網(wǎng)絡(luò)技術(shù)的電動(dòng)汽車有序充電方法,通過(guò)控制電動(dòng)汽車的無(wú)序充電,避免了電網(wǎng)和配電設(shè)施因過(guò)載而產(chǎn)生損耗[9].Aguado 等人提出了一種混合整數(shù)線性規(guī)劃策略,用于調(diào)度電動(dòng)車隊(duì)與電網(wǎng)交換能量的行為,避免自身的充電行為對(duì)當(dāng)?shù)仉娏ο到y(tǒng)產(chǎn)生影響[10].上述研究多基于電網(wǎng)端的因素考量,針對(duì)用戶端的充電體驗(yàn)考量不足;而針對(duì)用戶端的研究多通過(guò)研究歷史數(shù)據(jù)來(lái)對(duì)當(dāng)前的充電需求進(jìn)行預(yù)測(cè),使得調(diào)度缺乏實(shí)時(shí)性,不能較好地應(yīng)對(duì)突發(fā)情況.

實(shí)時(shí)路況作為一種重要的交通數(shù)據(jù),越來(lái)越為人們所重視[11,12].為此,本文提出一種基于實(shí)時(shí)路況的電動(dòng)汽車充電調(diào)度算法.本算法綜合考慮實(shí)時(shí)路網(wǎng)內(nèi)的道路擁堵情況以及充電站內(nèi)的排隊(duì)情況,對(duì)充電車輛進(jìn)行統(tǒng)一調(diào)度,使車輛避開較為擁堵的路線,并且選擇距離較近,充電排隊(duì)車輛較少,排隊(duì)時(shí)間較短的充電樁進(jìn)行充電服務(wù),以達(dá)到提高充電效率,節(jié)約充電時(shí)間的目的.仿真實(shí)驗(yàn)的數(shù)據(jù)表明:本算法能夠較好地解決車輛充電的盲目性以及區(qū)域內(nèi)充電站負(fù)載不均衡的問(wèn)題.

1 電動(dòng)汽車充電耗時(shí)分析

1.1 耗時(shí)分析

電動(dòng)汽車充電的耗時(shí)過(guò)程如圖1所示,充電所消耗時(shí)間包括:電動(dòng)汽車到達(dá)充電站的行駛時(shí)間、在充電站的排隊(duì)等待時(shí)間、將電池充滿所需要充電時(shí)間.

圖1 電動(dòng)汽車充電過(guò)程圖

1)路程

充電路程是指電動(dòng)汽車從當(dāng)前位置到充電樁所經(jīng)過(guò)的道路里程總和.為了量化電動(dòng)汽車到充電樁經(jīng)過(guò)的道路里程,本文假設(shè)待充電車輛從起點(diǎn)到充電樁的路徑是按照最短路徑行駛,最短路徑采用迪杰斯特拉算法[13](以下簡(jiǎn)稱最短路徑算法)計(jì)算得到.

根據(jù)最短路徑算法,將電動(dòng)汽車i到充電樁j的最短路徑所途徑的路段分別記為dij1,dij2,dij3電動(dòng)汽車行駛的總路程dij可用式(1)表示:

2)時(shí)間

電動(dòng)汽車充電所消耗的時(shí)間包括:從當(dāng)前位置到充電站的行駛時(shí)間、充電站內(nèi)的排隊(duì)時(shí)間、充電時(shí)間,即:

其中,Ttotal表示電動(dòng)汽車充電花費(fèi)的各項(xiàng)時(shí)間之和;aij表示車輛i到達(dá)充電樁j通過(guò)各路段所消耗的時(shí)間;tw表示排隊(duì)時(shí)間;tc表示充電時(shí)間.

行駛時(shí)間aij:

其中,aij表示車輛i到達(dá)充電樁j通過(guò)各路段所消耗的時(shí)間和;dij1,dij2,···,dijn表示車輛i到達(dá)充電樁j充電,所經(jīng)過(guò)的各路段的長(zhǎng)度;vij1,vij2,···,vijn表示車輛i到達(dá)充電樁j充電,所經(jīng)過(guò)的各路段的速度.

排隊(duì)時(shí)間tw:表示車輛抵達(dá)充電站后,若有前車排隊(duì),則需等待前車完成充電服務(wù)后,再進(jìn)行充電,等待時(shí)間即為排隊(duì)時(shí)間;若無(wú)前車,則無(wú)需等待,即排隊(duì)時(shí)間為0.

充電時(shí)間tc:表示待充電車輛排隊(duì)結(jié)束,開始充電到充電完成所消耗的時(shí)間.充電時(shí)長(zhǎng)可由式(4)計(jì)算出.

其中,tic表示車輛i的充電時(shí)間;表示車輛i的電池容量;表示車輛i的初始電量;表示車輛i從起點(diǎn)到充電樁消耗的電能;Vin表示車輛i的充電功率.

1.2 相關(guān)說(shuō)明

1)本文從地圖商網(wǎng)站抓取西安市城區(qū)某時(shí)段的道路交通數(shù)據(jù)[14],其中包含:道路編碼、道路名稱、道路等級(jí)、道路方向、起始路段、終止路段、平均速度等[15].

2)在未調(diào)度的情況下,我們認(rèn)為電動(dòng)汽車從起點(diǎn)到充電站是按照最短距離行駛的,本文使用最短路徑算法模擬未調(diào)度的情況.

3)所有車輛的電池容量相同,電量隨著行駛時(shí)間線性消耗.

4)充電站設(shè)備全部正常,每個(gè)充電樁每次服務(wù)一輛汽車.

5)每輛電動(dòng)汽車的剩余續(xù)駛里程,至少可以到達(dá)一個(gè)充電站.

6)電動(dòng)汽車及充電樁分布在路網(wǎng)中,調(diào)度時(shí)按照就近原則將其歸納到就近的路口.調(diào)度過(guò)程簡(jiǎn)化為從路口到路口的調(diào)度.

7)電動(dòng)車輛和充電樁的接口是兼容的.

8)某一時(shí)刻發(fā)起充電請(qǐng)求的車輛數(shù)目為一定值,且通信時(shí)延忽略不計(jì)[16].

2 調(diào)度算法

2.1 算法描述

電動(dòng)汽車在前往充電的時(shí)候往往會(huì)考慮兩個(gè)方面的因素,一是距離充電站的距離;二是到達(dá)目標(biāo)充電站的路況.若選擇較近的充電站進(jìn)行充電,站內(nèi)可能需要較長(zhǎng)時(shí)間的排隊(duì);若選擇較為空閑的充電站,則可能路途較遠(yuǎn),交通情況較為擁堵,花費(fèi)更多的時(shí)間.

針對(duì)上述的選擇問(wèn)題,我們?cè)诰C合考慮交通路網(wǎng)擁堵情況、各充電站內(nèi)的排隊(duì)情況、距離充電站的路程等因素后,提出了一種以節(jié)約不必要的充電時(shí)間開銷為目的,以提升全局充電效率為導(dǎo)向的基于實(shí)時(shí)路況的電動(dòng)汽車充電調(diào)度算法.該算法說(shuō)明如下.

根據(jù)建立的道路交通路網(wǎng)模型以及電動(dòng)汽車充電行為分析結(jié)果,我們?cè)谶x定的路網(wǎng)范圍內(nèi),由最短路徑算法可求得電動(dòng)汽車到每個(gè)充電樁的最短距離.路網(wǎng)內(nèi)的充電樁及電動(dòng)車輛均與服務(wù)器互聯(lián),實(shí)時(shí)共享自身的位置信息、充電狀態(tài)等信息.

某時(shí)刻路網(wǎng)內(nèi)的待充電的電動(dòng)汽車I,共n個(gè),用EVi表示:

路網(wǎng)內(nèi)的充電站Y,用CSy表示:

其中,每個(gè)充電站CSy內(nèi)有k個(gè)充電樁jyx,x=1,2,3,···,k,故區(qū)域內(nèi)共有m個(gè)充電樁:

該m個(gè)充電樁統(tǒng)一編號(hào)為:

其中,diy表示電動(dòng)汽車EVi到充電站CSy的距離,dijyx表示電動(dòng)汽車到該充電站內(nèi)某個(gè)充電樁的距離;我們認(rèn)為:在不影響計(jì)算結(jié)果的前提下,電動(dòng)汽車EVi到充電站CSy的距離和到該站內(nèi)充電樁的距離可以認(rèn)為是近似相等的,故有:

在電動(dòng)汽車可達(dá)范圍內(nèi),對(duì)于任意電動(dòng)汽車EVi到任意充電樁jyx的距離dijyx都是確定的,按式(3)計(jì)算出電動(dòng)汽車EVi到充電樁dijyx的時(shí)間.

某一時(shí)刻,充電樁jyx經(jīng)過(guò)tyx時(shí)長(zhǎng)后,切換到空閑狀態(tài).

2.2 算法步驟

結(jié)合上述內(nèi)容,下面給出基于實(shí)時(shí)路況的電動(dòng)汽車充電調(diào)度算法,步驟如下:

Step 1.某一時(shí)刻,服務(wù)器接收到相關(guān)車輛發(fā)起的充電請(qǐng)求,并獲得該時(shí)刻各充電樁切換到空閑狀態(tài)所消耗的時(shí)長(zhǎng)tyx;

Step 2.根據(jù)發(fā)起請(qǐng)求的順序?qū)囕v進(jìn)行編號(hào),首先對(duì)車輛EVi(i=1)進(jìn)行調(diào)度;

Step 3.通過(guò)最短路徑算法,計(jì)算車輛EVi到各個(gè)充電樁的里程距離dijyx,并根據(jù)剩余電量確定車輛可抵達(dá)的充電樁.對(duì)在續(xù)航范圍內(nèi)的充電樁jyx,進(jìn)行時(shí)間開銷計(jì)算;

Step 4.車EVi完 成充電所花費(fèi)的總時(shí)長(zhǎng)為Ttotal,充電樁jyx由忙碌切換到空閑狀態(tài)的時(shí)長(zhǎng)為tyx,由式(3)計(jì)算出車EVi到充電樁jyx的行駛時(shí)間aijyx,由式(4)計(jì)算出車輛充電時(shí)間為tc;

Step 5.若aijyx>tyx,說(shuō)明充電無(wú)需排隊(duì),車EVi到該樁充電花費(fèi)總時(shí)長(zhǎng)Ttotal=tc+aijyx;

Step 6.若aijyx

Step 7.在車輛EVi續(xù)航可達(dá)的充電樁中,選擇Ttotal最小的充電樁進(jìn)行調(diào)度,即能最快完成充電服務(wù)的充電樁,完成車輛EVi的調(diào)度;

Step 8.若車EVi為本次調(diào)度的最后一輛車,則結(jié)束本次調(diào)度;否則令i=i+1,轉(zhuǎn)到Step 3.

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

使用爬蟲工具抓取實(shí)時(shí)道路數(shù)據(jù)后,存入數(shù)據(jù)庫(kù)中待用.實(shí)時(shí)道路數(shù)據(jù)如表1所示.

表1 實(shí)時(shí)道路數(shù)據(jù)

此外,根據(jù)實(shí)際數(shù)據(jù)構(gòu)建的路網(wǎng)圖包括以下內(nèi)容:17個(gè)充電站(共計(jì)222個(gè)充電樁)、90個(gè)節(jié)點(diǎn)、309 條路段.各節(jié)點(diǎn)的充電樁分布如表2所示.

表2 充電樁的數(shù)量分布

3.2 仿真結(jié)果

在路網(wǎng)內(nèi)的各個(gè)節(jié)點(diǎn)處,模擬生成100 輛待充電的電動(dòng)汽車(剩余電量為總電量的20%–40%不等).對(duì)路網(wǎng)中隨機(jī)生成的電動(dòng)汽車進(jìn)行調(diào)度,并與最短路徑算法下(即未調(diào)度情況)的結(jié)果進(jìn)行了對(duì)比,仿真結(jié)果如圖2所示.

由圖2可知,基于最短路徑算法下的100 輛電動(dòng)汽車的平均充電時(shí)間為84.1 分鐘,而基于實(shí)時(shí)路況的電動(dòng)汽車充電調(diào)度算法的平均充電時(shí)間為50.4 分鐘.圖2中一些折線重合,表明在兩種算法下該編號(hào)的車都調(diào)度到同一個(gè)充電樁進(jìn)行充電服務(wù).

圖2 兩種算法的仿真結(jié)果對(duì)比

根據(jù)調(diào)度結(jié)果可知,在同時(shí)間段的交通路況下對(duì)有充電需求的車輛使用本算法進(jìn)行調(diào)度,能夠明顯降低全局車輛的平均充電時(shí)間.

兩種調(diào)度算法下,各充電站服務(wù)車輛的具體數(shù)據(jù)如表3所示.

表3 100 輛電動(dòng)汽車的充電分布

我們使用參數(shù) ρy來(lái)描述各個(gè)充電站CSy的負(fù)載:

其中,ny表示充電站內(nèi)實(shí)際服務(wù)的電動(dòng)汽車數(shù)量;Jy表示充電站內(nèi)充電樁的數(shù)量.

如果進(jìn)行充電的電動(dòng)汽車分布越均衡,那么各充電站的負(fù)載值越接近,充電站負(fù)載值的方差越小,計(jì)算Y個(gè)充電站負(fù)載值的方差如式(6)所示:

由表3及式(6),可以計(jì)算出兩種調(diào)度算法的方差,結(jié)果如表4所示.

表4 兩種算法的方差對(duì)比

由表4可知,通過(guò)本算法對(duì)車輛進(jìn)行調(diào)度,能夠有效平衡各個(gè)充電站的負(fù)載情況,即各充電站的充電資源可以得到有效的利用.

4 總結(jié)與展望

本文基于電動(dòng)汽車的充電特點(diǎn)與需求,建立了電動(dòng)汽車充電問(wèn)題的數(shù)學(xué)模型.以提升電動(dòng)汽車用戶體驗(yàn),優(yōu)化路網(wǎng)內(nèi)電動(dòng)汽車總體充電效率為導(dǎo)向提出了調(diào)度算法,并進(jìn)行了仿真實(shí)驗(yàn).

本算法采用了實(shí)時(shí)交通數(shù)據(jù)作為調(diào)度依據(jù),使調(diào)度策略更符合實(shí)際交通狀況,避免了采用歷史數(shù)據(jù)對(duì)當(dāng)前路況進(jìn)行預(yù)測(cè)的不準(zhǔn)確性,提高了調(diào)度效率.此外,本算法將道路擁擠程度,充電站內(nèi)排隊(duì)狀況納入考慮,使調(diào)度更為準(zhǔn)確、高效,避免了通過(guò)單一計(jì)算路程來(lái)確定目的充電站的不可靠性.總的來(lái)說(shuō),本算法通過(guò)全局調(diào)度,既降低了車輛的平均充電時(shí)間,又使區(qū)域內(nèi)的充電站負(fù)載更加均衡,提高了充電站的利用率.本算法的不足之處在于,算法運(yùn)行的部分條件較為理想,接下來(lái)的研究可以將現(xiàn)實(shí)中的各類細(xì)節(jié)及不確定因素添加到算法中來(lái),使其調(diào)度更加精準(zhǔn);此外,也可針對(duì)調(diào)度過(guò)程進(jìn)行優(yōu)化,來(lái)獲得更高的調(diào)度效率.