基于萤火虫算法的电动汽车充电站优化布局

邱金鹏，牛东晓，朱国栋

(华北电力大学 经济与管理学院，北京 102206)



基于萤火虫算法的电动汽车充电站优化布局

邱金鹏，牛东晓，朱国栋

(华北电力大学 经济与管理学院，北京 102206)

随着国家对节能环保设备的大力扶持，电动汽车市场规模不断扩大，充电站的投资不断增加。分析了电动汽车充电站选址的一般情况，综合考虑充电站与用户成本的综合效益成本最低条件下的运行情况，构建用户-充电站运营成本最小的综合优化模型，以充电站与用户之间的对应关系为约束条件，对充电站最优规划模型进行全面、充分地分析。所构建的电动汽车充电站规划问题是非凸、非线性、组合优化问题，引入萤火虫优化算法进行求解，萤火虫优化算法案例分析结果表明了该算法可以得到最优解，而不会陷入局部最优。结合构建的充电站成本最小模型，实例结果表明，基于萤火虫优化算法的电动汽车充电站的布局规划具有简单实用、全局最优、适应性强、经济性好等优点。

电动汽车；充电站；选址；萤火虫优化算法

0 引 言

电动汽车是目前流行最广、节能环保的绿色出行交通工具。随着电动汽车迅猛发展，与之相配套的充电站正成为一种新兴产业，电动汽车充电站行业发展潜力巨大，未来市场前景广阔。在日本，东电公司与各汽车厂商建立了密切的伙伴合作关系，计划在超市停车场、便利店及邮局等公共场所附近陆续建立充电站；而在法国巴黎，设有几百个充电站，凡重要停车场都设有充电站、配置电动汽车充电的专用插头。如何对电动汽车充电站进行合理布局，使其既方便电动汽车充电者充电，又节省建设成本已经成为城市规划部门、交通部门以及供电企业重点关注的问题。

目前，对于电动汽车充电站选址研究还较少，文献[1]以用户在充电路程中的损耗成本最小为目标进行选址，文献[2]运用动态交通网络思想建立了基于硬时间窗约束下的充电站布局及最佳规模确定的多目标优化模型，文献[3]建立了考虑建设成本等成本的综合优化模型，提出用差分进化混合粒子群算法进行求解，文献[4]建立考虑地理信息、建设成本和运行成本的综合优化目标函数，文献[5]以充电站收益最大化为目标函数，交通流量为约束条件，并运用模拟退火算法求解。目前电动汽车的选址研究成果并不完善，一方面是所建立的模型考虑不充分，多数学者只考虑了充电站的盈利目标，而没有对用户的成本进行了综合分析；另一方面考虑因素不全面[6-7]。

因此本文根据电动汽车用户以及待建电站的地址为基础，充分考虑用户成本，建立综合社会成本最小的最优站址的规划模型，基于萤火虫优化算法进行模型求解分析，通过仿真实验证明了该模型的有效性与可靠性。

1 萤火虫算法

萤火虫的发光行为为优化模型求解算法的设计提供思路。在算法设计中，忽略生物学的因素，而抽象其内在原理，主要通过发光进行搜索与移动，从而达到自身优化的目的。

通过模拟萤火虫发光的群体行为而设计的蛍火虫算法，基于的基本假设是：萤火虫发光亮度跟它们当前的位置有关，位置越好，发出的光亮度越高。因此，此时它有更大的吸引度，从而能吸引其范围内亮度不如它的其他萤火虫向其靠拢，而且它们之同的相对亮度与吸引度和距离成反比，这一点可以通过光的传播具有衰減来给于解释。在算法的实现中，利用问题的目标值来来衡量人工萤火虫的位置的好坏，而用迭代式子模拟萤火虫的搜索飞行移动，以此构造算法，逐步向问题的最优解移动，达到优化目的。

由于不同的模拟方式可以得到不同的表达式的算法：(1) 第一种模拟方式给出的算法叫作GSO[8](glowworm swarm optimization)；(2) 另一种模拟方式给出算法叫作FA (firefly algorithm)。两者的本质相同，只是描述方式具有一定差异。本文以GSO模型对充电站选址模型进行分析。

1.1 算法的数学描述与分析

定义1 荧光素更新

式中：J(xi(t))为每萤火虫i在t时刻位置xi(t)对应的目标函数值；li(t)表示t时刻第i只萤火虫的荧光素浓度；ρ为荧光素挥发系数；γ为荧光素增强因子。

定义2 概率选择

选择移向邻域集Ni(t)内个体j的概率为pij(t)：

其中，Ni(t)为邻域集：

定义3 位置更新

其中，s为移动步长。

定义4 动态决策域半径更新

式中：β表示领域变化率；nt表示邻居阈值(控制萤火虫的邻居数目)；|Ni(t)|表示邻居集合Ni(t)的元素数目(即邻居的个数)。

1.2 算法流程

算法步骤如下:

(1)给每个参数赋予初始值。

(2)以随机的方式给每一只萤火虫i(i=1,2…,n)赋予其在优化模型搜索空间中的位置。

(3)把通过式(1)得到的第t次迭代的萤火虫i的位置xi(t)所对应的目标值J(xi(t))转化为后面计算所需要的荧光素值li(t)。

(5)萤火虫i向Ni(t)中的萤火虫j移动的概率pij(t)通过式(2)计算得到。

(6)确定萤火虫i移动方向，通过上一步的概率pij(t)，利用轮盘赌选择萤虫j，再利用式(3)对其位置进行更新。

(7)依据式(4)来调整、更新感知半径。

(8)判断是否满足结束条件，若满足则执行(9)，若不然则转(4)。

(9)输出结果，程序结束。

图1 萤火虫算法流程图Fig.1 Flow chart of glowworm swarm optimization

2 最优选址模型建立

电动汽车充电站选址问题可以描述为在满足距离上限与电量需求的情况下，在备选站址中选择L个地点，以合理的规模设立充电站，为周围的电动汽车用户提供电源，使得在选出点建立的电动汽车充电站成本(包括前期建筑成本和实际运营成本)最低[9-13]，本文在充电站成本模型的基础上考虑用户成本，构建社会综合效益成本模型。

规划部门综合考虑充电站与用户之间的利益平衡，以此构建模型目标函数，其数学表达式如下：

式中：L为所建充电站的数量；C1i为充电站i每年的建设成本；C2i为充电站i每年的设备线路损耗以及运行维护成本；C3i为电动汽车用户每年在充电站i充电产生的费用；C4i为每年用户前往充电站进行充电所消耗的费用。

充电站i每年的建设成本数学表达式如下：

式中：ni为建设充电站i所需要安装的充电桩数量；d为其整套设备的单价，fi为充电站i基础设施的建设成本；w为充电站i的设计寿命，r为贴现率。

充电站每年的设备线路损耗以及运行维护成本主要包括设备零部件等的磨损消耗、线路损耗、充电损耗、检修运营费用等。由于检修运营费用一般不确定，可以根据其占初始投资一定的比值计算得出，令比值为ɑ，那么充电站i每年的设备线路损耗以及运行维护成本可表示如下：

式中：t为充电站每天的平均充电时间，λ为同时进行充电的充电桩占所有充电桩的比率，p1为充电站的用电单价，Ca、Cb、Cc分别表示设备零部件等的磨损消耗、线路损耗、充电损耗折算到单个充电桩上的损耗值。

电动汽车用户每年在充电站i充电产生的费用数学表达式为

式中：p2为用户的充电单价，Qi为充电站i平均每天的充电需求。

每年用户前往充电站进行充电所消耗的费用不仅包括用户前往充电站进行充电的损耗费用，还包括用户充电过程的时间价值。因此，每年用户前往充电站进行充电所消耗的费用的数学表达式为

式中：M为充电站i的充电需求点的数量；sij为需求点j到充电站i的距离；qj为每天充电需求点j处需要充电的汽车数量；h为电动汽车平均单位电量的行驶路程；v为电动汽车的平均行驶速度；g为用户的平均出行时间价值，可依据充电需求点处居民的平均收入估算得出。

电动汽车的充电需求可通过道路上的交通流量估算得出。设节点z处有u条道路与其相连，ze表示在t时刻与节点z相连的第e条道路上的交通流量密度，那么节点z在t时刻的交通流量密度为

计算一个路段的交通流量密度应当取某一时刻从该路段同一个方向流入或流出该节点的车流量。那么T时间段内z节点处的充电需求为

式中：y为电动汽车的平均容量，μ为车流中需要充电的电动汽车所占的比例。如果充电站i服务区域内有Z个节点，那么充电站i在T时间内的充电需求为

那么为了满足充电站i服务范围内所有电动汽车的充电需求，应该安装的充电桩的数量ni的数学表达式如下：

式中：θ为充电站i的充电容量裕度；P为单个充电桩的充电功率；η为充电桩的充电效率。

上述模型的约束条件为

(15)

(16)

Dmin≤dij≤Dmax

(17)

式中：Mi为备选站址集合。式(15)规定了备选充电站站址的数量为N，其中hz为0-1变量，表示充电站与用户之间的分配关系，当hz=1时，表示节点z被选为充电站站址，否则hz=0。式(17)中dij为充电站i与j之间的距离，满足两个充电站的最大与最小间距，保证了充电站规划的合理服务范围。

3 仿真实验及结果分析

以某地的电动汽车运行情况为例，采集此地区共33个电动汽车用户的坐标，由于每个电动汽车参数存在差别，其单位路程消耗电量也各不相同，由所建立的模型可知，充电站规划模型为多峰值函数模型，当充电站的数量不同时会有不同的运行结果：当充电站的数量增大时，每个充电站的容量降低，相应的运行成本降低，但是单台充电机的造价成本又逐渐上升；相反，充电站的数量较少时，单台充电机的造价成本又逐渐下降，可见，此充电站的规划研究，应该在成本与需求下取得平衡，得到规划最优解。

假设车流中需要充电的电动汽车所占的比例μ为12%，平均容量y为45 kW·h，单个充电桩的充电功率P为90 kW，充电容量裕度θ为20%，充电桩的充电效率η为0.95，电量电价按照0.6 元/kW·h计算，电动汽车的平均行驶速度v为30 km/h，根据该区域内的用户收入估算用户的平均出行时间价值g为20 元/h。以及用户位置及各电动汽车平均百公里路程消耗电量ki见表1所示。

结合站址最优规划模型与萤火虫算法，设置算法的参数为：种群规模为100，记忆库容量为10，迭代次数为100，交叉概率为0.5，变异概率为0.3，多样性评价参数设为0.98。

为了分析萤火虫算法求解此模型的适应性以及合理性，使用经典遗传算法与其进行结果对比分析。萤火虫算法(GSO)与遗传算法[14](GA)的收敛曲线如图2所示。

表1 用户位置及电动汽车参数

图2 萤火虫算法收敛曲线Fig.2 Convergence curve of glowworm swarm optimization

两种优化算法的寻优过程见图2所示，观察可得GSO在迭代到20代左右时已达到平稳状态，而GA模型波动较大，在50代之后才得到最优适应度值，另一方面GSO所得到的最优适应度小于GA运行结果，可见，从模型的运行效率以及优化结果上比较，GSO都明显优于GA算法。

充电站坐标、数量以及每个充电站的充电桩数量在两种模型分析下的最优规划结果见表2所示，而充电站运行以及用户的成本计算结果见表3所示。

表2 充电站坐标及数量最优规划结果

Tab.2 The optimal planning results of the coordinate and quantity of the charging station

GSO优化结果GA优化结果序号坐标充电桩数量序号坐标充电桩数量站址1(348,712)6站址1(371,735)5站址2(345,201)9站址2(331,310)8站址3(542,614)8站址3(568,635)7站址4(726,243)10站址4(518,287)9站址5(835,716)12站址5(725,275)10站址6(831,723)7

表3 充电站以及用户成本

从表2的运行结果可得，经过GSO与GA优化的结果该区域分别应建设5座、6座充电站，对表3中总成本进行分析，其中，C1、C2、C3、C4分别为充电站每年的建设成本、充电站每年的设备线路损耗以及运行维护成本、电动汽车用户每年在充电站充电产生的成本、用户前往充电站进行充电所消耗的成本。GSO得到更优的运行结果为2 514.32万元。对比两种模型优化的成本结果可以发现，规划建设6座充电站虽然在用户充电路途中的成本有所降低，但同时也导致了充电站建设成本、设备线路损耗以及运行维护成本、用户充电成本都有一定的上涨，最终导致了总成本的增加。对两种模型的规划坐标上分析可以发现，站址1、2、3的坐标较为接近，两者的不同存在地区的下半区域，由于该区域的用户分布密集，GSO模型运行时分配两座充电站进行补给，但GA模型规划了三座充电站，虽然用户的成本有所下降，但是应该考虑到建设成本的敏感性大于用户成本，所以导致结果偏大。

基于GSO与GA模型优化所得到的电动汽车站址优化方案如图3与图4所示。

图3 GSO优化的充电站选址分布Fig.3 Charging station location distribution optimized by GSO

图4 GA优化的充电站选址分布Fig.4 Charging station location distribution optimized by GA

由运行结果可得当站址个数为5时目标函数最优。寻优进化过程如图2所示，从图2可以看出，进化到20代时，最优适应度较为平稳。图3与图4分别展示了在GSO与GA模型优化后的站址中心与电动汽车用户之间的供求关系，可以发现站址基本都在用户中心，满足就近原则。可以看出，萤火虫算法可以快速地收敛到最优解，在成本最小的条件下满足实际运行情况，能有效解决电动汽车选址优化问题。

4 结 论

本文在总结已有研究的基础上，构建综合考虑了充电站与用户成本最小的电动汽车充电站规划模型，平衡了两者之间的经济性，克服以往研究的不足，并且基于一种萤火虫优化算法求解该问题。通过对某地区的电动汽车运行的仿真试验，结果表明利用本文所建立的优化模型可以有效地求解电动汽车充电站选址优化问题。但是实际此充电站规划问题是极其复杂的，里面应该考虑用户与充电站成本与利益分配问题以及各个复杂的多约束条件，还有待进一步的研究。

[1] 葛少云,冯亮,刘洪,等. 电动汽车充电站规划布局与选址方案的优化方法[J]. 中国电力, 2012，(11):54-61.

[2] 任玉珑, 史乐峰, 张谦,等. 电动汽车充电站最优分布和规模研究[J]. 电力系统自动化, 2011, 35(14):53-57.

[3] 赵书强, 李志伟. 基于差分进化粒子群算法的城市电动汽车充电站最优规划[J]. 华北电力大学学报, 2015, 42(2):1-7.

[4] 王成山,王赛一. 基于空间GIS和Tabu搜索技术的城市中压配电网络规划[J]. 电网技术, 2004,28(14):68-73.

[5] 康继光,卫振林,程丹明，等.电动汽车充电模式与充电站建设研究[J].电力需求侧管理, 2009,1l(5): 64-66.

[6] 田立亭,史双龙,贾卓.电动汽车充电功率需求的统计学建模方法[J]. 电网技术, 2010,34(11):126-130.

[7] 熊虎,向铁元,祝勇刚,等.电动汽车公共充电站布局的最优规划[J]. 电力系统自动化, 2012,36(23):65-70.

[8] 周季华,叶春明. 应用萤火虫算法求解置换流水线问题[J]. 计算机应用研究, 2013, 30(1):152-154.[9] 刘柏良,黄学良,李军,等. 含分布式电源及电动汽车充电站的配电网多目标规划研究[J]. 电网技术, 2015, 39(2):450-456.

[10] 黄小庆,杨夯,陈颉,等. 基于LCC和量子遗传算法的电动汽车充电站优化规划[J]. 电力系统自动化, 2015，39(17):176-182.

[11] 陆坚毅,杨超,肖来元,等. 基于单亲遗传算法混合动态规划的电动汽车充电调度优化策略[J]. 计算机工程与科学, 2015, 37(5):967-973.

[12] 陈连福. 电动出租车充电站布局规划研究[D]. 北京：北京交通大学, 2015.

[13] 高赐威,段天琪. 电动汽车换电站定址分容研究[J]. 电力需求侧管理, 2015，(1):2-8.

[14] 刘飞. 基于遗传算法的电动汽车充电站布局的最优规划[J]. 电力科学与工程, 2015，32(8):37-42.

Optimized Layout of Charging Station for Electric Vehicle Based on Firefly Algorithm

QIU Jinpeng, NIU Dongxiao, ZHU Guodong

(School of Economics and Management, North China Electric Power University, Beijing 102206, China)

Market size of electric vehicle keeps expanding and investment in electric vehicle charging station keeps increasing as Chinese government supports and advocates the development of energy saving and environmental protection equipment. This paper analyzed the general condition of site selection of electric vehicle charging station and comprehensively considered the operation situation in which the cost of charging station and users are the lowest. And then a comprehensive optimized model with lowest operation cost for users and charging station was established. Taking the corresponding relation between charging station and users as the constraint condition, the paper comprehensively analyzed the optimized model of the charging station. The planning of electric vehicle charging station is non-convex and non-linear, besides it is not about combination optimization. Firefly algorithm is introduced to solve the problem. The results of case study show that the result of the algorithm is the optimal solution rather than local optimum. By using the charging station model with lowest cost, the result of case study show that layout planning of electric vehicle charging station based on firefly algorithm boasts advantages such as simplicity, global optimum, adaptability and economical efficiency.

electric vehicle; charging station; site selection; firefly algorithm

10.3969/j.ISSN.1007-2691.2016.05.16

2016-01-04.

TM715

A

1007-2691(2016)05-0105-06

邱金鹏(1991-)，男，硕士研究生，研究方向为技术经济评价及管理；牛东晓(1962-)，男，博士生导师，研究方向为技术经济评价及管理；朱国栋(1992-)，男，硕士研究生，研究方向为技术经济评价及管理。