物聯(lián)網(wǎng)環(huán)境下基于圖模型尋找最優(yōu)充電站的方法

趙衍恒, 高洪雨，2，李榮凱，王文明，王 磊，2

(1. 國家電網(wǎng)有限公司技術(shù)學(xué)院分公司網(wǎng)絡(luò)大學(xué)運管中心，山東濟南250002； 2. 山東大學(xué)電氣工程學(xué)院，山東濟南250002)

隨著我國經(jīng)濟的快速發(fā)展，汽車產(chǎn)業(yè)增長迅速，由此帶來的能源消耗和環(huán)境污染問題越來越嚴(yán)重。當(dāng)前，汽車對石油的消耗總量占所有石油消耗量的60%[1]，新能源汽車將是降低石油消耗、改善環(huán)境污染現(xiàn)狀的有效方式以及未來汽車行業(yè)發(fā)展的一個大趨勢[2]。新能源汽車主要包括電動汽車、燃料電池汽車等，到2025年，新能源汽車數(shù)量可能達(dá)到5 000萬～8 000萬輛[3]。未來電動汽車的充電設(shè)施將遍布在住宅小區(qū)、停車場、街頭或者公共區(qū)域，對電動汽車進(jìn)行常規(guī)充電，同時在固定地點配置交流充電樁和直流充電機，為電動汽車進(jìn)行快速充電服務(wù)。

目前，電動汽車充電依然存在明顯的問題，如常規(guī)充電方式充電時間長[4]，快速充電對電網(wǎng)的沖擊明顯[5]； 充電站從交流配電網(wǎng)獲取電能，增加電網(wǎng)負(fù)擔(dān)，獲取電能的方式單一[6-7]。隨著電動汽車的普及，未來需要充電的汽車越來越多，容易出現(xiàn)某些熱門充電站電動汽車充電等待時間過長的現(xiàn)象，不同充電站的負(fù)載嚴(yán)重不平衡問題也會越來越嚴(yán)重，因此，充電調(diào)度問題是電動汽車領(lǐng)域的一個研究熱點。

一方面，電動汽車充電調(diào)度方面的研究集中于電動汽車在尋找充電站的路徑規(guī)劃。黃晶等[8]提出了建立下一目的地導(dǎo)向的電動汽車充電引導(dǎo)策略，實現(xiàn)了充電站設(shè)備利用率分布均衡、時間成本最小的目標(biāo)。嚴(yán)弈遙等[9]基于Dijkstra最短路徑算法，提出電動汽車充電路徑規(guī)劃方法，在一定程度上解決了電動汽車充電造成的配電網(wǎng)節(jié)點壓降過大、線路功率損耗過多問題。Liu等[10]利用充電站電價信息及交通信息，提出一種減少用戶行駛時間及充電成本的路徑優(yōu)化模型。楊洪明等[11]基于實時交通信息，構(gòu)建電動汽車充電路徑優(yōu)化模型，實現(xiàn)了用戶出行總成本最小。Wager等[12]對電動汽車在外部因素不同情況下的能耗率進(jìn)行試驗研究，發(fā)現(xiàn)電動汽車耗電量會隨著路況等因素發(fā)生變化。以上研究對本文中提出的定位最優(yōu)充電站的路徑查詢提供了解決思路。

另一方面，電動汽車充電研究集中在充電站有序充電調(diào)度。蒲勇健[13]通過基于物聯(lián)網(wǎng)協(xié)調(diào)有序預(yù)約快速充電的背景，證明了一個最大化配對數(shù)量的存在性定理。陸堅毅等[14]在實時電價和每個充電任務(wù)時間連續(xù)的假設(shè)下，提出單親遺傳算法混合動態(tài)規(guī)劃兩階段常規(guī)充電調(diào)度算法，有效地實現(xiàn)了電樁負(fù)載均衡和降低電費成本。康振南等[15]提出對電動汽車分層分區(qū)調(diào)度的方法，實現(xiàn)對電動汽車有序充放電控制，保證了電網(wǎng)經(jīng)濟運行和用戶的充電費用最小。曾鳴等[16]根據(jù)用戶的行駛計劃和各充電站的電量需求建立用戶與充電站之間的多對一匹配模型，有效地提高了系統(tǒng)總效用和用戶滿意度。李銘洋[17]、符云輝等[18]提出基于充電站和用戶實現(xiàn)雙邊滿意度的算法，改善了用戶的出行體驗，提高了充電站的收益。以上研究對本文中的定位最優(yōu)充電站方法中的預(yù)約充電提供了解決思路。

基于物聯(lián)網(wǎng)的電動汽車充電調(diào)度問題在本質(zhì)上涉及到用戶側(cè)和電網(wǎng)服務(wù)側(cè)2個方面的優(yōu)化問題，除了實現(xiàn)電網(wǎng)側(cè)的優(yōu)化外，用戶側(cè)的優(yōu)化也需要實現(xiàn)。隨著通信網(wǎng)絡(luò)的不斷發(fā)展，電動汽車車載監(jiān)控系統(tǒng)和信息采集系統(tǒng)逐步形成常規(guī)配置，但亟需一種新的方法，在不改變充電站基礎(chǔ)設(shè)施的前提下，從用戶側(cè)需求出發(fā)，考慮電動汽車的續(xù)航里程、到達(dá)充電站的行駛距離和時間、充電前排隊等待時間和充電時間作為充電代價，為電動車智能推薦綜合目標(biāo)最優(yōu)的充電站，并達(dá)到各個充電站負(fù)載平衡。本文中將對用戶側(cè)和電網(wǎng)服務(wù)側(cè)2個方面的優(yōu)化進(jìn)行研究，實現(xiàn)電動汽車充電業(yè)務(wù)的多方協(xié)同發(fā)展。

1 電動汽車充電站策略

在物聯(lián)網(wǎng)環(huán)境下，電動汽車通過自身的通信模塊，連接車載導(dǎo)航或者手機等通信設(shè)備，通信設(shè)備將電動車自身的剩余電量、車速、地理位置等信息發(fā)送到數(shù)據(jù)調(diào)度中心，同時數(shù)據(jù)調(diào)度中心訪問附近充電站的位置及充電站充電設(shè)施的使用情況。電動車作為根節(jié)點，各個充電站作為子節(jié)點，通過定位電動車自身位置和附近一定范圍內(nèi)充電站的地理位置，將電動汽車與充電站之間的關(guān)系抽象為圖模型，利用充電調(diào)度算法，動態(tài)為電動汽車推薦最小充電代價的充電站。圖1所示為基于物聯(lián)網(wǎng)的電動汽車通信方式。

2 充電調(diào)度問題模型

充電調(diào)度問題由電動汽車模型、充電站模型、路徑模型和充電代價模型4個部分構(gòu)成，本文中使用的主要參數(shù)如表1所示。

在電動汽車尋找最優(yōu)充電代價的充電站過程中，電動汽車作為根節(jié)點，一定距離范圍內(nèi)的所有的充電站作為子節(jié)點，電動汽車和充電站之間以及各相鄰充電站之間連接的路徑作為圖的邊，路徑的距離作為邊的長度。

CAN—控制器局域網(wǎng)絡(luò)。圖1 基于物聯(lián)網(wǎng)的電動汽車通信方式

表1 本文中使用的主要參數(shù)

圖2(a)為電動汽車與充電站布局示意圖。圖2(a)抽象出來的圖模型增加一個虛擬結(jié)點u0構(gòu)成拓?fù)鋱DG，如圖2(b)所示。G是一個帶權(quán)圖，定義G=(C,U,E)，其中C為所有待充電電動汽車的集合，C={c0}，c0作為G的根結(jié)點；結(jié)點集合U用于表示充電站集合，U={ui|0≤i≤n}，u0為輔助虛擬結(jié)束結(jié)點，ui(0

2.1 電動汽車模型

定義電動汽車c0自身剩余電量為e0，電池充電功率為p0，行駛速度為v0，可繼續(xù)行駛里程為s0，電動汽車可繼續(xù)行駛最長時間為t0，每度電可續(xù)航距離為k,

s0=ke0，

t0=s0/v0。

2.2 充電站模型

定義充電站ui的充電樁個數(shù)為mi，其中空閑充電樁個數(shù)為pi，等待充電的汽車輛數(shù)為wi，單樁

(a)電動汽車與充電站布局

c0—待充電電動汽車； u1—u8—搜索范圍內(nèi)的充電站； u0—虛擬結(jié)點，輔助構(gòu)成有向無環(huán)圖； 線上數(shù)字—行駛距離。(b)帶權(quán)圖G模型圖2 電動汽車與充電站布局及其帶權(quán)圖G模型

ni=wi/mi，

等待率為ni, 每輛汽車允許最長充電時間為ti。結(jié)點ui=(ti,Ωi)，其中Ωi為電動汽車到該充電站可能途經(jīng)的充電站，Ωi∈U，結(jié)點內(nèi)部數(shù)字為充電站編號。當(dāng)pi大于0時，ni為0。

2.3 路徑模型

有向邊集合E用于表示從電動汽車到充電站以及充電站之間的路徑集合，E={eij|0≤i≤n, 0≤j≤n}，當(dāng)i為0時，eij表示電動汽車到充電站j的路徑；當(dāng)i不為0時，有向邊集合eij的方向表示電動汽車的行駛方向，即電動汽車經(jīng)過充電站i到充電站j，eij的值表示充電站i直接到達(dá)充電站j的距離，圖2(b)給出了一個具有8個充電站抽象圖，例如充電站1到充電站3的直線距離為8 km，中間不經(jīng)過其他充電站。

2.4 充電代價模型

充電代價模型分為2個模塊：第1個模塊是計算電動汽車到任意充電站的最小充電代價；第2個模塊是在所有充電站中選擇具有最小充電代價的充電站，該充電站即為推薦出的充電站。

電動汽車c0到充電站ui的充電代價定義為qi，包括電動汽車到充電站路上的時間、電動汽車在充電站等待充電時間、電動汽車充電時間。

qi=t0i+niti+ti

式中：t0i為電動汽車c0通過最短路程到達(dá)ui的時間；niti為到達(dá)充電站i后所需平均等待時間。

t0i通過車速v0和計算電動汽車到充電的最短路徑s0i求出，計算公式為

t0i=60s0i/v0。

3 充電調(diào)度算法

物聯(lián)網(wǎng)環(huán)境下基于定位預(yù)約最優(yōu)充電站的實現(xiàn)方法，包括將運動中的電動汽車、一定范圍內(nèi)的充電站以及電動汽車到充電站和充電站之間的路徑，抽象為充電站拓?fù)淠Ｐ蛶?quán)圖G，如圖2(b)所示。對帶權(quán)圖G模型使用遍歷算法及最短路徑算法，對每一輛能到達(dá)的充電站的汽車進(jìn)行充電代價評估，并為電動汽車用戶動態(tài)推薦并預(yù)約代價最小的充電站?；趫D模型算法尋找最優(yōu)充電站的流程如圖3所示。

基于圖模型算法尋找最優(yōu)充電站調(diào)度算法中提出了計算電動汽車到任意充電站的最小代價的算法GetMixValue，思路如下： 1)計算電動汽車到充電站行駛時間代價； 2)計算電動汽車在充電站等待充電時間代價； 3)計算電動汽車充電時間代價與前2步代價之和。

該算法使用的是貪心算法，先把充電站U分成S和T共2個組，定義S為已求出最低充電代價的充電站的集合，T=U-S為尚未確定最低充電代價的充電站集合。

將T中結(jié)點按最小充電代價遞增的次序加入到S中，c0到T中充電站uk的最小充電代價，是c0到uk的直接路徑上的充電代價或是從c0路經(jīng)S中其他充電站到uk的充電代價之和。

求最小充電代價步驟如下：初始時令S={c0},T={其余結(jié)點}；若存在電動汽車直接到達(dá)充電站ui，即存在〈c0,ui〉[8]有值，則T中結(jié)點對應(yīng)的最小代價值為〈c0,ui〉邊上的行駛距離代價與充電站ui內(nèi)的充電時間代價之和(下文統(tǒng)稱充電代價之和)；若不存在〈c0,ui〉，則設(shè)置為無窮大值[10]。

DAG—有向無環(huán)圖。圖3 基于圖模型算法尋找最優(yōu)充電站的流程

從T中選取一個充電代價之和為最小的充電站w，加入S，對T中結(jié)點的代價值進(jìn)行修改。若加進(jìn)w作為中間結(jié)點(因為電動汽車不在w充電，只是路過，所以不計算在w的充電代價)，從c0到ui的充電代價比不加w的充電代價要小，則修改此代價值(上面2個并列for循環(huán)，使用最小充電代價值更新)。

重復(fù)上述步驟，直到S中包含所有結(jié)點，即S=U為止。

為電動汽車用戶動態(tài)推薦并預(yù)約代價最小的充電站，是將計算出的每一個充電站的充電代價Value進(jìn)行性能排序，得到qi最小值的充電站即為推薦預(yù)約充電站。獲取c0到uk最小充電代價算法偽代碼如下。

int GetMixValue (intc0, intuk)

{//計算c0到uk間最小充電代價，并返回充電路徑初始化S={c0}；

d[s]=0;//其余d值為正無窮大，d值為充電代價

while(NOTukinS)

{

for(所有不在

//取出不在S中的最小的d[i]

S中且與i相鄰的點j)

if(d[j]>d[i]+cost[i][j] )

d[j]=d[i]+cost[i][j]+cost[j];

S=S+{i};

//把i點添加到集合中

}

returnd[uk];

}

int SearchMostSuitableFillingStation(DAGG)

{//尋找最合適充電站，遍歷每個充電站結(jié)點，計算電動汽車到該訪問結(jié)點的最小充電代價，并在所有充電站中選出最小代價充電站。

SqQueueq;

//存儲圖G的結(jié)點

QElemTypep;

//臨時隊列元素q

int Station ID;

//最小充電代價的充電站ID

int Value;

//保存最小充電代價的充電站

If(!q)

//如果隊列不為空，則繼續(xù)執(zhí)行

{

InitQueue(&q);

EnQueue(&q,T);

while(!QueueEmpty(q))//對所有充電站進(jìn)行

遍歷

{

//充電站之間的充電代價

De Queue(&q,&p);

Value=GetMixValue(c0,p);

if(p->lchild!=NULL)

EnQueue(&q,p->lchild);

if(p->rchild!=NULL)

EnQueue(&q,p->rchild);

}

}

}

StationID=GetMixCostStation();

//返回最小充電代

價的充電站

4 算法分析

4.1 算法實例

以圖2所示的充電站為實例，將其抽象為有向無環(huán)圖(DAG)，如圖4所示。在電動汽車搜索范圍內(nèi)共有8個充電站，即u1—u8，在DAG圖中，c0為電動汽車，u0作為虛擬結(jié)束節(jié)點，每2個充電站之間路徑上的數(shù)據(jù)為2個充電站之間的行駛時間，每個充電站節(jié)點括號內(nèi)的數(shù)據(jù)為在此充電站等待充電及充電時間之和。如果電動汽車c0到充電站u1充電，最短行駛時間為5 min，充電等待及充電時間為125 min，總的充電代價為130 min；如果c0到u2充電，最短路徑中間途徑u1，則行駛時間為12 min，充電等待及充電時間130 min，總的充電代價則為142 min。

c0—待充電電動汽車； u1—u8—搜索范圍內(nèi)的充電站；u0—虛擬結(jié)點，輔助構(gòu)成有向無環(huán)圖； 線上數(shù)字—行駛距離； 括號內(nèi)數(shù)字—等待時間與充電時間之和。圖4 充電站抽象帶權(quán)有向無環(huán)圖

查找最優(yōu)充電站的算法為對電動汽車搜索范圍內(nèi)的所有充電站進(jìn)行遍歷，計算電動汽車到每個充電站的最小充電代價，然后在所有充電代價中，選擇充電代價最小的充電站作為推薦充電站。表2所示為圖4中DAG的鄰接矩陣表示。如果2個充電站之間有路徑直接相連，則〈ui,uj〉的值為2個充電站之間的行駛時間，若2個充電站之間沒有路徑直接相連，則〈ui,uj〉的值為無窮大[12]?！磚i,ui〉的值為電動汽車在充電站的等待時間和充電時間之和。

表3所示為使用基于圖模型算法尋找最優(yōu)充電站的計算過程和結(jié)果。第1列為DAG圖中代表充電站的各個節(jié)點，第2列數(shù)據(jù)為充電汽車使用最短路徑算法計算的到達(dá)充電站的最短時間，第3列數(shù)據(jù)為行駛路徑，第4列為充電汽車在充電站需要等&待和充電的時間，最后一列數(shù)據(jù)為電動汽車如果在該充電站充電所需要的充電時間代價。由表中的計算結(jié)果可知，充電站到u1有最短的行駛路徑，但是到u4具有最小的充電代價，且行駛路徑為u1→u2→u4。

表2 抽象帶權(quán)有向無環(huán)圖的鄰接矩陣表示

表3 基于圖算法的計算過程和結(jié)果

4.2 復(fù)雜度分析

設(shè)定待充電電動汽車搜索范圍內(nèi)的所有充電站數(shù)量為n,查找最優(yōu)充電站的算法的時間復(fù)雜度則為O(n2)。

查找最優(yōu)充電站的算法首先對所有充點站進(jìn)行隊列遍歷，時間復(fù)雜度為O(n)，然后嵌套使用電動汽車到充電站最小充電代價的算法，最終得出計算最優(yōu)充電站的時間復(fù)雜度為O(n2)。

4.3 仿真效果分析

本文中分別設(shè)計電動汽車搜索范圍內(nèi)的充電站個數(shù)為30、45、60進(jìn)行仿真模擬。本算法基于物聯(lián)網(wǎng)環(huán)境，可即時獲得電動汽車搜索范圍內(nèi)的充電站的到達(dá)時間和充電等待時間，實驗環(huán)境對每座充電站的到達(dá)時間和充電等待時間采用蒙特卡羅法生成，到達(dá)充電站的時間為5～50 min，充電等待時間為40～160 min。將查找最優(yōu)充電站算法和最近充電站算法以及最短等待時間的充電代價進(jìn)行對比，結(jié)果如圖5所示。

(a)充電站個數(shù)為30

(b)充電站個數(shù)為45

(c)充電站個數(shù)為60圖5 充電站個數(shù)不同時的總充電代價對比

從圖5中可以看出： 當(dāng)充電站個數(shù)為30時，最優(yōu)充電站所花費的充電代價最小，為最短等待時間的充電代價算法的85.5%，為最近充電站算法的67%； 當(dāng)充電站個數(shù)為45時，最優(yōu)充電站所花費的充電代價為最短等待時間的充電代價算法的75.9%，為最近充電站算法的38.2%； 當(dāng)充電站個數(shù)為60時，最優(yōu)充電站所花費的充電代價為最短等待時間的充電代價算法的78%，為最近充電站算法的61.3%。由此可以得出結(jié)論，物聯(lián)網(wǎng)環(huán)境下基于圖模型的尋找最優(yōu)充電站算法能以最小的充電代價推薦充電站，最大程度地節(jié)省用戶充電代價。

5 結(jié)語

通過物聯(lián)網(wǎng)環(huán)境下基于圖模型算法尋找最優(yōu)充電站的方法，從用戶側(cè)需求出發(fā)，為電動汽車用戶推薦定位預(yù)約充電的最省時充電站，同時也達(dá)到平衡各個充電站負(fù)載的作用。下一步，該算法將在原有思路的基礎(chǔ)上，將充電功率、充電計費和充電時間結(jié)合，對尋找充電站算法進(jìn)行優(yōu)化，以達(dá)到進(jìn)一步服務(wù)用戶和平衡充電站負(fù)載的目標(biāo)。