基于两阶段算法的时变电动车辆路径问题

文/邓诗言

1.引言

随着城市化的加快和人口密度的提高，城市拥堵状况日益严重。在此背景下，城市配送问题受到极大的影响。在使用电动车进行配送时，如果不考虑道路拥堵的情况，将会大大增加配送时间。因此，在考虑时变路网的情况下，合理规划电动车的运输路线，制定高效的配送方案至关重要。从2000年开始，就有国内外学者对时变网络下的车辆配送路径问题进行了研究，与传统的静态路网不同，时变路网会随时间而发生改变。王卫国[1]等学者建立了双目标的车辆配送路径模型，通过考虑车辆时变行驶速度的方式来描述时变路网，并改进了传统求解静态路网下车辆路径问题的算法。马华伟[2]针对时变车辆路径问题，以先进先出为原则，提出了一种两阶段启发式算法，有效解决了时变车辆路径问题中的“先出发，后到达”的问题。吴瑶[3]提出了一种食品损耗函数，车辆在配送部分易腐烂货物时，货物会随时间增加而带来更大的损耗，需考虑时变路网的影响，在最短的时间内将货物送达以减少货物损失。王杨[4]在时变路网下拓展了单一配送中心的情况，考虑了多个配送中心进行联合配送。王宁[5]将货物进行分类，针对不同价值的客户进行分级配送，并在时变网络下考虑客户的满意度。因此，在复杂多变的城市路网环境下，采用时变速度的方式描述时变路网，合理规划电动车配送路径，可以减少总配送路径，降低配送成本，防止电动车因电量不足而中途搁置情况的发生。

2.问题描述

在城市的某一物流中心，承担着为周围一定半径内的客户提供配送服务的任务。需要配送的货物，在当晚由城际货运车辆送达物流中心。根据信息系统和GPS系统，顾客的配送坐标和货物需求量以及时间窗是已知的。物流中心拥有同质的电动车队，假设物流中心拥有足够的场地和充电设施，以保证电动车在白天进行配送任务时为满电状态。在每天早上9点，电动车辆装载货物出发，为顾客提供配送需求。在城市中分布着地理信息已知的充电桩，电动车在配送途中若电量不足，可以访问充电站以补充电量。其中，城市路网的状态随时间发生改变，具体表现为车辆的行驶速度在不同的时间拥有不同的行驶速度。根据已知的顾客信息、充电桩信息和车辆信息合理规划配送路线。

3.模型建立

3.1 模型假设

为简化研究内容和确定主要研究目标，在建立模型前做出以下假设：假设1：电动车访问充电站时的充电时间相同，为1个小时；假设2：每个客户都需要被访问一次，且只能由一辆电动车访问；假设3：电动车的型号相同，即载重量和电池容量相同；假设4：电动车离开物流中心和充电桩为满电状态；假设5：每个客户都需要一定的时间收纳货物，因此车辆在到达顾客点后需停留10分钟交接货物；假设6：本文研究的车辆路径问题为封闭式，电动车完成配送任务后需要返回物流中心；假设7：电动车能耗为线性能耗。

3.2 时变路网下车辆行驶速度

本文以车辆在不同时间下拥有不同的行驶速度以描述时变网络，目前研究时变网络中车辆实际行驶速度的方法主要分为Malandraki[6]模型和Ichoua[7]模型两类，由于Malandrak模型没有满足先入先出原则，并且使用该模型可能出现先出发后到达的情况，因此本文使用Ichoua模型，将一天以5分钟为间隔划分为多个时间段，假设每个间隔内的平均速度不变，通过计算车辆在每个时段的行驶时间以获得车辆在道路的总行驶时间。具体情况如图1和图2所示：

图1 Malandraki模型行程时间图

图2 Ichoua模型行程时间图

3.3 时变网络电动车辆配送路径模型

以车辆使用成本、距离成本和时间窗惩罚成本最小化为目标，建立以下模型：

?

目标函数（1）表示车辆固定成本、行驶成本和时间窗惩罚成本最小化，约束（2）表示车辆的在完成配送任务后需返回物流中心，约束（3）为进出流量平衡，到达该节点的车辆数等于离开该节点的车辆数，约束（4）和（5）表示一个客户只能由一辆车服务一次，约束（6）和（7）为车辆载重约束，（8）-（10）为时间约束，约束（11）表示时间惩罚成本的计算，约束（12）表示电池电量不能为负且不超过最大满电量，（13）和（14）定义变量取值。

4.两阶段算法设计

时变电动车辆路径问题属于NP-hard问题，精确式算法难以求解大规模问题，因此本文设计了两阶段算法进行求解。第一阶段采用节约里程算法求得包含所有客户和配送中心的TSP解（Traveling Salesman Problem），并采用分车算子，通过载重约束将TSP解转化为包含多条子路径的VRP解(Vehicle Routing Problem)，第二阶段使用禁忌搜索算法对第一阶段得到的VRP解进行搜索优化，得到最终的的VRP解。在第二阶段使用一下四种算子进行解空间的搜索：（1）逆序邻域搜索算子：即随机截取一段路径并将其逆序；（2）1-opt交换搜索算子：随机截取一个点插入到路径中的另一个位置；（3）2-opt交换搜索算子：随机选择2个点交换位置；（4）3-opt交换搜索算子：随机选择3个点调换它们的位置。

5.实例分析

本文选取了重庆市九龙坡区某企业的一个物流中心，并选择了物流中心附近的30个点作为顾客点，顾客点的经纬度坐标和货物需求量已知，并存在8个公用充电桩可供电动车充电，假设充电桩数量足够，不考虑充电排队等候的因素。其中电动车的电池容量62KWh，载重量为718.4kg，单次充电时间为70分钟，单次充电成本为40元，每个客户的固定服务时间为10分钟，时间惩罚成本系数和分别为0.2和0.5元/分钟，车辆固定成本为180元/辆。DC表示物流中心，点1-30为客户点，点31-38为充电桩。在Intel core i5，内存为16GB的计算机上，使用MATLAB R2016b软件编写两阶段启发式算法对模型进行求解。将算法运行10次后，将得到的成本最小的解作为本文的最优解，最后车辆的路径规划如图4所示。一共使用了4辆电动车以完成配送任务，车辆的固定成本为720元，时间窗惩罚成本为189元，能量消耗成本为283元，充电成本为240元，总配送成本为1432元。具体配送路径如下所示：路线1：0->10->14->4->26->24->25->37->3->7->0；路 线2：0->12->19->21->16->38->1->20->2->6->37->0；路线3：0->15->27->37->23->22->5->17->32->8->0；路 线4：0->11->18->13->9->28->35->30->29->0

图3 算法迭代搜索图

图4 时变路网车辆路径图

6.总结

本文以Ichoua模型描述时变速度，运用两阶段求解算法对时变网络下的电动车辆路径问题进行求解，所提出的算法能够有效求解该问题。在未来研究时，可以从时变速度对电动车能耗的影响进行考虑。

引用出处

[1]王正国,王红卫,刘会新.双目标时变速度车辆路径问题的模型及算法[J].华中科技大学学报：自然科学版,2005,33(12):4.

[2]马华伟,靳鹏,杨善林.时变车辆路径问题的启发式算法[J].系统工程学报,2012,27(2):7.

[3]吴瑶,马祖军.时变路网下带时间窗的易腐食品生产-配送问题[J].系统工程理论与实践,2017,37(1):10.

[4]王杨,鲁晓春.时变路网下多配送中心多车型联合配送[J].科学技术与工程,2018,18(36):9.

[5]王宁,胡大伟,徐杰,等.基于客户价值和满意度的城市冷链物流时变路径问题[J].中国公路学报,2021,34(9):12.

[6]Malandraki C,Daskin M S.Time Dependent Vehicle Routing Problems:Formulations,Properties and Heuristic Algorithms[J].Transportation Science,1992,26(3):185-200.

[7]Ichoua S,Gendreau M,Potvin J Y.Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research,2003,144(2):379-396.