基于时间窗的电动汽车快速充电路径规划方法

何瑞辉 田东伟 汪映辉 石进永

1(海南电网有限责任公司 海南 海口 571000) 2(国电南瑞科技股份有限公司 江苏 南京 210061)

0 引 言

运输系统在全球能源消耗和二氧化碳排放中占有20%～25%的比重，对其具有重大影响。在中国，2014年温室气体(GHG)排放总量的26%来自使用化石燃料的交通运输系统[1]。此外，2012年74%的国内货运由卡车运输，预计2040年货运量将增长39%，2050年货运量将增长约80%。未来运输仍将是温室气体的主要和不断增长的来源，因此政府正在大力提倡和鼓励使用电动汽车。而电动汽车的运营也存在着缺点，例如行驶里程低、充电站数量有限、电池充电时间长[2-5]，这些限制使得电动车队的路线规划成为极具挑战性的组合优化问题。

EVRP是传统汽车路径问题(CVRP)的延伸[6]，由于电动汽车中电池容量有限，需要进行充电才能完成所规划的路线，且相比在加油站的加油过程，充电过程所需的时间较长，文献[7]首次提出了带有时间窗的EVRP，即EVRPTW。EVRPTW假设充电时间是传输能量的线性函数，电池充满电。文献[8-9]放宽了完全充电限制，允许以任何数量的电池容量进行部分充电，这是当前现实中广泛采用的做法。文献[10]通过考虑不同的收费策略并开发了分支价格和切割算法来解决优化问题。文献[11]将EVRPTW扩展到包括EV和ICEV的混合车队，目标是最小化定义为速度和货物载荷的总成本。文献[12]解决了车队规模和混合汽车路线问题与时间窗口，其中车队仅由EV组成，它们最大限度地降低了汽车获取和行驶距离的总成本，两项研究都使用ALNS作为解决方案。文献[13]通过允许使用多种技术进行部分充电来解决EVRP问题。他们限制了总路线持续时间，但没有考虑时间窗口。他们提出了局部搜索算法和基于模拟退火(SA)的元启发式方法。文献[14]研究了在时间窗存在的情况下快速充电选择的影响。文献[15]是第一项将EVRP扩展到考虑非线性充电功能的研究，目标函数最小化将包括行程时间和充电时间在内的总时间。在目前的研究中，尚未出现以降低总成本为目标来进行具有时间窗和快充站的电动汽车路径规划研究。

本文通过引入快速充电选项来扩展不完全充电，并将此问题称为EVRPTW和快速充电(EVRPTW-FC)。本文假设这些快充站配备了多种充电桩类型，将此问题表述为0-1混合线性程序，并提出一种有效解决它的算法。该算法将自适应大型邻域搜索(ALNS)与精确方法相结合，在ALNS的每次迭代中，通过从其路线中移除某些客户和站点来排除可行解决方案，然后通过在需要充电时将移除的客户与站点一起插回到解决方案中进行修复。插入充电站时，还会确定充电桩类型和充电量。然后通过求解混合线性整数程序来定期改进ALNS计算出的解决方案。

1 电动汽车充电模型

(1)

式(2)-式(4)确保每个用户只需进站充电一次且每个充电站最多可进一次。

(2)

(3)

(4)

式中：若车辆通过路径(i，j)，则xij为1，否则其值为0。

式(5)和式(6)表明电动汽车到达和离开充电站。

(5)

(6)

式(7)保证所有离开的电动汽车在规划路径结束时回到充电站。

(7)

服务时间由式(8)-式(10)决定。

τi+(tij+si)xij-l0(1-xij)≤τj

(8)

∀i∈F′,∀j∈VAD

(9)

(10)

式中：τi表示在i点服务开始时间；ei、li表示客户i的服务时间窗；Q表示电动汽车的电池容量。

式(11)和式(12)约束汽车的载荷并确保总载荷不超过货物容量：

(11)

0≤ui≤C∀i∈DD

(12)

式中：C表示车辆载货量；ui表示在i点的剩余货物水平。

式(13)和式(14)分别表示离开客户和站点时的电池SOC。

0≤yj≤yi-(hdij)xij+Q(1-xij)

(13)

式中：dij表示路径(i，j)距离；h表示单位距离所需电量。

0≤yj≤yi-(hdij)xij+Q(1-xij)

(14)

式(15)确定变量yi和Yi的界限，式(16)确保EV完全充满电后离开充电站。

(15)

Yi=Q∀i∈DD

(16)

式(17)确定传递的能量的值，式(18)-式(20)决定用哪种类型的充电桩进行充电。

(17)

(18)

(19)

(20)

最后，式(21)和式(22)定义二元决策变量。

ai,bi∈{0,1} ∀i∈F′

(21)

xij∈{0,1} ∀(i,j)∈A

(22)

2 模型求解

式(23)为最小化路线的总成本。

(23)

第一项代表路线的充电成本；第二项是能源成本，根据离开和到达之间的SOC差异计算得出。

式(24)-式(25)满足客户和充电站的时间窗可行性。

(24)

(25)

式中：si表示服务客户i的时间要求。

式(26)表征电池SOC：如果EV在离开客户i后没有进入充电站，那么通过减去沿曲线消耗的能量来计算到达客户i+1时的SOC(i，i+1)来自客户i的SOC。如果它进入了充电站，则在站j处充电的能量被添加到客户i处的SOC，并且减去沿着曲线(i，j)和(j，i+1)消耗的能量。

(26)

式(27)确保如果EV已进入充电站i，则到达站j的SOC是非负的。

(27)

(28)

式(29)确保充电后的SOC不超过电池容量。如果EV在i和i+1之间充电，则充电桩类型由式(30)-式(32)确定。

(29)

(30)

(31)

(32)

式(33)确保汽车在充满电的情况下离开充电站。式(34)-式(35)确定二元决策变量。

y0=Q

(33)

(34)

(35)

同时引入一个预处理过程，假设i和i+1为路线中的两个连续客户，Fi,i+1是EV的充电站集合，从客户i到i+1路程中可以进站。最初，Fi,i+1=F。然后，本文对站点与客户i和i+1的距离进行比较。例如，考虑两个站点j,j′∈Fi,i+1。如果dij′>dij即j更接近i和i+1，则j就从最优解中排除。为Fi,i+1中的所有站对重复该过程，以减小可行解个数。相同的过程适用于路径中的所有客户对(i，i+1)。

图1显示了四个充电站j、j′、j″和j‴的情况，其可以在客户i和i+1之间进站充电。如上所述，可以清楚地看出j′受j影响。然而j、j″和j‴中的任何一个都不影响另一个，因为两个条件都不满足。因此，Fi,i+1中包含j、j″和j‴。

图1 客户i和i+1之间的充电站集合

在图2中，使用由三个客户变量组成的模型来说明固定路线问题的结构。由于预处理可以排除一对客户之间可以充电的充电站，因此每条曲线与不同的充电站组相关联。于是，本文不需要创建工作站的副本在算法过程进行计算，这大大减少了决策变量的数量。

图2 两个节点之间的充电站

3 算例分析

本文构造了一个包括100个客户和21个充电站的大规模实例，数据在100×100网格上聚类和随机分布。其中根据时间窗口的长度、汽车负载和电池容量的不同将客户分为窄时间窗口(1类)和宽时间窗口(2类)两类，通过随机选择大规模实例中的客户和充电站子集生成小规模实例。本文在Window 10下搭建Visual Studio 2017+CUDA10.1+CPLEX12.9开发环境，采用C++调用CPLEX。本文配置完全依照CPLEX官方安装文档以及安装CPLEX后的c_cpp.html文件；电脑的系统环境变量配置参考CPLEX官方安装文档中的Setting up CPLEX on Windows一节中的设置。

3.1 大规模算例

本文从车队规模和能源成本两方面进行优化并验证使用快速充电的优势。在每过一定次数的迭代后都要对充电决策进行优化，这个次数称为CPLEX的调用频率，数值太小可能会增加运行时间，而太大会降低解决方案的质量。初步实验表明，当CPLEX的调用频率在200左右时，可在运行时间和方案质量两者间达到平衡，所得结果最优，因此本文的算例仿真中将迭代次数定为200。

具体调用CPLEX时，首先在Visual Studio 2017中将Visual Studio调试环境修改为release.x64，在Visual Studio 2017中选中解决方案“CPLEX”从而进行环境配置。在Testcplex属性页中依次选择“C/C++”-“代码生成”-“运行库”设置为多线程，将时间限制设置为7 200 s。将本文算法运行结果与在ALNS下只具备正常充电桩的运行结果进行比较，最优解用粗体表示，结果如表1所示，其中：N11表示1类客户的第一个实例；N21表示2类客户的第一个实例。

表1 大规模客户算例分析

续表1

从结果中可以看出当客户的时间窗口较窄(即1类客户)时，由于使用快速充电可以明显减少EV充电所花费的时间，且汽车可能能够沿着其路线服务其他客户，包括由于严格的时间窗口限制而无法提供服务的客户，因此快速充电更有利。EV可以沿其路线服务更多的客户，由此可以构建更有效的解决方案，可以减少车队的规模或是缩短行程，从而降低总的能源成本。而在时间窗口较宽的2类客户的结果中，快速充电仅在两个实例中减少了车队规模降低了成本。由于在这类问题中，时间窗口很容易满足，汽车可以在其路线上为更多的客户提供服务并且车队规模已经很少(在2到4辆之间)，因此通常不可能减少车队规模。

3.2 小规模算例

将本文算法的结果与CPLEX中给出的最佳边界比较，在Testcplex属性页中设置为单线程并将时间限制设置为7 200 s，结果如表2所示。在“时间”列中报告的计算时间以s为单位。实例名称中“c”和“s”后面给出的值分别代表客户和充电站的数量，如“N11c5s2”表示第一个实例包括5个类型1客户和2个电动汽车充电站，粗体表明在减少车队规模、能源成本或是运算时间上本文算法优于CPLEX计算的部分。

表2 小规模客户算例分析

续表2

结果中的运行时间为7 200 s的CPLEX结果显示在给定时间限制内找到的最佳上限，并不一定是最佳解决方案。CPLEX可以将客户数在10以下的算例进行优化，本文算法也可以找出最优解，但需要的时间更长。而客户数在10到15个的算例中，本文算法在寻找最优解和运行时间方面表现均优于CPLEX。结果表明了本文算法在解决小规模客户的实例中同样具有可行性和高效性。

4 结 语

本文解决了具有时间窗和快速充电桩的电动汽车路径规划问题。在EVRPTW-FC中，充电站配备了多个充电桩，文中考虑了三种充电桩类型，即正常、快速和超快速。由于中型和大型问题难以处理，本文提出一种有效解决问题的算法，将ALNS与精确方法相结合。在ALNS中，引入了针对问题性质的新机制；在精确方法中，在ALNS提供的解决方案中修复了每辆车所相连的客户的顺序，并利用CPLEX来优化充电决策。本文对小型和大型实例测试了算法的性能。在小实例中的结果表明，本文方法在解决方案质量和运行时间方面都优于CPLEX。在大型实例中，结果表明了在车队规模和能耗方面使用快速充电的优势。当时间窗比较窄时，能够获取需要较少EV且降低能源成本的路径规划；而当时间窗宽时，快速充电桩的影响相对较小。

在本次实验中，本文假设所有充电站都已经配备了所有类型的充电桩，但是考虑到高昂的安装成本和缺乏基础设施，实际情况可能并非如此，因此实际中还需考虑充电站的选址问题。进一步的工作还需要解决异构车队案例，其中汽车根据其货物容量、电池条件和车龄进行分类，这会影响到其路径范围和放电/充电时间。此外，本文假设充电站和充电桩始终可用，而在现实生活中，车站中可能存在排队现象，并且EV可能需要等待服务。因此，可以在随机背景下研究充电时间的可变性，从而使得结果更加准确。