论文题目：A Hybrid Genetic Algorithm on Routing and Scheduling for Vehicle-Assisted Multi-Drone Parcel Delivery
第一作者：彭凯 华中科技大学电子信息与通信学院教授，博士生导师，国务院学位中心信息与通信工程学科发展报告编写组成员。研究方向为云计算，边缘计算，区块链，分布式人工智能与安全。
E-mail：pkhust@mail.hust.edu.cn。
通讯作者：胡梦兰 华中科技大学电子信息与通信学院副教授，研究兴趣包括分布式计算、移动计算、云/边缘计算、物联网、调度与资源管理以及无线网络。
E-mail：humenglan@hust.edu.cn。
多无人机协同配送：混合遗传算法优化路线与调度
论文摘要
近年来，无人机在物流领域的潜力不断提升，但续航时间短限制了远距离应用。针对这一难题，论文将无人机作为“次级车辆”，由一辆地面车作为“移动基地”进行携带和协助配送。配送区域内预设若干候选停靠点，车辆顺序到达停靠点，释放多架无人机服务附近客户并完成返航。 论文将问题分解为三个子问题：停靠点选址属于设施选址问题，无人机路径规划属于带行程约束的车辆路径问题/旅行商问题，无人机任务分配属于装箱问题。结合这些子问题，作者提出一种混合遗传算法（HGA）并引入低访问成本交叉（LVCC）和三层局部搜索教育策略，既优化种群结构，又避免陷入局部最优。实验结果表明，该算法在时间成本和距离成本上显著优于贪婪算法、LKH和AMP等基线。
一、问题描述与数学建模
1.1 车辆辅助的多无人机协同配送
采用一辆地面车辆携带 Nu 台无人机，车辆在道路网络上行驶，选择 候选停靠点 作为无人机的释放与充电站。 客户集合记为 ，候选停靠点集合记为 ，其中 为仓库，车辆从该点出发并返回。 无人机从车辆处起飞、依次访问其任务客户后返回车辆；若电量不足，可在车辆移动到下一个停靠点后再执行剩余任务。 针对每条无人机路线 ，利用指示变量 表示结点 是否紧接在结点 后面；路线长度计算式为其中 为任意两点之间的距离。
1.2 成本函数与约束
总距离成本包括车辆行驶距离与所有无人机路径的距离之和：
其中 为车辆路线的长度， 为无人机 在停靠点 的累计飞行距离。
总时间成本由车辆行驶时间和所有停靠点处的最大无人机任务时间决定：
其中 表示 是否为选定停靠点。
约束条件：
至少需要一架无人机参与配送； 每条无人机路线长度不超过单次飞行最大航程； 所有选定停靠点必须由车辆访问且仅访问一次； 每条无人机路线仅连接一个停靠点。 目标是在满足上述约束条件下同时最小化距离成本和时间成本。
1.3 场景示意图
论文在 Fig.1 中用示意图说明车辆–无人机协同配送场景。下图展示车辆行驶在道路上并将多架无人机释放到不同区域服务客户：
二、混合遗传算法设计
论文提出的 混合遗传算法（HGA） 是一种结合遗传演化与局部搜索的高效优化框架。其核心思路包括解的表示、种群初始化、低访问成本交叉以及分层教育与管理。
2.1 算法整体结构
HGA 的基本流程如下：
初始化种群：随机生成若干可行解，每个解包括车辆路线和各停靠点处的无人机路径。
迭代演化：重复以下操作直至达到预设迭代次数：
父代选择：使用二元锦标赛从种群中选出两条父代解。 低访问成本交叉（LVCC）：从父代中提取路径与停靠点，按照访问成本选择路径，再根据覆盖率选择停靠点组合生成子代解。 局部教育：对子代解进行局部搜索优化，提高解的质量。 种群更新：将新解加入种群并根据多样性和规模管理原则删除质量较差的解。
整体流程的框图见下图：
2.2 方案构建：种群初始化
停靠点选择：采用启发式方法，从候选停靠点中反复选择覆盖最多客户的点，直至覆盖所有客户。 无人机路径构建：对每个停靠点，首先选择最远的客户形成回路，然后不断插入最近的客户，直至路径长度接近最大飞行距离。 无人机调度：按照路径长度将所有路径分配给多架无人机，优先给任务最少的无人机分派较长路径。
2.3 低访问成本交叉 (LVCC)
该交叉算子旨在从父代中提取优势基因片段，步骤包括：
收集两条父解所有路径和停靠点，形成集合 和 。 按 访问成本 依次选取访问成本最小的路径加入子解，并从剩余路径中删除已涉及的客户。 计算每个停靠点的 路线覆盖率选择覆盖率最大的停靠点并将与之相连的所有路径加入子解。 最终对子解中的停靠点进行一次旅行商路径规划，确定车辆的访问顺序。
该过程可使子代同时继承两个父代的优势特征，并避免一个客户被重复访问。
图3 对 LVCC 过程进行了直观示意：
2.4 分层局部搜索教育
在 LVCC 生成子解之后，HGA 采用三层教育策略进一步改良解的结构：
停靠点教育：通过删除访问量较少的“冷点”并将其路径重新分配至邻近停靠点，从而降低整体成本。 路径教育：将同一停靠点内两条短路径合并为一条，只要合并后的路径符合飞行距离约束，并能减少总成本。 客户教育：交换路径内客户的访问顺序，或跨路径调整客户分配，以进一步缩短距离。
这种分层教育能在种群更新前精细调整解，使其在全局搜索的基础上实现局部优化。
2.5 种群管理
为防止种群早熟收敛，HGA 设置了多样性和规模管理机制：
多样性管理：规定任何两条解的成本差值必须大于阈值，保证种群成员之间的差异。 规模管理：通过设定最大种群规模 ，当种群超过此规模时删除成本最大的若干解，以控制计算复杂度。
三、实验与结果分析
3.1 实验设置
作者在一个模拟区域内随机生成不同数量的客户和固定/变化的客户密度，采用一辆车携带 5 架无人机 进行投递，车辆和无人机速度分别设置为 5 m/s 和 3 m/s。评估指标包括：
时间成本：车辆离开仓库、完成所有配送并返回仓库所需的总时间。 距离成本：车辆行驶距离与无人机飞行距离之和。
算法与三种基线算法比较：
Lin-Kernighan Heuristic (LKH) ：对车辆单独进行 TSP 优化，不考虑无人机； Greedy：为所有客户构建多次无人机回路并选择合理的停靠点； AMP：为多车辆路径问题设计的近似算法，为公平起见假设无人机电量无限。
3.2 结果分析
实验分别在客户数量变化、客户密度变化和迭代次数变化等情况下评估算法性能：
当区域大小固定而客户数量逐渐增加时（即密度增加），HGA 在总体时间成本和无人机/车辆距离成本方面均优于 LKH、Greedy 和 AMP。 在客户数量增加但区域范围同步扩大的情况下（密度固定），HGA 同样表现出最好的运行时间和距离性能。 当迭代次数从 0 增加到 35 时，HGA 解的质量持续提升，表明算法具有较好的收敛性和稳定性。
整体来看，混合遗传算法既能在初始阶段迅速产生较优解，又能通过局部搜索和种群管理在迭代过程中进一步提升解的质量。
3.3 创新点与难点处理
多子问题耦合的 NP 难问题建模：传统研究往往单独处理 VRP 或 TSP，本研究将设施选址、路径规划、任务分配融为一个综合模型。难点在于同时优化车辆路线和多架无人机的路径与调度。 混合遗传算法框架：在遗传算法的框架下设计了 低访问成本交叉 和 三层教育，用结构性信息引导搜索，克服遗传算法易陷入局部最优的缺陷。 覆盖率驱动的交叉机制：提出以访问成本和覆盖率为指标的 LVCC，能够在父代之间选择优势片段并有效避免客户重复分配。 多层局部教育策略：分别针对停靠点、路径和客户层面进行局部优化，既优化任务划分又优化访问顺序，在不违反约束的情况下减少时间和距离成本。 多样性与规模管理：通过设定成本差异阈值和限制种群规模保证了算法的搜索多样性和计算效率。
四、结论
文章提出了面向车辆辅助多无人机包裹配送的混合遗传算法。通过对停靠点选址、无人机路径构建与调度等多个 NP 难子问题进行统一建模，并创新性地引入低访问成本交叉和分层局部教育策略，HGA 在时间和距离成本上均显著优于现有方法。论文表明该算法具有良好的可扩展性，可用于解决类似的协同路径规划与调度问题。
文章须知
链上镖师团队：常文婕（AEIC）、祁园园、汪朝杰、王一航、张仁义（EIC）、张晓乐
原文链接：10.1109/ACCESS.2019.2910134
原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。
