基于二次聚類的大規模電動汽車有序充電調度策略優化

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

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

基于二次聚類的大規模電動汽車有序充電調度策略優化

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

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

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

電動汽車;二次聚類;Dijkstra算法;充電策略;K-means算法

0 引言

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

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

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

1 數學建模

1.1 假設條件

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

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

1.2 目標函數

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

設F1表示每個充電站內分配的電動汽車數與充電樁數比值的差值,而這個差值表示每個充電站之間利用率的差異大小。其計算公式為：

(1)

(2)

其中:Sj表示充電站CSj內的電動汽車個數;?ij=0或1,1表示電動汽車EVi選擇充電站CSj充電,0表示否。

F2表示所有的電動汽車與前往充電的充電站的行駛時間之和。其計算公式為：

(3)

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

以上電動汽車與充電站之間的匹配問題的優化目標為最小化充電站內充電樁的利用率和前往充電站充電的平均行駛時間,因此考慮電動汽車行駛計劃的充電調度優化問題可建模為:

minF=α1F1+α2F2

(4)

lij≤li max

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

2 算法求解

2.1 Dijkstra最優路徑算法

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

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

圖1 基于位置相關的層次聚類示意圖

2.2 空間分配算法

2.2.1 層次聚類算法

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

(5)

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

2.2.2 K-means聚類算法

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

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

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

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

5)如果D值收斂,則return(z1,z2,…,zki)及每個類內的電動汽車集合,并進行電動汽車群Qi+1的聚類;否則轉至2)。

2.3 遺傳算法

在本文中,電動汽車類類似于單個電動汽車,因此,可以對電動汽車類進行求解。在目標函數確定之后,就是如何求解最佳方案的問題了。本文采用遺傳算法來求解,主要執行以下三步:

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

2)計算各個體的適應度。衡量字符串(染色體)好壞的指標是適應度,也就是遺傳算法的目標函數。

3)根據遺傳概率。通過選擇、交叉、突變等操作,不斷循環執行,逐漸逼近全局最優解。具體過程見文獻[8]。

3 算例仿真

3.1 算例數據

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

圖2中五角星所在的位置是已確定的充電站的所在地點,并建立如圖所示的坐標系,比例尺為:1∶0.001。可得到4個充電站的坐標分別為(0,-6.1),(5.2,2.3),(-3.3,0),(4.2,-4.4)；電動汽車的行駛區域橫坐標在(-10,10)內,縱坐標在(-10,10)內。

圖2 某一城市的道路網絡圖

考慮到電動汽車行駛軌跡在時間和空間上的隨機性,因此電動汽車的充電需求在交通網絡中也是隨機產生的,可以分布在城區的任意位置。當充電需求點不在主干道時,電動汽車會優先選擇行駛到距離最近的主干道,再行駛到充電站。因此,雖然模型中只有主干道,但在城市內部的任意位置都是可達的。如圖2所示,其中電動汽車EV1在某一時刻產生了充電需求,其在當前位置到達各個充電站的最短路徑可以通過Dijkstra算法獲得,最短距離和行駛時間可見表1。

表1 電動汽車到各個充電站的最短距離和行駛時間

由于人是群居性生物,所以在現實場景中電動汽車的分布是具有局部集中特性的,該地區環路人口分布呈圈層向外拓展,即由二、三環內向四環外聚集。根據2014年人口抽樣調查結果顯示,二環內占總人數的6.3%,二環至三環占11.3%,三環至四環占13.2%,四環至五環占18%,五環以外占51.2%。

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

為了便于表示電動汽車的位置分布,按電動汽車橫坐標由小到大的順序對其進行了編號。

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

經過層次聚類后,各個類的中心點坐標分別為(3.0,-3.6),(2.0,2.2),(7.0,8.1),(-7.3,8.8),(-5.2,-5.8),對應的電動汽車數為20、26、15、23、16。可以看到某些類中的電動汽車的數目過大,為了避免引起充電站資源分配不均衡的問題,對其進行了二次聚類,聚類后結果見表2。

圖3 基于位置相關的100輛電動汽車的層次聚類示意圖

表2 層次聚類后各個類中心點坐標及電動汽車數量

3.2 算例結果

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

表3 兩種算法在不同車輛數時的平均充電時間和計算時間

3.3 性能分析

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

圖4 不同數量的電動汽車的充電效率

4 結語

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

為了研究電動汽車充電站選擇問題,在電動汽車的行駛速度和充電時間方面作了相關假設,與實際情況有一定的偏差,后續需要進一步根據實際情況校正現有模型。

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] 陳中, 黃學良.電動汽車規模化發展所面臨的挑戰與機遇[J]. 電氣工程學報, 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] 劉卓然, 陳健, 林凱, 等.國內外電動汽車發展現狀與趨勢[J]. 電力建設, 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] 鞠非, 楊春玉, 徐小龍, 等.基于時空約束的電動汽車充電策略[J]. 電網與清潔能源, 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] 胡澤春, 宋永華, 徐智威, 等.電動汽車接入電網的影響與利用[J]. 中國電機工程學報, 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] 田文奇, 和敬涵, 姜久春, 等.電動汽車充電負荷空間分配優化算法[J]. 電工技術學報, 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] 苗世洪, 徐浩, 錢甜甜, 等.擴展時間尺度下的電動汽車有序充電策略[J]. 中國電機工程學報, 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] 張靜, 湯奕, 陳成, 等.考慮分時電價和系統峰谷差動態約束的電動汽車有序充電策略[J]. 電網與清潔能源, 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]. 電力系統自動化, 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]. 電力自動化設備, 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] 張良, 嚴正, 馮冬涵, 等.采用兩階段優化模型的電動汽車充電站內有序充電策略[J]. 電網技術, 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] 徐智威, 胡澤春, 宋永華, 等.充電站內電動汽車有序充電策略[J]. 電力系統自動化, 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] 常方宇, 黃梅, 張維戈.分時充電價格下電動汽車有序充電引導策略[J]. 電網技術, 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] 王潤芳, 時慶濤.車輛擁堵狀態下的最優路徑規劃建模研究[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] 周悅, 賈雪松, 張東偉, 等.基于層次聚類和人工免疫的無監督結構故障分類算法[J]. 沈陽建筑大學學報(自然科學版), 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。

國家自然科學基金資助項目(61472129);國家電網公司科技項目(SGJSCZ00FZJS1600884);南京郵電大學引進人才科研啟動基金資助項目(NY213036)。

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

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.