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

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

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

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

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

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

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

1 電動(dòng)汽車充電站策略

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

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

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

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

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

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

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

2.1 電動(dòng)汽車模型

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

s0=ke0，

t0=s0/v0。

2.2 充電站模型

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

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

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

ni=wi/mi，

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

2.3 路徑模型

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

2.4 充電代價(jià)模型

充電代價(jià)模型分為2個(gè)模塊：第1個(gè)模塊是計(jì)算電動(dòng)汽車到任意充電站的最小充電代價(jià)；第2個(gè)模塊是在所有充電站中選擇具有最小充電代價(jià)的充電站，該充電站即為推薦出的充電站。

電動(dòng)汽車c0到充電站ui的充電代價(jià)定義為qi，包括電動(dòng)汽車到充電站路上的時(shí)間、電動(dòng)汽車在充電站等待充電時(shí)間、電動(dòng)汽車充電時(shí)間。

qi=t0i+niti+ti

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

t0i通過車速v0和計(jì)算電動(dòng)汽車到充電的最短路徑s0i求出，計(jì)算公式為

t0i=60s0i/v0。

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

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

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

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

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

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

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

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

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

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

int GetMixValue (intc0, intuk)

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

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

while(NOTukinS)

{

for(所有不在

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

S中且與i相鄰的點(diǎn)j)

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

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

S=S+{i};

//把i點(diǎn)添加到集合中

}

returnd[uk];

}

int SearchMostSuitableFillingStation(DAGG)

{//尋找最合適充電站，遍歷每個(gè)充電站結(jié)點(diǎn)，計(jì)算電動(dòng)汽車到該訪問結(jié)點(diǎn)的最小充電代價(jià)，并在所有充電站中選出最小代價(jià)充電站。

SqQueueq;

//存儲(chǔ)圖G的結(jié)點(diǎn)

QElemTypep;

//臨時(shí)隊(duì)列元素q

int Station ID;

//最小充電代價(jià)的充電站ID

int Value;

//保存最小充電代價(jià)的充電站

If(!q)

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

{

InitQueue(&q);

EnQueue(&q,T);

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

遍歷

{

//充電站之間的充電代價(jià)

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();

//返回最小充電代

價(jià)的充電站

4 算法分析

4.1 算法實(shí)例

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

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

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

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

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

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

4.2 復(fù)雜度分析

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

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

4.3 仿真效果分析

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

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

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

(c)充電站個(gè)數(shù)為60圖5 充電站個(gè)數(shù)不同時(shí)的總充電代價(jià)對(duì)比

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

5 結(jié)語(yǔ)

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