结合层次分解方法的车辆路径问题（含无人机）的协同进化算法

《Swarm and Evolutionary Computation》：Co-evolution with hierarchical decomposition for Vehicle Routing Problem with Drones

　　翟若楠|张学军|梅毅|郭彤|杜文博
北京航空航天大学电子与信息工程学院，中国北京100091

**摘要**
近年来，无人机配送技术取得了快速进展，并在现实世界中得到了越来越多的应用。为了解决无人机在载荷和续航能力方面的固有局限性，卡车与无人机之间的协作配送系统（即带有无人机的车辆路径问题，VRP-D）引起了越来越多的研究兴趣。在本文中，我们提出了一种基于层次分解的协同进化（CH-SaBO）框架来解决VRP-D问题。首先，我们提出了一种协同进化方案，将原始的VRP-D问题分解为多个子问题，每个子问题只涉及一辆卡车，从而有效降低了问题的维度。接着，我们设计了一种层次分解策略：首先自上而下地将解决方案逐步细分为路线、操作、子路线、路径和弧等元素；然后通过递归自下而上的方法构建层间相关矩阵，捕捉这些元素之间的时间和空间依赖关系；最后利用k-medoids聚类算法对相关矩阵进行进一步分组。对于子问题之间的边界，我们设计了一种简单而有效的重叠策略以提高解决方案的质量。每个子问题随后使用基于代理的双层优化器进行独立优化，从而在结构良好的较小解决方案空间内高效搜索。在51个基准实例上的广泛实验表明，CH-SaBO在解决方案质量和计算效率方面均显著优于现有算法。进一步分析证实了CH-SaBO的可扩展性以及其层次分解和重叠策略的有效性。

**引言**
无人机配送已成为解决最后一公里物流挑战的有希望的方法，尤其是在人口密集的城市地区[1]。然而，独立无人机的部署受到有限载荷能力、短飞行续航时间和禁飞区的限制，这些因素阻碍了其大规模商业化应用。一种实际的替代方案是无人机-卡车协作系统[2]，在该系统中，无人机和卡车作为集成物流网络中的同步代理协同工作。卡车作为移动仓库扩展了无人机的操作范围，而无人机则提供灵活快捷的最后一公里服务。例如美团[3]和UPS[4]等公司的商业实践表明，这种混合方法将配送效率提高了多达150%[5]，凸显了其变革潜力。

从形式上讲，该问题可以建模为带有无人机的车辆路径问题（VRP-D [6][7][8]），它是经典车辆路径问题（VRP）的扩展，结合了卡车（地面车辆）和无人机（空中车辆）之间的同步操作。VRP-D的目标是在满足三个核心约束的前提下，为网络中的所有客户提供服务并最小化总完成时间：
- **服务**：每个客户必须由卡车或无人机恰好服务一次。
- **同步**：无人机必须从指定的卡车出发并在同一卡车返回（单次起飞）。
- **多次访问**：无人机在每次飞行任务中可以在其载荷限制内服务多个客户。

VRP-D自然地分解为两个相互依赖的子问题：卡车路径规划（类似于经典VRP）和无人机路径规划（类似于容量受限的VRP，CVRP）。同步约束使得解决方案空间呈现出组合爆炸性增长。VRP-D属于NP难问题[9]。为了解决这个问题，已经发展出了两种主要方法论流派：精确方法（如混合整数线性规划[2][10]、动态规划[11]、分支定价[12]和连续近似[13]）可以保证最优解，但随着问题规模的增加，计算复杂性也随之增加，限制了它们的适用性；而元启发式方法（如变邻域搜索[14]、禁忌搜索[15]、混合遗传算法[16]、蚁群优化[17]和多智能体策略[18]）则具有更好的可扩展性。基于个体的搜索方法容易陷入局部最优解，而基于群体的方法能够更广泛地探索解决方案空间，并更有效地摆脱局部陷阱。然而，大多数元启发式方法分别优化卡车和无人机的路线，这往往导致忽略全局最优协调模式。异构车队的联合优化会形成高维的组合问题空间。对于一个有N个客户、M辆卡车和每辆卡车m架无人机的实例，解决方案空间的大小增长为O((N+M)!M!(Mm(N+M)2)N)。具体推导过程见附录A。这种庞大的搜索空间带来了收敛性、不可行性和运行时间过长的挑战[19]，因此通过问题分解进行降维对于实际应用的可扩展性至关重要。

**协同进化框架**
协同进化框架通过将大规模组合问题分解为低维的子问题并使其独立进化，提供了一种有效的解决方法[20]。这一范式已成功应用于电动汽车路径规划[21]、弧路径规划[22]和空中交通流管理[23]等领域。它也非常适合VRP-D中的合作与竞争动态。据我们所知，目前尚无先例将协同进化应用于VRP-D。

**协同进化优化中的核心挑战**
协同进化优化中的一个核心挑战在于设计分解策略，以最大化组内相关性同时最小化组间干扰。现有的VRP分解方法大致可以分为空间聚类[24]、历史相关性[25]和基于路线模式的分组[22][26][27]。其中，基于路线模式的分组方法对于仅涉及卡车路线的问题已被证明是有效的。然而，将基于路线的分解策略应用于VRP-D时会遇到三个主要问题：
1. VRP-D中的路线由卡车路径和多次无人机飞行组成，而不是单一车辆轨迹，直接在路线层面进行聚类会导致结构不平衡，因此需要进一步划分路线；
2. 在进行问题分解时，必须保留卡车和无人机之间的关键时间和操作依赖信息（例如在卡车节点上的同步起飞和回收）；
3. 卡车-无人机协作本质上引入了强烈的跨子问题相关性，常常导致不同子问题之间存在客户或操作的重叠。

为了解决这些限制，我们提出了基于层次分解的协同进化框架（CH-SaBO）用于VRP-D。在CH-SaBO中，根据车队数量对客户进行层次化分解，将原始的多卡车-多无人机问题转化为多个单卡车-多无人机的子问题，并共同优化卡车路径和无人机操作。然后重新组合子问题的解决方案，形成当前的最佳整体解决方案，用于进一步调整客户分组。通过利用进化过程中揭示的卡车-无人机交互模式来指导这种调整，该框架动态优化了分解过程并加速了搜索速度。在经典数据集[28]上的实验表明，CH-SaBO在成本方面比现有算法低14%。具体创新点如下：
- 我们提出了一种基于领域知识的协同进化机制，动态调整分组，并在每个组内共同优化卡车路径和无人机操作，实现了解决方案空间的缩减和有效的卡车-无人机协调；
- 我们设计了一种层次分解策略，结合了自上而下的元素定义和自下而上的交互检测。通过逐步划分最佳的卡车-无人机路线来定义多层元素，并利用历史路由信息和地理相关性来指导有希望的元素分组；
- 为了避免子问题之间的客户重复，我们引入了一种重叠分配策略，利用客户的地理分布特征快速重新分组客户。

**本文结构**
第2节介绍了背景信息，包括VRP-D问题的描述和相关工作。第3节详细阐述了所提出的CH-SaBO框架。第4节进行了实验研究和讨论，第5节总结了研究结果。

**问题描述**
本文研究了带有无人机的车辆路径问题（VRP-D [8][29]）。如图1所示，多支卡车车队及其对应的无人机团队负责为具有确定位置和载荷要求的客户提供服务。每个客户必须由卡车或无人机恰好服务一次。在送货过程中，卡车可以将无人机运输到靠近客户区域的位置。无人机离开卡车后，可以在该区域提供服务。

**CH-SaBO的协同进化框架**
在本节中，我们首先介绍了CH-SaBO的协同进化框架、解决方案表示和评估方法。随后详细介绍了主要流程，即层次分解和子问题优化器。

**实验研究**
首先介绍了实验设置，然后通过将CH-SaBO与经典基准数据集上的现有算法进行比较来评估其有效性。最后进行了消融研究，以验证所设计分解策略的有效性。

**结论**
在本文中，我们提出了一种名为CH-SaBO的新协同进化策略，用于解决带有无人机的车辆路径问题（VRP-D）。为了应对大规模组合搜索空间的复杂性，我们将原始问题分解为多个独立子问题。为了提高分解的准确性，我们设计了一种层次化的分治分组机制，基于历史路由信息和地理相关性递归构建相关矩阵，以指导有希望的客户分组。

**资助**
本项工作得到了中国国家重点研发计划（项目编号2024YFE0217600）和中国国家自然科学基金（项目编号52525213）的支持。

**作者贡献声明**
翟若楠：撰写——原始草稿、方法论；
张学军：可视化、调查；
梅毅：撰写——审阅与编辑、方法论；
郭彤：撰写——审阅与编辑、方法论；
杜文博：监督、概念化。

**利益冲突声明**
作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：
杜文博报告称，本研究得到了中国国家重点研发计划（项目编号2024YFE0217600）的财务支持；
杜文博报告称，本研究还得到了中国国家自然科学基金（项目编号52525213）的财务支持。