论文：Electric Vehicle Charging Scheduling by an Enhanced Artificial Bee Colony Algorithm

内容来源：IWINAC 20

作者：Jorge García Álvarez, Miguel Ángel González, Camino Rodríguez Vela and Ramiro Varela

No.1

介绍

    由于电动汽车充电站的物理结构和运行条件，对大型电动汽车充电时间的调度一直是一个难题。本文研究了一个电动汽车充电站的充电调度问题，该充电站的设计场景在社区停车场，每个电动汽车都有自己的停车位；其主要目标是在满足用户需求的同时，最大限度地利用现有的电力资源。为了解决这一问题，本文借鉴了遗传算法的一些交叉策略，综合局部搜索，提出了一种增强型人工蜂群（hABC）算法，得到更高效的最优解。本文应用的充电站场景模型图如下图所示：

图1 充电站场景模型图

    场景图中各序号对应的解释如下表所示：

表1 序号释义表

No.2

问题描述

    本文考虑了动态和静态两种情况，静态模型不切合实际，但是它有助于更好地理解问题，之后再通过建立动态模型模拟真实场景。

静态模型

    假设充电站中有三条线路Li，1≤i≤3；其中线路Li最多可接收Mi辆电动汽车，可表示为；充电站可接收的总车辆数为：N=M1+M2+M3。每辆车都有三个时间参数，到达时间：；充电时间：；离开时间：。在静态模型中，所有的数据在调度开始前都是已知的，目标是建立一个可行的时间表，即确定电动汽车充电的开始充电时间(1≤i≤3，1≤j≤Mi)，使如下约束得到满足：

    其中Cij是电动汽车Vij的充电完成时间，Ni(t)是在时间区间（t，t + 1）内，在线路Li上充电的电动汽车的总数目，∆∈ [0,1]是一个参数。约束（1）表示电动汽车在到达充电站之后才能开始充电；约束（2）表示确保电动汽车在完成充电之前不会中断充电；约束（3）表示在一条线路中充电的电动汽车数量不能超过N；约束（4）通过参数∆约束任意两条线路之间的最大不平衡。

    整个模型的目标函数定义如下列公式所示，该目标函数的含义为从整个停车场的角度出发，建立合理的充电调度时间表，以最小化整体等待时间。

动态模型

    在动态问题中，电动汽车的到达时间、充电时长、以及预计离开充电站的时间均未知，因此将同一时间段内到达的一组车辆看作一个序列，再统一进行调度。用序列Pk表示在 T(k)时刻到达且未完成充电的车辆，在序列Pk中，有些车在 T(k)时刻已经开始充电，且所有车辆均会在下一序列车辆开始之前结束充电。该模型的目标是建立一个可行的时间表，最小化整体等待时间，并满足从静态问题中衍生的所有约束。

    在每个时间点 T(k)，服务器上运行的一个管理程序会检查自时间点T(k-1) = T(k)−∆T以来是否有新的电动汽车到达。如果有一些新的电动汽车到达，则会创建一个新的序列Pk并加入到时间表中；否则在下一个时间点之前，当前时间表将一直有效。为了在许多电动汽车几乎同时到达的情况下服务器不会出现过载的情况，同时也为了充分利用充电资源，时间间隔∆T设置为2分钟。

No.3

算法描述

    人工蜂群算法(Artificial Bee Colony, ABC)是由Karaboga于2005年提出的一种新颖的基于群智能的全局优化算法，其直观背景来源于蜂群的采蜜行为，蜜蜂根据各自的分工进行不同的活动，并实现蜂群信息的共享和交流，从而找到问题的最优解。标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类: 采蜜蜂、观察蜂和侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源。在标准的ABC算法中，采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息；观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的有价值的蜜源，它们在蜂房附近随机地寻找蜜源。

    对于电动汽车充电调度问题，本文采用了相似的解决方案。人工蜂群算法首先产生SN个初始解或蜜源，之后进入周期性的循环迭代。在每个周期中，都会执行如下几个步骤：采蜜蜂阶段、观察蜂阶段和侦察蜂阶段。当连续多次循环的最优解没有得到改善，计算结果趋于稳定时，即认为满足终止准则。最后，引入局部搜索用于衡量得到的最佳解决方案。

初始化种群

    本文建议将两个调度规则与一些随机蜜源相结合来创建初始种群，这样可以在蜜源质量和多样性之间取得良好的平衡。第一个调度规则是DDR（the Due Date Rule）规则，它按照最晚离开时间的升序对所有车辆进行排序。第二个是LST（the Latest Starting Time）规则，它按照最近开始充电时间的升序对所有车辆进行排序。本文使用的初始种群，三分之一的个体由DDR调度规则生成，三分之一的个体由LST调度规则生成，另外三分之一则是随机生成的。

采蜜蜂阶段

    采蜜蜂负责寻找新的、更好的蜜源。为此，在原始的人工蜂群算法中，每一个采蜜蜂在一个蜜源的解的邻域中生成一个新的候选蜜源。如果比原始蜜源更好的话，新的蜜源将会取代原始蜜源。本文提出了两种不同的方法，并利用遗传算法中的交叉算子寻找新的蜜源。

    在第一种方法中（e_meth1），选择到目前为止能找到的可利用的最优解。本文首先选择将num_trials值最大的蜜源与原始蜜源结合，产生两个新的子蜜源；之后将四个蜜源进行比较，选出其中最好的一个作为新蜜源。如果原始蜜源被取代，新蜜源的num_trials值将归零；如果原始蜜源仍然是所有蜜源中表现最好的一个，蜜源位置不变，其num_trials值将会增加一个单位。这种方法可以产生表现优异的解的基本原理是，经过多次循环后没有得到改善的解就很有可能是一个表现优异的解。同时，在算法的连续循环中总是从不同的蜜源中产生新的解，这可以保证蜜源种群的多样性。

    在第二种方法（e_meth2）中，我们随机抽取蜜源，并将抽到的蜜源成对组合起来用以产生子蜜源。通过这种方式得到的蜜源种群，多样性将优于第一种方法，但是蜜源的质量略差。  

    本文考虑不同的交叉算子来解决问题。第一个是专门为这个问题设计的基于起始时间的交叉（SBX），它随机选择一个时间t0 ∈ [Tmin,Tmax]（其中Tmin是所有车辆的开始充电时间的最小值，Tmax是该时间的最大值）。P1和P2是两个父序列，O1和O2是由父序列产生的子序列。O1是由P1中开始充电时间在t0之前的所有车辆与P2中开始充电时间在t0之后的所有车辆组成的；O2是由P1中开始充电时间在t0之后的所有车辆与P2中开始充电时间在t0之前的所有车辆组成的。第二个算子是经典部分映射交叉（PMX），它常用于置换编码。此外，本文还考虑了第三种方法，即在每个时间点随机选择SBX或PMX中的一个进行计算；该方法比单独使用一个交叉算子得到的结果更好。

观察蜂阶段

    采蜜蜂会将其了解的关于蜜源的信息告知观察蜂，再由观察蜂依概率对蜜源进行选择。观察蜂选择蜜源k的概率为：

    在观察蜂阶段，本文也提出了不同的方法来解决充电调度问题，其基本原理是试图提前安排有延误的车辆或推迟安排没有延误的车辆。

    第一个方法（o_meth1）首先随机选择10%的电动汽车（v1，…，vn）；对于每个选定的电动汽车vi，其延迟被标记。如果延迟为零，vi可能会被推迟安排充电；即尝试将vi与后面的每辆车进行位置交换，直到找到一个改进的方案。反之，如果vi延迟是正数，则将vi 与前面的电动汽车进行位置交换。在任何情况下，一旦找到改进的方案，它就会替换原来的方案，同时num_trials值也会归零。否则，原始方案仍然有效，并且num_trials值会增加一个单元。

    本文使用了两个参数：max_improv和step_size，来对o_meth1进行改进。一旦出现一个更好的方案，就有num_improv←num_improv+1，直到达到最大max_improv。另一方面，选择合适的步长step_size，仅对相隔一定距离的车辆进行交换，这个设置可以提高运行效率，减少计算时间。

    第二种方法（o_meth2）根据时间表的结构选择将电动汽车提前移动或推迟移动。首先要考虑的是提前安排延误的电动汽车，还是提前安排无延误的电动汽车。这个选择和两种电动汽车的占比有关。例如，如果20%的电动汽车无延误，那么就有80%的概率会选择提前安排无延误的电动汽车。这种策略背后的原因是当大量电动汽车有延误时，推迟安排无延误的电动汽车会给大部分车辆提前安排充电的机会，从整体上减少等待时间。此外，num_steps是一个附加的控制参数，它表示每个电动汽车所能尝试的最大交换次数，可以有助于进一步减少计算时间。

侦查蜂阶段

    当一个方案在有限次的试验后无法得到改进时，它的蜜源就会被抛弃，而侦查蜂要做到的就是及时寻找新的蜜源。在侦查蜂阶段，所有num_trials值大于上限的方案都会被替换为随机方案，并为每个方案设置num_trials=0。

局部搜索

    本文将爬山机制应用于人工蜂群算法得出的最终解决方案，方法如下：首先按照计划的顺序安排电动汽车，如果处于位置i的电动汽车（vi）有延迟，尝试提前安排vi，将其安排在与其距离为i∗max_step_perc的电动汽车之前，其中max_step_perc∈[0,1]是为了在原始方案中引入合理的小变化而给出的一个小值。如果得到了一个改进的方案，它将替换原始方案，并重新开始迭代过程。当在整个迭代过程中没有得到改进方案时，局部搜索结束。

No.4

结论

    本文基于实际场景中的电动汽车充电调度问题，提出了一种增强型解决算法。该算法结合了人工蜂群算法和局部搜索算法，并提出了一些其他改进。多样性和质量之间的适当平衡使得这种混合算法在实际运用中可以获得非常好的结果。此外，该算法所花费的合理计算时间使得它可以用于实际环境中的在线调度，下表是增强型人工蜂群算法（hABC）与另外两种算法的执行时间的对比，由下表可以看出本文提出的增强型人工蜂群算法从一定程度上减少了算法执行时间，有利于提高实际应用的效率。

表2 执行时间表

    本文的主要贡献可概括为如下几点：

1、在人工蜂群算法中设计了一些引入领域知识的策略，即在局部搜索中使用邻域结构，并在采蜜蜂和观察蜂阶段做了一些可提升算法性能的改进。

2、新的混合算法在延迟惩罚方面优于以往的所有方法。因此，它可以在满足用户需求的同时充分利用电力资源。

3、通过对电动汽车充电调度问题的静态模型和动态模型的实验研究，对问题的结构有了有趣的见解，这将有利于在充电模型的未来扩展中融入新的特征和目标函数。

关于 天 方 夜 “谈”

天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。

方班人有自己的浪漫，

我们探讨知识，谈论理想，

采摘科研的繁星，

脚下是星辰大海。

天：代表我们的理想犹如天空般浩荡

方：代表方班

夜：代表代码人的冷静与静谧

谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”