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

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

扫码查看
原文链接
  • 万方数据
  • 维普
在现代社会中,复杂物流配送场景的车辆路径规划问题(Vehicle routing problem,VRP)一般带有时间窗约束且需要提供同时取送货的服务.这种复杂物流配送场景的车辆路径规划问题是NP-难问题.当其规模逐渐增大时,一般的数学规划方法难以求解,通常使用启发式方法在限定时间内求得较优解.然而,传统的启发式方法从原大规模问题直接开始搜索,无法利用先前相关的优化知识,导致收敛速度较慢.因此,提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm,MBEA),通过使用迁移优化方法加快算法收敛速度,其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题.首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务,然后使用进化多任务(Evolutional multitasking,EMT)方法用于生成原大规模问题和优化子任务的候选解.由于优化子任务相对简单且与原大规模问题相似,其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题,从而加快其求解速度.最后,提出的算法在京东物流公司快递取送货数据集上进行验证,其路径规划效果优于当前最新提出的路径规划算法.
Multitask-based Assisted Evolutionary Algorithm for Vehicle Routing Problems in Complex Logistics Distribution Scenarios
In complex logistics,addressing the vehicle routing problem(VRP)with simultaneous pickup and deliv-ery 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 acceler-ate 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 valid-ate MBEA's efficacy,empirical studies were conducted on a large-scale express dataset from Jingdong,and the res-ults demonstrate that MBEA outperforms recently proposed vehicle routing algorithms.

Vehicle routing problem(VRP)time windows constraintsimultaneous pickup and deliveryevolution-ary algorithmtransfer optimization

李坚强、蔡俊创、孙涛、朱庆灵、林秋镇

展开 >

深圳大学计算机与软件学院 深圳 518060

深圳大学大数据系统计算技术国家工程实验室 深圳 518060

车辆路径规划问题 时间窗约束 同时取送货 进化算法 迁移优化

国家自然科学基金国家自然科学基金国家自然科学基金国家自然科学基金国家自然科学基金广东省自然科学基金广东省自然科学基金深圳市科技计划深圳大学科学仪器开发项目

62325307620732256220313462376163622033082023B15151200382019B151502018202208091412160032023YQ019

2024

10.16383/j.aas.c230043

自动化学报
中国自动化学会 中国科学院自动化研究所

自动化学报

CSTPCD北大核心
影响因子：1.762
ISSN：0254-4156
年,卷(期)：2024.50(3)
  • 70