电动汽车充电站规划的多种群混合遗传算法

冯 超，周步祥，林 楠，徐 飞，李 阳，夏榆杭

（1.四川大学电气信息学院，成都 610065；2.四川电力职业技术学院，成都 610071）

电动汽车充电站规划的多种群混合遗传算法

冯 超1，周步祥1，林 楠2，徐 飞1，李 阳1，夏榆杭1

（1.四川大学电气信息学院，成都 610065；2.四川电力职业技术学院，成都 610071）

建立考虑充电站建设运营成本和充电者充电成本的电动汽车充电站综合成本最小模型。针对电动汽车充电站规划的特点，提出了一种新的多种群混合遗传算法（MPHGA）。该算法将标准遗传算法（SGA）与交替定位分配算法（ALA）结合，针对充电站规划的多目标性，采用多种群概念，建立多种群并进行协同进化搜索。基于地理信息系统（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