doi: 10.12052/gdutxb.200095
基于Voronoi图和改进引力搜索算法的
电动汽车充电站选址定容
赵炳耀1，陈璟华1，郭经韬2，陈友鹏1，张兆轩1
（1. 广东工业大学 自动化学院，广东 广州 510006；2. 中国能源建设集团 广东省电力设计研究院
有限公司，广东 广州 510663）
摘要: 电动汽车充电站的选址定容属于多变量、多约束及高维度的非线性数学问题, 针对该问题提出一种基于Voronoi图和改进引力搜索算法(Improved Gravity Search Algorithm, IGSA)的选址定容方法。综合考虑主观权值和客观权值, 运用层次分析熵权法, 建立以建设运行成本、用户充电时间成本及配网损耗成本为目标的电动汽车充电站选址定容多目标决策模型。针对标准引力搜索算法(Gravity Search Algorithm, GSA)收敛速度慢、求解高维度问题精度不足等问题, 在粒子初始化和更新阶段引入混沌映射, 增加算法遍历性; 同时, 引入全局最优点引导速度更新公式, 提高算法跳出局部最优的能力。利用Voronoi图划分充电站服务区域, 提出Voronoi图与IGSA联合求解流程。仿真结果证明了所建模型和算法的可行性和实用性。
关键词: 电动汽车；充电站；选址定容；Voronoi图；改进引力搜索算法
中图分类号: TM743 文献标志码: A 文章编号: 1007–7162(2021)03–0072–07
Location and Capacity of Electric Vehicle Charging Station Based on Voronoi Diagram and Improved Gravity Search Algorithm
Zhao Bing-yao1, Chen Jing-hua1, Guo Jing-tao2, Chen You-peng1, Zhang Zhao-xuan1
(1. School of Automation, Guangdong University of Technology, Guangzhou, 510006, China; 2. Guangdong Electric Power
Design Institute Co., Ltd., China Energy Engineering Group, Guangzhou 510663, China) Abstract: Considering the characteristics of location and capacity problems such as multi-variable, multi-constrained, high-dimensional and nonlinear, a method based on Voronoi diagram and improved gravitational search algorithm (IGSA) is proposed. Considering both subjective and objective weights, a multi-objective decision model considering construction costs, operation costs, user charging time costs and distribution network loss costs is established. In order to solve the slow convergence and the inadequate accuracy of standard gravitational search algorithm (GSA), a chaotic map is introduced in the particle initialization and updating phase to enhance the ergodicity of the algorithm. At the same time, a global optimal point to guide speed updating formula is introduced
to improve the ability of the algorithm to jump out of the local optimal. Voronoi diagram is used to divide service area of charging station, and a joint solution process of Voronoi diagram and IGSA is proposed. The simulation results prove the feasibility and validity of the model.
Key words: electric vehicles; charging station; location and capacity; voronoi diagram; improved gravity search algorithm
随着日益严峻的环境污染与化石能源问题，世界各国大力推进汽车电气化，把禁售燃油汽车提上日程，如荷兰、挪威禁售时间是2025年，印度是2030年，法国是2040年。我国采用分区域、分车类、分
第 38 卷 第 3 期广东工业大学学报Vol. 38 No. 3 2021 年 5 月Journal of Guangdong University of Technology May 2021
收稿日期：2020-07-30
基金项目：中央财政支持地方高校发展专项资金资助项目([2016]202号)
作者简介：赵炳耀(1995– )，男，硕士研究生，主要研究方向为电力系统优化规划、电动汽车充电站选址定容、智能算法
通信作者：陈璟华(1974–)，女，副教授，博士，主要研究方向为电力系统安全运行及人工智能技术在电力系统中的应用，E-mail：***************
阶段的方案，有望于2050年全面退出燃油汽车[1]。随着电动汽车数量快速增多，充电站数量也迅速增长。截止2019年9月，我国充电设施数量达到111.5万座，是国内加油站数量的10倍[2]。尽管充电站数量庞大，但是充电难问题依然存在。充电站分布不合理、“跑马圈地”式建设导致充电站要么不堪重负，要么闲置率极高。因此充电站的合理规划非常必要。
电动汽车充电站选址定容问题是多变量、多约束、高维度的非线性优化问题。目前，该问题的研究仍处在起步阶段，尚未形成完整的理论体系。文献[3]提出交通满意度模型，结合加权Voronoi图和遗传算法，进行多场景分析；文献[4]提出目标为最大充电网络服务能力和最小配电系统网络损耗的多目标优化模型，模糊化处理后采用遗传算法进行求解；文献[5]综合考虑充电站建设成本与用户广义充电成本，引入便捷系数概念，提出多种规划目标的取值建议；文献[6]提出以最大化满足路径中需求与最小化平均等待时间为目标的混合整数规划模型，求解后得出选址定容问题的3大关键要素；文献[7]通过分析用户出行行为和充电习惯，提出兼顾运营商利益与用户充电需求的规划模型；文献[8]把用户碳排放量作为充电站规划考核指标之一，并采用帕累托最优前沿分析可选的方案；文献[9]依据城市道路信息，确定充电站最优位置分布，再运用Voronoi图划分充电站所服务的负荷区，确定其容量。上述研究成果均片面考虑用户或运营商的利益，考虑的因素不够全面，在实际推行过程中可能会遇到较大阻力。
文献[10]建立的模型虽考虑了充电站运营商、电动汽车用户以及电网企业三者的综合利益，但电网侧利益是通过设备损耗来简单折算，与实际运行情况存在较大差距。文献[11]建立的模型选中了多个交通节点作为最优站址；文献[12]建立的模型是在规划范围内随机生成站点，运用改进PSO算法求得最优站址。上述研究得出的最优站址在现实中不一定具备建站条件，实用性偏低。
本文综合多种约束条件，建立以建设运行成本、用户充电时间成本、配网损耗成本为目标的电动汽车充电站选址定容多目标决策模型；针对多目标决策难问题，引入层次分析熵权法进行决策；针对标准引力搜索算法收敛速度慢，求解高维度问题精度不足的缺点，引入混沌理论以及全局最优来引导粒子速度更新；针对选址定容模型的求解，引入Voronoi 图划分充电站服务区域，与改进引力搜索算法联合求解。小区几何分布与IEEE30节点系统的算例表明本模型及算法具有较高的可行性。
1 电动汽车充电站选址定容数学模型
电动汽车充电站属于公共服务设施，在进行规划时不仅要考虑运营商的效益，还应考虑用户便利程度等多个因素。本文在考虑潮流、充电站规模等约束条件下，提出以建设运行成本、用户充电时间成本及配网损耗成本为目标的电动汽车充电站选址定容数学模型。
1.1 目标函数
1.1.1 建设运行成本
建设运行成本包括建设成本和运行成本[13]。建设成本C con主要包括充电桩、土地、变压器等费用，如式(1)所示。
其中，r0为贴现率；n year为折旧年限；C g
为固定投资成本；n char为站内充电桩数量；φ是配电变压器和输电线路等相关设备成本的等效投资系数；ε为充电桩的单价。运行成本C op主要有人力成本、设备维护成本等，如式(2)所示。
其中，γ为人工、设备运行维护成本折算系数。综上，充电站年建设运行成本f1的目标函数为
其中，I为充电站合集；i为充电站；C con i和C op i分别为充电站i的建设成本和运行成本。
1.1.2 用户充电时间成本
用户充电时间成本包括电动汽车前往充电站的时间成本及站内排队等待的时间成本[12]。假设用户
在充电站内的排队过程符合M/M/s排队模型，充电站i 的排队等待期望W i为
其中
其中，ρ=D/ψ为充电桩服务强度，D为充电需求量，ψ为充电桩服务效率；p0为充电桩全部闲置概率。
用户前往充电站的行驶时间t DA与站内排队等待时间t WA如式(6)与式(7)所示。
第 3 期赵炳耀，等：基于Voronoi图和改进引力搜索算法的电动汽车充电站选址定容73
其中，I 为充电站合集；J 为需求点合集；μ为道路曲折系数；D j 为需求点j 的充电需求量；E ij 为0或1，若需求点j 选择充电站i 充电，则E ij 为1，反之为0；d ij 为需求点j 与充电站i 的欧氏距离；v
q 为汽车平均行驶速度；W i 为充电站i 的排队等待期望。
则用户充电时间成本f 2的目标函数为
其中，C cut 为用户单位时间成本。1.1.3 配网损耗成本
电动汽车充电站的大规模接入会对电网产生一定影响，如网损增加、频率下降、电压下降。为降低电动汽车充电负荷对电网的影响，提高电网公司效益，本文在充电站选址定容中计算配网损耗[14]
。其计算公式为
其中，P Loss 为配网损耗，用功率表示；N 为节点集合；
G hk 为节点h ,k 之间的电导；U h 为节点h 电压；U k 为节点
k 电压；δhk 为节点h ,k 的功角差。
所以配网损耗年成本f 3的目标函数为
其中，t CH 为充电站日运行时间；C fa 为电价。
1.2 约束条件1.
2.1 潮流约束
其中，B hk 为节点h
, k 之间的电纳；P GE h 和P CH h 分别是
电网节点h 的发电机有功功率和充电站有功功率；Q GE h 和Q CH h 分别是电网节点h 的发电机无功功率和充电站无功功率，Y 为电网中的支路集合，θhk 为节点h ，k 之间的电压相差角。1.2.2 支路视在功率约束
其中
S max
hk 其中，是节点h , k 中视在功率的上限，P hk 是节点h ,
k 中有功功率，Q hk 是节点h , k 中无功功率。1.2.3
节点电压约束
其中，U h min 和U h max 分别是节点h 的电压下限和上限。
1.2.4 充电站数量约束
其中，n CH,min 和n CH,max 分别是候选充电站最小和最大数量。
1.2.5 站内充电桩数量约束
其中，n char,min 和n char,max 分别是充电站内允许安装充电桩的最小和最大值。
1.3 基于层次分析熵权法的多目标决策
在对多目标问题进行决策时，采用层次分析法得到的权值虽反映了专家的经验和决策者的意向和偏好等主观因素，但不能反映各个目标函数之间的客观博弈结果，主观随意性较大。如采用熵权法决策，虽得到的权值较为客观，但不能反映专家的经验和决策者的意见，得到的权重可能与实际情况有偏差，甚至相违背。因此，本文综合上述
2种决策方法的优缺点，提出了层次分析熵权法[15]，该方法可以避免过度依赖主观权值或客观权值而导致的决策偏差。
F =(F 1,F 2,···,F z ,···,F
Z )M =(M 1,M 2,···,M z ···,M Z )λz 假定现有目标数为Z 的决策问题，采用层次分析法计算得到权值矩阵为，采用模糊权法计算得到权值矩阵为，由式(17)得到综合了层次分析法和熵权法后的权值。
移动汽车网综上，本文采用层次分析熵权法把电动汽车充电站选址定容的多目标问题转化为单目标问题，目标函数如式(18)所示。
2 改进引力搜索算法
2.1 标准引力搜索算法(GSA)
引力搜索算法(GSA)于2009年由Esmat Rashedi 提出，是一种受万有引力定律以及牛顿第二定律启
74
广 东 工 业 大 学 学 报第 38 卷
发的优化算法[16]。引力搜索算法与粒子算法相似，通过不断改变种粒子的位置来寻最优解。GSA 算法在迭代过程中，把粒子看作存在一定质量的物体，相互之间存在引力。粒子的适应度越大，其惯性质量越大，引力就越大；适应度越小的粒子惯性质量越小，引力也越小。质量小的粒子容易被质量大的粒子吸引并移动。因此，每代可能接近全局最优的粒子质量最重，其吸引力也最大。随着算法的循环，粒子靠它们之间的万有引力在搜索空间内不断运动，当粒子移动到最优位置时，最优解便到了。其速度和位置更新公式为
其中，π为当前代数；v e (π)表示粒子e 的速度；x (π)为第π次更新后的状态值；R 是区间[0,1]间的随机数，a e (π)是粒子e 的加速度。
2.2 改进引力搜索算法(IGSA)2.2.1 引入组合混沌映射策略
GSA 算法在初始化阶段随机生成初始种，不利于种的多样性和遍历性，因此本文采用Logistic 映射与Tent 映射相结合，将其应用于种初始化与寻优过程，增加粒子遍历性，提高收敛性能，其表达公式为
其中，x 0, y 0是粒子初始值，x π+1, y π+1是更新后状态值，temp 为待求余状态值，ξ是Logistic 混沌系数，
mod()为取余函数。
2.2.2 引入全局最优点引导的自适应移动策略
标准GSA 算法在粒子移动阶段仅考虑了当前位置信息，缺少记忆性，寻优效率及效果较差，特别是在求解高维优化问题时容易陷入局部最优。受粒子算法启发，在粒子移动阶段，引入全局最优点GB
来引导速度更新[17]，其更新公式为
其中，GB 是全局最优点，c 1和c 2是加速因子，其表达式为
其中，
Φ为最大迭代次数。
3 基于Voronoi 图和改进引力搜索算
法的选址定容
3.1 Voronoi 图及服务区域划分
Voronoi 图，又名泰森(Thiessen)多边形，于1908年由M. G. Voronoi 提出，由一组连接两邻点直线的垂直平分线形成的连续多边形组成。Voronoi 图生成方法如图1所示。设生长点集合H ={H 1,H 2,H 3,···,H L }, 3≤L ≤∞，则Voronoi 图的数学表述为
b ,l =1,2,···,L b l H b b d (u ,H b )u H b 其中，，且；和H
l 为平面上生长点和 l ；和d (u ,H l )为任意一个点与点和H l 点间的欧氏距离。
图 1 Voronoi 图生成方法
Fig.1 Voronoi diagram generation method
利用Voronoi 图，进行服务区域划分。把充电站的选址集合视为二维平面上的点集，需求点视为平面上的点。以充电站点集为生长点作Voronoi 图，由
Voronoi 图特点可知，充电站服务区域内的需求点到该充电站的距离应小于等于到其他充电站的距离，满足车主就近选择充电站原则。
3.2 求解步骤
步骤1
：初始化数据，输入规划区的面积、人口密度、需求点和候选点的具体坐标、需求点的负荷信息、配
网结构等参数信息，根据式(25)折算各需求点电动汽车数量。
其中，n car i 是需求点i 的电动汽车数量；A 是规划区占地面积；α是人口密度；β是人均汽车保有量；η是电动汽车占比；O i 为需求点i 的电荷，O Σ为需求点总电荷。
步骤2：生成初始种，粒子具体编码方式为
例如当ω=3，x =[1 5 8 10 20 30]指选取了1、5、8号候选站，对应站内充电桩数目分别为10、20、30。如种粒子数为m ，则初始种编译为
第 3 期赵炳耀，等：基于Voronoi 图和改进引力搜索算法的电动汽车充电站选址定容75
步骤3：对步骤2生成的初始种归一化处理，再进行m–1次混沌操作，然后反归一处理。
步骤4：依据建站数量和建站规模，由式(3)得到建设运行成本f1。
步骤5：把候选站址坐标作为生长点作Voronoi 图，划分各充电站服务范围。由式(4)和式(8)计算出用户充电时间成本f2。
步骤6：将候选站址接入配网后并进行潮流计算，由式(10)得到配网损耗成本f3。
步骤7：依据改进策略更新粒子位置和速度，并对粒子按步骤3进行混沌操作。
步骤8：由层次分析熵权法得到的λ1、λ2、λ3代入式(18)，将多目标函数变为单目标函数，记录个体最优和全局最优。
步骤9：重复步骤4~8，直至满足收敛条件，输出全局最优值。
4 算例分析
以某市规划区为例进行分析，该区占地面积为12.1 km2，人口密度为7 000人/km2，人均汽车保有量
为19%，其中电动汽车占30%。规划区包含21个小区
位置重心(需求点)和根据实际情况确定的9个候选站址(候选点)，假设其对应IEEE30节点系统，需求点、候选点具体坐标和对应接入的节点号如表1所示。其中，1~34号为需求点，35~43号为候选点。
假设该规划区电动汽车型号为比亚迪E2，电池容量为35.2 kW；充电站固定投资成本为300 万元/座；折算到充电桩的等效投资系数为2 万元/台；充电桩价格为10
万元/台；站内允许安装充电桩的最小数量为8台；站内允许安装充电桩的最大数量为45台；人工、设备运行维护成本折算系数为0.1；贴现率为0.08；折旧年限为20年；道路曲折系数为1.3；车辆平均行驶速度为35 km/h；用户单位时间成本为20 元/h；充电桩额定功率为120 kW；充电效率为0.9；充电站日运行时间为12 h；电价为0.6 元/kW·h。IGSA算法参数设置为：种规模为20，迭代次数最大值为500，引力常数初始值为100，引力系数衰减因子为30。
根据3.2节求解步骤，建不同数量候选站的计算成本如图2所示。由图2可知，若建站数量过少会由于用户时间成本的增加而导致综合总成本过高；而建站数量过多又会由于建设运行成本和配网损耗成本的
增加导致综合成本过高。
图 2 不同建站数量的综合成本
Fig.2 Calculation result of selecting different number of candidate stations
由图2可知，当建站数量为5个时，综合总成本最低，为2 099.7 万元。具体站点分布、服务区域划分以及配置的充电桩数量如图3所示，图中圆点为需求点，方形为候选点，其中实心方形为被选中的候选点，实心方形旁的数值为选中充电站安装的充电桩数量，网状直线由Voronoi图生成，即服务区域划分表 1 需求点、候选点坐标和节点号
Table 1 Demand point, candidate point coordinates and node number
序号节点坐标/km序号节点坐标/km
12(0.34,2.64)2315(3.05,2.49)
22(0.34,2.17)2416(2.82,2.24)
32(0.37,1.72)2517(3.05,2.25)
43(0.79,2.64)2618(2.81,1.99)
54(0.79,2.19)2719(3.04,1.99)
65(0.82,1.64)2820(2.93,1.67)
75(1.37,2.62)2921(2.93,1.10)
85(1.28,2.07)3023(2.59,0.66)
95(1.36,1.55)3124(3.66,2.58) 105(1.96,2.48)3226(3.72,1.75) 115(1.74,2.03)3329(3.69,1.05) 125(1.87,1.61)3430(3.68,0.48) 135(1.85,1.20)351(0.86,1.74) 145(2.31,2.71)366(1.96,0.84) 155(2.57,2.70)379(3.23,0.35) 167(2.43,2.38)3811(3.88,2.57) 177(2.44,1.86)3913(3.96,1.66) 188(2.37,1.42)4022(2.06,1.94) 198(2.40,1.13)4125(2.64,1.55) 2010(2.82,2.72)4227(0.51,2.38) 2112(3.04,2.71)4328(2.64,2.55) 2214(2.82,2.49)
76广 东 工 业 大 学 学 报第 38 卷
发布评论