張 潔,楊春玉,鞠 非,徐小龍

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,南京 210023; 2.國家電網(wǎng)公司 常州供電公司,江蘇 常州 213017) (*通信作者電子郵箱zhangjie@njupt.edu.cn)

基于二次聚類的大規(guī)模電動(dòng)汽車有序充電調(diào)度策略優(yōu)化

張 潔1*,楊春玉1,鞠 非2,徐小龍1

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,南京 210023; 2.國家電網(wǎng)公司 常州供電公司,江蘇 常州 213017) (*通信作者電子郵箱zhangjie@njupt.edu.cn)

針對大量電動(dòng)汽車無序充電造成的充電站利用率不均衡問題,提出一種大規(guī)模電動(dòng)汽車有序充電調(diào)度策略。首先,以電動(dòng)汽車充電需求的位置為聚類指標(biāo),借助歸一化相似度進(jìn)行層次聚類和基于K-means算法的二次劃分,以實(shí)現(xiàn)屬性相似的電動(dòng)汽車的匯聚。進(jìn)一步地,通過Dijkstra算法獲取電動(dòng)汽車到達(dá)各個(gè)充電站的最優(yōu)路徑,以充電站內(nèi)電動(dòng)汽車的均勻分配和電動(dòng)汽車充電路程最短作為目標(biāo)函數(shù),構(gòu)建了基于電動(dòng)汽車聚類的充電調(diào)度模型,通過遺傳算法求取最優(yōu)解。與未進(jìn)行電動(dòng)汽車聚類的充電調(diào)度策略進(jìn)行的仿真對比實(shí)驗(yàn)結(jié)果表明,在車輛較多時(shí)所提方法的計(jì)算時(shí)間可減少一半以上,具有較高的實(shí)用性。

電動(dòng)汽車;二次聚類;Dijkstra算法;充電策略;K-means算法

0 引言

當(dāng)前，全球面臨能源供應(yīng)趨緊和環(huán)境污染嚴(yán)重的雙重壓力，節(jié)能減排成為國家戰(zhàn)略[1-3]。與燃油汽車相比，電動(dòng)汽車依靠電力驅(qū)動(dòng)，噪聲低，能效高，無污染物排出，在節(jié)能環(huán)保方面具有明顯的優(yōu)勢，因此，世界各國都紛紛加入到電動(dòng)汽車技術(shù)研發(fā)和市場競爭中[4]。據(jù)公安部交管局統(tǒng)計(jì),截至2015年底,新能源汽車保有量達(dá)58.32萬輛,與2014年相比增長169.48%。其中,純電動(dòng)汽車保有量33.2萬輛,占新能源汽車總量的56.93%,與2014年相比增長了317.06%[5]?？梢灶A(yù)見,未來將有大量可移動(dòng)的電動(dòng)汽車充電負(fù)荷接入電網(wǎng),然而,大規(guī)模電動(dòng)汽車在時(shí)間和空間上的無序充電行為不僅可能導(dǎo)致充電站的資源利用率不均衡、電網(wǎng)局部過負(fù)荷、線路擁塞等問題,給電網(wǎng)的穩(wěn)定運(yùn)行帶來不利影響[6-7]；而且有可能使用戶的充電時(shí)間過長,影響電動(dòng)汽車用戶出行的便利性,直接影響消費(fèi)者對電動(dòng)汽車的購買行為。因此,有必要在時(shí)間和空間兩個(gè)維度上研究對電動(dòng)汽車充電負(fù)荷的分配引導(dǎo)方法,實(shí)現(xiàn)對電動(dòng)汽車這一移動(dòng)負(fù)荷的優(yōu)化調(diào)度。

在電動(dòng)汽車充電優(yōu)化控制方面,國內(nèi)外學(xué)者已經(jīng)開展了相關(guān)研究。文獻(xiàn)[8]提出使用智能調(diào)度系統(tǒng)通過估計(jì)電動(dòng)汽車在每個(gè)充電站的充電等待時(shí)間,選擇充電時(shí)間最短的充電站作為最佳充電選擇。文獻(xiàn)[5]針對單個(gè)電動(dòng)汽車行駛過程中的充電需求在時(shí)間和空間上的隨機(jī)性問題,充分考慮電動(dòng)汽車往返充電站行駛時(shí)長、站內(nèi)排隊(duì)等待時(shí)間和電動(dòng)汽車充電過程的充電行為總用時(shí)最短,提出了一種基于時(shí)空約束的電動(dòng)汽車最佳充電選擇策略,該策略可以使所有的電動(dòng)汽車在最短的時(shí)間內(nèi)完成充電服務(wù)。文獻(xiàn)[9]以充電負(fù)荷均勻分配和充電時(shí)間、路程最少為目標(biāo),分別采用粒子群算法和遺傳算法求解。仿真結(jié)果表明,遺傳算法在車輛較多時(shí)的性能明顯優(yōu)于粒子群算法,有效地降低了問題的維數(shù),提高了計(jì)算速度。也有文獻(xiàn)以最小化系統(tǒng)的能量損耗[10]、減少系統(tǒng)負(fù)荷峰谷差[11-12]、降低電池?fù)p耗[13]、減小電壓波動(dòng)[14]、充電站收益[15-17]等為目標(biāo),對電動(dòng)汽車有序充電進(jìn)行優(yōu)化。

從以上文獻(xiàn)可以看出,目前對電動(dòng)汽車充電策略的研究多是從單個(gè)電動(dòng)汽車角度出發(fā),而隨著全球?qū)﹄妱?dòng)汽車的關(guān)注熱度的提高,未來電動(dòng)汽車的數(shù)量將是極大的。如果以單個(gè)電動(dòng)汽車為研究對象,其計(jì)算量會(huì)很大,計(jì)算時(shí)間也會(huì)急劇增加。因此,本文考慮從整個(gè)電動(dòng)汽車群出發(fā),通過層次聚類和基于K-means的二次劃分,得到多個(gè)電動(dòng)汽車群,然后使用遺傳算法求解,并將其與文獻(xiàn)[8]中的求解方法進(jìn)行對比,分析了兩種方法的優(yōu)化性能。

1 數(shù)學(xué)建模

1.1 假設(shè)條件

1)充電站。將某區(qū)域內(nèi)位置上相近的分散充電樁視為一個(gè)虛擬充電站,充電站內(nèi)有若干充電樁接有充電頭可供充電,不區(qū)分快慢充的時(shí)間影響。

2)待充電車輛。區(qū)域內(nèi)某時(shí)刻共有待充電汽車N輛,假設(shè)不考慮剩余電量和車輛類型的影響,所有的電動(dòng)汽車的充電時(shí)間是電池容量從20%充至100%所用時(shí)間。

1.2 目標(biāo)函數(shù)

設(shè)電動(dòng)汽車總數(shù)為M,用EVi(i=1,2,…,M)表示電動(dòng)汽車;充電站總數(shù)為N,使用CSj(j=1,2,…,N)表示充電站,每個(gè)站內(nèi)的充電樁個(gè)數(shù)表示為hj(j=1,2,…,N)。

設(shè)F1表示每個(gè)充電站內(nèi)分配的電動(dòng)汽車數(shù)與充電樁數(shù)比值的差值,而這個(gè)差值表示每個(gè)充電站之間利用率的差異大小。其計(jì)算公式為：

(1)

(2)

其中:Sj表示充電站CSj內(nèi)的電動(dòng)汽車個(gè)數(shù);?ij=0或1,1表示電動(dòng)汽車EVi選擇充電站CSj充電,0表示否。

F2表示所有的電動(dòng)汽車與前往充電的充電站的行駛時(shí)間之和。其計(jì)算公式為：

(3)

其中:lij表示電動(dòng)汽車EVi到充電站CSj的最優(yōu)路徑距離；vEVi為電動(dòng)汽車EVi的平均行駛速度。

以上電動(dòng)汽車與充電站之間的匹配問題的優(yōu)化目標(biāo)為最小化充電站內(nèi)充電樁的利用率和前往充電站充電的平均行駛時(shí)間,因此考慮電動(dòng)汽車行駛計(jì)劃的充電調(diào)度優(yōu)化問題可建模為:

minF=α1F1+α2F2

(4)

lij≤li max

其中:α1,α2(α≥0)是平衡因子。每輛電動(dòng)汽車每次能且僅能選擇一個(gè)充電站充電。由于車輛剩余電量不足、交通阻塞、電動(dòng)汽車用戶主觀意愿造成的電動(dòng)汽車的可行駛的路程最大值為li max。

2 算法求解

2.1 Dijkstra最優(yōu)路徑算法

電動(dòng)汽車到充電站的最優(yōu)路徑距離采用Dijkstra算法獲取,迪杰斯特拉提出了按路徑長度的非遞減次序逐一產(chǎn)生最短路徑的算法:首先求得長度最短的一條路徑,再求得長度次短的一條路徑,以此類推,直到從源點(diǎn)到其他所有頂點(diǎn)之間的最短路徑都已求得為止。該算法是一種計(jì)算兩點(diǎn)之間最短路徑準(zhǔn)確率非常高的經(jīng)典算法,而且最重要的是,它可以搜索到從起點(diǎn)到所有路網(wǎng)中的其他節(jié)點(diǎn)的最短路徑。

Dijkstra算法的具體做法是:設(shè)集合V為所有點(diǎn)的集合，集合S存放已經(jīng)求得最短路徑的終點(diǎn),則V-S為尚未求得最短路徑的終點(diǎn)。初始狀態(tài)時(shí),集合S中只有一個(gè)源點(diǎn),設(shè)為頂點(diǎn)v0。首先產(chǎn)生從源點(diǎn)v0到它自身的路徑,其長度為0,將v0加入S;算法的每一步上,按照最短路徑值的非遞減次序,產(chǎn)生下一條最短路徑,并將該路徑的終點(diǎn)加入S;直到獲取到的終點(diǎn)是所要求的頂點(diǎn)時(shí),停止搜索,就可得到最短路徑。

圖1 基于位置相關(guān)的層次聚類示意圖

2.2 空間分配算法

2.2.1 層次聚類算法

凝聚型層次聚類通過逐步將距離最小的一對類合并形成評價(jià)圖,利用L方法確定子簇?cái)?shù)目,即在評價(jià)圖中利用兩條直線來逼近左右兩個(gè)區(qū)域的數(shù)據(jù)點(diǎn),這兩個(gè)直線的交叉點(diǎn)對應(yīng)x軸的最近整數(shù)值就是最佳的子簇?cái)?shù)目[19]。隨機(jī)生成的10個(gè)數(shù)據(jù)點(diǎn)所在的分布如圖1(a)所示,通過凝聚型層次聚類,每步將聚類距離最小的那一對類合并成一個(gè)新的簇。計(jì)算聚類距離間距的計(jì)算方法如下:

(5)

其中:|loc-loc′|分別是簇Ci與Cj中的點(diǎn)loc與loc′之間的距離；numi是簇Ci中對象的數(shù)目。逐步進(jìn)行,形成評價(jià)圖如圖1(b)所示。由L方法確定最佳的子簇?cái)?shù)目,即為模式K。這里K=3,很顯然符合圖1(a)中數(shù)據(jù)分布情況。

2.2.2 K-means聚類算法

但是,在層次聚類之后可能存在電動(dòng)汽車群間差距較大的情況,會(huì)引起有的充電站排隊(duì)時(shí)間很長的問題,因此要對其中電動(dòng)汽車數(shù)量大的類需要重新劃分。根據(jù)充電站內(nèi)的最小充電樁數(shù)量,對于數(shù)量極大的類,按照最小充電樁數(shù)進(jìn)行二次劃分。算法步驟如下:

1)假設(shè)層次聚類后獲得的類個(gè)數(shù)為K,某個(gè)電動(dòng)汽車群數(shù)量為Qi,最小充電樁數(shù)為q,則該電動(dòng)汽車群的聚類指標(biāo)為ki=?Qi/q」(i=1,2,…,K)。從電動(dòng)汽車群Qi中任選ki個(gè)樣本作為初始聚類中心(z1,z2,…,zki)。

2)對電動(dòng)汽車群Qi中每個(gè)樣本xi找到離它最近的聚類中心zq,并將其分配到zq所表明的類uq。

3)采取平均的方法計(jì)算重新分類后的各類心。

5)如果D值收斂,則return(z1,z2,…,zki)及每個(gè)類內(nèi)的電動(dòng)汽車集合,并進(jìn)行電動(dòng)汽車群Qi+1的聚類;否則轉(zhuǎn)至2)。

2.3 遺傳算法

在本文中,電動(dòng)汽車類類似于單個(gè)電動(dòng)汽車,因此,可以對電動(dòng)汽車類進(jìn)行求解。在目標(biāo)函數(shù)確定之后,就是如何求解最佳方案的問題了。本文采用遺傳算法來求解,主要執(zhí)行以下三步:

1)建立初始群體。其中染色體上的基因表示電動(dòng)汽車類選擇的充電站類型,比如,有8個(gè)電動(dòng)汽車群,4個(gè)充電站,則染色體可以表示為12341234或者43214321。

2)計(jì)算各個(gè)體的適應(yīng)度。衡量字符串(染色體)好壞的指標(biāo)是適應(yīng)度,也就是遺傳算法的目標(biāo)函數(shù)。

3)根據(jù)遺傳概率。通過選擇、交叉、突變等操作,不斷循環(huán)執(zhí)行,逐漸逼近全局最優(yōu)解。具體過程見文獻(xiàn)[8]。

3 算例仿真

3.1 算例數(shù)據(jù)

考慮到電動(dòng)汽車?yán)m(xù)航里程的限制,一般只在城市內(nèi)部使用,因此本文所用的算例路網(wǎng)是以某城市道路網(wǎng)絡(luò)圖為例,如圖2所示,為了增加模型的有效性,只選取了該城市的主干道。假設(shè)不考慮剩余電量和車輛類型的影響,所有的電動(dòng)汽車的充電時(shí)間是電池容量從20%至100%所用時(shí)間;假設(shè)不考慮道路交通狀況的影響,所有電動(dòng)汽車的平均行駛速度相同為60 km/h;充電站內(nèi)的充電樁數(shù)分別為qj=10,12,15,17(j=1,2,3,4)。平衡因子取α1=0.6,α2=0.4。

圖2中五角星所在的位置是已確定的充電站的所在地點(diǎn),并建立如圖所示的坐標(biāo)系,比例尺為:1∶0.001?？傻玫?個(gè)充電站的坐標(biāo)分別為(0,-6.1),(5.2,2.3),(-3.3,0),(4.2,-4.4)；電動(dòng)汽車的行駛區(qū)域橫坐標(biāo)在(-10,10)內(nèi),縱坐標(biāo)在(-10,10)內(nèi)。

圖2 某一城市的道路網(wǎng)絡(luò)圖

考慮到電動(dòng)汽車行駛軌跡在時(shí)間和空間上的隨機(jī)性,因此電動(dòng)汽車的充電需求在交通網(wǎng)絡(luò)中也是隨機(jī)產(chǎn)生的,可以分布在城區(qū)的任意位置。當(dāng)充電需求點(diǎn)不在主干道時(shí),電動(dòng)汽車會(huì)優(yōu)先選擇行駛到距離最近的主干道,再行駛到充電站。因此,雖然模型中只有主干道,但在城市內(nèi)部的任意位置都是可達(dá)的。如圖2所示,其中電動(dòng)汽車EV1在某一時(shí)刻產(chǎn)生了充電需求,其在當(dāng)前位置到達(dá)各個(gè)充電站的最短路徑可以通過Dijkstra算法獲得,最短距離和行駛時(shí)間可見表1。

表1 電動(dòng)汽車到各個(gè)充電站的最短距離和行駛時(shí)間

由于人是群居性生物,所以在現(xiàn)實(shí)場景中電動(dòng)汽車的分布是具有局部集中特性的,該地區(qū)環(huán)路人口分布呈圈層向外拓展,即由二、三環(huán)內(nèi)向四環(huán)外聚集。根據(jù)2014年人口抽樣調(diào)查結(jié)果顯示,二環(huán)內(nèi)占總?cè)藬?shù)的6.3%,二環(huán)至三環(huán)占11.3%,三環(huán)至四環(huán)占13.2%,四環(huán)至五環(huán)占18%,五環(huán)以外占51.2%。

本文為了模擬可能存在的電動(dòng)汽車分布特性,根據(jù)人口占比情況,通過Matlab仿真模擬出區(qū)域內(nèi)隨機(jī)分布的100輛電動(dòng)汽車的位置分布圖,如圖3(a)所示(黑點(diǎn)表示區(qū)域內(nèi)隨機(jī)分布的電動(dòng)汽車)。

為了便于表示電動(dòng)汽車的位置分布,按電動(dòng)汽車橫坐標(biāo)由小到大的順序?qū)ζ溥M(jìn)行了編號(hào)。

由圖3(b)可以看出,采用L方法判斷100輛隨機(jī)分布的電動(dòng)汽車子類的數(shù)目,通過兩條擬合直線相交的交點(diǎn)可以得到其最佳子簇個(gè)數(shù)為5。

經(jīng)過層次聚類后,各個(gè)類的中心點(diǎn)坐標(biāo)分別為(3.0,-3.6),(2.0,2.2),(7.0,8.1),(-7.3,8.8),(-5.2,-5.8),對應(yīng)的電動(dòng)汽車數(shù)為20、26、15、23、16?？梢钥吹侥承╊愔械碾妱?dòng)汽車的數(shù)目過大,為了避免引起充電站資源分配不均衡的問題,對其進(jìn)行了二次聚類,聚類后結(jié)果見表2。

圖3 基于位置相關(guān)的100輛電動(dòng)汽車的層次聚類示意圖

表2 層次聚類后各個(gè)類中心點(diǎn)坐標(biāo)及電動(dòng)汽車數(shù)量

3.2 算例結(jié)果

經(jīng)過迭代計(jì)算得到區(qū)域內(nèi)所有車輛在各充電站間的分配結(jié)果,以單個(gè)電動(dòng)汽車為研究對象(詳細(xì)過程可見文獻(xiàn)[8])和本文的以電動(dòng)汽車群為研究對象得到的電動(dòng)汽車選擇充電站的結(jié)果見表3。其中：以單個(gè)電動(dòng)汽車為研究對象經(jīng)過仿真得到的目標(biāo)函數(shù)F1=8.583 7、F2=2.4、F=10.983 7；本文所用方法得到的目標(biāo)函數(shù)F1=8.347 5、F2=2.3、F=10.647 5。結(jié)果表明,兩種方法得到的電動(dòng)汽車平均充電時(shí)間是差不多的,驗(yàn)證了本文算法的有效性和可行性。

表3 兩種算法在不同車輛數(shù)時(shí)的平均充電時(shí)間和計(jì)算時(shí)間

3.3 性能分析

電動(dòng)汽車充電負(fù)荷空間分配優(yōu)化問題是一個(gè)高度優(yōu)化問題,優(yōu)化算法在高維數(shù)時(shí)的計(jì)算速度決定了控制系統(tǒng)的實(shí)時(shí)性。表3給出了兩種方法在不同車輛數(shù)時(shí)的平均充電時(shí)間和計(jì)算時(shí)間。圖4給出了基于單個(gè)電動(dòng)汽車的遺傳算法求解與本文提出的基于二次聚類的大規(guī)模電動(dòng)汽車有序充電策略在不同數(shù)量的電動(dòng)汽車下的充電效率，可以明顯出本文的充電策略性能更優(yōu)。

圖4 不同數(shù)量的電動(dòng)汽車的充電效率

4 結(jié)語

傳統(tǒng)的電動(dòng)汽車充電選擇策略大多是從單個(gè)電動(dòng)汽車的角度出發(fā),但是隨著大規(guī)模電動(dòng)汽車普遍應(yīng)用,可能會(huì)增加系統(tǒng)的計(jì)算成本,也可能會(huì)導(dǎo)致電動(dòng)汽車用戶獲取最佳充電站的時(shí)間增加,從而影響用戶的出行體驗(yàn)。本文基于區(qū)域內(nèi)電動(dòng)汽車充電需求的隨機(jī)分布現(xiàn)狀,提出了一種規(guī)模化電動(dòng)汽車有序充電策略。通過對電動(dòng)汽車充電行為和充電站的利用率進(jìn)行數(shù)學(xué)建模、理論分析和數(shù)值仿真,研究表明,與對每個(gè)電動(dòng)汽車使用遺傳算法求解相比,本文所提出的電動(dòng)汽車聚類方法能夠更快地向用戶提供最佳的充電站,提高用戶的出行便利性,有利于電動(dòng)汽車的規(guī)模化發(fā)展。

為了研究電動(dòng)汽車充電站選擇問題,在電動(dòng)汽車的行駛速度和充電時(shí)間方面作了相關(guān)假設(shè),與實(shí)際情況有一定的偏差,后續(xù)需要進(jìn)一步根據(jù)實(shí)際情況校正現(xiàn)有模型。

References)

[1] GUO P, LIU P. Research on development of electric vehicles in China[C]// Proceedings of the 2010 International Conference on Future Information Technology and Management Engineering. Piscataway, NJ: IEEE, 2010: 94-96.

[2] WENTAO J, YADAN Y, LNHI K, et al. Electric vehicle: a review of network modelling and future research needs [J]. Advances in Mechanical Engineering, 2016, 8(1): 1-8.

[3] 陳中, 黃學(xué)良.電動(dòng)汽車規(guī)?；l(fā)展所面臨的挑戰(zhàn)與機(jī)遇[J]. 電氣工程學(xué)報(bào), 2015, 10(4): 35-44. (CHEN Z, HUANG X L. The challenge of scale development of electric vehicles [J]. Journal of Electrical Engineering, 2015, 10(4): 35-44.)

[4] 劉卓然, 陳健, 林凱, 等.國內(nèi)外電動(dòng)汽車發(fā)展現(xiàn)狀與趨勢[J]. 電力建設(shè), 2015, 36(7): 25-32. (LIU Z R, CHEN J, LIN K, et al. Domestic and foreign present situation and the tendency of electric vehicles [J]. Electric Power Construction, 2015, 36(7): 25-32.)

[5] 鞠非, 楊春玉, 徐小龍, 等.基于時(shí)空約束的電動(dòng)汽車充電策略[J]. 電網(wǎng)與清潔能源, 2016,32(9): 96-101. (JU F, YANG C Y, XU X L, et al. A charging strategy for electric vehicles based on spatiotemporal restriction [J]. Power System and Clean Energy, 2016, 32(9): 96-101.)

[6] HU H, LUO Q, GUO J. Electric vehicles operations oriented network and data analysis [C]// Proceedings of the 4th National Conference on Electrical, Electronics and Computer Engineering. New York: Curran Associates, 2015: 1264-1267.

[7] 胡澤春, 宋永華, 徐智威, 等.電動(dòng)汽車接入電網(wǎng)的影響與利用[J]. 中國電機(jī)工程學(xué)報(bào), 2012, 32(4): 1-10. (HU Z C, SONG Y H, XU Z W, et al. Impacts and utilization of electric vehicles integration into power systems [J]. Proceedings of the CSEE, 2012, 32(4): 1-10.)

[8] QIN H, ZHANG W. Charging scheduling with minimal waiting in a network of electric vehicles and charging stations[C]// VANET 2011: Proceedings of the Eighth ACM International Workshop on Vehicular Inter-Networking. New York: ACM, 2011: 51-60.

[9] 田文奇, 和敬涵, 姜久春, 等.電動(dòng)汽車充電負(fù)荷空間分配優(yōu)化算法[J]. 電工技術(shù)學(xué)報(bào), 2013, 28(3): 269-276. (TIAN W Q, HE J H, JIAG J C, et al. Electric vehicle charging load spatial allocation optimization algorithm [J]. Transactions of China Electrotechnical Society, 2013, 28(3): 269-276.)

[10] ESMAILI M, RAJABI M. Optimal charging of plug-in electric vehicles observing power grid constraints[J]. IET Generation, Transmission amp; Distribution, 2014, 8(4): 583-590.

[11] 苗世洪, 徐浩, 錢甜甜, 等.擴(kuò)展時(shí)間尺度下的電動(dòng)汽車有序充電策略[J]. 中國電機(jī)工程學(xué)報(bào), 2015, 35(23): 5959-5967. (MIAO S H, XU H, QIAN T T, et al. An ordered charging strategy for electric vehicles under an extended time scale [J]. Proceedings of the CSEE, 2015, 35(23): 5959-5967.)

[12] 張靜, 湯奕, 陳成, 等.考慮分時(shí)電價(jià)和系統(tǒng)峰谷差動(dòng)態(tài)約束的電動(dòng)汽車有序充電策略[J]. 電網(wǎng)與清潔能源, 2014,30(5): 79-84. (ZHANG J, TANG Y, CHEN C, et al. Coordinated charging strategy for electric vehicles considering time-of-use price and peak-valley difference dynamic constraints [J]. Power System and Clean Energy, 2014,30(5): 79-84.)

[13] 劉利兵, 劉天琪, 張濤,等.計(jì)及電池動(dòng)態(tài)損耗的電動(dòng)汽車有序充放電策略優(yōu)化[J]. 電力系統(tǒng)自動(dòng)化, 2016, 40(5):83-90. (LIU L B, LIU T Q, ZHANG T, et al. Orderly charging and discharging strategy optimization for electric vehicles considering dynamic battery-wear model [J]. Automation of Electric Power Systems, 2016, 40(5): 83-90.)

[14] 陳靜鵬, 樸龍健, 艾芊.基于改進(jìn)貪心算法的大規(guī)模電動(dòng)汽車充電行為優(yōu)化[J]. 電力自動(dòng)化設(shè)備, 2016, 36(10): 38-44. (CHEN J P, PIAO L J, AI Q. Charging optimization based on improved greedy algorithm for massive EVs [J]. Electric Power Automation Equipment, 2016, 36(10): 38-44.)

[15] 張良, 嚴(yán)正, 馮冬涵, 等.采用兩階段優(yōu)化模型的電動(dòng)汽車充電站內(nèi)有序充電策略[J]. 電網(wǎng)技術(shù), 2014, 38(4): 967-973. (ZHANG L, YAN Z, FENG D H, et al. Two-stage optimization model based coordinated charging for EV charging station [J]. Power System Technology, 2014, 38(4): 967-973.)

[16] 徐智威, 胡澤春, 宋永華, 等.充電站內(nèi)電動(dòng)汽車有序充電策略[J]. 電力系統(tǒng)自動(dòng)化, 2012, 36(11): 38-43. (XU Z W, HU Z C, SONG Y H, et al. Coordinated charging of plug-in electric vehicle in charging station [J]. Automation of Electric Power System, 2012, 36(11): 38-43.)

[17] 常方宇, 黃梅, 張維戈.分時(shí)充電價(jià)格下電動(dòng)汽車有序充電引導(dǎo)策略[J]. 電網(wǎng)技術(shù), 2016, 40(9): 2609-2615. (CHANG F Y, HUANG M, ZHANG W G. Research on coordinated charging of electric vehicles based on TOU charging price [J]. Power System Technology, 2016, 40(9): 2609-2615.)

[18] 王潤芳, 時(shí)慶濤.車輛擁堵狀態(tài)下的最優(yōu)路徑規(guī)劃建模研究[J]. 計(jì)算機(jī)仿真, 2016, 33(2): 204-206. (WANG R F, SHI Q T. Modeling research of optimal path planning in status of vehicle congestion [J]. Computer Simulation, 2016, 33(2): 204-206.)

[19] 周悅, 賈雪松, 張東偉, 等.基于層次聚類和人工免疫的無監(jiān)督結(jié)構(gòu)故障分類算法[J]. 沈陽建筑大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014(2): 374-378. (ZHOU Y, JIA X S, ZHANG D W, et al. Unsupervised structural damage classification algorithm based on hierarchical clustering and artificial immune pattern recognition[J]. Journal of Shenyang Jianzhu University (Natural Science), 2014(2): 374-378.)

Optimizationoforderedchargingstrategyforlargescaleelectricvehiclesbasedonquadraticclustering

ZHANG Jie1, YANG Chunyu1, JU Fei2,XU Xiaolong1

(1.SchoolofComputerScience,NanjingUniversityofPostsandTelecommunications,NanjingJiangsu210023,China;2.ChangzhouPowerSupplyCompany,StateGridCorporationofChina,ChangzhouJiangsu213017,China)

Aiming at the problem of unbalanced utilization rate distribution of charging station caused by disordered charging for a large number of electric vehicles, an orderly charging strategy for electric vehicles was proposed. Firstly, the location of the electric vehicle’s charging demand was clustered, and the hierarchical clustering and quadratic division based onK-means were used to achieve the convergence of electric vehicles with similar properties. Furthermore, the optimized path to charging station was determined by Dijkstra algorithm, and by using the even distribution and the shortest charging distance of electric vehicles as objectives functions, the charging scheduling model based on electric vehicle clustering was constructed, and the genetic algorithm was used to solve the problem. The simulation results show that compared with the charging scheduling strategy without clustering of electric vehicles, the computation time of the proposed method can be reduced by more than a half for large scale vehicles, and it has higher practicability.

electric vehicle; quadratic clustering; Dijkstra algorithm; charging strategy;K-means algorithm

2017- 05- 11;

2017- 07- 20。

國家自然科學(xué)基金資助項(xiàng)目(61472129);國家電網(wǎng)公司科技項(xiàng)目(SGJSCZ00FZJS1600884);南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目(NY213036)。

張潔(1981—),女,江蘇沛縣人,高級工程師,博士,主要研究方向:電動(dòng)汽車與電網(wǎng)互動(dòng)、電力信息集成; 楊春玉(1992—),女,安徽安慶人,碩士研究生,主要研究方向:電動(dòng)汽車充電站規(guī)劃、電動(dòng)汽車充電站運(yùn)行; 鞠非(1977—),男,江蘇常州人,高級經(jīng)濟(jì)師,主要研究方向:電力系統(tǒng)的運(yùn)行; 徐小龍(1977—),男,江蘇鹽城人，教授，博士，主要研究方向:電力系統(tǒng)運(yùn)行、信息網(wǎng)絡(luò)、分布式計(jì)算、信息安全。

1001- 9081(2017)10- 2978- 05

10.11772/j.issn.1001- 9081.2017.10.2978

TM74

A

This work is partially supported by the National Natural Science Foundation of China (61472129), the State Grid Corporation of China (SGJSCZ00FZJS1600884), NUPTSFC (NY2130306).

ZHANGJie, born in 1981, Ph. D., senior engineer. Her research interests include electric car interaction with grid, electric power information integration.

YANGChunyu, born in 1992, M. S. candidate. Her research interests include electric car charging station planning, electric car charging station operation.

JUFei, born in 1977, senior economist. His research interests include power system operation.

XUXiaolong, born in 1977, Ph. D., professor. His research interests include power system operation, information network, distributed computing, information security.