電動汽車充電站規劃的多種群混合遺傳算法

馮 超，周步祥，林 楠，徐 飛，李 陽，夏榆杭

（1.四川大學電氣信息學院，成都 610065；2.四川電力職業技術學院，成都 610071）

電動汽車充電站規劃的多種群混合遺傳算法

馮 超1，周步祥1，林 楠2，徐 飛1，李 陽1，夏榆杭1

（1.四川大學電氣信息學院，成都 610065；2.四川電力職業技術學院，成都 610071）

建立考慮充電站建設運營成本和充電者充電成本的電動汽車充電站綜合成本最小模型。針對電動汽車充電站規劃的特點，提出了一種新的多種群混合遺傳算法（MPHGA）。該算法將標準遺傳算法（SGA）與交替定位分配算法（ALA）結合，針對充電站規劃的多目標性，采用多種群概念，建立多種群并進行協同進化搜索?；诘乩硇畔⑾到y（GIS），考慮地理信息對充電站選址的影響，通過某市充電站規劃實例驗證了該模型和方法的正確性和有效性。

地理信息系統；多種群；混合遺傳算法；電動汽車充電站；選址定容

隨著全球化石能源危機和環境污染的逐步加重，電動汽車越來越受到各個國家的重視。電動汽車充電站是電動汽車發展的基礎，充電站的規劃研究就顯得尤其重要。

文獻[1]對影響電動汽車充電站規劃的相關因素做了分析，對充電站布局規劃提出了原則性建議。文獻[2]提出了充電方式的選擇優化模型以及充電設施規劃的原則、流程和模型。文獻[3]運用動態交通網絡思想建立了基于硬時間窗約束下的充電站布局及最佳規模確定的多目標優化模型，提出了求解該模型的兩階段啟發式算法。到現階段為止還沒有一套完善的充電站規劃理論可供使用。

本文建立綜合考慮充電站建設運營成本和充電者充電成本的電動汽車充電站綜合成本最小模型，并采用一種新的多種群混合遺傳算法進行尋優求解。為克服標準遺傳算法SGA（standard genetic algorithm）局部尋優能力較差的缺陷，將SGA與交替定位分配算法ALA（alternative location and allocation algorithm）[4]結合形成混合遺傳算法。針對電動汽車充電站規劃的多目標性，改善SGA的未成熟收斂現象和交叉、變異概率的取值對搜索結果有較大影響的問題，引入多種群概念[5]，并最終形成多種群混合遺傳算法MPHGA（multiple-population hybrid genetic algorithm）。為了避免算法尋優結果所示站點位置不適宜建設充電站，借助地理信息系統GIS（geographical information system）[6]，考慮地理信息對站址選擇的影響。在適應度函數中引入經濟適應度因子和地理適應度因子，實現站址經濟性和可行性的雙重優化搜索。通過某市規劃實例驗證了該模型和算法的正確性和有效性，為未來電動汽車充電站規劃提供一套完善的理論。

1 充電站綜合成本最小模型

為體現充電站網絡建設的社會綜合效益最大化，本文建立充電站綜合成本最小模型。模型中不僅考慮充電站的建設運行成本最小，還考慮充電者的充電成本最小。

本文采用面向充電需求的不規則分區來進行充電站服務區域劃分，服務分區內每個小區的充電需求用處于其幾何中心的點即充電需求點表示[2]。因此，基于規劃目標年電動汽車充電需求的充電站站址和容量的優化問題采用充電站綜合成本最小模型描述為

式中：C為各服務分區成本總和；f1為充電站的建設運行成本（折算到每年）；f2為充電者的充電成本（不含充電電量的費用）；λ1、λ2為權重因子，0≤λi≤1，i=1、2，且λ1+λ2=1；λ1、λ2的大小由充電站網絡規劃決策人員在綜合考慮社會效益的情況下決定，在充電站網絡建設的不同階段（示范階段、公益階段、商業運營階段）[2]可有側重性的選取不同的λi值。

式中：n為新建充電站數量；Si為充電站i的容量；C1（Si）為充電站i的建設投資成本；C2（Si）為充電站i的運行、維護費用；γ0為貼現率；mi為充電站i的折舊年限。

式中：N為新建和現有充電站數量總和；Ji為分區i內充電需求點集合；K為充電者出行時間價值；?為公路曲折系數（隨機取1.0～1.5）；lij為充電需求點j到充電站i的直線距離，； mij為從充電需求點j到充電站i的充電汽車數量；v為電動汽車到達充電站的平均行駛速度；H為充電電價；G為充電過程中的單位耗電量充電行程；S0為標準充電站的容量；T0為電動汽車在標準充電站正常充電過程所花時間；表示充電者從需求點j駛往充電站i的所花時間的成本；H表示充電者駛往充電站所耗費的電量成本表示充電者在充電站充電所花時間的成本；此處考慮了充電站規模大小對充電者的等待及充電時間的影響，即e（Si/S0-1）2T0。

約束條件如下。

（1）在考慮一定冗余度的情況下，各充電站容量之和需要滿足規劃區內的充電容量需求。充電站容量約束條件為

式中：η為充電站容量冗余系數，其值大小可根據充電站建設情況及充電需求確定，現考慮η∈[1.5，2.0]；Q為規劃區內的充電需求容量（由前期預測得到）。

（2）由于受到投資成本總額的限制，充電站建設總成本需要控制在建設投資上限以內。充電站投資約束條件為

式中，M為到規劃目標年充電站建設投資上限。

（3）為了保證充電站均勻分布并具有合理的服務半徑，充電站站址的間距不能過大或過小。充電站間距約束條件為

式中：d為相鄰充電站間的間距；α、β為間距上下限，其取值需綜合考慮電動汽車的續航里程及充電需求點的密度大小。

2 地理信息的處理

地理信息系統（GIS）[6]能為充電站站址提供足夠的位置信息和屬性數據，為充電站選址的優化決策提供依據。

在充電站選址時，充電站站址在GIS中被看作一個點，而站址所坐落的地塊可看成是由幾個頂點的多段線組成的閉合區域。GIS中所含的各個地塊的相關信息決定了所選站址是否適合建設充電站。在GIS中不適宜建站區域一般有兩種表現形式：一種是圓形；另一種是不規則的多段線組成的閉合區域。站址點和不適宜建站區域的拓撲關系通常分為3種：點在區域內；點在區域的邊界上；點在區域外[6]。

采用射線法來判斷站址點與不適宜建站區域的拓撲關系，即：如果點在區域內部，則從此點出發，經一定的方向作射線，此射線和圍成區域的邊的交點數量為奇數；如果點在區域外，則交點數量為偶數[6]。具體判斷方法如圖1所示。

圖1 射線法判斷點和區域的拓撲關系Fig.1 Radial method for point and grid topological relationship

若采用射線法判斷出站址點落在不適宜建站區域內，則在當前點附近選取可行點為新站址。

3 多種群混合遺傳算法

為解決遺傳算法在求解多目標優化問題時存在的未成熟收斂問題，針對充電站規劃的多目標性，本文采用多種群遺傳算法的思想。該算法中多個種群使用同一目標函數，各種群的交叉率和變異率取不同的值，以搜索不同解空間中的最優解，種群之間定期進行信息交換[7]。為加強算法的局部尋優能力，本文結合交替定位分配算法（ALA），在每個子種群中每一代的選擇、交叉、變異操作之后，增加一個定位分配操作，從而形成多種群混合遺傳算法（MPHGA）。算法的具體結構示意如圖2所示。

圖2 多種群混合遺傳算法結構示意Fig.2 Scheme of multiple-population hybrid genetic algorithm structure

本文的混合遺傳算法HGA（hybrid genetic algorithm，）是在標準遺傳算法（SGA）的遺傳算子之后增加一個定位分配算子，并結合GIS對搜索結果進行篩選。HGA的具體算法流程如圖3所示。圖中nmin和nmax分別為在滿足充電站容量需求的情況下，考慮各種充電站容量組合后，所需要新建的充電站數量最小、最大值。

圖3 HGA算法流程Fig.3 Flow chart of HGA

3.1 多種群定義

本文定義1+t個進化種群和1個精英種群，其中1～t種群為子種群，第t+1種群為父種群。每個進化種群采用本文提出的混合遺傳算法（HGA）。每個子種群對應于一個單獨的目標函數（f1，f2，…，ft），父種群對應于歸一化的目標函數（C）。精英種群不參與遺傳操作，用于保存其他兩類進化種群進化所得的最優個體。

3.2 編碼策略

本文采用三維編碼策略表示充電站的站址和容量信息。采用浮點數編碼方法，用連續的實數編碼直接表示站址坐標。采用符號編碼方法，用數字序號編碼直接表示充電站容量。染色體編碼示意圖如圖4所示。

圖4 染色體編碼示意Fig.4 Scheme of chromosome coding

圖中：一個個體表示一種選址定容方案，代碼長度n為規劃區需要新建的充電站數量。其中Xi、Yi、Si（i=1，2，…，n）分別表示新建充電站的站址橫、縱坐標和容量。

在選取初始種群時，對每個基因位置，隨機選取初始站址坐標和容量，其公式為

式中：Xmin、Xmax、Ymin、Ymax分別為選址平面內橫、縱坐標最小、最大值。μ、ν為[0，1]區間內的隨機數。rand{Q}為充電站設計規范中規范容量的隨機值。

3.3 綜合適應度函數

充電站的規劃結果不僅需要經濟性較優，還需要有很好的可行性。故本文建立基于經濟適應度因子和地理適應度因子的綜合適應度函數。綜合適應度函數為

式中：1/C表示經濟適應度因子，與綜合成本C成反比；φ表示地理適應度因子，取值范圍為（0，1.5），φ的值由規劃人員基于GIS對選址結果進行評價得到；a為評判方案是否符合約束條件式（4）、（5）、（6）而引入的懲罰因子。a取值范圍為

式中，ε為一個非常小的正數。

3.4 遷徙算子

遷徙算子將各種群在進化過程中出現的最優個體定期引入其他種群，實現各種群間的聯系及信息交流[7]。

3.5 遺傳算子

3.5.1 選擇算子

本文采用傳統的排序選擇方法[8]產生下一代群體。

3.5.2 交叉算子

本文采用兩種交叉算子：對表示充電站站址基因的浮點數編碼采用算術交叉算子，對表示充電站容量基因的符號編碼采用單點交叉算子。

算術交叉算子：由兩個個體的線性組合而產生兩個新的個體。假設在兩個站址基因之間進行算術交叉，則交叉運算后所產生的兩個新站址基因為

式中，τ取一常數，此處采用均勻算術交叉。

假定第z代的兩個雙親個體（省略容量基因）為

單點交叉算子：在個體染色體編碼串中隨機設置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體。假設第z代的兩個雙親個體（省略站址基因）為

如果隨機產生的交叉位置為3，則進行單點交叉計算，得到兩個新的第z+1代個體分別為

3.5.3 變異算子

本文采用兩種變異算子：對表示充電站站址基因的浮點數編碼采用非均勻變異[8]算子，對表示充電站容量基因的符號編碼采用基本位變異[8]算子。

非均勻變異算子：非均勻變異策略，即對原有基因值做隨機擾動，以擾動后的結果作為變異后的新基因值。假設對個體中變異點k進行變異操作，如橫坐標變異操作取值為

式中：φ為[0，1]范圍內符合均勻概率分布的一個隨機數；Z為最大進化代數；θ為一個系統參數，它決定了隨機擾動對進化代數z的依賴程度。

基本位變異算子：當∑S/η≥Q時，隨機選取一個變異位置，從充電站規范容量集里隨機選取一個容量S′取代原位置上的基因，且要求S′＜S；當∑S/η＜Q時，隨機選取一個變異位置，隨機選取一個容量S′取代原位置上的基因，且要求S′＞S。如果變異后個體不滿足∑S/η≥Q，則在適應度函數中通過參數a來表示懲罰。

3.6 定位分配算子

為加強算法的局部尋優能力，本文結合交替定位分配算法（ALA），在每個子種群中每一代的選擇、交叉、變異操作之后，增加一個定位分配操作。以個體Pz為例，即

定位分配算子的具體操作方法如下。

第1步（分配）：本文采用面向充電需求的不規則分區來進行充電站服務區域劃分[2]。對于個體P所代表的n個新建充電站，將所有的充電需求點劃分到n個集合（J1，J2，…，Jn）中。在滿足充電需求的情況下，將充電需求點分配到距離最近的充電站，實現充電站服務分區的確定。

第2步（定位）：對充電需求點集合采用平面單中位選擇方法（1-PMP）來確定每個分區的中位點坐標為式中：xj、yj為充電需求點j的橫縱坐標；Wj為充電需求權重，即充電需求點j所需的充電容量在分區i總容量中所占的比重。用新坐標代替原坐標即得到新個體Pz+1，再進行下一代的進化操作。

采用定位分配操作使得新建充電站的位置更加接近于分區的中位點，實現分區內所有充電需求點到充電站的總距離最短，從而提高遺傳算法的局部尋優能力，獲得最優解。

3.7 地理信息處理

借助GIS所提供的地理信息，考慮地理情況對所選站址的可行性的影響，避免所選站址落在不可建區域的情況出現。具體操作方法見本文的第2節。

3.8 最優保存策略

為避免遺傳操作將上一代出現的優良個體破壞，本文采用最優保存策略[4]將適應度最好的個體保留到下一代群體中。

3.9 人工算子

人工算子[7]可將父、子種群中的最優個體及時地保存在精英種群中，從而保證進化過程中良好信息能夠保存下來。

3.10 參數選取

本文的多種群混合遺傳算法（MPHGA）相關運行參數選取原則和標準遺傳算法[8]一致。

4 某市充電站規劃實例

以某小型城市的充電站規劃為例，該市現有1座配有12個充電機的小型充電站。經專業的充電需求量預測，到規劃年全市需要：若全部選擇大型充電站（至少16個充電機）則需要新建2座；若全部選擇小型充電站（最多8個充電機）則需要新建5座。該例中多種群混合遺傳算法的運行參數選取如下：群體大小NMPHGA=40，交叉概率pc和變異概率pm采用自適應思想計算而得，終止代數Z=250。

分別采用本文基于GIS的MPHGA算法、HGA算法、遺傳算法GA（genetic algorithm）和不基于GIS的MPHGA算法求解，得到規劃結果如圖5所示。圖中的●為已有充電站、▲為規劃新建充電站、○為充電需求點、虛線范圍為充電站服務分區、灰色區域為不適宜建站區域。

圖5 4種方法的規劃結果對比Fig.5 Contrast of four kinds of methods’prediction results

由圖5的規劃結果對比情況來看，本文提出的基于GIS的MPHGA算法能得到最優的規劃結果。（a）新建3個充電站，站址選擇合理；（b）新建3個充電站，但由于算法出現未成熟收斂現象，站址偏離最優位置；（c）新建4個充電站，充電站經濟性、充電站服務區域劃分和站址的選擇均不理想；（d）新建3個充電站，但由于沒有考慮站址的地理信息造成圖中左下方站址落在不適宜建站區域、右下方站址落在街道上，使得選擇的站址不具可行性。4種方法規劃結果的詳細技術、經濟參數對比如表1所示。

表1 4種方法規劃結果參數對比Tab.1 The parameters contrast of four kinds of methods’prediction results

從表1中的參數對比可以看出：本文提出的基于GIS和MPHGA的方法在搜索尋優能力上優勢明顯。該方法的尋優結果在充電站建設運行成本、充電者充電成本和總成本上均能達到最小。雖然地理信息的考慮使得充電者充電成本有所增加但是提高了方案的可行性，使得規劃結果更加科學、合理。

5 結論

電動汽車充電站的選址定容規劃是一個多目標、多約束、大規模、非線性的組合優化問題。本文針對該研究問題的特點，提出基于GIS和多種群混合遺傳算法（MPHGA）的新研究方法。該方法克服傳統方法的缺陷，很好地滿足充電站規劃的各方面需求。通過對某市的充電站規劃實例的優選結果分析，得到以下結論。

（1）多種群思想能很好地解決遺傳算法不成熟收斂問題，并滿足充電站規劃的“多目標性”。交替定位分配算法的融入能加強算法的局部搜索能力。與單純的HGA或GA相比，本文的多種群的混合遺傳算法（MPHGA）的全局和局部搜索能力都更強，具有更好地綜合尋優性能。

（2）本文基于GIS考慮站址的地理信息，能避免所選站址落在不適宜建設區域的情況出現。同時在適應度函數中引入地理適應度因子，使得最后的優選站址方案不僅具有很好的經濟性還具有很好的可行性，使規劃結果更加科學、合理。

（3）在本文建立的充電站綜合成本最小模型中，不僅考慮充電站的建設運行成本最小，同時還考慮充電者的充電成本最小，體現了充電站建設的社會綜合效益最大化目標，使得規劃結果更能滿足充電站的發展需要。

參考文獻：

[1]徐帆，俞國勤，顧臨峰，等（Xu Fan，Yu Guoqin，Gu Linfeng，et al）.電動汽車充電站布局規劃淺析（Tentative analysis of layout of electrical vehicle charging stations）[J].華東電力（East China Electric Power），2009，37 （10）：1678-1682.

[2]吳春陽，黎燦兵，杜力，等（Wu Chunyang，Li Canbing，Du Li，et al）.電動汽車充電設施規劃方法（A method for electric vehicle charging infrastructure planning）[J].電力系統自動化（AutomationofElectricPowerSystems），2010，34（24）：36-39，45.

[3]任玉瓏，史樂峰，張謙，等（Ren Yulong，Shi Lefeng，Zhang Qian，et al）.電動汽車充電站最優分布和規模研究（Optimal distribution and scale of charging station for electric vehicles）[J].電力系統自動化（Automation of Electric Power Systems），2011，35（14）：53-57.

[4]王成山，劉濤，謝瑩華（Wang Chengshan，Liu Tao，Xie Yinghua）.基于混合遺傳算法的變電站選址定容（Substation location and sizing based on hybrid genetic algorithm）[J].電力系統自動化（Automation of Electric Power Systems），2006，30（6）：30-34，47.

[5]葉在福，單淵達（Ye Zaifu，Shan Yuanda）.多種群遺傳算法在電網擴展規劃中應用的改進（A new transmission network expansion planning using improved multiplepopulation genetic algorithm）[J].電力系統及其自動化學報（Proceedings of the CSU-EPSA），1999，11（5-6）：55-61.

[6]劉自發，張建華（Liu Zifa，Zhang Jianhua）.基于改進多組織粒子群體優化算法的配電網絡變電站選址定容（Optimal planning of substation locating and sizing based on refined multi-team PSO algorithm）[J].中國電機工程學報（Proceedings of the CSEE），2007，27（1）：105-111.

[7] 余健明，吳海峰，楊文宇（Yu Jianming，Wu Haifeng，Yang Wenyu）.基于改進多種群遺傳算法的配電網規劃（An improved poly-population genetic algorithm based power distribution network planning）[J].電網技術（Power System Technology），2005，29（7）：36-40，55.

[8] 周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，1999.

[9]Davis L.Adapting Operator Probabilities in Genetic Algorithms[M].San Francisco：Morgan Kaufmann，1989.

[10]王小平，曹立明.遺傳算法—理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

[11]熊信銀，吳耀武.遺傳算法及其在電力系統中的應用[M].武漢：華中科技大學出版社，2002.

[12]王成山，魏海洋，肖峻，等（Wang Chengshan，Wei Haiyang，Xiao Jun，et al）.變電站選址定容兩階段優化規劃方法（Two-phase optimization planning approach to substation location and sizing）[J].電力系統自動化（Automation of Electric Power Systems），2005，29（4）：62-66.

[13]Sandy Thomas C E.Transportation options in a carbonconstrained world：hybrids，plug-in hybrids，biofuels，fuel cell electric vehicles，and battery electric vehicles[J].International Journal of Hydrogen Energy，2009，34（23）：9279-9296.

[14]Quintana V H，Temraz H K，Hipel K W．Two-stage power-system distribution planning algorithm [J].IEE Proceedings C，1993，140（1）：17-29.

[15]Lin W M，Tsay M T，Wu S W．Application of geographic information system for substation and feeder planning[J]．International Journal of Electrical Power and Energy System，1996，18（3）：175-183.

[16]周逢權，連湛偉，王曉雷，等（Zhou Fengquan，Lian Zhanwei，Wang Xiaolei，et al）.電動汽車充電站運營模式探析（Discussion on operation mode to the electric vehicle charging station）[J].電力系統保護與控制（Power System Protection and Control），2010，38（21）：63-66，71.

[17]康繼光，衛振林，程丹明，等（Kang Jiguang，Wei Zhenlin，Cheng Danming，et al）.電動汽車充電模式與充電站建設研究（Research on electric vehicle charging mode and charging stations construction）[J].電力需求側管理（Power Demand Side Management），2009，11（5）：64-66.

Electric Vehicle Charging Station Planning Based on Multiple-population Hybrid Genetic Algorithm

FENG Chao1，ZHOU Bu-xiang1，LIN Nan2，XU Fei1，LI Yang1，XIA Yu-hang1
（1.School of Electrical Engineering and Information，Sichuan University，Chengdu 610065，China；2.Sichuan Electric Power College，Chengdu 610071，China）

The electric vehicle charging station's minimum comprehensive cost model is established in the paper，which considers charging station'construction and operation cost and the cost of charging people.According to the characteristics of the electric vehicle charging station planning，a new kind of multiple-population hybrid genetic algorithm（MPHGA）is proposed.The algorithm combines the standard genetic algorithm（SGA）with alternative location and allocation algorithm（ALA）.According to the multi-objective of the charging station planning，the concept of multigroup is used to do collaborative evolution search.Based on the geographic information system（GIS），the geographic information'influence on the location of the charging station will be considered.The model and method are proved that they have great correctness and effectiveness by a charging station planning example of a city.

geographic information system（GIS）；multiple population；hybrid genetic algorithm；electric vehicle charging station；locating and sizing

TM715

A

1003-8930（2013）06-0123-07

馮 超（1987—），男，碩士研究生，從事調度自動化及計算機信息處理方面的研究。Email：634521532@qq.com

2011-11-10；

2011-12-31

周步祥（1965—），男，博士，教授，從事電力系統自動化、計算機應用等方面的研究。Email：hiway_scu@126.com

林 楠（1973—），女，碩士，講師，從事電力系統自動化、計算機應用的研究和教學。Email：cdlinlan@yahoo.com.cn