充电服务能力和运行效率最大化的电动汽车充电网络规划

张新松，徐杨杨，袁 越，朱俊澎

（1.南通大学 电气工程学院，江苏 南通 226019，2.河海大学 能源与电气学院，江苏 南京 211100）

利用电动汽车（electric vehicle，EV）替代传统燃油汽车是促进能源利用形式转型升级，实现可持续发展的重要途径之一[1]。近年来，随着石油资源的不断枯竭和环境污染的逐步加剧，EV 引起了世界各国的广泛关注[2]。作为EV 充电的主要场所之一，充电站是支撑EV 发展的重要基础设施，不合理的EV充电网络将显著降低EV 使用的便利性，降低用户购买意愿，阻碍EV 产业的进一步发展[3]。在此背景下，EV 充电网络规划的重要性日益凸显，国内外学者对此进行了大量研究，取得了丰硕的成果[4-13]。文献[4-6]在充电网络规划中侧重考虑配电系统运行效益，而忽略了充电网络的充电服务能力与运行效率。文献[6-13]主要关注充电网络规划中的经济类优化目标，如充电站运营商收益，充电站投资、运营成本与充电站建设成本等，而对充电网络充电服务能力与运行效率的考虑略有不足。

为弥补现有研究的不足，本文提出了一种基于流量需求模型的EV 充电网络充电服务能力计算方法，接着，建立了充电网络多目标规划模型，在充电站建设数量和充电桩配置总数给定的情况下，通过优化充电站建设地址和充电桩配置数目使得充电网络的充电服务能力和运行效率最大化。

1 充电网络充电服务能力计算

对EV 充电网络来说，可基于点需求模型或流量需求模型计算其充电服务能力[14-15]。点需求模型中，将EV 充电需求局限在交通网络中的重要节点，而忽略EV 行驶途中产生的充电需求；流量需求模型与点需求模型不同，还可同时考虑EV 行驶途中产生的充电需求。考虑到流量需求模型的优势，本文将基于该模型对充电网络的充电服务能力进行计算，得到

式中：Fc为充电网络截获的总车流量，Fc越大，充电网络的充电服务能力越强；目前，以高德地图和百度地图为代表的导航软件得到了大规模应用，因此，可假定EV 总能沿出发地与目的地间的最短路径行驶，在这一假定下，Q 为交通网络中的最短路径集[16]，可通过Floyd 算法确定该最短路径集[17]；q 为路径索引；yq为表征充电网络能否截获路径q 车流量的二进制变量；fq为路径q 车流量。yq有“1”“0”两种取值：“1”表示能截获，“0”表示不能截获。fq可通过重力空间互动模型计算，得到

式中：WS、WE分别为路径q 出发点S 与目的地E 的权重；dq为路径q 的长度。

从以上描述可看出，充电服务能力计算的关键是判断所有最短路径上的车流量能否被充电网络截获。为解决这一问题，本文提出了一种简洁、明了且易于编程实现的方法，要点如下：

1）对路径q 来说，经沿途充电，若EV 能从出发点S 行驶至目的点E，并能再次返回出发点S，则说明充电网络可截获该路径车流量，即yq=1；否则，充电网络不能截获该路径车流量，即yq=0[16]。

2）从出发点S 出发时，EV 可续航里程lav的初始值由出发点S 是否建有充电站决定。若出发点S建有充电站，EV 可充满电再出发，此时lav初始化为EV 满充状态下的最大续航里程lmax，即lav=lmax；否则，令lav=lmax/2，即lav初始化为EV 满充状态下最大续航里程lmax的1/2[16]。

3）现阶段，由于续航里程与传统燃油汽车相比仍存在一定差距，EV 车主普遍存在里程焦虑，因此，在行驶途中，若遇到充电站，不管剩余电量如何，EV 立即驶入充电站充电至满充状态。

以图1 为例，对路径车流量能否被充电网络截获的判断方法进行详细说明。图1 给出的简单路径括4 个节点与3 段道路：4 个节点分别为出发点S，中间节点A、B 与目的点E；3 段道路分别为SA，AB与BE，其长度分别为lSA，lAB与lBE。需指出的是，交通网络中的实际路径可能比图1 更复杂，但同样由若干节点和道路组成。

为判断如图1 所示的路径上的车流量能否被充电网络截获，假定EV 从出发点S 出发后，依次驶过中间节点A、B，目的点E，中间节点B、A 后再次返回出发点S。首先，按上文给出的原则初始化EV从出发点S 出发时的可续航里程lav，接着，按式（3）更新EV 驶经每一个节点（包括目的点E）时的可续航里程lav，

式中ltwo-node为EV 从上一个节点至当前节点的行驶距离，如EV 从中间节点B 行驶至目的点E 时，ltwo-node=lBE。

EV 可续航里程lav更新后，若数值小于0，说明EV 因续航能力不足无法行驶至当前节点，当然，更无法再次返回出发点S，此时，该路径车流量不能被截获；反之，说明EV 可行驶至当前节点，并将继续驶向下一节点。若当前到达节点设有充电站，EV将充电至满充状态，即按式（4）再次更新EV 可续航里程lav

若EV 最终能再次回到出发点S，该路径车流量能被截获；否则，该路径车流量不能被截获。从以上描述可看出：路径车流量能否被截获与路径上各段道路的长度，路径各节点的充电站建设情况及EV 满充状态下的续航里程lmax有关。

2 电动汽车充电网络规划模型

2.1 优化目标

充电网络是支撑EV 发展的重要基础设施，充电网络规划模型的首要优化目标是实现充电网络的充电服务能力最大化，具体为

充电网络规划模型的另一个优化目标是充电网络运行效率最高。充电网络中，某些充电站截获的车流量较大，则驶入此类充电站充电的EV 数目较多，应尽可能在这些充电站中多配置充电桩，否则，大量EV 同时驶入此类充电站充电时将面临过长的充电等待时间，降低充电网络运行效率；反之，对那些截获车流量较少的充电站来说，应尽可能减少充电桩配置数，从而避免充电桩资源闲置，提高充电网络运行效率。基于以上分析可知：在充电桩配置总数给定的情况下，可基于各充电站中的充电桩配置数目与截获车流量间的匹配度衡量充电网络运行效率。此时，充电网络运行效率最高这一优化目标为

式中：Vmatch为充电站充电桩配置数目与截获车流量间的匹配度，取值越大，说明充电网络运行效率越高；M 为规划区域内的充电站建设总数，由规划人员根据EV 总数、充电网络建设投资总额、充电站建设成本与市政规划等因素综合确定；j 为充电站索引（j=1，2，…，M）；zj为充电网络规划模型中的整数优化变量，表示充电站j 中的充电桩配置数目；Fc，j为充电站j 截获的车流量

式中Ωj为交通网络中途经充电站j 的路径集合。

2.2 模型约束

充电站建设总数约束为

式中：N 为充电站候选地址总数，由EV 渗透率、交通网络现状与市政规划等因素综合确定；i 为候选地址索引（i=1，2，3，…，N）；xi是充电网络规划模型中二进制优化变量，有“1”、“0”两种取值：“1”表示候选地址i 建有充电站，“0”表示候选地址i 未建充电站。

充电桩配置总数约束为

式中Ctotal为充电网络中的充电桩配置总数，由规划区域内EV 渗透率、充电桩成本、充电网络建设拟投资总额等因素综合确定。

单个充电站充电桩配置数目约束

式中zm为单个充电站的充电桩配置数目上限，由规划区域内EV 渗透率、充电桩配置总数、充电站建设总数与市政规划等因素综合确定。

3 模型求解

3.1 整体求解思路

第2 节描述的充电网络规划模型为同时考虑两个不同维度优化目标的多目标优化问题，并同时包含二进制优化变量xi与整数优化变量zj，直接对其进行求解有一定的难度。从本文给出的充电服务能力计算模型可看出，充电服务能力最大这一优化目标仅与二进制优化变量xi有关，即只要充电站建设地址给定，便可基于流量需求模型确定充电网络的充电服务能力。进一步分析充电网络规划模型可发现：在充电站选址方案和充电桩配置总数给定的情况下，充电网络运行效率最高这一优化目标仅与各充电站中的充电桩配置数相关，也就是说，仅与整数优化变量zj相关。

基于以上分析，可将充电网络规划模型解耦为两个单目标优化问题求解：1）求解以式（5）为优化目标、式（8）为约束的单目标二进制优化问题，优化充电站建设地址；2）求解以式（6）为优化目标、式（9）与式（10）为约束的单目标NIP 问题，给出各充电站的最优充电桩配置数目。

3.2 充电站建设地址优化

遗传算法（genetic algorithm，GA）是一种根植于自然遗传学和计算机科学的优化方法，具有较强的适应性和全局寻优能力，在多个领域得到了成功应用[18]。本文采用GA 求解以式（5）为优化目标、式（8）为约束的单目标二进制优化问题，优化充电站建设地址，具体流程如图2 所示。

图2 中，Npop为种群规模，Gmax为GA 最大进化代数，一旦到达该最大进化代数，便认为算法收敛。利用GA 求解充电站建设地址优化问题时，应依据待求优化问题的特点对染色体编码方案、适应度计算方法及交叉、变异操作算子进行专门设计，具体如下：

1）染色体编码。染色体为N 个码位组成的二进制码串，表示一个可行的充电站选址方案。各码位均有“1”和“0”两种取值：码位i 取值为“1”，说明在候选地址i 建有充电站；反之，说明未在候选地址i建设充电站。为满足式（8）给出的充电站建设总数约束，染色体中有且仅有M 个码位取值为“1”。为确保初始种群中的染色体满足上述要求，分两步对GA 种群进行初始化：首先，将初始种群中所有染色体的全部码位赋值为“0”；接着，在每条染色体中随机挑选M 个码位，将赋值由“0”改为“1”。

2）适应度计算。染色体解码后，可确定M 个充电站的建设位置，此时，依据本文第1 节介绍的方法计算充电网络截获的总车流量Fc，并将其作为染色体的适应度

3）交叉、变异操作。交叉、变异操作是遗传操作的重要组成部分，但通用交叉、变异操作可能会破坏染色体结构，导致无法满足式（8）给出的充电站建设总数约束。为解决这一问题，本文根据待充电站建设地址优化问题的特点设计了专门的交叉、变异操作算子，具体如下所示。

为保证交叉后的染色体中依然保留M 个取值为“1”的码位，分3 步实施交叉操作：

步骤1从父代种群中随机选取两条染色体作为待交叉染色体。

步骤2随机生成待选交叉位Ncan（1 ＜Ncan＜N），若两条待交叉染色体第Ncan个码位后取值为“1”的码位数一致，则该待选交叉位为可行交叉位Nc；否则，重新随机生成待选交叉位Ncan，直至找到满足上述要求的可行交叉位Nc。

步骤3以交叉概率Pc交换待交叉染色体可行交叉位Ncr后的二进制码串，完成交叉操作。

为保证变异后的染色体中依然保留M 个取值为“1”的码位，分3 步实施交叉操作：

步骤1从父代种群中随机选取一条染色体作为待变异染色体。

步骤2随机生成待变异码位Nmu1与Nmu2（1 ＜Nmu1＜N，1 ＜Nmu2＜N），并确保其取值不能同时为“1”或“0”。

步骤3以变异概率Pm同时对两个待变异码位实施变异操作，即取值为“1”的待变异码位变异为“0”，取值为“0”的待变异码位变异为“1”。

3.3 充电桩配置数目优化

充电站最优选址方案给定后，可依据各充电站建设位置，按式（7）计算各充电站截获的车流量Fc，j（j=1，2，…，M）。交通网络中，某些最短路径上同时建有多座充电站，因此，所有充电站截获的车流量之和与充电网络整体截获的总车流量Fc并不相等。

求解如下所示的整数优化问题

即可给出各待建充电站中的最优充电桩配置数目。从式（12）可看出，优化目标中出现了绝对值求和运算和倒数运算，因此，上述优化问题为典型的NIP问题。研究中，将其转换为如下所示的线性整数规划问题（linear integer programming，LIP）后再调用CPLEX 求解器求解。

式中：Vau为式（6）给出优化目标的分母部分，取最小值对应于式（6）给出的优化目标取最大值；vj、dj和pj是优化问题转换中引入的辅助变量，其中，vj用于替换优化目标中的绝对值表达式，dj和pj为二进变量。对第j 个待建充电站，若

4 算例分析

为验证本文所提电动汽车充电网络多目标规划模型与求解方法的有效性，本节以25 节点交通系统为例进行了仿真计算和分析。

4.1 算例介绍与规划边界条件

25 节点交通系统由25 个交通节点与43 条道路组成，拓扑如图3 所示，各交通节点的权重如表1所示[14]。图3 中的道路仅表示交通节点间的拓扑联接关系，不代表道路的实际物理走向与长度。算例假定图3 中每条道路均可双向通行，此时，从出发地至目的地的最短路径与从目的地返回出发地的最短路径相同。在此假定下，算例系统最短路径集Q由[25 × （25 -1）]/2=300 条最短路径组成，可由Floyd 算法求得，所有最短路径总车流量为0.282。充电网络规划中，拟在算例系统中建设4 座充电站、共配置100 个充电桩，各充电站的最大充电桩配置数目均为50。EV 满充状态下的续航里程lmax暂定为250 km。

4.2 规划结果

本文提出的充电网络规划模型包含两个不同维度优化目标的多目标优化问题，直接求解有一定的难度。为此，本文将其解耦为两个单目标优化问题进行依次求解：首先，利用GA 对充电站选址进行优化，在此基础上，调用CPLEX 软件求解式（12）给出的NIP 问题，优化各充电站中的充电桩配置数目。通过上述两步优化，可给出最优充电网络规划方案，具体如图4 所示。

表1 交通节点权重系数Tab.1 Weights of traffic nodes

利用GA 对充电站建设地址进行优化时，种群规模设为30，交叉概率、变异概率分别设为0.10 和0.05，最大进化代数设为120。种群进化中，每代种群最优染色体的适应度如图5 所示。由图可知，随着算法种群的不断进化，各代种群最优染色体的适应度逐步提升。当GA 进化到第50 代左右时，算法已趋于收敛；当进化到第77 代时，算法收敛于最优解0.242。GA 能有效求解以式（5）为优化目标、式（8）为约束的单目标二进制规划问题，给出充电站的最优建设地址。

如图4 所示，充电站最优选址方案中，在节点3，8，13 与14 各建设一座充电站，此时，充电网络充电服务能力最大，总截获车流量为0.242。对图3 给出的交通系统来说，最短路径集合Q 中所有路径的总车流量为0.282，则图4 所示的充电网络可截获总车流量的85.82%。在充电站选址方案给定后，可按式（7）计算各充电站分别截获的车流量，建设在节点3，8，13 与14 的4 座充电站截获的车流量分别为0.038 7，0.047 2，0.032 9，0.126 0。在此基础上，调用CPLEX 软件求解式（12）给出的单目标NIP问题，给出各充电站中的最优充电桩配置数目，分别为16，20，14，50。此时，充电站截获车流量与充电桩配置数目间的匹配度Vmatch为34.31；若将100 个充电桩平均分布于4 个充电站，Vmatch由34.31 下降为1.89，下降幅度为94.49%，说明本文提出的方法可通过优化各待建充电站中的充电桩配置数目最大化充电网络的运行效率。

4.3 续航里程对充电网络规划的影响

从第2 节给出的充电服务能力计算模型可看出，EV 满充状态下的最大续航里程lmax是判断各路径车流量能否被充电网络截获的关键参数之一，因此，参数lmax的取值可能会影响充电网络的规划结果。表2 给出了不同lmax取值下的充电网络规划结果。

从表2 可看出，当EV 满充状态下的最大续航里程lmax由250 km 减少为200 km 时，4 座充电站的建设地址和充电桩配置数目均发生改变。此时，4 座充电站分别建设于节点2，10，18 与22，截获车流量分别为0.042 4，0.060 3，0.057 5 与0.051 4。在此基础上，求解式（12）给出的单目标NIP 问题，可得4座充电站中的充电桩配置数目分别为20，28，27 与25，对应的匹配度Vmatch为70.53。当EV 满充状态下的最大续航里程lmax由250 km 增至300 km 时，建设于节点13 的充电站改建至节点12，即4 座充电站分别建设于节点3，8，12 与14，截获车流量分别为0.038 7，0.047 0，0.032 4 与0.126 0。基于上述数据，求解式（12）给出的单目标NIP 问题，可得4 座充电站中的充电桩配置数目分别为16，20，14 与50，对应的匹配度Vmatch为31.44。也就是说，当EV满充状态下的最大续航里程lmax由250 km 增至300 km 时，仅1 座充电站的建设地址发生改变，但充电桩配置数目保持不变。从以上分析可看出，EV满充状态下的最大续航里程lmax对充电站建设地址和充电配置数目的影响较为复杂，是充电网络规划中需考虑的关键因素。

表2 不同lmax 取值下的充电网络规划结果Tab.2 Planning results corresponding to different values of lmax

5 总结与展望

为给出合理的电动汽车充电网络规划方案，提出了一种充电网络多目标规划模型，在给定充电站建设数量和充电桩配置数量的前提下，通过优化充电站建设地址和充电桩配置数目来实现充电网络的充电服务能力与运行效率最大化。将充电网络多目标规划模型解耦为两个单目标优化问题依次求解，基于25 节点交通系统的仿真实验验证了所提模型和求解方法的有效性。

下一步可在以下两方面进行研究：

1）对本文提出的充电网络规划方法来说，确定合理的充电站建设总数与充电桩配置总数是给出合理规划方案的前提；

2）EV 充电站是配电系统中的大功率用电负荷，会对配电系统运行工况产生显著影响，因此，充电网络规划中，应同时考虑充电网络对配电系统运行工况的影响，方可给出更为合理的规划方案。