考虑充电策略与电池损耗的电动汽车路径优化问题研究

郭 放，杨 珺，杨 超

(1.郑州大学管理工程学院，河南 郑州 450001；2.华中科技大学管理学院， 湖北 武汉 430074)

1 引言

由电池提供动力的电动汽车能够有效地减少尾气污染节约环境治理成本，这一特点促使其在物流配送行业中得到关注与应用[1]。与此同时，国家先后出台了一系列政策法规推进电动汽车产业和配套服务设施快速发展，为电动汽车在物流配送行业的普及提供了有力保障。不同于传统燃油车辆，电动汽车行驶距离受到电池容量的限制，在行驶途中需要去往充电站点补充电量。其次，充电站点的选择会影响电动汽车的配送路径。充电设施数量不足经常导致电动汽车被迫改变行驶线路，绕行前往充电站点。再次，电动汽车所需的充电量是动态变化的，与当前电池剩余电量和车辆后续配送线路有关。电动汽车的充电量和电池状态直接影响充电时间。因此，科学地规划电动汽车配送路径，优化电动汽车物流网络成为了近期的研究热点问题。在实际生活中电动汽车锂电池的充电方式有两种：一种是恒流充电，另一种是恒流+恒压充电。后者的充电效率更高，其过程主要分为两个阶段：第一阶段为恒流快速充电阶段，第二阶段为恒压慢速充电阶段。当电池电量充到电压阈值(此时电量一般为总容量的80%左右)，充电模式由第一阶段转化为第二阶段。此外，车载电池的价格约为整车价格的1/3，部分车型电池价格高达整车价格的45%[2]。放电深度(电池放电量与储存电量的比值)过深(超过70%)会对电池使用寿命造成损害[3]。为了延缓电池性能退化，应避免电池进入深度放电状态。对于已经深度放电的电池，目前较为先进的充电方案对它们有一个涓流充电(低压预充)阶段[4]：电池在快速充电之前有一个低电流慢充的缓和过程，此过程可以一定程度修复因深度放电致电压大幅度下降而造成的电池损伤。本文结合电池充、放电特性，在考虑了绕行、充电时间与电池损耗等成本的情况下研究了电动汽车物流配送路径问题。

近年来，国内外学者从多方面对车辆路径优化问题进行了研究，取得了丰富的成果。Erdogan和Miller-Hooks[5]提出了绿色车辆路径问题(Green Vehicle Routing Problem，GVRP)，对车辆路径和电动汽车充电策略进行研究并建立了以行驶距离最小为目标的混合整形规划模型，运用改进的节约算法和基于密度的聚类算法求得近似解。但是该文章把车辆补充燃料的时间设为定值且忽略了车辆的载重约束。Schneider等[6]考虑了时间窗约束，充电时间取决于充电率和车辆到达充电站的电量状况。随后采用变邻域搜索和禁忌搜索相结合的启发式算法求得模型的近似解。Yang Jun等[7-8]研究了电动汽车物流配送系统的换电站选址和配送路径优化问题，提出了基于禁忌搜索-改进节约算法的两阶段启发式算法和基于贪婪算法-自适应大邻域搜索算法的启发式算法。符卓等[9]针对带软时间窗的需求依订单拆分车辆路径问题及其优化算法进行研究。李进等[10]研究了低碳环境下由第三方提供运输服务的车辆路径问题。在安排车辆路径时，同时考虑了能耗、碳排放和租车费用。揭婉晨等[11]研究了含时间窗的多车型电动汽车车辆路径问题，采用分支定价算法求其最优解。

以上文献均关注的是车辆行驶距离最小化问题，并未涉及电动汽车充电策略。近期有一些文献考虑了充电策略，Felipe等[12]在GVRP问题的基础上加入充电量。Desaulniers等[13]提出了4种充电策略(single-FR，single-PR，multiple-FR，and multiple-PR)，使用启发式算法对充电策略的结果进行比较。Keskin和Catay[14]在(1)电动汽车离开仓库时为满电量；(2)电动汽车回到仓库时恰好将电量耗尽；(3)充电速率为恒定值的假设下，研究了如何根据实际需求来确定充电策略。Bruglieri等[15]采用变邻域搜索的方法来求解带时间窗的电动汽车货物配送路径问题，该研究允许车辆在途充电且充电速率恒定。Penna等[16]对混合迭代局部搜索算法在电动汽车车辆路径与车队规模问题中的运用进行了探索，该研究考虑了由多种不同类型电动汽车组成的车队的货物配送策略，允许车辆在途充电，每次充满且充电速率恒定。

综合来看，(1)多数研究车辆路径问题的文献关注于路线长度的最小化，没有将充电策略纳入考虑范围。(2)考虑了充电策略的文献也仅仅关注于充电量，没有根据电池本身的充电特性刻画模型来考虑充电模式与成本。鉴于此，本文建立基于电动汽车运营成本最小化的允许在途充电的电动汽车车辆路径决策模型，与已有研究主要区别如下：(1)首次将电池损耗成本加入车辆路径优化问题中，将车辆深度放电状态下行驶的距离作为优化对象；(2)电池的充电速率不再是恒定值，而是跟电池当前状态相关的函数；(3)充电时间不仅取决于车辆到达充电站时电池的电量状况和车辆接下来的配送任务安排，还需要在充电时间成本以及深度放电行驶的机会成本之间进行权衡。

2 问题描述及数学模型

2.1 问题描述

物流配送网络G=(V,E)，其中V={v1,v2,…,vn}表示顶点集合，它由顾客集合I、充电站集合J、配送中心o和虚拟配送中心o′共同组成，V=I∪J∪{o}∪{o′}。E={(vi,vj):vi,vj∈V,vi≠vj}表示弧的集合。集合I∪J中每个节点i都具有需求量参数qi，qi表示点i所需配送的货物数量。对于集合J中的节点i，qi=0。集合E中每条弧都包含非负参数dij，dij表示节点i和j之间的距离。K={k1,k2,…,km}表示配送车辆集合。集合K中每一辆车k都包含两个非负参数，即车辆k的最大载重Uk和满电量状态下最长行驶里程Q。集合R={r1,r2,…,rz}是配送路径的集合，每条路径由一辆车负责配送。本文需要解决的问题可以描述为：创造不超过|K|条路径为N位顾客提供货物配送服务，使得(1)配送车辆从配送中心o点出发，服务若干顾客后返回到配送中心；(2)每个顾客只被服务一次；(3)路径rk的配送总重量不能超过车辆最大载重Uk；(4) 车辆在配送途中剩余电量必须为非负值，允许车辆在执行配送任务途中前往站点充电；(5)整体运营成本最低。

2.2 定义变量

图1 充满电池所需时间

T=

(1)

2.2 数学模型

基于上述条件，数学模型如下：

(2)

s.t.

(3)

∀h∈V{o,o′},k∈K

(4)

(5)

(6)

(7)

uhk≤ugk-qhxghk+Uk(1-xghk)

∀h∈V{o},g∈V{o′},g≠h,k∈K

(8)

uok≤Uk∀k∈K

(9)

uhk≥0 ∀k∈K,h∈V{o′}

(10)

∀h∈V{o},g∈V{o′},g≠h,k∈K

(11)

(12)

(13)

(14)

(15)

(16)

xghk∈{0,1} ∀h∈V{o},g∈V{o′},k∈K

(17)

上述模型中，目标函数(2)表示最小化运营成本。式(3)表示每个顾客点只被服务一次。式(4)表示各点车流量平衡。式(5)表示配送车辆从配送中心出发，服务若干顾客点后最终回到出发点。式(6)表示每辆车最多服务一条路径。式(7)表示参与配送任务的车辆数目不能超过拥有的车辆总数。式(8)表示配送车辆按照路径途经各点的剩余货物量。式(9)确保任何一条路径中的顾客总需求量不能超过提供服务的车辆的最大载重量。式(10)表示剩余货物量为非负。式(11)表示配送车辆按照路径途经各点的剩余电量。式(12)表示车辆离开充电站点后的剩余电量。式(13)表示充电量为非负数，且充电后的电量不能超过电池容量。式(14)表示车辆离开配送中心时电池是满电量状态。式(15)表示车辆剩余电量在顾客点无变化。式(16)确保车辆有充足的电量完成预定线路的配送任务。式(17)表示变量属性。

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

k∈K,j∈J,i∈{1,2},n∈{1,2,3}

(27)

(28)

3 启发式算法MCWIGALNS

本章采用启发式算法MCWIGALNS解决电动汽车配送路径与充电策略问题。MCWIGALNS分为三部分：首先采用Erdogan等[5]提出的改进节约算法求得初始路径集合，将其作为当前路径集合代入充电策略子问题阶段。然后，迭代贪婪算法为服务路径在合适的位置加入站点，电动汽车在站点的充电量取决于当前电池状态和车辆后续配送任务。随后，将充电策略子问题选择的充电站点集合作为输入参数代入到路径子问题阶段，采用自适应大邻域搜索算法搜寻最优路径集合并将其反向传递给充电策略子问题阶段。算法通过多次迭代使可行解逐渐向最优解靠近。图2给出了MCWIGALNS算法流程图。

图2 MCWIGALNS算法流程图

3.1 改进节约算法

初始化阶段电动汽车行驶里程约束被松弛。

步骤1：顾客点i∈I生成服务线路(o-i-o)。

步骤2：计算合并两条路径的节省成本。

步骤3：根据步骤2的计算结果，按照节省成本由高到低合并路径。检查车辆容量约束是否满足新路径的服务要求。如果不满足，则取消这两条路径的合并，继续合并其余路径。如果满足，保存新路径后继续合并剩余路径。

步骤4：如果新路径满足继续合并的条件，返回步骤2。否则，输出路径的初始解。

3.2 迭代贪婪算法

本节采用迭代贪婪算法为路径选择合适的充电站点使得完成所有配送任务所需付出的成本最低。

(1)安置成本分析：算法首先删除掉路径中存在的充电站点，根据安置成本的高低为路径重新选择充电站点。

(c)充电时间：车辆到达充电站i后，首先将电量充到恰好能到达终点或者下一个站点(充电量上限为充满)得到初始充电时间，如果充满后仍不足以到达终点或者下一个站点，则令该充电时间为一个极大值；其次，检查车辆电池状态(SOC)，如果电池电量低于0.8Q且该路径在点i之后还安排有其余充电站点，则将这部分电池的电量充至0.8Q，更新充电时间和SOC。如果电动汽车以当前电量行驶到终点或下一站点的剩余电量低于ηQ，则比较继续慢充的时间成本与深度放电的电池损耗成本，计算出最佳的充电量。

j∈J,v∈V,rk∈R

(29)

β1+β2+β3+β4+β5=1,β1,β2,β3,β4,β5≥0

(30)

(31)

(32)

(33)

(34)

(35)

(2)本环节包括三个阶段：可行度分析阶段、站点加入阶段以及优化阶段。

(a)可行度分析阶段

步骤1：设置当前解为不可行解；

步骤2：删除当前解路径中所有的充电站点；

步骤3：将删除站点后的路径集合作为当前解；

步骤4：计算顾客点可达性参数，判断当前路径是否可行，将不可行路径送入下一阶段。

(b)站点加入阶段

步骤5：对于不可行路径rk，将其第一个断点前面顾客点依次加入备选集合Bk，直到遇到充电站点或者回到起点为止。

步骤9：更新各个点的可达性参数，判断路径的可行性。如果全部路径都可行，将当前解送入下一阶段。否则，将不可行路径返回步骤5。

(c)优化阶段

本阶段通过交换和移动充电站点的位置进一步优化当前可行解，如果优化后仍为可行解且目标值更优，则更新当前解和相应充电策略。

算法通过交换充电策略和路径策略的信息，使可行解在迭代过程中逐渐向最优解靠近。迭代贪婪算法安排安置成本最低的充电策略。新的充电策略作用于路径策略。路径策略通过自适应大邻域搜索来完成。

3.3 自适应大邻域搜索

自适应大邻域搜索由Ropke和Pisinger[17]提出，此算法的主要思想是通过从当前路径中删除一部分顾客点并将其重新放入路径这一过程的反复迭代，到达在更大邻域范围内搜索新解的目的。

3.3.1 定义阐述

(a)大邻域：算法通过删除策略删除nq个顾客并将其暂存在顾客等待集合(RB)。随后通过插入策略将RB中顾客重新放回路径中从而得出新的解。

(b)删除和插入算子：上文提及的删除和插入策略即为算子。

(d)惩罚函数：本文对解的搜索范围进行适当延展。对于违反行驶里程的解，其目标函数值中需加入惩罚值：

(36)

M是极大值，qvk是前一阶段顾客点可达性。

(e)终止标准：采用Adulyasak等[18]提出的基于模拟退火的终止标准。如果邻域解s′优于当前解s则保留邻域解，否则邻域解被保留的概率为e-(z(s′)-z(s))/T。初始温度T0=10000，Tn=cTn-1，冷却速率c=0.995。当迭代次数达到给定的最大次数时，整个搜索过程结束。

3.3.2 自适应大邻域搜索流程

步骤1：将迭代贪婪的结果作为初始解s0，初始解赋值给当前解s和最优解s*，进入第一次迭代；

步骤2：在迭代次数小于给定的最大次数时，选择一对删除和插入算子，将当前解s赋值给邻域解s′。如果迭代次数达到给定的最大次数搜索结束；

步骤3：使用选择的删除算子处理s′；

步骤4：使用选择的插入算子处理s′；

步骤5：如果此时s′满足接受标准，则将s′赋值给当前解s，否则放弃；

步骤6：如果z(s)

步骤7：更新各项算子的得分和权重，迭代次数+1，返回步骤2。

3.3.3 删除算子

Random removal(RaR)：从当前解中随机删除nq个顾客点并将其存入等待集合(RB)。

Related removal(ReR)：从当前解中挑选出跟指定顾客点i相似的顾客点，将它们和i点一同删除并存入集合RB[20]。随机选择一个顾客点i，通过参数Iden(i,j)=α1dij+α2|qi-qj|+ηij来判断i和j的相似度。其中α1和α2是权重系数，α1+α2=1。dij是两点之间的距离，|qi-qj|是两点需求量的差值。如果i和j属于同一条路径，ηij=1，否则ηij=0。类似于BWR，被挑选出来的顾客点会以一定的概率被删除，概率由参数ρr。

Request graph removal(RGR)：由Pisinger和Ropke[21]提出，图中边的权重为这条边在最优解中被车辆经过的次数，两个权重最大的顾客点被认定为最相似的点。RGR的删除机制类似于ReR。

Station-based removal(SBR)：随机选择一个站点，删除与之相连的顾客点。

Single point removal(SPR)：两个充电站点或者充电站点和o点之间的区域为一个服务区域。SPR的目的是破坏一个现有的服务区域构建新的车辆路径。在路径中随机选择一个操作点，删除该点到它相邻充电站点(或o点)之间的所有顾客点。

Binary removal(BiR)：BiR是SBR的一种特殊情况，区别在于BiR选择路径的中间点为操作点。

3.3.4 插入算子

3.4 优化最新解

步骤1：按顺序删除路径rk中充电站点。如果删除操作导致路径不可行，进行步骤2；

步骤2：选择增加成本最低的点作为路径分裂点，将rk分为两条新的路径rk1和rk2。增加成本计算方法类似于ΔZik；

步骤3：如果最新解更优，则更新当前解。返回步骤1，直到路径数到达指定的最大可用车辆数或者当前解不能再被进一步优化。

4 实验结果及分析

实验的计算机参数配置为Intel(R) I5-4460，3.20GHz，8GB RAM。算法在JAVA实现为单线程代码。

4.1 测试用例

数据来源于三部分，一部分是Augerat等[22]、Taillard[23]和Golden等[24]提出的3组不同规模算例，算例可从网站http://neo.lcc.uma.es/vrp/vrp-instances/ 获取。一部分是Yang Jun和Sun Hao[7]的实验参数，表1对算法中部分参数的取值进行了介绍。其余数据参考相关专业网站，如工资标准、电动货车售价以及充电桩充电速率等。算例将货车司机的时薪作为充电时间的单位成本。以最有可能率先大规模使用电动物流车辆的发达地区为例，北上广三地的最低工资标准分别是21、19和18.3元/小时，本文折中选取20元作为单位时间成本。以某款由锂电池提供动力的电动货车A为例，其售价330000元，最大行驶里155km(40km/h 匀速法测量)。考虑到实际工作环境，本文假设其最大行驶里程100km。根据Green Car Report[2]的研究结果，电池约占电动汽车成本的1/3，估算A的电池成本约为100000元。锂电池可以重复充电600—1000余次，即电池最多可以支持车辆行驶100000km，平均每公里电池成本1元。电池使用寿命与诸多因素有关，本文仅考虑深度放电对其的影响。长时间深度放电会导致电池寿命下降30% —50%，据此计算深度放电行驶的机会成本为每公里1.4-2元，本文选择2元作为深度放电行驶的单位成本。充电速率取值参考国家电网充电桩实际参数，直流快充桩2小时能将一辆电动汽车的电量从0充到80%，慢充桩每小时为车辆充入10% 的电量。

表1 参数赋值

4.2 邻域搜索配置

本节对上述算子的寻优能力进行比较，挑选出优秀的算子组合以到达提高算法效率的目的。算子入选的评价机制如下：算子在至少一半的算例中被使用次数高于所有算子被使用次数的平均值。考虑到算法中包含随机参数，算例皆采用默认参数运行10次，取其平均值作为最后结果。表2展示了删除算子的比较结果。根据上述入选评价机制选择了RaR、RGR、ReR、SPR和BiR。插入算子的比较结果见表3所示，BR2I、BR3I、AR2I和AR3I满足要求。但是，RkI比AGI 的计算效率低，尤其是Ropke和Pisinger[17]对算法计算效率的影响较为明显。AGI能够在更短的计算时间内得到与BR3I较为接近的解，本文在权衡解的精确性和运算效率之后采用AGI替代BR3I。表2-3中“*”表示被挑选出来，在下面的实验中会用到的算子。

表2 删除算子的性能比较

表3 插入算子的性能比较

4.3 实验结果分析

4.3.1 模型与算法的验证分析

为了评估模型的准确性以及算法的寻优能力，本文使用能被CPLEX12.6求解的小规模算例进行计算。为保证实验的一般性，在Augerat等[22]算例P-n16-k8中选择5组实例数据，实例数据只选用了初始算例的最后n个顾客点。每组实例包含的顾客数与可用车辆数目不同。设定CPLEX运行时间的上限为3 小时(10800s)。“*”表示此解是CPLEX运行3小时得到的可行解。“#”表示CPLEX未能在规定时间内找到可行解。测试结果整理如表4所示。第2列和第3列分别是算例包含的顾客点数目和可调配的车辆数。第4列到第7列依次为CPLEX求得的最优解、最优解的充电时间、深度放电行驶距离、求解时间(s)。第8列到第11列是MCWIGALNS的求解结果。第12列是算法与CPLEX最优解的相对差值(Gap)：(算法的最优解-CPLEX求出的最优解)/CPLEX求出的最优解。通过表4可以看出两者的结果非常接近，MCWIGALNS的求解效率较高，验证了本文提出的模型和算法的正确性。

表4 实验结果对比

4.3.2 运营成本影响性分析

本节将考虑充电时间与电池损耗的VRP模型与传统VRP模型进行对比研究。从Augerat等[22]和Taillard[23]两大类数据集中分别选取4组和3组实例，比较算例在两种数学模型下的最优运营成本。图3对两种模型在不同案例中行驶路径总长进行比较。图3表明两种模型在不同算例中的行驶距离非常接近，模型二的距离略短于模型一。图4对比了两种模型在不同案例中运营成本。其中，模型二在得出最优解后，根据最优解的路径计算其相应的充电时间与深度放电行驶成本并加入到总成本中。由图4可以看出，模型一在所有算例中的运营成本皆低于模型二。可节约成本((成本1-成本2)/成本2)的均值为22.89%。在图5-6充电时间和深度放电行驶成本的比较中可以看出，模型一的表现更好，该模型在所有算例中的充电时间和深度放电行驶成本全部低于模型二。模型一可以在总路径略微增加的情况下，通过改变路径策略来减少充电时间和深度放电行驶路程，最终到达降低运营成本的目的。

4.3.3 算法寻优能力对比分析

下文采用三组不同规模算例验证MCWIGALNS的路径优化能力，并与传统禁忌算法TSMCWS和自适应大邻域搜索SIGALNS进行对比。实验算例从Augerat等[22]、Taillard[23]和Golden等[24]中分别选取10组、12组和2组，算例包含的顾客点数目从16到480不等，可调配车辆数从8辆到38辆不等。对照算法的实验数据来自于Yang Jun和San Hao[7]的研究成果。为增强对比结果的公正性，需要使算法目标函数保持一致。本节实验中MCWIGALNS松弛了充电时间和深度放电的惩罚并赋予被选择的充电站点相应的建设成本。算法运行10次并将最优解记录到表5。表5第3列和第4列分别是算例包含的顾客点数目和可调配的车辆数。第5列到第7列依次为TSMCWS、SIGALNS和MCWIGALNS的最优解，第8列是MCWIGALNS求解时间(s)。第9列和第10列分别是TSMCWS和SIGALNS的最优解与MCWIGALNS最优解的相对差距。由表5可知，MCWIGALNS与两种算法第一组算例最优解的相对差距最大分别达到了11.1%和3.4%，只有在算例1中，SIGALNS得到了最优值。在第二组和第三组算例中，TSMCWS在算例17和24得到了最优解，根据Ropke和Pisinger[17]的研究结论解释为个别特殊顾客点的空间分布对自适应的大邻域算法的可行解产生了不良影响。通过比较可知，MCWIGALNS搜索能力优于其余两种算法。此外，实验结果显示对不同的算例，MCWIGALNS的求解时间大相近庭，同类实例求解时间随模型规模呈现出上升趋势。规模相近的不同类型实例的求解时间也有较大差异。这表明该算法的性能同时受到问题规模和数据自身特性的影响。总体来说，计算时间在企业可接受的时间范围内，不影响算法的一般实用性。

图3 配送距离对比

图4 运营成本对比

图5 充电时间对比

图6 深度放电行驶距离对比

图7 算法最优解平均值对比

图8 算法最优值与均值差异对比

表5 算法结果对比

图7展示了对照算法平均解与MCWIGALNS的平均解的相对差距。其计算方式为(对照算法平均解—MCWIGALNS的平均解)/MCWIGALNS的平均解。图7展示了算例平均值的相对差值为正数表明MCWIGALNS的平均解小于与其进行对比的算法。由此可见，表5展示的各算例结果中MCWIGALNS的解更优并非偶然，其平均值也优于其余两种算法。图8展示了SIGALN和MCWIGALNS计算结果的平均值与最优值的相对差值，可以看出MCWIGALNS的最优解与解的平均值差值波动小于SIGALNS，MCWIGALNS求解的稳定性优于SIGALNS。

5 结语

本文在允许在途充电的电动汽车的配送车辆路径问题的基础上引入了两个重要概念：充电时间函数和深度放电行驶距离。将车辆在配送货物途中的充电时间和电池损耗成本纳入求解的目标函数并建立了它的线性规划数学模型，统筹安排车辆的行驶路径和充电策略使得物流企业运营成本最低。此外，还设计了一种求解该问题的改进型算法MCWIGALNS。实验结果表明，考虑充电时间与深度放电成本的模型可以在略微增加配送距离的情况下，较大幅度压缩时间与电池损耗成本，到达降低运营成本的目的。算法MCWIGALNS对VRP有出色的求解能力，提升了该问题理论成果的实用性。

以下几方面还有待进一步研究，本文所考虑的充电速率仍为确定性分段线性函数形式，深度放电过程中也仅考虑了行驶距离，并未考虑深度放电过程对电池损耗的非线性变化；其次，设计更加高效的策略将是未来工作的一个重点。