艾 欣，李一錚，王坤宇，胡俊杰

華北電力大學 新能源電力系統(tǒng)國家重點實驗室，北京 102206)

0 引言

近年來，我國電動汽車的保有量迅速攀升，截至2016年底，我國電動汽車保有量已經(jīng)接近100萬輛，經(jīng)測算，到2020年全國電動汽車保有量將超過500萬輛[1]。電動汽車充電基礎設施作為電動汽車發(fā)展的重要保障，其發(fā)展水平直接影響了電動汽車行業(yè)的發(fā)展速度和質量。目前，全國各地按照“樁站先行，適度超前”的原則，逐步推進充電基礎設施的科學發(fā)展。根據(jù)需求預測結果，到2020年新增集中式電動汽車充換電站將超過1.2萬座[1]。

電動汽車充電站的選址與定容問題是高維非線性數(shù)學問題，決策的優(yōu)劣直接影響了其服務質量、效率、成本等?，F(xiàn)有的國內外學者對城市電動汽車充電站的選址與定容問題研究仍處在起步階段，沒有形成系統(tǒng)完整的理論。文獻[2]以投運至目標年綜合費用最小為規(guī)劃目標，利用變權Voronoi圖的方法劃分充電站的服務范圍，并采用混合粒子群優(yōu)化(PSO)算法求解，提高了算法迭代中后期的全局搜索能力。文獻[3]將量子理論與粒子群優(yōu)化算法結合，增強了優(yōu)化算法的種群多樣性以及算法的全局搜索能力。文獻[4]結合了城市道路信息和電動汽車續(xù)駛里程，提出了電動汽車充電便捷系數(shù)，并利用Voronoi圖理論和排隊論確定充電站的容量。文獻[5]將配電網(wǎng)約束等引入充電站規(guī)劃模型中，同時以截獲最大交通流量為目標進行規(guī)劃，并采用快速非支配排序遺傳算法-Ⅱ進行多目標優(yōu)化規(guī)劃求解。文獻[6]引入了路網(wǎng)結構、車流信息、配電網(wǎng)絡結構等約束進行優(yōu)化規(guī)劃。文獻[7]綜合考慮了城市路網(wǎng)和配電網(wǎng)的交互性，引入博弈論思想，并對電動汽車充放電特性對配電網(wǎng)供電可靠性的支撐作用進行了評估。文獻[8]利用網(wǎng)格法確定充電站的站址，分析了充電站的盈利模型，提出了充電站的日負荷率、投資回收期、充電行駛里程、綜合滿意度4類評價指標。文獻[9]將碳排放指標引入充電站選址定容規(guī)劃模型中，采用Pareto最優(yōu)前沿分析可選的方案，提出了基于需求點柵格化的充電站服務范圍求解方法。文獻[10]對電動汽車出行活動及充電過程進行預測，提出了基于電動汽車用戶出行的規(guī)劃模型，兼顧了電動汽車用戶的出行需求以及充電站運營商的利益。

上述的研究均從一定的角度出發(fā)，提出了電動汽車充電站選址定容的模型，并采用了不同算法進行求解。本文在上述研究的基礎上，提出了一種綜合考慮全社會利益的選址定容規(guī)劃模型。為了求解該模型，克服傳統(tǒng)粒子群優(yōu)化算法的早熟、局部收斂等缺點，本文將混沌理論與模擬退火算法與粒子群優(yōu)化算法相結合，通過混沌理論優(yōu)化粒子的搜尋空間，并用模擬退火算法的概率突跳特性改善粒子群優(yōu)化算法的早熟問題；采用Voronoi圖思想及需求點柵格化理論來確定充電站的服務范圍；求解距離時引入了Floyd算法代替?zhèn)鹘y(tǒng)歐氏距離，使結果更加接近實際情況，進一步提高了算法的準確程度。

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

目前主流的電動汽車能源補給方式主要為充電方式及換電方式2種，限于文章篇幅，本文暫未考慮換電方式，只針對充電方式進行探究。電動汽車充電站是社會的公共服務設施，在進行選址定容時不僅應考慮運營方的效益，還應考慮其社會服務作用。本文在考慮充電站運營方、電網(wǎng)企業(yè)的電力負荷均勻性、電力線路走廊、電動汽車車主的方便程度的綜合基礎上，提出了一種全社會成本最小化的電動汽車充電站選址定容優(yōu)化規(guī)劃數(shù)學模型，如式(1)—(7)所示。

minC=C1+C2+C3+C4

(1)

(2)

ArCA+Br+Lr]

(3)

C3=ε[Tr(CT+CP)+MrCM+ArCA+Br+Lr]

(4)

C4=365CeTe[Tr(CCu+CFe)+Mr(CL+CW)]

(5)

(6)

Nqγmaxyqr≤MrTe

(7)

其中，C1為電動汽車用戶去往充電站路程產(chǎn)生的成本；C2為折算至每年的電動汽車充電站固定建設成本；C3為電動汽車充電站的年均運行維護成本；C4為電動汽車充電站的網(wǎng)損年費用；p為電動汽車行駛單位千米耗電量；Ce為電動汽車充電電價；dqr為從充電需求點q到電動汽車充電站r的距離；yqr為從充電需求點q是否去電動汽車充電站r充電的決策變量,且yqr∈{0，1}；Nq為充電需求點q需要充電的車輛數(shù)；r0為資金回收率；nk為充電站設計運行年限；Tr和CT分別為充電站r裝設的配電變壓器數(shù)目和配電變壓器單價；Mr和CM分別為充電站r裝設的充電機數(shù)目和充電機單價；CP為配電變壓器改擴容折算至單臺配電變壓器的費用系數(shù)；Ar和CA分別為充電站r的用地面積和土地征用單價；Br為充電站r的基礎設施建設費用；Lr為充電站r的電力走廊建設費用，表示由架空線更換為地下電纜所產(chǎn)生的費用；ε為將設備維護費用、折舊費用、員工工資折算到初期投資成本的折算系數(shù)；Te為充電站每天平均有效工作時間；CCu和CFe分別為折算至單臺配電變壓器的銅損和鐵損；CL和CW分別為折算至單臺充電機的線路損耗和充電損耗；Q為充電需求點的集合，且q∈Q={1,2,…,qmax}，qmax為充電需求點總數(shù)；R為電動汽車充電站集合，且r∈R={1,2,…,rmax}，rmax為充電站總數(shù)；γmax為需求點電動汽車最大同時充電率。式(6)、(7)為約束條件，式(6)表示每一個需求點到且只到一個充電站進行充電，式(7)表示充電站r服務范圍內的需求充電車輛不應大于該站的服務能力。

2 混沌模擬退火粒子群優(yōu)化算法

2.1 粒子群優(yōu)化算法及其不足之處

粒子群優(yōu)化算法是一種基于群體協(xié)作的隨機搜索算法，其算法的中心思想源自對鳥群捕食行為的研究，自從其在1995年由Eberhart和Kennedy提出以來[11]，一直是廣大學者的研究熱點。其迭代形式如下：

(8)

(9)

分析其迭代方程可以看出，粒子群優(yōu)化算法在計算中雖然收斂速度較快，但非常容易陷入局部最優(yōu)的情況。例如，處于全局最優(yōu)位置的粒子其移動速度只由其自身的速度慣性決定，當自身速度為0時其將停止運動，當所有粒子被吸引運動到這個位置時將會停止搜尋。而在實際中，這個位置往往是局部極值。因此，為了將算法應用于充電站選址定容問題中，必須提高算法的全局搜索能力，避免過早陷入局部最優(yōu)的情況。

2.2 算法的改進

為了解決粒子群優(yōu)化算法后期收斂于局部極值的問題，本文提出了一種基于混沌理論和模擬退火算法的粒子群優(yōu)化(CSAPSO)算法，引入模擬退火算法的概率突跳能力，使CSAPSO算法不但可以接受好的解，也能以一定的概率接受差的解，在退火溫度的控制下能有效地提高全局搜索能力。同時引入混沌理論對r1、r2進行動態(tài)賦值，使粒子種群的運動行為更加優(yōu)化。CSAPSO算法的計算步驟如下。

a. 初始化參數(shù)：慣性權重ω、學習因子c1和c2、退火速度δ。

b. 隨機生成包含m個粒子的種群，隨機初始化粒子的位置和速度，在電動汽車充電站問題中粒子的位置與速度均為正整數(shù)。

c. 計算每個粒子i的適應度，記錄各個粒子位置Pid和全局最優(yōu)位置Ppd。

d. 選出整個種群的最優(yōu)適應度Zbest，計算得到退火算法初始溫度T。

e. 計算得到當前溫度下各個Pid的退火算法適應度如下：

(10)

其中，f(Pid)為粒子位置在Pid時的粒子群優(yōu)化算法適應度值；f(Ppd)為粒子群最優(yōu)適應度值。

f. 采用輪盤賭輸?shù)牟呗?，從所有個體最優(yōu)位置Pid中選出一個值代替全局最優(yōu)位置，將其存入Pzd中。

g. 用Pzd代替Ppd，代入式(8)中更新各個粒子的速度如下：

(11)

h. 計算各個粒子的適應度值，更新各粒子的最優(yōu)位置Pid和種群最優(yōu)位置的Ppd。

i. 按照下式進行退火操作：

T=δT

(12)

j. 判斷是否滿足算法終止條件(電動汽車充電站選址問題中為預設的迭代次數(shù))，若滿足則停止搜索，輸出計算結果，否則轉至步驟e。

2.3 相關參數(shù)的設置

a. 慣性權重的設置。

慣性權重表示粒子過去飛行狀態(tài)對當前狀態(tài)的影響，其值直接決定了粒子種群的全局尋優(yōu)能力和局部尋優(yōu)能力。本文采取文獻[12]提出的線性遞減策略調整慣性權重。在算法運行初期，較大的慣性權重確保了粒子群可以進行大范圍的全局搜索，以較快的速度確定最優(yōu)解的大致位置。在迭代中后期，慣性權重的縮小使粒子群能在局部更加精確地搜尋最優(yōu)解。設置公式如下：

(13)

其中，ωstart和ωend分別為起始和終止的慣性權重值，一般分別設置為0.9和0.4；kmax和k分別為迭代次數(shù)和當前迭代數(shù)。

b.r1、r2的設置。

本文采用混沌理論對r1、r2進行動態(tài)調整。采用Logistic模型產(chǎn)生混沌序列[13]如下：

(14)

c. 初始溫度設置。

算法中初始溫度T直接影響了模擬退火算法的全局搜索能力，較高的初始溫度可以顯著提高搜索到全局最優(yōu)解的可能性。設置公式如下：

(15)

其中，Zbest為初始粒子種群中最優(yōu)的適應度值。

d. 退火速度設置。

模擬退火算法運行中，模擬的退火過程越慢，算法找到全局最優(yōu)的概率就越大，本文將退火速度設置為0.95。

3 基于CSAPSO算法的充電站選址定容

3.1 規(guī)劃假設

基于上文提出的電動汽車充電站選址定容規(guī)劃模型，做以下假設。

a. 選擇城市的交通節(jié)點為電動汽車充電站的候選站址，現(xiàn)實中應根據(jù)實際情況選取。

b. 將所有需求充電的車輛整合到距離其最近的交通節(jié)點，將每個交通節(jié)點看作一個充電需求點，在實際規(guī)劃過程中充電需求量可結合交通節(jié)點典型日車流量數(shù)據(jù)和目標年電動汽車占比獲得。

c. 假設每一個需求點的車輛到且僅到距離其最近的充電站進行充電。根據(jù)Voronoi圖原理和需求點柵格化理論[14]，即規(guī)定充電站的服務范圍為到該充電站實際距離(由Floyd算法求得)最近的需求點的集合。

3.2 服務范圍劃定及Floyd算法概述

根據(jù)柵格化理論的思想，將城市道路和交通節(jié)點組成的二維圖形視作柵格化后的圖形。按照假設將道路上需要充電的車輛和每個柵格內的需要充電的車輛整合到道路節(jié)點處，將交通節(jié)點看作充電需求點。

劃分充電站的服務范圍：將充電站的選址集合看作二維平面上的點集，充電需求點視為平面上的點。根據(jù)Voronoi圖原理可知，充電站服務范圍內的充電需求點到該站的實際距離應小于等于充電需求點到其他充電站的實際距離。

本文采用Floyd算法求實際距離，F(xiàn)loyd算法的具體步驟如下。

a. 根據(jù)規(guī)劃新區(qū)實際道路情況生成城市道路CAD圖，并對各道路節(jié)點進行編號。

(16)

其中，l,j=1,2,…,b；wlj為道路節(jié)點l到j之間的實際道路長度。

c. 對于任何2個道路節(jié)點l和j，判斷是否存在一個中間節(jié)點s，使節(jié)點l通過節(jié)點s再到節(jié)點j的距離小于現(xiàn)有的距離，如果存在這樣的節(jié)點s，則更新迭代距離矩陣D(k)，如式(17)所示。

(17)

d. 按照上述規(guī)則更新迭代獲得距離矩陣D(k+1)，若D(k+1)≠D(k),則返回步驟c；否則終止迭代，得到最短路徑矩陣即為D(k)。

3.3 規(guī)劃流程

具體規(guī)劃流程如下。

a. 初始數(shù)據(jù)處理。處理規(guī)劃目標城市道路交通信息及車流量信息，生成城市道路CAD圖，得到各需求點充電需求量。以充電站最大服務容量、最小服務容量以及總充電需求量來估算最大建站數(shù)nmax和最小建站數(shù)nmin。

b. 充電站規(guī)劃的粒子群編碼。電動汽車充電站選址定容包含兩部分內容：站址的確定和站規(guī)模的確定。因此粒子編碼形式如下：

X=[x1,x2,…,xn,y1,y2,…,yn]n∈(nmin,nmax)

(18)

其中，xg為互不重復的正整數(shù)，表示第g個充電站選在備選位置xg處；yg為正整數(shù)，表示第g個充電站的規(guī)模等級。例如n=4時，X=[15,9,31,19,1,4,4,3]表示在備選站址15、9、31、19處建站，站規(guī)模等級分別為1、4、4、3。

c. 按照編碼形式生成初始粒子種群和粒子速度，在充電站選址定容問題中，粒子位置與速度的分量均為正整數(shù)，因此在算法中應進行取整操作。

d. 根據(jù)規(guī)劃模型求出個體適應度值和全局最優(yōu)值(模型中涉及的距離均采用Floyd算法求解)，按照式(15)求出模擬退火算法初始溫度。

e. 采用CSAPSO算法更新粒子群的位置與速度，并記錄全局最優(yōu)適應度值。

f. 循環(huán)操作步驟c—e。求出不同建站數(shù)n的最優(yōu)適應度值及選址定容方案。

采用CSAPSO算法進行電動汽車充電站選址定容的規(guī)劃流程如附錄中圖A1所示。

4 算例分析

以某典型新區(qū)的電動汽車充電站選址定容為例進行分析，該新區(qū)規(guī)劃總面積為26.75 km2，東西跨度為6.4 km，南北跨度為5.3 km,含有道路78條。該新區(qū)的道路節(jié)點圖如圖1所示，圖中的道路節(jié)點處數(shù)字為該節(jié)點的編號。各道路節(jié)點及其典型日的車流量見附錄中表A1。

圖1 規(guī)劃新區(qū)道路節(jié)點Fig.1 Road nodes of new planning district

規(guī)劃在該新區(qū)建設適當?shù)碾妱悠嚦潆娬?，使充電站的全社會成本最小。假設充電站的使用運行年限為20 a，每輛電動汽車電池平均容量為50 kW·h。根據(jù)文獻[15]對電動汽車充電站等級及各項指標的劃分，合理假設電動汽車充電站的基本參數(shù)如附錄中表A2所示，表中建設成本為充電機成本、配電變壓器成本以及基礎建設成本之和，不包含用地成本。該新區(qū)各類型土地出讓價格如附錄中表A3所示。

由于現(xiàn)有的車輛群體是汽油車與電動汽車的混合群體，所以假設至規(guī)劃目標年電動汽車所占的比例為10%，結合附錄中表A1的數(shù)據(jù)可知，分別按照單位日最小服務能力和最大服務能力配置充電站時，可以計算得到分別需要3座和18座充電站。隨著充電站數(shù)目的增多，雖然降低了用戶的充電路程成本，但同時增加了充電站建設成本。所以經(jīng)過合理的篩選規(guī)劃，可以得出該新區(qū)建設充電站數(shù)目為3～7座。采用CSAPSO算法進行計算的各項參數(shù)值見附錄中表A4。

CASPSO算法參數(shù)如下：粒子種群規(guī)模為50，起始慣性權重值ωstart=0.9，終止慣性權重值ωend=0.4，退火速度δ=0.95，學習因子c1=c2=1.494 45，終止迭代次數(shù)為200次。通過計算可得當建設3～7座充電站時，全社會成本如圖2所示?？梢姰斀ㄔO4座充電站時，可滿足該算例中用戶充電需求并且使全社會成本最優(yōu)。當建設4座充電站時，各充電站選址、等級及其服務范圍如表1所示。各項成本如下：C1=204.5萬元，C2=363.9萬元，C3=407.8萬元，C4=365萬元。

圖2 建站數(shù)目及對應成本Fig.2 Cost of station vs. number

充電站建站道路節(jié)點建站等級服務道路節(jié)點12042—4,6—9,11—15,18,19,21226424,25,27,31—34,36—45322123,28—30,3541621,5,10,17

為了驗證算法的優(yōu)化能力，當建站數(shù)目為4座時，分別采用粒子群優(yōu)化算法和CSAPSO算法對該算例進行求解，得出2種算法的最佳適應度曲線如圖3所示。由實驗數(shù)據(jù)可知，粒子群優(yōu)化算法在迭代第25次時求得其最佳適應度值為1 360.7萬元；CSAPSO算法在迭代第130次時求得最佳適應度值為1 341.2萬元。對比圖3中2條曲線可知，迭代初期粒子群優(yōu)化算法收斂的性能優(yōu)于CSAPSO算法，并于較少的迭代次數(shù)時收斂，而CSAPSO算法在迭代的中后期仍保有較好的種群多樣性，其最終綜合優(yōu)化結果優(yōu)于粒子群優(yōu)化算法。最終求得的建站位置及其服務范圍示意圖如圖4所示。

圖3 2種算法最佳適應度曲線對比Fig.3 Comparison of best fitness curve between two algorithms

圖4 建站位置及其服務范圍示意圖Fig.4 Schematic diagram of charging station location and its service range

5 結論

本文考慮了充電站運營方、電網(wǎng)企業(yè)的電力負荷均勻性、電力線路走廊、電動汽車車主的方便程度等多方面因素，對選址定容問題進行了研究，通過對某典型新區(qū)的算例進行分析，得到的主要結論如下。

a. 針對電動汽車選址定容問題，提出了一種全社會成本最優(yōu)化的充電站規(guī)劃模型，平衡了電動汽車用戶、充電站運營方和電網(wǎng)企業(yè)的利益。提出了CSAPSO算法來改善粒子群優(yōu)化算法早熟和局部收斂的問題。

b. 提出的CSAPSO算法相較于傳統(tǒng)的粒子群優(yōu)化算法全局尋優(yōu)能力更好，求得的規(guī)劃結果更為優(yōu)化。通過引入混沌理念，使粒子更加高效地遍歷整個搜索空間。同時結合模擬退火算法的概率突跳特性，使算法在迭代進行到中后期時，仍能保持較高的全局尋優(yōu)能力，避免出現(xiàn)過早的陷入局部最優(yōu)的情況。

c. 算例中考慮了不同用地性質的情況，并且采用Floyd算法求取距離代替?zhèn)鹘y(tǒng)算法中的歐氏距離，結合Voronoi圖思想及需求點柵格化理論劃分充電站服務范圍，進一步提高了算法的準確性。

現(xiàn)實中，充電站的選址定容問題仍有很多需要考慮的因素，例如：充電站中快慢樁的配比問題、充電需求的時空分布問題、電動汽車充換電方式等。在下階段的研究中可以針對以上問題，構建更加合理準確的規(guī)劃模型。

附錄見本刊網(wǎng)絡版(http:∥www.epae.cn)。