基于自适应变邻域搜索的大规模电动车辆路径优化

赵灿华， 侍洪波

（华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 200237）

随着国家对电动汽车的大力推广，越来越多的物流车辆开始采用电动车。与常规的燃油车相比，电动车具有较低的污染排放和噪声，但同时也面临着续航里程短、充电时间长、充电桩少等问题[1-3]，这使得电动车辆路径问题(Electric Vehicle Routing Problem, EVRP)的求解更加复杂。

车辆路径问题(Vehicle Routing Problem, VRP)[4]是典型的NP-hard 问题[5]。在精确式算法研究方面，文献[6]使用分支定界法对VRP 进行了建模求解，可求解260 点的VRP。文献[7]使用k 度中心树算法将原问题转化为3 个易求解的子问题，然后进行求解。文献[8]提出了一种节约值计算方法，能够较好地生成车辆路径。对于组合优化问题，精确式算法常常无法在合理的时间内给出满意解，因此多采用启发式算法求解。文献[9]提出了一种反馈精英教学优化算法，通过引入反馈机制提高了算法的全局搜索能力，并将算法成功应用于背包问题。文献[10]使用禁忌搜索算法对带有随机需求的动态VRP 进行了建模求解。文献[11]针对粒子群算法容易陷入局部极值的缺陷，提出了一种多相粒子群优化算法(Multi-phases Particle Swarm Optimization,MPSO)，对带软时间窗的VRP 进行了建模求解。文献[12]构造了一种求解VRP 的自适应蚁群算法，能够有效地解决小规模的VRP。文献[13]在充分分析了启发式算法的基础上，构造了新型的染色体结构及操作算子，使用遗传算法对VRP 进行了有效求解。文献[14]面向仓库VRP，对禁忌搜索算法进行了改进及应用。对于大规模的VRP，由于可行解空间极大，通常使用多种搜索算法混合的策略对问题进行求解，其中变邻域搜索(Variable Neighborhood Search，VNS)[15]是解决大规模VRP 的有效方法。文献[16]将变邻域搜索和禁忌搜索算法结合起来，采用动态惩罚机制，求解了带时间窗的电动车辆路径问题(EVRP-TW)。文献[17]将自适应大规模邻域搜索与变邻域搜索算法相结合，提出了一种自适应变邻域搜索算法求解带中间站的EVRP，根据在不同抖动过程中的搜索表现来自适应调整抖动的邻域算子选择。文献[18]使用变邻域搜索对三维装箱问题下的VRP 进行了求解。文献[19]研究了部分充电的EVRP-TW，提出了一种变邻域搜索分支的元启发式算法。文献[20]使用了一种改进的变邻域搜索算法对客户规模达到两万的超大规模VRP 进行求解，其中利用引导局部搜索算法来跳出局部最优。文献[21]提出了两种并行协作方案，使用了一种协作自适应变邻域搜索算法求解了多车场带时间窗的VRP。文献[22]对混合车型的带时间窗的VRP 进行了建模，并使用反应式变邻域搜索算法进行了求解。

本文以京东物流为案例背景，对大规模带时间窗可回程取货的电动车辆路径问题（Electric Vehicle Routing Problem with Backhauls and Time Window,EVRP-BTW）进行了建模分析。利用客户时间窗、地理位置等信息构造了高效的初始解生成算法；针对传统变邻域搜索算法在后期出现优化效率降低的情况，提出了一种高效的自适应变邻域搜索算法(Adaptive Variable Neighborhood Search，AVNS)，设计了新的邻域搜索算子，并结合经典的2-opt、Relocation、Cross-change 等算子进行了变邻域搜索。最后，使用不同规模的实际脱敏数据验证了本文算法的有效性。

1 问题描述及数学模型

上述模型中，式(1)为目标函数；式(2)表明所有的客户需要被访问；式(3)保证了每名客户只能被一辆车服务一次；式(4)、式(5)分别为车辆上午送货行驶路径的质量和体积约束；式(6)、式(7)分别为车辆下午取货行驶路径的质量和体积约束；式(8)为电动车辆的里程约束，保证了车辆能够在电量耗尽之前到达下一个充电站；式(9)为每个客户的服务时间窗约束。

2 基础算法

3 AVNS 算法

在变邻域搜索的后期，往往会出现在某些邻域内长时间无法找到更优可行解的情况，此时对这些邻域过多地重复搜索会降低算法的优化效率。针对上述问题，本文提出的AVNS 算法能够根据每个邻域的优化情况，自适应调整选择在某个邻域进行搜索的概率，从而减少算法在一些长时间无改进邻域的搜索时间，提高算法的优化效率。AVNS 算法包括一步更新和阶段更新两种概率更新方式。

3.1 一步更新AVNS 算法

3.2 阶段更新AVNS 算法

3.3 算法收敛性分析

文献[23]对VNS 算法的全局收敛性进行了论证说明，本文AVNS 算法的邻域结构以及抖动的过程与VNS 算法完全一致。由于设置了最小邻域选择概率，AVNS 算法在收敛到全局最优解之前，每次迭代后的改进概率可以始终保证大于0，故AVNS 算法的全局收敛性依旧可由文献[23]中关于VNS 算法的全局收敛性证明方法得出。图1 为一步更新和阶段更新方式下的AVNS 算法流程图。

4 EVRP-BTW 的初始解生成与邻域结构

4.1 初始解构造

图 1 AVNS 算法流程图Fig. 1 Flow chart of AVNS algorithm

4.2 邻域结构的设计和选择

在进行自适应变邻域搜索时，按照送取货路径片段交换、基于空间邻近性的路径片段交换、2-opt 算子、Cross 算子以及Relocation 算子的邻域顺序进行搜索，同时这些邻域也在抖动过程中使用。在使用邻域算子对路径进行变换之前，会先删除路径中的充电站；完成变换后，使用4.1 节的充电策略将充电站插入到变换后的路径中，最后计算得出变换前后的成本变化。

（1）送取货路径片段交换（Part-change）。送取货路径片段交换是指利用车辆上午送货、下午回程取货的特点，随机选取已生成的两条路径，将两条路径各自上、下午的行驶路径进行交换，若交换后的两条路径均路径合法且总成本下降，则进行路径覆盖；否则，取消交换。

（2）基于空间邻近性的路径片段交换（Segchange）。基于空间邻近性的路径片段交换的基本思想是利用路径片段的两个端点客户的空间邻近性，有针对性地进行路径片段的交换，操作示例如图2所示。

图 2 路径片段交换Fig. 2 Route segment exchange

（3）2-opt 算子。2-opt 算子是指随机地选择两条路径，从两条路径中各自选择一个客户进行互换，若交换后的路径合法且总成本出现下降，则进行路径覆盖；否则，取消交换。

（4）Cross 算子。在Cross 算子中，先随机选择两条路径，然后从两条路径中各自选择一个客户作为路径的断点，每一条路径被分成了两段，最后进行交叉，操作示例如图3 所示。

图 3 交叉操作Fig. 3 Cross operation

（5）Relocation 算子。Relocation 是指从一条路径中随机选择一个客户，随机地插入到其他路径中的某个客户之前，若执行上述操作后的路径合法且总成本出现下降，则进行路径覆盖；否则，不进行插入操作。操作示例如图4 所示。

图 4 重定位操作Fig. 4 Relocation operation

5 实验研究

以京东某城配物流中心已脱敏的实际数据作为实验数据。城配物流中心每天要使用电动车辆为分布在本城区的1 000 余名客户进行城市配送。本文分别对客户规模为1 100、1 200、1 300、1 400、1 500的数据进行了实验分析，充电站的数量为200 个，每小时充电成本为100 元，每小时等待成本为24 元，最早发车时间为早上8 点，回配送中心最晚时间为当日24 点，充电站里的充电桩没有数量限制。具体的车型信息以及客户样例如表1、表2 所示。

由实验结果可以看出，蚁群算法计算效率较低，较容易陷入局部最优，故效果较差；而使用模拟退火算法进行仿真时，由于充分利用了本文提出的邻域结构，因此其优化结果VNS 较为接近；一步更新AVNS 算法和阶段更新AVNS 算法的结果最好，从5 种客户规模优化后的最终成本的角度分析，两种概率更新方式下的AVNS 算法的性能表现没有显著差别。

表 1 车型信息Table 1 Vehicle type information

表 2 客户样例Table 2 Customer sample

表 3 实验结果Table 3 Experimental result

图 5 一步更新AVNS 下的选择概率收敛曲线Fig. 5 Select probability vector convergence curves under one step update

图 6 阶段更新AVNS 下的选择概率收敛曲线Fig. 6 Select probability vector convergence curves under phase update

6 总结与展望

本文提出了一种有效的自适应变邻域搜索算法，在算法中为每个邻域都设置了一个选择概率，并使用一步更新和阶段更新两种方式对选择概率向量进行了更新，提高了算法优化效率。该算法部署方便，具有较强的通用性。建立了大规模带时间窗可回程取货的电动车辆路径问题的数学模型，利用时间窗宽度、客户地理位置等信息生成了高质量的初始解；使用2-opt、Relocation、Cross-change 等算子进行了自适应变邻域搜索。通过对5 组不同客户规模的实际脱敏数据的仿真计算表明，AVNS 算法能够更有效地降低物流成本，验证了算法的有效性。