基于Voronoi图和改进引力搜索算法的电动汽车充电站选址定容

2021-04-12赵炳耀陈璟华郭经韬陈友鹏张兆轩

广东工业大学学报 2021年3期

赵炳耀，陈璟华，郭经韬，陈友鹏，张兆轩

（1. 广东工业大学自动化学院，广东广州 510006；2. 中国能源建设集团广东省电力设计研究院有限公司，广东广州 510663）

随着日益严峻的环境污染与化石能源问题，世界各国大力推进汽车电气化，把禁售燃油汽车提上日程，如荷兰、挪威禁售时间是2025年，印度是2030年，法国是2040年。我国采用分区域、分车类、分阶段的方案，有望于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]。建设成本Ccon主要包括充电桩、土地、变压器等费用，如式(1)所示。

其中，r0为贴现率；nyear为折旧年限；Cg为固定投资成本；nchar为站内充电桩数量；φ是配电变压器和输电线路等相关设备成本的等效投资系数；ε为充电桩的单价。运行成本Cop主要有人力成本、设备维护成本等，如式(2)所示。

其中，γ为人工、设备运行维护成本折算系数。综上，充电站年建设运行成本f1的目标函数为

其中，I为充电站合集；i为充电站；Cconi和Copi分别为充电站i的建设成本和运行成本。

1.1.2 用户充电时间成本

用户充电时间成本包括电动汽车前往充电站的时间成本及站内排队等待的时间成本[12]。假设用户在充电站内的排队过程符合M/M/s排队模型，充电站i 的排队等待期望Wi为

其中，ρ=D/ψ为充电桩服务强度，D为充电需求量，ψ为充电桩服务效率；p0为充电桩全部闲置概率。

用户前往充电站的行驶时间tDA与站内排队等待时间tWA如式(6)与式(7)所示。其中，I为充电站合集；J为需求点合集；μ为道路曲折系数；Dj为需求点j的充电需求量；Eij为0或1，若需求点j选择充电站i充电，则Eij为1，反之为0；dij为需求点j与充电站i的欧氏距离；vq为汽车平均行驶速度；Wi为充电站i的排队等待期望。

则用户充电时间成本f2的目标函数为

其中，Ccut为用户单位时间成本。

1.1.3 配网损耗成本

电动汽车充电站的大规模接入会对电网产生一定影响，如网损增加、频率下降、电压下降。为降低电动汽车充电负荷对电网的影响，提高电网公司效益，本文在充电站选址定容中计算配网损耗[14]。其计算公式为

1.2 约束条件

1.2.1 潮流约束

其中，Bhk为节点h, k之间的电纳；PGEh和PCHh分别是电网节点h的发电机有功功率和充电站有功功率；QGEh和QCHh分别是电网节点h的发电机无功功率和充电站无功功率，Y为电网中的支路集合，θhk为节点h，k之间的电压相差角。

1.2.2 支路视在功率约束

1.3 基于层次分析熵权法的多目标决策

在对多目标问题进行决策时，采用层次分析法得到的权值虽反映了专家的经验和决策者的意向和偏好等主观因素，但不能反映各个目标函数之间的客观博弈结果，主观随意性较大。如采用熵权法决策，虽得到的权值较为客观，但不能反映专家的经验和决策者的意见，得到的权重可能与实际情况有偏差，甚至相违背。因此，本文综合上述2种决策方法的优缺点，提出了层次分析熵权法[15]，该方法可以避免过度依赖主观权值或客观权值而导致的决策偏差。

2 改进引力搜索算法

2.1 标准引力搜索算法(GSA)

引力搜索算法(GSA)于2009年由Esmat Rashedi提出，是一种受万有引力定律以及牛顿第二定律启发的优化算法[16]。引力搜索算法与粒子群算法相似，通过不断改变种群粒子的位置来寻找最优解。GSA算法在迭代过程中，把粒子看作存在一定质量的物体，相互之间存在引力。粒子的适应度越大，其惯性质量越大，引力就越大；适应度越小的粒子惯性质量越小，引力也越小。质量小的粒子容易被质量大的粒子吸引并移动。因此，每代可能接近全局最优的粒子质量最重，其吸引力也最大。随着算法的循环，粒子靠它们之间的万有引力在搜索空间内不断运动，当粒子移动到最优位置时，最优解便找到了。其速度和位置更新公式为

其中，π为当前代数；ve(π)表示粒子e的速度；x(π)为第π次更新后的状态值；R是区间[0,1]间的随机数，ae(π)是粒子e的加速度。

2.2 改进引力搜索算法(IGSA)

2.2.1 引入组合混沌映射策略

GSA算法在初始化阶段随机生成初始种群，不利于种群的多样性和遍历性，因此本文采用Logistic映射与Tent映射相结合，将其应用于种群初始化与寻优过程，增加粒子遍历性，提高收敛性能，其表达公式为

其中，x0, y0是粒子初始值，xπ+1, yπ+1是更新后状态值，temp为待求余状态值，ξ是Logistic混沌系数，mod()为取余函数。

2.2.2 引入全局最优点引导的自适应移动策略

标准GSA算法在粒子移动阶段仅考虑了当前位置信息，缺少记忆性，寻优效率及效果较差，特别是在求解高维优化问题时容易陷入局部最优。受粒子群算法启发，在粒子移动阶段，引入全局最优点GB来引导速度更新[17]，其更新公式为

其中，GB是全局最优点，c1和c2是加速因子，其表达式为

其中，Φ为最大迭代次数。

3 基于Voronoi图和改进引力搜索算法的选址定容

3.1 Voronoi图及服务区域划分

Voronoi图，又名泰森(Thiessen)多边形，于1908年由M. G. Voronoi提出，由一组连接两邻点直线的垂直平分线形成的连续多边形组成。Voronoi图生成方法如图1所示。设生长点集合H={H1,H2,H3,···,HL}, 3≤L≤∞，则Voronoi图的数学表述为

其中， b,l=1,2,···,L ，且b ≠l ； Hb和Hl为平面上生长点 b 和 l；d (u,Hb) 和d(u,Hl)为任意一个点u 与点 Hb和Hl点间的欧氏距离。

图1 Voronoi图生成方法Fig.1 Voronoi diagram generation method

利用Voronoi图，进行服务区域划分。把充电站的选址集合视为二维平面上的点集，需求点视为平面上的点。以充电站点集为生长点作Voronoi图，由Voronoi图特点可知，充电站服务区域内的需求点到该充电站的距离应小于等于到其他充电站的距离，满足车主就近选择充电站原则。

3.2 求解步骤

步骤1：初始化数据，输入规划区的面积、人口密度、需求点和候选点的具体坐标、需求点的负荷信息、配网结构等参数信息，根据式(25)折算各需求点电动汽车数量。

其中，ncari是需求点i的电动汽车数量；A是规划区占地面积；α是人口密度；β是人均汽车保有量；η是电动汽车占比；Oi为需求点i的电荷，OΣ为需求点总电荷。

步骤2：生成初始种群，粒子具体编码方式为

例如当ω=3，x=[1 5 8 10 20 30]指选取了1、5、8号候选站，对应站内充电桩数目分别为10、20、30。如种群粒子数为m，则初始种群编译为

步骤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，人口密度为7000人/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可知，若建站数量过少会由于用户时间成本的增加而导致综合总成本过高；而建站数量过多又会由于建设运行成本和配网损耗成本的增加导致综合成本过高。

表1 需求点、候选点坐标和节点号Table 1 Demand point, candidate point coordinates and node number

图2 不同建站数量的综合成本Fig.2 Calculation result of selecting different number of candidate stations

由图2可知，当建站数量为5个时，综合总成本最低，为2099.7万元。具体站点分布、服务区域划分以及配置的充电桩数量如图3所示，图中圆点为需求点，方形为候选点，其中实心方形为被选中的候选点，实心方形旁的数值为选中充电站安装的充电桩数量，网状直线由Voronoi图生成，即服务区域划分边界。由图3可知，规划区由5个充电站划分为5个服务区域，具体划分情况为：有8个充电桩的充电站覆盖了2个需求点；有16个充电桩的充电站分别覆盖了8个和5个需求点；有24个充电桩的充电站覆盖了8个需求点；有32个充电桩的充电站覆盖了11个需求点。

图3 最优方案及服务区域划分Fig.3 Optimal plan and service area division

本文分别采用IGSA、GSA和PSO 3种算法进行仿真，其收敛曲线对比如图4所示。由图4可知，PSO前期收敛速度很快，但在中期陷入了局部最优；GSA前期收敛速度较慢，中期缓慢收敛，后期陷入了局部最优；IGSA前期收敛速度跟GSA相比有了一定提升，中期平稳收敛逐渐趋于最优。优化结果如表2所示，结果显示，IGSA求得的方案综合总成本最低，GSA求得的方案充电桩数量较少，因此建设运行成本和配网损耗成本较低，但用户充电时间成本大大增加，综合总成本较高；PSO求得的方案由于充电桩数量过多导致建设运行成本和配网损耗成本激增，综合总成本最高。求解时间方面，IGSA运算效率虽不如PSO，但较GSA有了一定改善，效率提高了16%。