基于多维状态空间MCMC充电负荷预测的充电站规划

张美霞，叶睿琦，杨 秀，孙铨杰

(上海电力大学电气工程学院，上海 200090)

随着环境污染问题和全球对传统能源危机问题的不断重视，各地政府不断推出新能源汽车推广等政策导向，电动汽车(electric vehicle，EV)作为能源转型的重要载体，其发展具有势不可挡的趋势[1]。2020年中国发布关于延长新能源汽车购置的财政补贴政策，继续加大电动汽车的推广[2]。近几年，相关企业不断提高电动汽车的续航能力，但仍无法较好规避“里程焦虑”问题[3]，面对增长的市场需求，迫切需要对充电设施进行合理的规模化建设。

目前许多学者对电动汽车充电站规划进行的研究，需要在电动汽车充电负荷需求预测的基础上进行，文献[4]考虑用户起始充电时刻，在确定性概率分布下分析用户行为特性，建立充电负荷预测影响因素的概率模型；文献[5]通过荷电状态(state of charge，SOC)与最低限值比较，判断车辆是否存在充电需求；文献[6]通过划分不同功能区域，建立考虑车辆不同出行目的地的充电负荷预测方法。

车辆充电实际受SOC状态、车辆与充电站的距离及充电站繁忙程度等多方面因素影响，上述方法虽然宏观上建立了充电负荷的预测模型，但考虑的变化因素比较单一，不能多方位的体现出电动汽车特性的变化。为此，文献[7]考虑电动汽车出行状态与充电需求时序交互影响，结合蒙特卡洛法进行电动私家车出行需求预测；文献[8]引入马尔科夫模型对电动汽车充电需求进行预测，得到充电站规划方案；文献[9]对车辆行驶工况进行特征值提取，以此构建动态能耗模型进而选择不同电动汽车充电路径。上述研究中虽然考虑了多方因素对充电负荷的影响，但车辆状态的变化规律为固定值，忽略了用户出行时与交通路网交互的移动随机性，不能较准确地反映真实路网中电动汽车用户的充电需求。

在充电需求预测的基础上，许多学者对充电站规划进行了研究。不同学者规划时考虑的目标不尽相同，文献[10-12]从投资建设者利益为目标建模，直接决定充电站的规划布局，属于上层决策；文献[13-14]从用户出行特性出发，按需选择充电站，属于下层决策。显然，只考虑其中一方不够全面，结合双方利益进行考虑更符合实际情况。文献[15]综合用户充电耗时成本及充电站建设运行成本进行建模，兼顾了用户与充电站的利益；文献[16-17]从以上2个方面分别建立目标函数，建立双层规划问题。双层规划问题是一个NP-hard问题，具有非凸性；文献[18]指出求解双层规划问题是非常困难的，即使能找到双层规划问题的解，通常也只可能是局部最优解而非全局最优解。

从上述文献可以看出，目前对电动汽车充电负荷预测时，许多研究考虑的充电行为受影响的因素较单一或值被预先设定，对用户充电需求在路网中的随机性与灵活性考虑较少，且预测中传统的蒙特卡洛积分存在只能静态模拟的缺陷，不能客观反映充电负荷的动态情况。因此，本文在现有研究成果基础上，提出基于多维状态空间的马尔科夫链蒙特卡洛(Markov Chain Monte Carlo, MCMC)法构建电动汽车充电需求的时空分布模型，通过对用户多个维度的状态空间进行描述，得到状态转移概率矩阵，结合电动汽车实际出行实时样本数据对充电负荷进行时空预测，更精确地反映电动汽车在路网中的真实状态。考虑充电站总投资成本最小和充电用户满意度最大提出双层规划模型，引入罚函数实现双层模型向单层模型的转化，采用变权重的粒子群算法(particle swarm optimization, PSO)对模型进行迭代求解，算例仿真分析验证模型的合理性和可行性。

1 基于MCMC的电动汽车充电负荷预测

MCMC法用于概率空间中，通过随机采样估算兴趣参数分布[19]。MCMC法将马尔科夫过程引入蒙特卡洛模拟中，弥补了传统的蒙特卡洛积分只能静态模拟的缺陷。当模拟次数足够多时，所得模拟序列可视作电动汽车车辆状态的样本，再基于这些样本进行随机抽样预测。

1.1 电动汽车出行马尔科夫性

电动汽车出行过程的状态变化具有马尔科夫性[20]，对电动汽车行程进行相关性分析，车辆相邻2次出行行为存在弱关联，车辆未来行为只与当前状态有关，而历史行程对其不构成影响[21]。本文通过多维状态空间马尔科夫链对电动汽车状态进行描述。根据马尔科夫理论，记当前时刻的状态为Si，下一时刻的状态为Sj，则马尔科夫链可用条件概率表示为

P(Si→Sj)=P(Sj|Si)

(1)

电动汽车在路网中的转移状态如图1所示，其中Park(P)代表车辆处于停置状态，Charge(C)表示车辆处于充电状态，Discharge(D)表示车辆反向充电，m表示前后车辆状态变化的概率。

图1 电动汽车转移状态Figure 1 The transition status of EV

1.2 电动汽车状态空间定义

基于不同用户出行习惯的差异性及用户充电需求的随机性，将电动汽车所在位置、荷电状态、电池充电状态作为电动汽车的状态向量的3个元素，建立电动汽车三维状态向量S，确定不同用户的实时状态，即

S={s1,s2,s3}

(2)

(3)

式(2)、(3)中s1为用户位置状态，s1=(x,y)，(x,y)为电动汽车的位置坐标；s2为荷电状态，即电动汽车当前剩余电量，s2=Q，Q∈[0,1]，表示剩余电量的百分比，最低为0，最高为100%；s3为电动汽车的电池行为状态，s3=pdisch、pchfa、pchlo、preve、0，分别表示放电、快充、慢充、反向充电、停止状态，确定充电状态后对电动汽车充电负荷进行状态统计与更新；pch、pdisch分别为充、放电功率；ηch、ηdisch分别为充、放电时的效率；C为额定容量。

1.3 车辆状态转移矩阵

基于电动汽车状态空间的定义，根据实际车辆出行数据建立状态转移概率。由于不同车型用户的出行特性差异较大，电动公交车通常充电位置和时间比较固定，电动私家车用户没有过多要求，电动出租车因为出行需要，在电量低于一定值的时候需要及时充电，其他情况根据司机的习惯确定，因而具有随机性，本文主要对电动出租车进行研究。

在所提车辆状态空间中，车辆3个维度的状态相互影响，s1对应车辆下一步的位置变化情况，s2与s1、s3有关。当车辆位置状态停在充电站产生充电行为时，车辆剩余电量对应发生改变；当车辆位置远离充电站且自身荷电充足时，不会发生充电行为。s3根据充电行为习惯决定车辆是否充电，若不去充电，s1就不会向充电站的位置发生改变。三者共同决定每个时段对应的不同车辆状态转移矩阵。

对用户位置状态进行判断时关键位置的选取很重要，在电动汽车行进过程中，通常在直线上保持同方向行驶，只有在路口存在变向的情况。因此，在直道行驶中的状态转移只存在2种概率0和1，需要重点考虑路口位置的状态转移概率，将路口位置定义为关键位置。路网中车辆转移有横向和纵向2个方向上的路径选择，根据2个方向上的累加概率，结合轮盘赌算法决策出车辆的位置状态转移情况。

车辆的荷电状态根据当剩余荷电量与所设充电阈值的大小相比，分为充电状态、放电状态和静止状态。荷电状态与车辆位置变化相关，会随着车辆位置的改变发生变化。当车辆产生充电需求时，判断车辆当前位置到各个充电站的距离，选择最近的充电站充电，否则当前状态保持不变。

电池行为状态根据电动汽车是否使用充电机进行划分。由于目前电动汽车反向充电的情况较少，因而本文只考虑电池的快充和不充电2种状态。结合实际情况考虑，车辆当前位置离充电站近或剩余电量低时，车辆选择充电的概率高；当用户在充电时，车辆电池行为信息发生改变。

根据电动汽车定位数据，由行程信息统计各时段各关键位置间不同车辆状态的转移次数，得到路网车辆状态转移矩阵：

(4)

式中bij为始发于位置i的行程目的地落在位置j的累计次数；N为关键位置总数。

Si={si1,si2,si3}状态出现的概率为

(5)

从Si转移到Sj的概率为

Pij=P(Sj|Si)=

(6)

实际情况下电动汽车行驶中的状态难以获得，而根据状态转移矩阵可以在既定初始条件下得到后续车辆状态信息。因而经过分析实际数据统计得到状态转移情况后，基于当前时刻信息，根据其可能产生的状态转移概率生成下一步的车辆状态，做出车辆行为变化的判断。本文根据由实际车辆3个维度状态统计的状态转移行为，采取蒙特卡洛的方法模拟生成电动汽车的初始状态。此处蒙特卡洛时间相关，不同时间对应的概率不一样，运行中的车辆总量会随时间改变，因而对车辆转移状态矩阵进行实时更新计算。

电动汽车的初始位置状态概率模型[21]为

(7)

式中f为位置编号为x的概率密度；μ为单位时间内平均经过该点的电动汽车数目；σ为标准差。

综合前述MCMC方法，结合电动汽车充电需求状态更新，电动汽车用户充电需求分布的预测流程如图2所示。

图2 电动汽车充电需求预测流程Figure 2 The forecasting process of EV charging demand

2 充电站双层规划模型

建立充电站规划模型时考虑企业建站的经济效益作为上层规划，将用户满意度作为下层规划，建立双层规划模型。由于实际可行解空间为离散整数值，因此模型属于非凸非线性优化问题。考虑到双层规划耦合导致难以求解的问题，引入罚函数将双层规划转化为单层规划。

双层规划数学模型[22]为

(8)

式中y为上层决策者的决策变量；x为上层决策变量y给定条件下的下层规划最优解。

2.1 企业建站侧上层规划

充电桩建设企业作为电力供应方首先考虑充电桩的建立成本，包括充电桩的建设投资成本Ccon和运行成本Cope。初期建设投资成本主要包括电机、配电变压器、人力、土地及其他相关设备，其他建设投资成本是建设规模即充电桩容量的函数。充电桩建设用地成本是地址和建设规模的函数，投资建设成本为

Ccon=fL(Li)·

(9)

式中Ncha,i为第i个充电站的充电桩个数；Li为第i个充电站的位置；fL(Li)为对应位置的单位地价；fN(Ncha)为Ncha个充电桩的占地面积；a为单个充电桩及其配套设施的等效成本；b为配电变压器、电缆等设备的等效成本。

运行成本包括后期维护保养、服务成本，维护保养成本随着建设年限增加逐渐增大，服务成本可近似认为与充电站规模成正比，运行成本为

(10)

式中k1、k2为折算系数；μ为维护率；y为运行年限。

上层规划需要满足的约束条件有充电桩接入点容量、充电桩占地规模、电能质量约束。

1)充电桩接入点容量约束。

(11)

式中pi,j为第j个充电站第i个充电桩的充电功率；Ncha,j为充电柱数目；pj,max为节点j最大输出功率。

2)充电桩占地规模约束。

(12)

式中Si,j为第j个充电桩的第i个充电桩所占的等效面积；Sj,max为区域j最大可用建筑面积。

3)电能质量约束。包括电压降、谐波畸变率(THD)等，使得充电站接入对电力系统的影响维持在允许范围内，具体数学表达为

|ΔV|≤ΔVmax

(13)

XTHD≤XTHD,max

(14)

2.2 用户侧下层规划

根据上层规划确定的最优经济效益条件下充电站地址L和容量N，用户选择合适站址进行充电，以达到用户自我满意水平取得较高值，进行考虑用户侧的下层规划。用户满意度可以通过充电需求的解决时效评价，可以用有效充电时长与总充电用时的比值确定，总充电时长为

T∑=Tcharge+Twait

(15)

式中Tcharge为充电时长；Twait为等待时长。

充电时长为剩余SOC与充电速率的函数：

(16)

式中p为充电功率；Qmax为总电量。

等待时间包括从当前位置到达充电站位置的时间和到达充电站后等待时间两部分：

(17)

(18)

式中Di,j为从当前位置i到第j个充电站电动汽车行驶距离；vij为从当前位置到充电站的平均行驶速度；n为充电站中车辆充电的占用率；m为充电站充电车辆的数目；Qi为车辆i荷电状态；Qimax为车辆i最大电量；Nj为第j个充电站的充电桩个数；pj为充电桩的充电功率。

用户满意度定义为

(19)

则下层规划目标函数为

(20)

由双层优化配置模型可知，当上层企业充电站建设者设定出一套充电站选址方案L=(L1,L2,…,LN),下层电动汽车用户会据此充电站址分布选择出使得自己所获满意水平最大的最佳充电路线。同时，下层电动汽车用户的行驶路线会反馈给上层建设者，使得建设者做出为适应用户行驶习惯的选址调整。通过两者的信息交互及互相影响，最终使得双方整体取得相对最优状态。

2.3 上、下层模型求解

求解双层规划非常复杂，双层规划是NP难问题，且其嵌套结构导致了问题的非凸性。对于非线性双层规划通常只能得到一个局部最优解，而非全局最优解，罚函数法可以将约束问题转化为无约束优化问题，以此减小双层规划算法求解复杂度，同时提高收敛性和收敛速度，故本文通过罚函数算法对原问题进行转化。由于本文中上层规划的目标为求解成本最小，而下层目标为求解用户满意度最大，当下层目标函数作为分母加入到上层规划时，上、下层均转化为最小值问题，具有求解一致性。同时下层规划的目标函数还是上层规划的惩罚项，转化后的函数解既能满足上层成本取得最小，又使得下层用户满意度达到最大，即能得到满意的合理解。因此，将下层规划转化为无约束数学规划，然后作为惩罚项加入上层目标函数中，将原双层规划问题转化为带惩罚参数的单层规划问题[18]，得到目标函数：

(21)

其中，n为运行年限。

规划中按照分钟(m)、小时(h)、日期(d)进行迭代，充电站的整体规划流程如图3所示。

图3 罚函数算法双层规划流程Figure 3 Flowchart of penalty function algorithm bi-level optimization process

3 基于PSO算法的模型求解

3.1 PSO算法

PSO属于人工智能算法，是由美国学者Kennedy和Eberhart于1995年基于群智能提出的优化仿生算法[23]。近年来，PSO在处理大量非凸、非线性、不可微等复杂优化问题时得到了很好的应用，广泛应用于工程、科学等研究领域，证实了其算法的良好可行性和优化性。本文的规划需要兼顾双层目标得到整体最优解，同时需要算法可以对多种可能并行求解，而PSO在全局空间中从初始集合解的形式对问题求解，具有记忆性、隐含并行搜索特性，因此采用PSO进行求解。

PSO的关键部分在于粒子位置的更新，优化过程中，每个粒子都有一个速度决定它们下一步搜索的方向及距离，假设种群中的粒子i在D维空间中的位置用n维向量xi=(xi1,xi2,…,xid,…,xiD)表示，搜索空间中单位迭代的位移用一个n维向量vi=(vi1,vi2,…,vid,…,viD)表示，种群中所有粒子更新速度及位置公式分别为

xid=xid+vid

(22)

vid=wvid+c1r1(pid-xid)+

c2r2(pgd-xid)

(23)

式(22)、(23)中vid为粒子的速度；c1、c2为学习因子，一般取c1=c2=2.0；r1、r2为(0,1)之间的随机数；pid为个体最优粒子；pgd为全局最优粒子；w为惯性权重。

w的取值会影响算法的搜索能力，惯性因子较小时算法的局部搜索能力较强，利于精确局部搜索；惯性因子过大易引发早熟收敛、导致全局最优解在算法后期产生振荡，针对PSO此类容易早熟以及后期易陷入全局最优解附近振荡的现象，本文采用线性递减权重法进行改进：

(24)

式中t为迭代步数。

3.2 求解流程

PSO作为一种寻优算法，粒子群中的每一个粒子都代表一个问题的可能解，通过粒子个体间的信息交互，结合自身向群体最优粒子方向移动，进而移动到最优点。本文采取PSO进行求解，解决充电站的选址定容问题，并验证通过罚函数方法解决双层规划问题的有效性。

选址区域及规模的数学描述为

Xi=[xi,yi,Ni]

(25)

式中 (xi,yi)为第i个充电站的位置坐标；Ni为充电站中充电桩的数目即充电站规模。

根据实际情况划定可选择区域为n个，则自变量的个数为n。求解电动汽车充电站规划的具体流程如图4所示，具体求解步骤如下。

1)载入数据。包括充电站位置坐标、电动汽车概率密度矩阵、MCMC状态转移矩阵等初始参数以及充电站最小和最大规模、电压降、谐波畸变率等约束条件参数。

2)种群初始化。包括种群大小、惯性权重方式、迭代次数等参数，随机产生初代种群并计算目标函数作为全局最优解。

3)迭代计算。根据权重、速度、适应度以及约束条件更新粒子位置，计算目标函数并更新、记录全局最优解。

图4 充电站规划求解流程Figure 4 Flow chart for EV charging station planning

4 算例分析

4.1 算例描述

为验证本文所提充电站规划模型的可行性，以华东某市区域为例，规划区域经过栅格化处理后包含路网节点50个，单辆EV电池容量为50 kW·h，NEDC综合工况续航里程为420 km，平均速度为25 km/h。假定该区域有20个可选规划场所为区域内电动出租车汽车提供充放电服务，区域内电动汽车初始保有量为600辆，考虑其数量随时间变化进行仿真。单台充电机充电功率为100 kW，充电模式为快充；充电站最小容量配置为5台充电机，最大容量配置为30台充电机。

4.2 仿真结果及分析

基于文1中提出的充电负荷预测方法，对规划区域内样本车辆信息数据集进行统计分析。将输入的已有车辆信息进行统计分析，读取并计算出其状态转移矩阵，再根据文1.3中所提预测步骤得到时段内MCMC充电负荷空间分布模型。电动汽车充电需求时间分布如图5所示，可知电动出租车充电行为有较强随机性，其中11:00—14:00、18:00—24:00、次日02:00—05:00充电量相对达到峰值。

图5 电动汽车充电需求时间分布Figure 5 Distribution of temporal charging demand of EVs

因仿真计算复杂度较大，所以取包含充电需求峰谷的部分时段进行可视化具有代表性，规划区域内12:00—16:00时段内到达空间点的车辆累计数目分析分布如图6所示，颜色越浅对应统计时间内该区域的累计车辆数量越多。车辆累计分布数目明显较多的几个区域，应配置规模相对较大的充电站。

图6 车辆累计分布Figure 6 Cumulative distributions of EVs

区域内随机某时刻车辆充电需求空间分布如图7所示，颜色越浅对应统计时间内该区域充电需求越大，配置的充电站规模应相对较大。仿真计算中由于区域空间内车辆的剩余电量及车辆位置与可选充电站的距离不同，每个时刻对应的充电需求分布也不尽相同。当寻优计算不断迭代时，确定当前时段车辆位置、剩余电量、充电信息分布模态，通过状态转移矩阵计算不断更新，可得到下个时段的车辆信息状态。

图7 充电需求空间分布Figure 7 Distributions of spatial charging demand of EVs

结合本文所提双层规划模型进行选址优化和容量配置。寻优求解时依据可配置充电机的数目约束，对下层寻优所得充电机数目进行修正，淘汰低于限值的可选站，反之取最大阈值保留，粒子最终选出12个充电站规划站址。最终选址及规划配置方案如表1、图8所示。由图8可得，最终所选站址多分布于电动汽车行驶密集区，且在非车辆密集区域的位置也配置了少量站址，可以满足不同地区用户的需求；在可选址位置相近情况下，能够选择相对最优位置，避免了相近区域重复选址会造成的资源浪费，节约建设成本。

表1 规划配置结果Table 1 Final charging station planning results

图8 充电站选址结果Figure 8 Results of selected charging station site

求解过程中用户等待时间变化以及用户满意度、建设成本、最优目标函数变化曲线分别如图9～12所示，仿真结果表明，算法有较快的搜索速度且分阶次达到稳定收敛。当最优目标函数、建设成本达到最小值时，相应的用户满意度达到最大。当迭代次数相同时，三者对应变化趋势一致，体现出罚函数的有效性。若不采用罚函数，则可能会产生成本较低时满意度却大幅下降，或牺牲成本才能满足用户满意度的情况，会导致成本和用户满意度之间的利益难以平衡。最终所得规划结果有利于减少充电排队时间、提高用户满意度，同时又能保证充电站建设投入的成本较低，为推动电动汽车的推广与发展做出重要参考。

图9 用户等待时间变化Figure 9 Changes in waiting time for charging users

图10 用户满意度变化Figure 10 Changes in users satisfaction

图11 建设成本变化Figure 11 Changes in the construction cost of charging stations

图12 最优目标函数变化Figure 12 Changes in the optimal objective function

5 结语

本文提出一种基于多维状态空间的充电需求预测和电动汽车充电站双层规划罚函数求解规划方法，以某城区路网电动汽车为例进行了验证分析。

1)基于多维状态空间的马尔科夫蒙特卡洛方法模拟电动汽车行为状态，得到了充电需求时空分布模型，在此基础上建立的经济效益模型和用户满意度模型，模型不是单一的对电动汽车出行行为进行罗列，而是结合具体时间及相应路网情况进行分析。充分考虑了实际中电动汽车车辆的充电需求受多方因素影响的情况，更加精确的反映实际情况。

2)本文提出的双层规划经罚函数转化、嵌套粒子群算法进行求解的方法，明显提高了规划全局寻优能力及算法收敛速度，解决了电动汽车充电站规划时供需双方的平衡问题，为建站企业对充电站规划配置提供了一种新思路。

算例表明了所提规划方案的有效性和可行性，为实际规划者提供了重要参考。由于近年来政策的宏观调控及新基建的提出，市场对电动汽车引导的力度逐渐加强，因而，在此基础上，将进一步研究充电引导策略等因素加入后对电动汽车充电站规划方案的影响。