Abstract:

A new variant of the vehicle routing problem, Vehicle Routing Problem with Occasional Drivers and Scheduled Lines (VRPOD-SL), is introduced for the rural delivery scenario. The VRPOD-SL involves selecting public transportation vehicles and occasional drivers for delivery services, identifying the customers serviced by public transport, and planning the optimal route for occasional drivers. To address the VRPOD-SL, an integer programming model is developed considering multiple factors. These factors include the distribution of the starting and ending points, service range of occasional drivers, and capacity of their vehicles. Additionally, the model considers the capacity limitations and fixed route constraints of the public vehicles involved in the problem. The objective of this model is to minimize the overall delivery cost. The VRPOD-SL exhibits high computational complexity owing to the interdependence between customer decision to select public transportation vehicles and occasional drivers. This interdependence necessitates repeatedly solving the occasional driver routing problem, which further increases the computational burden. Therefore, a heuristic algorithm based on Deep Reinforcement Learning (DRL), called a Genetic Algorithm (GA) integrated with an Attention Model (GA-AM), is proposed. The GA-AM combines the global search capability of genetic algorithms with the parallel decision-making ability of attention models, effectively reducing the computational burden of solving the VRPOD-SL. Additionally, a local search algorithm is proposed to further enhance the solution. Numerical experiments demonstrate that the proposed GA-AM outperforms the Gurobi solver, Adaptive Large Neighborhood Search (ALNS) and Variable Neighborhood Search (VNS) heuristic algorithms in terms of solution performance. Furthermore, the results validate the effectiveness of the collaborative delivery mode, which involves occasional drivers and public vehicles.

Key words: vehicle routing problem, Deep Reinforcement Learning (DRL), improved Genetic Algorithm (GA), Vehicle Routing Problem with Occasional Drivers and Scheduled Lines (VRPOD-SL), Adaptive Large Neighborhood Search (ALNS) algorithm

摘要：

针对农村地区配送场景, 提出一种车辆路径问题的变体——众包车辆-公共交通协同配送问题(VRPOD-SL)。该问题对参与配送的公交车辆及其服务的物流客户进行选择, 同时需选择参与配送的众包车辆, 并对众包车辆的行驶路径等进行决策。考虑众包车辆的起终点、服务范围和最大载重, 以及公交车辆的载货空间限制和按固定路线行驶等特点, 以最小化配送总成本为优化目标, 构建VRPOD-SL的整数规划模型。由于公交车辆提供物流服务的客户选择决策, 影响到众包车辆的服务客户选择, 进而需要不断求解众包车辆路径问题, 导致问题的计算复杂度较高, 因此设计一种基于深度强化学习(DRL)的启发式算法, 即融合了注意力模型的遗传算法(GA-AM)。该算法将遗传算法(GA)的全局搜索特性和注意力模型(AM)的并行决策能力相结合, 能够有效减少VRPOD-SL的求解时间。同时设计局部搜索算法, 进一步提高解决方案的质量。数值实验结果表明, 所提出的GA-AM在求解性能方面明显优于Gurobi求解器、自适应大邻域搜索(ALNS)算法和变邻域搜索(VNS)算法。此外, 研究结果也验证了众包车辆-公共交通协同配送模式的有效性。

关键词: 车辆路径问题, 深度强化学习, 改进遗传算法, 众包车辆-公共交通协同配送, 自适应大邻域搜索算法