考虑弹性时间窗的电动车辆配送路径问题研究

广告 | 点击查看

摘要：电动车辆充电时间长和充电设施不足的问题严重影响了其在物流配送领域的有效推广。针对该问题，提出了换电模式下电动车辆配送路径问题。首先构建了包括车辆租赁成本、运输成本、惩罚成本和换电成本在内的物流运营成本最小化的数学模型，并使用弹性时间窗代替传统软时间窗；其次，应用改进的遗传算法对模型进行求解；得出最优的配送方案，验证了模型和算法的有效性，并与传统软时间窗下的优化结果进行对比，研究表明采用弹性时间窗可以有效降低物流运营成本。

关键词：电动车辆路径问题、换电模式、弹性时间窗、改进遗传算法

作者：李辉

重庆交通大学经济与管理学院

一

引言

电动车辆因其绿色环保、节能的优点被广泛应用于城市物流配送领域。不同于传统VRP问题，电动车辆路径优化问题（EVRP）要将电动车辆访问充电站补充电量这一过程考虑在内，增加了问题复杂程度[1]。电动车辆补充电量时会产生较长的等待时间，极大地影响了配送服务时效性。而配送服务时效性是影响客户满意度的关键因素，较高的客户满意度可以给物流企业带来经济效益的提升[2]。因此，越来越多的物流企业开始重视配送服务的时效性，如何提升电动车辆配送的时效性成为了研究的热点。

相关研究大致可以分为两类，一类是增加客户服务时间窗约束，并对违反约束的行为增加相应的惩罚成本，以此来提升配送服务时效性。甘俊伟[3]等采用两阶段法构建了协同考虑能耗与时间窗的电动冷藏车辆路径优化模型。葛显龙等[4]研究了带软时间窗的电动车辆路径优化问题，建立了以最小化行驶成本、时间窗惩罚成本以及车辆使用成本为目标函数的数学模型。Xiao等[5]研究了具有时间窗口和混合回程的EVRP问题，提出一种多样性增强的模因算法求解该问题。黄建华等[6]探讨了动态负载下电动汽车耗电速率和不完全充电策略问题，构建了带软时间窗的车辆路径优化模型。另一类研究是通过采用换电模式提升电动车辆的配送效率。换电模式通过在换电站更换满电的电池为车辆补充电量，其所需的时间远远小于充电模式，根本上解决了电动车辆充电时间长的问题。Zhou等[7]研究了换电模式下具有混合时间窗约束的电动配送车辆路径优化问题。郭放等[8]提出了考虑货物分类需求的电动汽车路径优化与换电策略问题。Yang等[9]提出了一种考虑换电站选址的电动车辆路径优化问题。Jie等[10]提出换电模式下具有容量限制的两级电动车辆路径问题，并设计了一个结合列生成和自适应大邻域搜索的混合算法来解决该问题。

本文从上述研究入手，研究换电模式下带时间窗的电动车辆配送路径优化问题，并引入了弹性时间窗的概念，在软时间窗的基础上考虑了客户对于违反时间窗的容忍度，更加具有现实意义。

二

数学模型

1.问题描述

一个配送中心采用电动车辆为多个客户进行配送服务，每个客户的需求和地理位置已知。要求配送车辆在客户服务时间窗内进行配送，早到或晚到都要支付一定的惩罚成本。配送车辆在配送途中电量不足时前往换电站换上满电状态的电池后继续进行配送，配送完成后返回配送中心。在传统的软时间窗中，无论车辆是早于或者晚于客户服务时间窗到达，都允许提供服务，但是要求配送方支付相应的惩罚费用，这种惩罚费用一般与时间偏差的程度是简单的线性关系。然而，对于最佳服务时间窗的服务时间偏差，顾客有容忍和不容忍之分。因此，本文在传统软时间窗的基础上，考虑客户的容忍范围，提出了弹性时间窗，如图1所示。

图1 弹性时间窗示意

图1（a）中[a,b]是客户服务时间窗，图1（b）中[m,n]是弹性时间窗。换算关系分别为m=a-(b-a)/ts和 n=b+(b-a)/ts，ts代表服务客户所用时间。该公式表明客户的弹性时间窗与客户原本的服务时间窗和客户所需服务时间有关。当客户服务时间窗范围越大，所需服务时间越少时，代表其对违反服务时间窗的容忍度越高，弹性时间窗的范围就越大。当配送车辆在时间窗[a,b]内到达时，惩罚成本为0；配送车辆在[m,a)、(b,n]内到达时要支付一定的惩罚费用；配送车辆在[m,n]范围外到达时，每单位时间要支付更高的惩罚费用。模型考虑载重约束、电量约束、时间窗约束等，以物流运营成本最小化为目标，并作出如下假设：

(1)电动配送车辆充电速率恒定。

(2)电动配送车辆耗电量与行驶里程成正比并匀速行驶。

(3)换电站可以满足多辆车同时换电且换电时间忽略不计。

2.符号定义

基于对问题的描述和假设，下面对模型所需变量和参数的符号进行定义。

表示所有节点集合；o表示配送中心；C表示客户点集合；S表示换电站集合；K表示配送车辆集合。Q为车辆载重；B为电池容量；r表示单位行驶里程的电量消耗；qi为客户i的需求量；uik 表示配送车辆k离开客户i时的剩余载货量；tsik表示配送车辆k在客户i的服务时间；taik为配送车辆k到达节点i的时间；dij表示节点i到节点j之间的距离；tlik为配送车辆k离开节点i的时间；tlijk为配送车辆k从节点i到j的行驶时间；Eijk表示配送车辆k从节点i到j所消耗的电量；AEik表示配送车辆k到达节点i时的电量；LEik表示配送车辆k离开节点i时的电量；[ei,li]表示客户i的服务时间窗；[Ei,Li]表示配送中心时间窗；配送车辆在弹性时间窗和服务时间窗之间到达的惩罚成本系数分别为pe和pl；配送车辆在弹性时间窗外到达的惩罚成本分别是pm和pn；k表示配送车辆k的租赁成本；v表示配送车辆单位里程的运输成本；为单次换电费用；Pik表示配送车辆k到达客户i的惩罚成本；M为一个极大的数；表示卸货速率；xijk表示配送车辆k是否从节点i到达节点j，如果是，xijk=1；否则，xijk=0。

3.模型建立

基于上述条件，构建以下模型：

公式（1）是目标函数，表示物流运营成本最小化；公式（2）~（5）是物流运营成本的组成部分，分别是车辆租赁成本、车辆运输成本、车辆换电成本和车辆惩罚成本；公式（6）表示每个客户只被一辆车服务一次；公式（7）确保流量的平衡，即每辆车进入某点的次数和离开该点的次数相等；公式（8）~（9）是车辆载重约束；公式（10）表示车辆电量消耗的计算方法；公式（11）~（13）限制了配送车辆在各个节点的电量状态；公式（14）表示配送车辆途经各个客户之间的电量关系；公式（15）~（16）表示配送车辆不能违反配送中心时间窗；公式（17）表示配送车辆的服务时间；公式（18）表示配送车辆途经各个客户的时间关系；公式（19）表示配送车辆服务客户时所产生的惩罚成本；公式（20）表示决策变量xijk的取值范围。

三

算法设计

本文所研究的问题属于VRP问题的扩展，是一个典型的N-hard问题，求解较为复杂，现有研究多采用启发式算法进行求解[11]。遗传算法是一种常用的启发式算法，其通过模拟自然进化过程的全局搜索机制，具有快速寻找新解的能力，能够在合理的时间内找到复杂的组合优化问题的较优解决方案[12]。本文对传统的遗传算法进行了改进，在遗传操作后加入了局部搜索操作，旨在提升算法的寻优能力。改进的遗传算法的具体流程如图2所示。

图2 算法流程图

1.染色体编码设计

本文采用整数编码的方式构建染色体[13]。对于包含1个配送中心、10个客户和2个换电站的配送问题，[1-2-3-4-5-11-6-0-7-8-9-12-10]表示该问题的一个可行解。其中，0表示配送中心；1~10表示客户；11和12表示换电站。

2.种群初始化

本文采用Sweep扫描算法构造初始种群。首先，在配送区域内随机选择一个客户点，将配送中心与该客户点相连形成一条射线，以配送中心为极点，该射线为极轴；其次，以极轴为初始位置进行逆时针旋转，计算区域各个客户点的极角θ，并按θ大小升序排列客户；然后按照顺序依次将客户加入配送路径并根据车辆载重划分不同的配送路径；最后，在不满足电量约束的配送路径中加入换电站。

3.遗传操作

(1)选择算子

遗传算法采用轮盘赌方法根据适应度大小从种群中选择较优的个体[14]。在遗传算法中适应度用来评价个体的优劣，适应度越大，个体越好，被选择的概率越高。本文的优化目标是物流运营成本最小化，因此将成本函数的倒数作为适应度函数。

(2)交叉算子

本文采用部分映射交叉(PMX)算子对染色体进行交叉操作。PMX通过随机选择两个交叉点确定交叉区域。执行交叉后一般会得到两个无效的染色体，个别基因会出现重复的情况，为了修复染色体，可以在交叉区域内建立每个染色体的匹配关系，然后在交叉区域外对重复基因应用此匹配关系就可以消除冲突。

(3)变异算子

本文采用多点突变算子对染色体进行变异操作。突变操作是为了避免使算法陷入局部最优，多点突变增强了跳出局部最优的能力。首先随机选择多个突变点，然后随机交换突变点的位置生成突变后的个体。

4.局部搜索

传统遗传算法中种群经过交叉后产生的子代会进入变异操作，但概率低的变异操作搜索能力较差，将局部搜索与基本的遗传算法结合，有助于算法跳出局部最优，使算法更有效。局部搜索引入了LNS算法中的摧毁算子和修复算子，通过对当前解进行破坏和修复产生新解并对不满足电量约束的解加入换电站[15]。如果产生的新解优于当前解则用新解代替当前解，对种群中的每个个体执行上述步骤直到整个种群更新完毕。

(1)相关性破坏算子

相关性破坏算子是指通过破坏路径中相似的客户节点来对当前解进行破坏。本文的相关性计算公式如下：

(2)遗憾值插入修复算子

本文使用遗憾值修复算子将破坏算子移除的客户重新插入到遗憾值最大的插入位置中。式（22）是遗憾值的计算公式：

四

实例验证及结果分析

1.实例数据

本文以重庆市某小型配送中心及其所服务的30个客户为例，对提出的模型和算法进行验证，该配送区域内存在5个换电站可供使用。在已有文献[16,17,18]和多次实验的基础上，算法和算例的参数设置如表1所示。

表1 参数设置表

2.优化结果分析

本文应用改进的遗传算法对上述实例进行求解，优化效果如图3所示。图3（a）是应用改进的遗传算法求解上述实例得到的优化过程图，图3（b）是传统遗传算法的优化过程图。对比两图可以看出，本文提出的改进遗传算法的求解效率和优化结果均优于传统遗传算法，能在较少的迭代次数中得到更优的解，验证了本文所提出算法的有效性。

图3 算法运行收敛图

分别在弹性时间窗和传统软时间窗情况下，对上述实例进行求解。两种情况下的物流运营成本、行驶距离和车辆平均装载率如表2所示。

表2 优化结果

由表2可知，采用弹性时间窗的物流运营成本比采用传统软时间窗降低了14.9%，行驶距离减少了47.7km，车辆平均装载率提升了16.1%。研究结果表明，采用弹性时间窗，适当放宽时间窗约束，可以降低物流运营成本，缩短配送车辆行车距离，提高车辆装载率，从而提升企业的物流效益。

五

结语

电动车辆具有节能、环保的特点，其在配送领域的应用具有巨大的环境和经济效益，因此对电动配送车辆路径优化问题的研究具有极大的现实意义。本文首先建立了考虑换电和弹性时间窗的电动车辆配送模型；其次，设计了改进的遗传算法对模型求解，提升了求解效率；最后，对比分析了不同时间窗的优化结果。结果表明：适当设置弹性时间窗能降低物流运营成本，为企业带来更大的经济效益。

参考文献:

[1] 郭戈,张振琳.电动车辆路径优化研究与进展[J].控制与决策,2018,33(10):1729-1739.

[2]孙奇,马良.基于客户满意度的车辆路径问题的混合蝙蝠算法[J].上海理工大学学报,2019,41(02):160-166.

[3] 甘俊伟,张晓蓉,李钧.能耗与时间窗协同考虑的电动冷藏车辆路径优化[J].工业工程与管理,2022,27(01):204-210.

[4]葛显龙,竹自强.带软时间窗的电动车辆路径优化问题[J].工业工程与管理,2019,24(04):96-104+112.

[5]Xiao J, Du J, Cao Z, et al. A diversity-enhanced memetic algorithm for solving electric vehicle routing problems with time windows and mixed backhauls[J]. Applied Soft Computing,2023,134:110025.

[6]黄建华,刘方翔.动态负载下电动汽车充电策略及路径优化问题[J/OL].计算机集成制造系统:1-23[2023-09-15].

[7]Zhou B, Zhao Z. Multi-objective optimization of electric vehicle routing problem with battery swap and mixed time windows[J]. Neural Computing and Applications, 2022: 1-24.

[8]郭放,杨珺,杨超.基于货物分类配送的电动汽车路径优化与换电策略研究[J].运筹与管理,2018,27(09):33-44.

[9]Yang J, Sun H. Battery swap station location-routing problem with capacitated electric vehicles[J].Computers & operations research,2015,55:217-232.

[10]Jie W, Yang J, Zhang M, et al. The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology[J]. European Journal of Operational Research, 2019, 272(3):879-904.

[11]李浩然.车辆路径优化问题综述[J].信息与电脑(理论版),2022,34(03):27-30.

[12]胡钟骏,周泓.改进遗传算法的需求可拆分车辆路径优化研究[J].计算机仿真,2018,35(03):80-83.

[13]王勇,罗思妤,周雪等.多中心共同配送开闭混合式的车辆路径优化问题[J].系统管理学报,2023,32(02):215-232.

[14]李嫚嫚,陆建,安颖.考虑客户偏好的双目标时间窗指派车辆路径问题[J].东南大学学报(自然科学版),2018,48(03):568-575.

[15]伍国华,毛妮,徐彬杰等.基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法[J].控制与决策,2023,38(01):201-210.

[16]Ferro G, Paolucci M, Robba M. Optimal charging and routing of electric vehicles with power constraints and time-of-use energy prices[J]. IEEE Transactions on Vehicular Technology, 2020, 69(12):14436-14447.

[17]Wang Y, Zhou J, Sun Y, et al. Collaborative multidepot electric vehicle routing problem with time windows and shared charging stations[J]. Expert Systems with Applications, 2023,219:119654.

[18]樊自甫,程垚,丁惠琳.考虑货物载重的软时间窗电动车辆路径优化研究[J].数学的实践与认识,2022,52(03):109-120.

———— 物流技术与应用 ————

编辑、排版：罗丹

本文内容源自

欢迎文末分享、点赞、在看！转载请联系后台。

广告宣传