基于改进加权Voronoi图的多场景电动汽车充电网络规划方法

李逸欣，林勇，杨军

(1.广东电网有限责任公司电网规划研究中心，广东 广州 510600；2.武汉大学 电气与自动化学院，湖北 武汉 430072)

随着社会的不断发展，环境污染和传统能源短缺问题越来越严峻[1-2]，电动汽车具有低污染和可持续性发展的特点，因此很多国家制订了大力推进电动汽车发展的政策[3-6]。根据国务院发布的《节能与新能源汽车产业发展规划(2012—2020年)》，到2020年，我国新能源电动汽车保有量将达到500万辆以上[7]。为了配合与促进电动汽车的快速发展，有必要对多场景电动汽车充电网络规划问题进行研究。

目前国内外对电动汽车充电站规划问题开展了一定的研究，主要从考虑交通流量[8-9]、电动汽车充电负荷时空分布[10-12]出发，对电动汽车充电站进行选址或提出电动汽车充电站选址评价指标体系，以及对充电站站址进行评价[13]。选址标准包括：以充电站总成本和网损费用最小[14]，以投资商和用户费用最小[15-16]为优化目标，以电动汽车排队等候时间[17]、服务能力[18]为依据匹配电动汽车充电站容量。Voronoi图在数学上限定了每个离散点数据的有效作用范围[19]，在电动汽车服务范围划分中被广泛运用[20-22]。

综上所述，当前研究主要考虑交通路网某一确定的交通流量分布，但未考虑不同场景下交通流量分布存在的明显不同，以及不同场景下电网中节点负荷特性的不同。Voronoi图或者加权Voronoi图以区域内的任意点到区域内充电站的欧氏距离或加权欧式距离不大于到区域外任意充电站的欧式距离为划分标准，电动汽车的行驶路径需要沿着交通路网，需要对Voronoi图进行改进。

本文考虑节假日、工作日交通流量分布不同及电网负荷不同对电动汽车充电站规划的影响，综合考虑交通流量、综合建设成本、用户排队等待时间忍耐度等因素，建立多场景的电动汽车充电网络规划模型，对电动汽车充电服务网络进行合理规划。首先建立多场景交通满意度模型，以交通满意度最大为目标进行优化，得到电动汽车充电站最优站址；基于改进加权Voronoi图，以电动汽车充电站年综合成本最小为优化目标，综合考虑排队时间、电网安全等因素，对电动汽车充电站容量进行优化，并得到各充电站的服务范围。

1 基于交通满意度的分场景电动汽车充电站选址方法

电动汽车充电站的选址问题需要考虑多方面因素，主要需要从用户和交通2个方面综合规划。由分析可知，充电站在交通路网中需要尽可能大地覆盖交通流量，因此充电站选址是典型的位置分配问题，而解决该问题最常见的方法是P-中值模型和最大覆盖选址模型。本文综合二者，定义交通满意度，综合工作日、节假日多场景下的交通流量特性，构建多场景交通满意度选址模型，如图1所示，其中ncs,min、ncs,max分别为该区域需要建设充电站数量的最小值及和最大值，ε为服务范围修正量允许误差值。

1.1 分场景交通流量分析

由于城市人们生活活动特性不同，在工作日和节假日，城市交通流量的分布也随之不同。本文分别对工作日和节假日的城市交通流量特性进行分析，进而阐述进行多场景电动汽车充电网络规划的必要性。

图1 基于改进Voronoi图的电动汽车分场景充电站规划步骤

a)工作日。由于工作需求，用户主要活动于市中心的金融商业中心、科技发展中心、制造工业中心等工作区，因此市中心的各交通枢纽、路口交通压力大，工作区域内早晚高峰也出现较大的交通需求。

b)节假日。节假日城市用户的工作需求降低，并且由于生活水平不断提高，城市用户的活动半径变大；因此，在节假日人们往往选择郊区旅游风景区、周边城市、城市公园游乐城、城市娱乐商业圈等场所活动，城市郊区、出入城路段、风景区以及娱乐商业区的交通压力相对于工作日大幅增加。

1.2 基于交通满意度的充电站选址模型

建立P-中值模型的目的是尽可能保持所有车辆的行驶距离最短，这是从交通方面进行考虑和分析；而最大覆盖选址模型是为了保证充电站能够截住最多的车流，即服务最多车辆，这是从用户角度进行考虑分析的。二者均为电动汽车充电站选址的目的，所以本文结合2个模型建立了交通满意度模型，定义z为交通满意度，则

(1)

其中

(2)

式中：ω为折中权重，取(0,1)区间内的小数，本文ω取0.5，可将P-中值模型和最大覆盖选址模型有效结合；nq为路径数量；dq为路径距离；式(1)前半部分代表网络需求权重距离，Si为在起始点i的流量需求；式(2)中SO和SD即表示在起始点O和D的流量需求，此处需求抽象化为权重表示，即节点上车辆多少；dij为节点ij之间的最短距离，本文采用迪杰斯特拉算法求得；Xij表示节点ij之间是否存在设施，存在则为1，不存在则为0；式(1)后半部分表示网络需求满意度，fq为网络中O-D路径q的交通流量，O-D路径本文采用迪杰斯特拉算法求得；Yq为1表示满足fq，Yq为0表示不满足fq，本文在选址时简化假设O-D路径上有充电站则满足fq。

通过对P-中值模型和最大覆盖选址模型的分析可知，在交通网路中，需要尽可能保持较小的网络需求权重距离和尽可能大的网络需求满意度，因此以最小满意度为优化目标进行求解，即可得到充电站的最优站址。

考虑工作日、节假日2个场景下的交通网络中交通流量具有不同的特性，建立多场景交通满意度充电站选址模型，具体模型表示为

maxz=max(ηwzw+ηhzh) .

(3)

式中：ηw、ηh为多场景权重，取(0,1)区间内的小数，其大小与工作日、节假日数量相关；zw、zh为工作日、节假日时的交通满意度。为简化分析，本文忽略特殊节假日、法定假日及国家调休安排等因素，按照一周双休进行分析，即工作日与节假日比例为5∶2，因此本文ηw取0.714，ηh取0.286。

2 基于排队论的电动汽车充电站定容模型

电动汽车充电站定容规划时既要考虑充电站的建设运行成本、充电站网损成本，还要考虑电动汽车用户的需求。本文充分考虑电网公司和用户2个方面的利益，以充电站总成本最小化为优化目标，电动汽车用户排队等待时间忍耐极限为约束条件，对电动汽车充电站容量进行优化。

2.1 定容优化目标函数

以电动汽车充电站年综合成本为优化目标，得到电动汽车充电站容量的最优配比，年综合成本包括年固定投资、年运行成本和网损成本。年固定投资主要为充电桩、配电变压器、土地成本以及其他辅助设备的投资成本；年运行成本主要是电动汽车充电站的维护人员的薪水和设备维护等成本。

充电桩是决定固定投资大小的主要因素，其数量体现了该充电站的规模和容量，即充电桩越多，充电站能够服务的电动汽车越多，服务能力也越强，占地面积越大，相应的土地投资成本、配电变压器、其他辅助设备的投资成本越大。同时，规模越大，充电站的年运行成本也会越大。综上可得，年固定投资成本和年运行成本都是充电桩数量Ncm的函数。年综合成本

Cop(Ncm,i)]+Closs.

(4)

其中

Cfix(Ncm,i)=w+mNcm,i+eNcm,i2.

(5)

Cop(Ncm,i)=αCfix(Ncm,i) .

(6)

Closs=8 760cPloss(Psi,Qsi) .

(7)

式(4)—(7)中：Cfix(Ncm,i)表示充电站i的年固定投资成本；Cop(Ncm,i)表示充电站i的年运行成本；Closs为充电网络年网损成本；Ncm,i为充电站i的充电桩数量；r0为贴现率；Ms表示第s个充电站的折旧年限;Jcs为充电站集合；w为固定投资，主要包括营业建筑和道路等辅助建设成本；m为站内与充电桩单价有关的等效投资系数，单位为万元/台；e为与充电桩数量有关的等效投资系数，主要包括占地面积、配电变压器容量、电缆等与充电桩数量相关的投资成本，单位为万元/台2；α为年运行成本与年固定投资成本有关的相关系数；Psi、Qsi为节点i注入的有功功率和无功功率；Ploss(Psi,Qsi)表示由于充电站接入引起的网损；c为平均电价。

工作日、节假日时交通路网中的交通流量不同，电网负荷也具有不同的特性，建立的多场景电动汽车充点电站定容模型

Cev=ηwCw+ηhCh.

(8)

其中：根据第1.2节分析，ηw取0.714，ηh取0.286；Cev为充电站年综合成本；Cw为工作日场景下年综合成本；Ch为节假日场景下年综合成本。

2.2 约束条件

本文从电动汽车充电用户心理和电网安全2个角度考虑，对电动汽车充电站容量优化过程进行约束，得到待规划区域电动汽车充电站容量最优匹配结果。

2.2.1 电动汽车充电用户排队等待时间约束

当区域内的电动汽车数量一定时，用户平均排队等待时间随着站内充电机数量的增加而减少。通过对电动汽车用户心理进行调查可知，大多数用户对排队等待时间存在最大忍耐值，需要在满足用户排队等待时间的条件约束下对电动汽车充电站的充电机数量进行匹配。

由分析可知：每辆电动汽车到达充电站进行充电的行为是相互独立的，即该行为满足独立性和无后效性的特点，因此根据排队论可以认为电动汽车到达充电站的充电行为满足M/M/S模型。本文利用参数为λ的泊松流来描述电动汽车到达充电站的规律，电动汽车在充电站进行充电的服务时间用参数为μ的负指数分布进行描述，则：

(9)

ρi=λi/μ.

(10)

μ=1/tc.

(11)

(12)

(13)

式(9)—(13)中：nev,i为充电站i初始服务区域内的电动汽车数量；p为电动汽车去充电站充电的概率；tc为充电时间；ρi为充电站i的服务强度；P0i为充电站i的总闲置概率；Wqi为充电站i的排队时间均值。

通过排队忍耐时间的约束可以得到充电站充电桩的最小值；同样，可以通过充电站建设需求约束求出充电站i建设充电桩数量Ni的最大值Ni,max和最小值Ni,min。充电站充电机数量约束表示为

Ni,min≤Ni≤Ni,max.

(14)

2.2.2 电网约束

由于快充充电站具有较大的电流和功率，可能对电网运行安全造成一定的影响，主要从节点电压约束和潮流约束2个角度进行分析。

节点电压约束

Ui,min≤Ui≤Ui,max,i=1,2,….

(15)

潮流等式约束

(16)

式中：Ui和Uj为节点i和j的电压幅值；Gij和Bij为节点i、j之间的电导和电纳；θi,j为节点i、j之间的相角差。

3 基于改进加权Voronoi图的电动汽车充电站服务范围划分

Voronoi图在与几何信息相关的许多领域有着广泛的应用[21-22]，因此Voronoi图在划分电动汽车充电站服务范围时也得以广泛应用。传统的Voronoi图或加权Voronoi图以区域内任意点到区域内充电站的欧式距离或加权欧式距离不大于到区域外任何充电站的欧式距离为划分标准，然而结合用户实际消费心理，应该为服务范围内的任意电动汽车到该区域内充电站进行充电消耗的总时间(包括行驶时间和平均排队时间)不大于到区域外的任意充电站进行充电消耗的时间。因此，提出改进的Voronoi图进行电动汽车充电站服务范围的划分。

设平面上中心点集合为P={p1，p2，…，pn}，3≤n≤∞，即充电站站点，d(x,pi)为汽车至站点pi的路径距离，wi表示第i个充电站，则改进的Voronoi图可表示为

V(pi,wi)=

j=1,2,…,n,j≠i}.

(17)

目前，普通Voronoi图的生成算法也比较成熟，如MATLAB、ArGIS等专业软件均可以实现，但加权Voronoi图的生成相对比较困难，需要根据需求编写程序才能实现。目前生成Voronoi图的思路主要是基于矢量生成算法和基于离散生成算法，前者涉及的运算、建模过程较为复杂，因此实现起来具有一定的难度，本文主要采用基于离散生成算法的思路进行编程实现。

加权Voronoi图离散生成算法的基本思想是：每一个顶点设定1种颜色，每个顶点设定不同的颜色；将顶点周围的负荷点用与顶点相同的颜色进行表示；分别计算每个离散的负荷点属于哪个顶点的影响，标注与该顶点相同的颜色；最终将所有离散负荷进行分类划分，得到改进的加权Voronoi图。本文算例以此为思路，在MATLAB中编程实现仿真。

4 算例分析

本文利用提出的多场景电动汽车充电网络规划方法对某地区的电动汽车充电网络进行规划(如图2所示)。图2中，含有25节点交通路网和24标准节点电网，具体参数如图3、4所示，图中黑色实线表示节点之间具有连接关系，实线中的数字表示交通节点之间的距离(单位：km)，节点下的数字为交通节点标号。

图2 交通路网及电网示意图

4.1 分场景交通流量

工作日及节假日各交通节点车流量分别见表1和表2，权重越大表示该节点处交通流量越大。

4.1.1 工作日时25节点交通路网交通流量

根据表1得到交通节点流量示意图，如图3所示，图中节点颜色越深表示节点交通压力越大。

表1 工作日各节点车流量权重

图3 工作日25节点交通流量示意图

4.1.2 节假日时25节点交通路网交通流量

根据表2得到交通节点流量示意图，如图4所示。

表2 节假日各节点车流量权重

图4 节假日25节点交通流量示意图

由图3、图4可以看出，工作日时城中心交通压力大，但节假日时随着人们出游等活动，城中心交通压力将有所缓解，而郊区风景区的交通压力将增大。因此，非常有必要对多场景电动汽车充电网络规划方法进行研究。

4.2 电动汽车充电网络规划

模型中节点5和17已建设充电站，拥有充电桩数量分别为5个和6个，对该区域进行电动汽车充电站规划。式(3)—(7)中的参数具体取值为：固定投资为100万元，站内与充电桩单价有关的等效投资系数m为10万元/台，与充电桩数量有关的等效投资系数e为3万元/台2，贴现率r0为0.08。式(9)—(13)中的参数具体取值为：电动汽车去充电站充电的概率p为0.05，充电服务时间tc为6 h，排队等待时间均值的忍耐极限Wq,max为15 min。

为了满足排队等待时间忍耐极限的限制，需要对式(13)求关于充电桩数量Ncm,i的反函数，由于阶乘运算的存在，该公式的反函数较难求得。对M/M/S模型进行研究可知，式(9)—(13)的成立条件为ρ

进行合理性分析，该区域建设的充电站个数为3～7个，综合以上参数和分场景交通流量数据，利用本文提出的多场景电动汽车充电网络规划方法以及MATLAB进行建模，对该区域进行规划。该规划问题为非线性整数优化问题，选择MATLAB中的遗传算法工具箱进行求解。选择种群大小为50、代数为40、代沟为0.9进行求解，得到结果如图5所示。

图5 新设不同数量电动汽车充电站的计算结果曲线

由图5可知，当建设充电站数量为5时，年最小综合成本215.224 7万元。由式(1)—(3)可以得到选址结果为：充电站为5时，站址分别为节点5、9、11、17、24最优，此时工作日交通满意度为3 230.4，节假日交通满意度为1 432.4，综合交通满意度为4 662.8。

由式(3)—(15)可以得到定容结果，见表3；由式(16)可以得到充电站服务范围及各站平均排队等待时间均值，见表4。

由表4得到规划结果，如图6所示。

表3 定容结果

表4 充电站服务范围及排队等待时间均值

图6 电动汽车充电网络规划结果示意图

5 结束语

本文分析了工作日、节假日下交通网络中流量分布的差异，综合考虑交通覆盖率和用户需求，建立多场景交通满意度模型进行选址。考虑充电站综合成本、用户排队等待时间忍耐极限、配电网运行安全等因素，对充电站容量进行配置。考虑用户行驶特性，对加权Voronoi图进行改进，提出改进加权Voronoi图划分电动汽车充电站服务范围，完成多场景电动汽车充电网络规划。本文利用所提出的方法对某区域的充电服务网络进行规划，并指出多场景电动汽车充电网络规划的重要性。