引用本文

李坚强, 蔡俊创, 孙涛, 朱庆灵, 林秋镇. 面向复杂物流配送场景的车辆路径规划多任务辅助进化算法. 自动化学报, 2024, 50(3): 544−559 doi: 10.16383/j.aas.c230043

Li Jian-Qiang, Cai Jun-Chuang, Sun Tao, Zhu Qing-Ling, Lin Qiu-Zhen. Multitask-based assisted evolutionary algorithm for vehicle routing problems incomplex logistics distribution scenarios. Acta Automatica Sinica, 2024, 50(3): 544−559 doi: 10.16383/j.aas.c230043

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230043

关键词

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

摘要

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

文章导读

车辆路径规划问题(Vehicle routing problem, VRP)作为一个经典的组合优化问题, 在车辆辅助多无人机监控[1]、机场接送服务[2]、无人驾驶车辆路径规划[3-5]、物流[6-8]等领域广泛应用, 因此近年来引起研究者的广泛关注. 一般来说, VRP的优化目标是最小化车辆从仓库出发并为多个客户派送货物的路径总成本. VRP已被证明是NP-难问题[9-10], 因此是一个极具挑战性的组合优化问题. 在过去的几十年中, 学者们开展了大量求解VRP相关问题的研究工作. 例如, 为更好地优化大规模VRP, 文献[11]提出一种进化多目标路径分组方法. 该方法采用多目标进化算法进行路径分组, 同时优化3个目标, 即组内距离、组间距离和组间大小平衡, 然后使用局部搜索方法提高组内路径的质量.

近年来, 复杂物流配送场景的VRP引起研究人员的广泛关注. 在实际应用中, 绿色制造业和物流在现代供应链管理中扮演着重要角色[12]. 制造工厂需要从客户处收集废弃产品, 以供再次使用或适当处置, 这被称为逆向物流[13]. 一般来说, 逆向物流与货物的双向流动有关, 即交货和取货. 前者指向客户交付货物, 后者指从客户处收取货物. 由于逆向物流在降低能源消耗和减少环境污染方面的显著作用, 其已应用于各个应用场景的配送系统, 如图书馆图书配送[14]、杂货配送[15]和包裹配送[16]等. 此外, 为提高配送效率, 取送货服务需要在预定的时间窗口内完成. 这类问题称为带时间窗和同时取送货的车辆路径问题 (Vehicle routing problem with simultaneous pickup-delivery and time windows, VRPPDT)[17].

VRPPDT是一个更具挑战性的组合优化问题, 包含经典VRP中不存在的一些复杂约束, 因此也是一个NP-难问题[18-20]. 在这些约束条件中, 时间窗口定义了车辆到达客户并开始服务的最早和最晚时间, 具有软时间窗和硬时间窗约束. 配送服务违反软时间窗约束将会受到惩罚[21], 但不能违反硬时间窗约束, 即如果车辆在时间窗口之前到达, 则必须等到服务开始时间, 而且不允许在时间窗口之后到达[22]. 本文考虑硬时间窗约束, 规划一队同质或异质车辆从仓库出发, 为分布在不同地区的客户提供服务. 车辆不仅需要将货物从仓库交付给客户, 还需要同时在客户处收取货物带回仓库, 且不能违反车辆装载容量和客户指定的时间窗约束[23]. 一般的数学规划方法难以求解上述VRPPDT[17], 因此研究人员通常设计启发式算法进行求解, 期望在合理计算时间内找到高质量的候选解. 目前求解VRPPDT的启发式算法包括差分进化[24]、遗传算法[17]、模拟退火[13]、群体智能[25]、可变邻域搜索[26]、自适应大邻域搜索[27]等.

然而, 在现实应用中, 很少有问题是孤立存在的, 正确使用从相关问题中学到的知识, 可以提高解决新问题的能力[28-29]. 因此, 相关文献中提出迁移优化方法, 通过从已优化的相似任务中迁移知识到新任务来提高其优化效果[30]. 这种进化多任务(Evolutional multitasking, EMT)算法已成为进化计算领域的研究热点, 其目的是通过多个相似任务之间的知识迁移, 加快全局最优解的搜索速度[31-34]. 与传统进化算法求解单个优化任务相比, EMT算法可以同时求解多个优化任务, 且每个任务对应一个特定的优化问题. 通过利用优化问题之间潜在的协同作用, EMT算法在解质量和搜索速度方面的优秀性能已在组合优化问题上得到验证[35-37]. 例如, 随着众包和共享经济的出现, 文献[35]研究一种具有临时驾驶员的广义车辆路径问题变体, 称为具有异质容量、时间窗和临时驾驶员的车辆路径问题(Vehicle routing problem with heterogeneous capacity, time window, and occasional driver, VRPHTO), 同时提出一种新的进化多任务算法, 使用单个种群同时优化多个VRPHTO. 与大多数现有的通过交叉实现跨任务隐式知识迁移的EMT算法不同, 文献[36]提出一种显式EMT算法(Explicit EMT algorithm, EEMTA)用于求解VRP等组合优化问题. EEMTA包含用于捕获迁移映射的加权L1范数正则化学习过程, 以及基于解的跨VRP知识迁移过程, 其性能在仿真实验中被证明是有效的. 为加快车辆路径优化的速度, 文献[38]建议通过学习新的客户表示来捕获之前优化的路径规划解中隐藏的有用特征. 这些客户表示可以作为先验知识在VRP之间进行传递, 从而优化目标VRP. 文献[39]求解只带有容量约束的一般VRP时采用K-means方法, 将原VRP分解为多个只包含单条路径的简单VRP作为子任务, 并使用模因搜索同时优化子任务和原始任务. 最后, 所有子任务的解直接叠加组成原始任务的解, 以实现子任务优化原始VRP任务. 然而, 其知识迁移方式比较简单, 只是使用简单的分解和合并方法来生成原始VRP任务的候选解.

受此启发, 为提高VRP算法的性能, EMT算法可以在多种形式的VRP上执行进化搜索, 而不仅仅是在单一形式VRP上. 因此, 在不同形式的VRP上搜索得到的有用路径轨迹可以在多任务之间进行传递, 以加速车辆路径规划的搜索过程. 因此, 为更好地求解复杂物流配送场景的大规模VRPPDT, 本文首先介绍使用EMT算法求解VRPPDT的想法, 并提出一种面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm, MBEA)用于求解大规模VRPPDT. MBEA首先将原大规模VRPPDT分解为多个低维子任务, 并利用这些子任务使用EMT算法求解原VRPPDT. MBEA主要包括3个操作: 1)子任务生成; 2)基于多任务的知识迁移; 3)环境选择. 在子任务生成中, MBEA通过从原任务中随机选择一些客户订单来创建多个不同的子任务. 因为子任务的客户规模比原任务小, 所以更容易求解这些子任务. 在基于多任务的知识迁移中, MBEA使用进化多任务方法用于生成原任务和优化子任务的候选解. 在环境选择中, MBEA从父代种群和子代种群的混合种群中选择N个(N是种群大小)最好的个体存活到下一代. 经过不断迭代进化, MBEA可以快速得到原大规模VRPPDT的高质量候选解. 本文的主要贡献总结如下.

1)针对复杂物流配送场景的大规模VRPPDT, 提出一种多任务辅助进化算法MBEA. MBEA包括子任务生成、基于多任务的知识迁移和环境选择等操作, 可以在子任务和迁移优化方法的帮助下更快地求解大规模VRPPDT. 这是首次应用进化多任务方法用于求解大规模VRPPDT, 具有显著的实际应用与研究价值.

2) MBEA的优化性能已在实际大规模VRPPDT数据集上得到验证. 该数据集来自于京东公司的物流配送系统. 与最近提出的5种VRPPDT算法相比, MBEA在大多数测试问题上都能取得更好的优化性能, 证明了迁移优化对大规模VRPPDT的有效性.

本文的其余部分组织如下. 第1节给出本文研究的VRPPDT定义, 并回顾现有的相关研究. 第2节详细介绍MBEA算法, 并在第3节给出其与最新提出的VRPPDT算法在大规模京东数据集的仿真比较结果. 最后, 第4节给出本文的结论并讨论未来的研究工作.

图 1  VRPPDT模型

图 2  MBEA总体框架图

图 3  一个个体的编码方法

本文提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法MBEA, 通过对多个简单且相关的子任务使用知识迁移操作来辅助优化原大规模VRPPDT, 加快算法收敛速度. 与现有算法相比, MBEA的创新性表现为两个方面: 子任务生成和基于多任务的知识迁移. 子任务生成操作将原始VRPPDT划分为多个简单且相关的子任务. 然后MBEA在进化多任务迁移中使用两种不同的交叉算子产生下一代种群. 当两个父代个体来自同一个任务时, 使用基于路径的交叉算子(优化)产生子代个体; 否则, 使用顺序交叉算子(迁移)产生子代个体. 在本文的实验分析中, 与最近提出的5种算法相比, MBEA在京东大规模VRPPDT数据集上的路径规划结果更优.

在未来的工作中, 我们将在MBEA算法的基础上进一步探索解决VRPPDT的有效策略. 首先, 我们将进一步结合问题特征设计出更高效的子任务生成方法. 其次, 我们将在MBEA中探索使用更多高效的局部搜索方法. 最后, 我们将逐步把MBEA构建成一个通用的路径规划算法框架, 从而支持求解更多的VRP变体, 例如动态VRP、多站点VRP和电动车队VRP.

作者简介

李坚强

深圳大学计算机与软件学院教授. 2008年获华南理工大学博士学位. 主要研究方向为嵌入式系统和物联网. E-mail: lijq@szu.edu.cn

蔡俊创

深圳大学计算机与软件学院博士研究生. 主要研究方向为进化计算及其在物流领域中的应用. E-mail: caijunchuang2020@email.szu.edu.cn

孙涛

中兴通讯股份有限公司工程师. 2022年获深圳大学硕士学位. 主要研究方向为进化计算和路径规划. E-mail: 1910272020@email.szu.edu.cn

朱庆灵

深圳大学计算机与软件学院博士后. 2021年获香港城市大学博士学位. 主要研究方向为进化多目标优化和机器学习. E-mail: zhuqingling@szu.edu.cn

林秋镇

深圳大学计算机与软件学院副教授. 2014年获香港城市大学博士学位. 主要研究方向为人工免疫系统,多目标优化和动态系统. 本文通信作者. E-mail: qiuzhlin@szu.edu.cn