电动汽车充电预约配对算法研究*

张 鑫 李 琰 王文斌 赵 玉 徐天奇

(云南民族大学电气信息工程学院 昆明 650500)

1 引言

在传统燃油汽车向电动汽车转型的趋势下，电动汽车充电问题成为了新时代的一个社会问题。电动汽车与传统燃油汽车的本质区别在于充电时间远远长于加油时间，使得电动汽车的充电问题成为电动汽车普及的一个障碍。随着电动汽车充电基础设施的发展，以及各类运营标准的制定和逐步完善，充电站将根据自身的基本情况决定充电桩数目、充电价格、充电类型等，使充电站在充电市场中具有竞争力[1]。对于用户来说，在充电桩的充电类型未知且电动汽车电池剩余电量有限的情况下，去往充电站的过程中容易出现折返[2]、道路拥堵、甚至电池能量耗尽的情况，这明显增加了用户的充电时间与充电成本。大部分用户在购买电动汽车前都会有此顾虑，这可能也是现阶段用户更愿意选择传统燃油汽车而不是电动汽车的原因[3]。电动汽车用户作为较大充电负荷群体，大规模的随机接入电网对电网正常运行也会带来巨大影响。这方面现有的研究主要是通过分析私家电动汽车出行规律及历史用电数据等，进行负荷预测[4]，基于电网需求，从电网的利益诉求出发，从而将电网损失降低到最小[5-6]。充电高峰期时，由于车辆充电周期长，若能缩短排队等待时间就相当于提高了充电桩的利用率，同时也能提高用户的满意程度[7-8]。

为更好地实现电动汽车的推广，本文以预约系统作为连接充电站与电动汽车用户之间的纽带，在明确了当前位置距充电站的距离、充电站充电类型、充电价格、当前等待充电车辆数量以及充电站结束当前充电任务的剩余时间等情况后，为用户推荐合适的充电站，以提高车辆充电成功率。本研究的重点是设计针对此问题的预约算法，并提出相应的调度策略，以达到引导用户进行有序充电的目的。

2 充电预约配对模型建立

当电动汽车电池电量将要耗尽时，电动汽车用户主动向充电服务平台提出充电申请，平台根据一些特定条件为其指派充电站进行充电。考虑一个离散的时间模型，每个时隙的长度固定[9]，比如10 min。假设有一组充电站可以为电动汽车提供充电服务，在当前时段申请充电的电动汽车集合为。我们的目标是为每一辆电动汽车i∈I指派一个充电站j∈J，优化是指在电动汽车排队时间短的基础上减少充电站的空闲，从而提高充电设施的使用效率。

假设一个区域内的所有充电站在一定时间内能够结束现在正在进行的充电任务和已预约成功仍在排队的充电任务，且可以为在这之后预约成功的电动汽车进行充电。经调查，根据现有的技术水平，市面上的电动汽车快速充电大约需要 30 min。设Twait为充电站内充电桩的限制等待时间，限制等待时间即为充电桩可接受等待时间，规定若已预约成功的电动汽车在 Twait内还未到达预约的充电站，则平台将该预约取消[10]。 Twait的取值应能满足一次充电时间(如平均30 min)，并且可以适当留出一些时间用于等待(可能由于道路拥堵或其他突发事件)。但是，由于并不知道每一辆电动汽车提出充电申请时的剩余电量，所以每一辆提出充电申请的电动汽车所需的充电时间可能不同，这就说明了每一轮开始预约时，充电桩提供服务的起止时间不同，会导致在下一轮预约中可提供预约充电服务的充电桩数量受到影响。另外，Twait也可看作一个平均时间段，可以把在这个时间段内提出充电申请的电动汽车和能提供服务的充电桩包含在同一轮预约中，这样既可以降低预约计算的频度，又能提高该区域内电动汽车的充电效率与充电设施的利用率，从而有效地促进充电秩序的有序化[11]。但是，考虑到平均时段Twait的选取会涉及到一部分电动汽车和充电桩的排队时长等复杂性问题，在这里只假设了一个平均时间段waitT 。needT 为充电站结束当前充电任务所需时间，ijT为i电动汽车到j充电桩需要的行驶时间，那么充电桩的等待时间waitT 应满足式(1)

设在区域内规定的汽车最大行驶速度为v。如果一辆电动汽车i在t时刻提出快速充电申请，以规定最大行驶速度v及最方便的路线(拥堵尽可能降低)，可以在时刻内到达该充电站，将这样的充电站构成的集合记为 Mij，Mij为可接受预约的充电站集合。

同一时段内只能为每辆电动汽车指派一个充电站，如式(3)所示

3 算法设计

快速充电预约算法可以减少用户充电等待时间，同时也可以减轻充电站在用电高峰期的拥挤程度，无论是从用户的角度还是从充电站的角度来说，都具有积极意义。本文提出了一种基于充电高峰期的电动汽车成功预约充电数量最大化以及充电低谷期就近预约充电机制，为用户推荐充电站，以提高车辆充电成功率，减少用户等待时间。在这样的调度方案下，可以合理分配充电高峰期的充电资源，从而缓解高峰期充电压力，减少用电低谷期充电桩的闲置时间，在一定条件下为用户提供最优的可用充电桩。算法的总体流程如图1所示。

根据所得到可行预约集合，找到一个当前时隙内的最优指派集。若将电动汽车1与充电桩A预约匹配，则将剩下的可行预约集合ijM 中的元素求和，按此方法将电动汽车1与每个充电桩两两预约匹配一次，取匹配时剩下可行预约集合ijM 中所有元素之和最大的一次匹配，即为最优选择[7]。将此最优选择记录下来，对未预约的电动汽车与充电桩重复上述步骤进行匹配，直到得出所有电动汽车与充电桩的最优匹配集合。

已知在某时段，物联网信息平台得到所有进入该区域的电动汽车数量，以及它们的电量情况，用户向平台发出快速充电申请[12-13]，并查询是否可以尽快进行充电。这里所提的尽快进行充电，指的是充电桩能在一定时间内为电动汽车进行充电服务，同时电动汽车不进行其他工作，只进行寻找充电站充电这一项任务。

4 算例仿真

根据以上观点，基于两个算例来剖析所提出算法的有效性。将预约充电配对问题分为充电低谷期(无需排队)与充电高峰期(需要排队)两种情况考虑。所有算法均基于Matlab R2012a软件进行编程求解。

4.1 充电低谷期算例分析

针对充电低谷期的特征，考虑包含10个充电桩以及5辆电动汽车的充电调度情境，并进行求解。

假设在一个城市区域内的物联网协调电动汽车系统里有10个可以提供服务的充电桩，现有5辆电动汽车提出充电申请。假定充电桩的限制等待时间Twait=40 min，10个充电桩完成当前充电行为开始新一轮充电所需时间在[0，40]之间随机产生，如表1所示。

表1 各充电桩完成当前充电行为开始新一轮充电所需时间

5辆电动汽车分别到达10个充电桩所需的时间随机生成，表2给出了每一辆电动汽车根据城市限速规定，选择最短路线行驶并考虑路线可能会出现拥堵时间的情况下，预计到各个充电桩所需要的时间，且当前电动汽车的剩余电量能支持其在预计的时间内到达其中的任意一个充电桩。

表2 5辆电动汽车分别到10个充电桩所需时间 (单位：min)

由表1可判断出10个充电桩完成当前充电行为的时间都小于waitT，即10个充电桩都属于本轮可以接受预约的充电桩集合。充电桩接受的最大等待时间应小于或等于完成当前充电任务时间与下一轮充电所需时间之和。因此，据表1、表2可得，每一辆电动汽车可以进行预约的集合如式(4)所示

把预约配对分为几次计算，在第一次计算中，将电动汽车1与充电桩A配对，剩余可预约个数为32个；与充电桩B配对，剩余可预约个数为32个；与充电桩D配对，剩余可预约个数为32个；与充电桩G配对，剩余可预约个数为32个；与充电桩H配对，剩余可预约个数为32个；与充电桩I配对，剩余可预约个数为32个；与充电桩J配对，剩余可预约个数为32个。按此方法，将所有提出申请的电动汽车与每个充电桩进行两两配对，取剩余可预约个数最多的一个配对为优先匹配，在此算例中，电动汽车5与充电桩E配对剩余可预约个数最多，为34个，我们将电动汽车5与充电桩E优先进行配对。

在第二次计算中，在电动汽车5已经预约了充电桩E的基础上，按照上述方法，将剩下提出申请的电动汽车与充电桩配对可以得到，电动汽车1预约到充电桩G和电动汽车4预约到充电桩C时，剩下的可行预约个数最多，都为24个。通过对比行驶时间Tij来决定最后的匹配，根据表2可知，电动汽车1到充电桩G需要用时33 min，电动汽车4到充电桩C需要用时23 min，所以电动汽车4到达充电桩C用时更短，更能节省用户的时间，所以接下来预约的是电动汽车4与充电桩C。

按上述方式继续进行配对，得到一个最优的预约配对集合如式(7)所示

将可行集内的配对转化为对应的时间，根据时间长短不同划分为三个阈值段，如图2所示。[1，15]这个阈值是大多数用户都能接受的行驶时间；(15，30]是用户勉强能接受的行驶时间；(30，60]是用户几乎不能接受的行驶时间。根据以上算法得到的匹配集，可以得到的结果如图3所示。

由图3可以看出，在我们得到的最优匹配中，4位用户需要的行驶时间在[1，15]阈值段内，1位用户在(15，30]阈值段内，没有(30，60]阈值段的用户，表明此算法得到的指派有效。

4.2 充电高峰期算例分析

针对充电高峰期的特征，考虑包含5个充电桩以及7辆电动汽车的充电调度情境，并进行求解。假设在一个城市区域内的物联网协调电动汽车系统里有5个可以提供服务的充电桩，现在有7辆电动汽车提出充电申请。假定充电桩的限制等待时间Twait=40 min，其他参数均随机生成。每一个充电桩完成当前充电行为开始新一轮充电所需时间如表3所示。

表3 各充电桩完成当前充电行为开始新一轮充电所需时间

表4给出了每一辆电动汽车根据城市限速规定，选择最短路线行驶并考虑路线可能会出现拥堵时间的情况下，预计到各个充电桩所需要的时间，并且当前电动汽车的剩余电量能支持其在预计的时间内到达其中的任意一个充电桩。

表4 7辆电动汽车分别到5个充电桩所需时间 (单位：min)

与充电低谷期算例一样，由表3、表4可得到每一辆电动汽车可以进行预约的集合如式(8)所示

则对应的可行数组ijM可写为如式(9)所示

按照提出的算法，将电动汽车与每个充电桩两两预约匹配一次，将匹配时剩下可行预约集合ijM中所有元素之和最大的一次匹配作为最优选择，记录此最优选择；将未预约的电动汽车与充电桩重复上述步骤进行匹配，重复上述步骤，得到一个最优的预约配对集合如式(10)所示。充电高峰期算例与充电低谷期算例的配对方式相同，此处不详细展开。

将可行集内的配对转化为对应的时间，根据时间长短不同划分为三个阈值段，如图4所示。同样，[1，15]这个阈值是大多数用户都能接受的行驶时间；(15，30]是用户勉强能接受的行驶时间；(30，60]是用户几乎不能接受的行驶时间。根据以上算法得到的匹配集，可以得到的结果如图5所示。

从图5可以看出，在得到的最优匹配中，3位用户需要的行驶时间在[1，15]阈值段内，2位用户在(15，30]阈值段内，没有(30，60]阈值段的用户，表明此算法在充电高峰期得到的指派同样有效。

5 结论

本文对电动汽车的充电预约问题进行了深入研究以及情景分析，针对高峰期和低谷期两种情况区别处理。通过算例对提出的算法进行仿真验证，结果表明该算法在充电高峰期充分考虑了提出充电申请车辆的综合情况，根据综合情况考虑的结果可能匹配到的不是对单个车辆最短的路线，而是综合考虑了多车辆充电冲突问题后使最多车辆在可接受时间范围内充上电的最优化解决方案；在充电低谷期能优先匹配距离车辆所需时间最短的充电桩。高峰期在保证每个充电桩工作的同时，减小充电桩的工作间隙；低谷期指派距车辆最近的充电桩，提高了所有充电桩的总利用率。