面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

Multitask-based Assisted Evolutionary Algorithm for Vehicle Routing Problems in Complex Logistics Distribution Scenarios

在现代社会中,复杂物流配送场景的车辆路径规划问题(Vehicle routing problem,VRP)一般带有时间窗约束且需要提供同时取送货的服务.这种复杂物流配送场景的车辆路径规划问题是NP-难问题.当其规模逐渐增大时,一般的数学规划方法难以求解,通常使用启发式方法在限定时间内求得较优解.然而,传统的启发式方法从原大规模问题直接开始搜索,无法利用先前相关的优化知识,导致收敛速度较慢.因此,提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm,MBEA),通过使用迁移优化方法加快算法收敛速度,其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题.首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务,然后使用进化多任务(Evolutional multitasking,EMT)方法用于生成原大规模问题和优化子任务的候选解.由于优化子任务相对简单且与原大规模问题相似,其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题,从而加快其求解速度.最后,提出的算法在京东物流公司快递取送货数据集上进行验证,其路径规划效果优于当前最新提出的路径规划算法.

In complex logistics,addressing the vehicle routing problem(VRP)with simultaneous pickup and delivery and time windows,an NP-hard problem,becomes increasingly challenging as the scale expands.Traditional heuristic methods,often unable to leverage prior optimization knowledge,result in slow convergence.To address this,we introduce a multitask-based evolutionary algorithm(MBEA),which assists the optimization of the original large-scale problem by constructing multiple simple and similar subtasks and utilizing transfer learning to accelerate convergence speed.First,a subset of orders is randomly selected from the original problem to construct various subtasks,and then a multitask evolutionary approach is applied to generate candidate solutions for the original problem and subtasks.Given that the subtasks are simpler yet similar to the original problem,useful routing traits can be shared through knowledge transfer among the tasks,thereby speeding up its evolutionary search.To validate MBEA's efficacy,empirical studies were conducted on a large-scale express dataset from Jingdong,and the results demonstrate that MBEA outperforms recently proposed vehicle routing algorithms.