基于Voronoi圖和改進引力搜索算法的電動汽車充電站選址定容

趙炳耀，陳璟華，郭經(jīng)韜，陳友鵬，張兆軒

（1. 廣東工業(yè)大學 自動化學院，廣東 廣州 510006；2. 中國能源建設(shè)集團 廣東省電力設(shè)計研究院有限公司，廣東 廣州 510663）

隨著日益嚴峻的環(huán)境污染與化石能源問題，世界各國大力推進汽車電氣化，把禁售燃油汽車提上日程，如荷蘭、挪威禁售時間是2025年，印度是2030年，法國是2040年。我國采用分區(qū)域、分車類、分階段的方案，有望于2050年全面退出燃油汽車[1]。隨著電動汽車數(shù)量快速增多，充電站數(shù)量也迅速增長。截止2019年9月，我國充電設(shè)施數(shù)量達到111.5萬座，是國內(nèi)加油站數(shù)量的10倍[2]。盡管充電站數(shù)量龐大，但是充電難問題依然存在。充電站分布不合理、“跑馬圈地”式建設(shè)導致充電站要么不堪重負，要么閑置率極高。因此充電站的合理規(guī)劃非常必要。

電動汽車充電站選址定容問題是多變量、多約束、高維度的非線性優(yōu)化問題。目前，該問題的研究仍處在起步階段，尚未形成完整的理論體系。文獻[3]提出交通滿意度模型，結(jié)合加權(quán)Voronoi圖和遺傳算法，進行多場景分析；文獻[4]提出目標為最大充電網(wǎng)絡(luò)服務(wù)能力和最小配電系統(tǒng)網(wǎng)絡(luò)損耗的多目標優(yōu)化模型，模糊化處理后采用遺傳算法進行求解；文獻[5]綜合考慮充電站建設(shè)成本與用戶廣義充電成本，引入便捷系數(shù)概念，提出多種規(guī)劃目標的取值建議；文獻[6]提出以最大化滿足路徑中需求與最小化平均等待時間為目標的混合整數(shù)規(guī)劃模型，求解后得出選址定容問題的3大關(guān)鍵要素；文獻[7]通過分析用戶出行行為和充電習慣，提出兼顧運營商利益與用戶充電需求的規(guī)劃模型；文獻[8]把用戶碳排放量作為充電站規(guī)劃考核指標之一，并采用帕累托最優(yōu)前沿分析可選的方案；文獻[9]依據(jù)城市道路信息，確定充電站最優(yōu)位置分布，再運用Voronoi圖劃分充電站所服務(wù)的負荷區(qū)，確定其容量。上述研究成果均片面考慮用戶或運營商的利益，考慮的因素不夠全面，在實際推行過程中可能會遇到較大阻力。文獻[10]建立的模型雖考慮了充電站運營商、電動汽車用戶以及電網(wǎng)企業(yè)三者的綜合利益，但電網(wǎng)側(cè)利益是通過設(shè)備損耗來簡單折算，與實際運行情況存在較大差距。文獻[11]建立的模型選中了多個交通節(jié)點作為最優(yōu)站址；文獻[12]建立的模型是在規(guī)劃范圍內(nèi)隨機生成站點，運用改進PSO算法求得最優(yōu)站址。上述研究得出的最優(yōu)站址在現(xiàn)實中不一定具備建站條件，實用性偏低。

本文綜合多種約束條件，建立以建設(shè)運行成本、用戶充電時間成本、配網(wǎng)損耗成本為目標的電動汽車充電站選址定容多目標決策模型；針對多目標決策難問題，引入層次分析熵權(quán)法進行決策；針對標準引力搜索算法收斂速度慢，求解高維度問題精度不足的缺點，引入混沌理論以及全局最優(yōu)來引導粒子速度更新；針對選址定容模型的求解，引入Voronoi圖劃分充電站服務(wù)區(qū)域，與改進引力搜索算法聯(lián)合求解。小區(qū)幾何分布與IEEE30節(jié)點系統(tǒng)的算例表明本模型及算法具有較高的可行性。

1 電動汽車充電站選址定容數(shù)學模型

電動汽車充電站屬于公共服務(wù)設(shè)施，在進行規(guī)劃時不僅要考慮運營商的效益，還應(yīng)考慮用戶便利程度等多個因素。本文在考慮潮流、充電站規(guī)模等約束條件下，提出以建設(shè)運行成本、用戶充電時間成本及配網(wǎng)損耗成本為目標的電動汽車充電站選址定容數(shù)學模型。

1.1 目標函數(shù)

1.1.1 建設(shè)運行成本

建設(shè)運行成本包括建設(shè)成本和運行成本[13]。建設(shè)成本Ccon主要包括充電樁、土地、變壓器等費用，如式(1)所示。

其中，r0為貼現(xiàn)率；nyear為折舊年限；Cg為固定投資成本；nchar為站內(nèi)充電樁數(shù)量；φ是配電變壓器和輸電線路等相關(guān)設(shè)備成本的等效投資系數(shù)；ε為充電樁的單價。運行成本Cop主要有人力成本、設(shè)備維護成本等，如式(2)所示。

其中，γ為人工、設(shè)備運行維護成本折算系數(shù)。綜上，充電站年建設(shè)運行成本f1的目標函數(shù)為

其中，I為充電站合集；i為充電站；Cconi和Copi分別為充電站i的建設(shè)成本和運行成本。

1.1.2 用戶充電時間成本

用戶充電時間成本包括電動汽車前往充電站的時間成本及站內(nèi)排隊等待的時間成本[12]。假設(shè)用戶在充電站內(nèi)的排隊過程符合M/M/s排隊模型，充電站i 的排隊等待期望Wi為

其中，ρ=D/ψ為充電樁服務(wù)強度，D為充電需求量，ψ為充電樁服務(wù)效率；p0為充電樁全部閑置概率。

用戶前往充電站的行駛時間tDA與站內(nèi)排隊等待時間tWA如式(6)與式(7)所示。其中，I為充電站合集；J為需求點合集；μ為道路曲折系數(shù)；Dj為需求點j的充電需求量；Eij為0或1，若需求點j選擇充電站i充電，則Eij為1，反之為0；dij為需求點j與充電站i的歐氏距離；vq為汽車平均行駛速度；Wi為充電站i的排隊等待期望。

則用戶充電時間成本f2的目標函數(shù)為

其中，Ccut為用戶單位時間成本。

1.1.3 配網(wǎng)損耗成本

電動汽車充電站的大規(guī)模接入會對電網(wǎng)產(chǎn)生一定影響，如網(wǎng)損增加、頻率下降、電壓下降。為降低電動汽車充電負荷對電網(wǎng)的影響，提高電網(wǎng)公司效益，本文在充電站選址定容中計算配網(wǎng)損耗[14]。其計算公式為

1.2 約束條件

1.2.1 潮流約束

其中，Bhk為節(jié)點h, k之間的電納；PGEh和PCHh分別是電網(wǎng)節(jié)點h的發(fā)電機有功功率和充電站有功功率；QGEh和QCHh分別是電網(wǎng)節(jié)點h的發(fā)電機無功功率和充電站無功功率，Y為電網(wǎng)中的支路集合，θhk為節(jié)點h，k之間的電壓相差角。

1.2.2 支路視在功率約束

1.3 基于層次分析熵權(quán)法的多目標決策

在對多目標問題進行決策時，采用層次分析法得到的權(quán)值雖反映了專家的經(jīng)驗和決策者的意向和偏好等主觀因素，但不能反映各個目標函數(shù)之間的客觀博弈結(jié)果，主觀隨意性較大。如采用熵權(quán)法決策，雖得到的權(quán)值較為客觀，但不能反映專家的經(jīng)驗和決策者的意見，得到的權(quán)重可能與實際情況有偏差，甚至相違背。因此，本文綜合上述2種決策方法的優(yōu)缺點，提出了層次分析熵權(quán)法[15]，該方法可以避免過度依賴主觀權(quán)值或客觀權(quán)值而導致的決策偏差。

2 改進引力搜索算法

2.1 標準引力搜索算法(GSA)

引力搜索算法(GSA)于2009年由Esmat Rashedi提出，是一種受萬有引力定律以及牛頓第二定律啟發(fā)的優(yōu)化算法[16]。引力搜索算法與粒子群算法相似，通過不斷改變種群粒子的位置來尋找最優(yōu)解。GSA算法在迭代過程中，把粒子看作存在一定質(zhì)量的物體，相互之間存在引力。粒子的適應(yīng)度越大，其慣性質(zhì)量越大，引力就越大；適應(yīng)度越小的粒子慣性質(zhì)量越小，引力也越小。質(zhì)量小的粒子容易被質(zhì)量大的粒子吸引并移動。因此，每代可能接近全局最優(yōu)的粒子質(zhì)量最重，其吸引力也最大。隨著算法的循環(huán)，粒子靠它們之間的萬有引力在搜索空間內(nèi)不斷運動，當粒子移動到最優(yōu)位置時，最優(yōu)解便找到了。其速度和位置更新公式為

其中，π為當前代數(shù)；ve(π)表示粒子e的速度；x(π)為第π次更新后的狀態(tài)值；R是區(qū)間[0,1]間的隨機數(shù)，ae(π)是粒子e的加速度。

2.2 改進引力搜索算法(IGSA)

2.2.1 引入組合混沌映射策略

GSA算法在初始化階段隨機生成初始種群，不利于種群的多樣性和遍歷性，因此本文采用Logistic映射與Tent映射相結(jié)合，將其應(yīng)用于種群初始化與尋優(yōu)過程，增加粒子遍歷性，提高收斂性能，其表達公式為

其中，x0, y0是粒子初始值，xπ+1, yπ+1是更新后狀態(tài)值，temp為待求余狀態(tài)值，ξ是Logistic混沌系數(shù)，mod()為取余函數(shù)。

2.2.2 引入全局最優(yōu)點引導的自適應(yīng)移動策略

標準GSA算法在粒子移動階段僅考慮了當前位置信息，缺少記憶性，尋優(yōu)效率及效果較差，特別是在求解高維優(yōu)化問題時容易陷入局部最優(yōu)。受粒子群算法啟發(fā)，在粒子移動階段，引入全局最優(yōu)點GB來引導速度更新[17]，其更新公式為

其中，GB是全局最優(yōu)點，c1和c2是加速因子，其表達式為

其中，Φ為最大迭代次數(shù)。

3 基于Voronoi圖和改進引力搜索算法的選址定容

3.1 Voronoi圖及服務(wù)區(qū)域劃分

Voronoi圖，又名泰森(Thiessen)多邊形，于1908年由M. G. Voronoi提出，由一組連接兩鄰點直線的垂直平分線形成的連續(xù)多邊形組成。Voronoi圖生成方法如圖1所示。設(shè)生長點集合H={H1,H2,H3,···,HL}, 3≤L≤∞，則Voronoi圖的數(shù)學表述為

其中， b,l=1,2,···,L ，且b ≠l ； Hb和Hl為平面上生長點 b 和 l；d (u,Hb) 和d(u,Hl)為任意一個點u 與點 Hb和Hl點間的歐氏距離。

圖1 Voronoi圖生成方法Fig.1 Voronoi diagram generation method

利用Voronoi圖，進行服務(wù)區(qū)域劃分。把充電站的選址集合視為二維平面上的點集，需求點視為平面上的點。以充電站點集為生長點作Voronoi圖，由Voronoi圖特點可知，充電站服務(wù)區(qū)域內(nèi)的需求點到該充電站的距離應(yīng)小于等于到其他充電站的距離，滿足車主就近選擇充電站原則。

3.2 求解步驟

步驟1：初始化數(shù)據(jù)，輸入規(guī)劃區(qū)的面積、人口密度、需求點和候選點的具體坐標、需求點的負荷信息、配網(wǎng)結(jié)構(gòu)等參數(shù)信息，根據(jù)式(25)折算各需求點電動汽車數(shù)量。

其中，ncari是需求點i的電動汽車數(shù)量；A是規(guī)劃區(qū)占地面積；α是人口密度；β是人均汽車保有量；η是電動汽車占比；Oi為需求點i的電荷，OΣ為需求點總電荷。

步驟2：生成初始種群，粒子具體編碼方式為

例如當ω=3，x=[1 5 8 10 20 30]指選取了1、5、8號候選站，對應(yīng)站內(nèi)充電樁數(shù)目分別為10、20、30。如種群粒子數(shù)為m，則初始種群編譯為

步驟3：對步驟2生成的初始種群歸一化處理，再進行m-1次混沌操作，然后反歸一處理。

步驟4：依據(jù)建站數(shù)量和建站規(guī)模，由式(3)得到建設(shè)運行成本f1。

步驟5：把候選站址坐標作為生長點作Voronoi圖，劃分各充電站服務(wù)范圍。由式(4)和式(8)計算出用戶充電時間成本f2。

步驟6：將候選站址接入配網(wǎng)后并進行潮流計算，由式(10)得到配網(wǎng)損耗成本f3。

步驟7：依據(jù)改進策略更新粒子位置和速度，并對粒子按步驟3進行混沌操作。

步驟8：由層次分析熵權(quán)法得到的λ1、λ2、λ3代入式(18)，將多目標函數(shù)變?yōu)閱文繕撕瘮?shù)，記錄個體最優(yōu)和全局最優(yōu)。

步驟9：重復步驟4～8，直至滿足收斂條件，輸出全局最優(yōu)值。

4 算例分析

以某市規(guī)劃區(qū)為例進行分析，該區(qū)占地面積為12.1 km2，人口密度為7000人/km2，人均汽車保有量為19%，其中電動汽車占30%。規(guī)劃區(qū)包含21個小區(qū)位置重心(需求點)和根據(jù)實際情況確定的9個候選站址(候選點)，假設(shè)其對應(yīng)IEEE30節(jié)點系統(tǒng)，需求點、候選點具體坐標和對應(yīng)接入的節(jié)點號如表1所示。其中，1～34號為需求點，35～43號為候選點。

假設(shè)該規(guī)劃區(qū)電動汽車型號為比亞迪E2，電池容量為35.2 kW；充電站固定投資成本為300 萬元/座；折算到充電樁的等效投資系數(shù)為2 萬元/臺；充電樁價格為10 萬元/臺；站內(nèi)允許安裝充電樁的最小數(shù)量為8臺；站內(nèi)允許安裝充電樁的最大數(shù)量為45臺；人工、設(shè)備運行維護成本折算系數(shù)為0.1；貼現(xiàn)率為0.08；折舊年限為20年；道路曲折系數(shù)為1.3；車輛平均行駛速度為35 km/h；用戶單位時間成本為20 元/h；充電樁額定功率為120 kW；充電效率為0.9；充電站日運行時間為12 h；電價為0.6 元/kW·h。IGSA算法參數(shù)設(shè)置為：種群規(guī)模為20，迭代次數(shù)最大值為500，引力常數(shù)初始值為100，引力系數(shù)衰減因子為30。

根據(jù)3.2節(jié)求解步驟，建不同數(shù)量候選站的計算成本如圖2所示。由圖2可知，若建站數(shù)量過少會由于用戶時間成本的增加而導致綜合總成本過高；而建站數(shù)量過多又會由于建設(shè)運行成本和配網(wǎng)損耗成本的增加導致綜合成本過高。

表1 需求點、候選點坐標和節(jié)點號Table 1 Demand point, candidate point coordinates and node number

圖2 不同建站數(shù)量的綜合成本Fig.2 Calculation result of selecting different number of candidate stations

由圖2可知，當建站數(shù)量為5個時，綜合總成本最低，為2099.7萬元。具體站點分布、服務(wù)區(qū)域劃分以及配置的充電樁數(shù)量如圖3所示，圖中圓點為需求點，方形為候選點，其中實心方形為被選中的候選點，實心方形旁的數(shù)值為選中充電站安裝的充電樁數(shù)量，網(wǎng)狀直線由Voronoi圖生成，即服務(wù)區(qū)域劃分邊界。由圖3可知，規(guī)劃區(qū)由5個充電站劃分為5個服務(wù)區(qū)域，具體劃分情況為：有8個充電樁的充電站覆蓋了2個需求點；有16個充電樁的充電站分別覆蓋了8個和5個需求點；有24個充電樁的充電站覆蓋了8個需求點；有32個充電樁的充電站覆蓋了11個需求點。

圖3 最優(yōu)方案及服務(wù)區(qū)域劃分Fig.3 Optimal plan and service area division

本文分別采用IGSA、GSA和PSO 3種算法進行仿真，其收斂曲線對比如圖4所示。由圖4可知，PSO前期收斂速度很快，但在中期陷入了局部最優(yōu)；GSA前期收斂速度較慢，中期緩慢收斂，后期陷入了局部最優(yōu)；IGSA前期收斂速度跟GSA相比有了一定提升，中期平穩(wěn)收斂逐漸趨于最優(yōu)。優(yōu)化結(jié)果如表2所示，結(jié)果顯示，IGSA求得的方案綜合總成本最低，GSA求得的方案充電樁數(shù)量較少，因此建設(shè)運行成本和配網(wǎng)損耗成本較低，但用戶充電時間成本大大增加，綜合總成本較高；PSO求得的方案由于充電樁數(shù)量過多導致建設(shè)運行成本和配網(wǎng)損耗成本激增，綜合總成本最高。求解時間方面，IGSA運算效率雖不如PSO，但較GSA有了一定改善，效率提高了16%。

圖4 3種算法收斂曲線對比Fig.4 Comparison of convergence curves of three algorithms

表2 3種算法優(yōu)化結(jié)果對比Table 2 Comparison of four algorithm optimization results

5 結(jié)論

隨著電動汽車的推廣普及，電動汽車充電站的選址定容非常重要。本文考慮了多方面因素，建立了以建設(shè)運行成本、用戶充電時間成本、配網(wǎng)損耗成本為目標的電動汽車充電站選址定容多目標決策模型，通過對某市規(guī)劃區(qū)的算例進行仿真，得出以下結(jié)論。

(1) 提出的IGSA算法是在GSA算法基礎(chǔ)上，引入混沌理論以及自適應(yīng)移動策略，提高了算法的收斂速度和跳出局部最優(yōu)能力，與GSA、PSO算法相比，IGSA在電動汽車充電站規(guī)劃方面具有較高的效率和更強的尋優(yōu)能力。

(2) 運用Voronoi圖劃分充電站服務(wù)區(qū)域，配合IGSA對模型進行聯(lián)合求解，為電動汽車充電站規(guī)劃提出新思路。

本文未考慮電動汽車類型、電動汽車換電站、用戶充電習慣等因素，需日后繼續(xù)研究完善。