多类型无人机协同监测：自适应车队规划与路由优化解析

论文题目：Synchronized truck-drone routing with adaptive fleet planning for heterogeneous monitoring tasks

通讯作者：王正礼，南京大学工程管理学院副教授（特聘研究员）、博士生导师。研究领域包括交通运输建模与管理优化、交通数据挖掘分析、交通安全、智慧物流等。

E-mail：zhlwang@nju.edu.cn

多类型无人机协同监测：自适应车队规划与路由优化解析

论文摘要

在电力巡检、森林防火等实时监测任务中，车–无人机协同系统通过将卡车作为移动基站、无人机负责采集数据，可大幅提升监测效率。然而，传统研究普遍假设任务和无人机类型均为同质，这会导致车辆冗余和效率下降。本文首次引入异质监测任务和多类型无人机，提出了一个同时优化车队配置和路线的混合整数规划模型，并设计了自适应大邻域搜索（ALNS）算法求解。与传统预定义车队方案相比，新模型通过让一辆卡车携带多种无人机完成不同任务，实现了更高的车队利用率和更低的总成本。文中还通过大量数值实验与敏感性分析验证模型有效性，得出电池容量、空间分布等因素对系统成本的影响规律。研究在理论和实践上为异质监测任务的协同调度提供了新框架。

一、研究背景与问题定义

1.1 场景与挑战

• 监测任务的多样性：线路巡检、风电机组检查等任务对设备的传感器类型和操作方式要求不同，需要多种无人机配置。
• 传统假设局限：既有研究通常假设任务同质、无人机同类，且车队配置预先确定，忽视了任务异质性和车队灵活性。
• 目标与决策：本文希望在异质任务背景下同时决定车队中各卡车所携无人机的类型与数量，以及各车辆和无人机的巡航路线，以最小化总成本。

1.2 基本符号与概念

• 车队与任务：集结点为仓库  ，车集合记为 ，无人机集合记为 。每个任务节点可能为卡车任务或无人机任务。
• 费用构成：包括卡车和无人机的启动成本（购买/调度成本）以及行驶成本。
• 能耗约束：无人机电池容量限制了航程；卡车必须在预定时间窗口内完成任务。

下图示意了卡车线路（红色）、不同类型无人机的飞行路径（蓝色与灰色）与关键变量的关系：

二、模型构建：异质任务的混合整数规划

2.1 目标函数

模型以最小化系统总成本为目标。设  表示卡车  是否启用， 表示无人机  是否被分配给卡车 ， 表示卡车  是否从节点  行驶到节点 ， 表示无人机  在第  次飞行中是否从节点  飞到节点 。则总成本可表示为：

其中第一、二项分别为卡车和无人机的启动成本，第三、四项为车辆和无人机的行驶成本。

2.2 约束条件

模型通过一系列约束保证调度可行：

• 路径与流平衡：卡车必须自仓库出发并返回，且不能形成子回路。每条无人机航程必须在卡车路线的起始/结束节点起降。
• 任务覆盖：每个任务节点恰好由一辆卡车或无人机服务。
• 装载与能耗限制：卡车装载的无人机数量有限；无人机每次出航不得超过电池容量。
• 时间窗约束：卡车必须在允许的时间窗内完成所有任务，避免长时间等待。

模型还考虑到了卡车和无人机在同一节点启动与回收的先后顺序，以及不同类型无人机执行特定任务的适配性。

三、求解方法：自适应大邻域搜索（ALNS）

3.1 算法框架

由于模型是 NP 难的，文中采用ALNS算法快速求解中大规模实例。该算法从初始解出发，迭代执行破坏–修复操作，通过随机或启发式方式删除若干节点并重新插入，以探索解空间。核心步骤包括：

1. 初始化：生成初始解并设定各类操作的权重。
2. 选择操作：通过轮盘赌选择破坏算子和修复算子，分别用于删除和插入节点。
3. 接受准则：若新解优于当前最优解则更新，否则按照模拟退火准则接受一定的较差解，提高跳出局部最优的能力。
4. 权重更新：根据算子表现调整其权重，使得表现好的算子在后续迭代中更可能被选择。

算法配合多种破坏算子（如随机删除、聚簇删除、最差成本删除）和修复算子（插入卡车节点和无人机节点），能够灵活处理异质任务与多种无人机类型。

3.2 算法性能

实验结果表明，ALNS 算法在不同规模实例上平均计算时间较短，其计算时间随节点数增长而适度增加，如图 2 所示。这证明算法适用于中等规模的实际场景。

四、数值实验与案例分析

4.1 多类型无人机配置的优势

研究设置了随机分布（R 系列）和聚簇分布（C 系列）共十个实例，对比提出模型与传统“每车只携带一种无人机”的同质设置。结果显示：提出模型在所有实例上总成本均低于同质设置。成本差异主要来自于卡车启动和行驶成本的降低，因为一辆卡车携带多种无人机即可在一条线路上完成多个类型任务。

下图以 R3 实例为例比较同质与异质配置。在同质设置下需要两辆卡车协同完成任务（图3），而提出模型仅需一辆卡车即可完成全部任务（图4）。

类似地，对于聚簇实例 C1，传统同质配置需要两辆卡车（图5）；而提出模型能够将两种无人机装配在同一辆车上，从而降低车辆使用（图6）。

4.2 联合优化与预定义车队的比较

传统方案通常预先指定每辆卡车携带的无人机类型与数量，再优化路线。文中通过案例 A 和 C 进行对比。结果表明：在预定义方案中，两辆卡车分别携带一型或两型无人机；而联合优化通过重新分配无人机，可将任务集中到一辆车上，使另一辆车不需出动，降低总成本。这一发现突显出在任务异质性较大时，车队配置与路径应同步优化。

4.3 无人机电池容量的影响

图 7 分析了在不同地理范围下，电池容量对系统成本的影响。主要结论：

• 地理范围小（平均车行时间 8.49 分钟）：电池容量对成本影响较小，成本差异不足 1.33%。
• 范围中等或较大（14.06 和 20.76 分钟）：电池容量的提升显著降低总成本（成本降低 3.57%~7.48%），因为小容量导致频繁更换电池或增加无人机数量。

4.4 地理分布的敏感性分析

为评估任务空间结构对调度的影响，研究构建了两种真实场景：线性输电线路（图8）与聚集风电场（图9）。二者任务数量和覆盖范围相同，差异在于节点分布形态。

• 成本比较：在相同电池容量下，聚集场景的总成本始终低于线性场景，原因在于卡车行驶距离更短。
• 电池容量增益：当容量从 30 提升到 50 时，线性场景成本下降 12.53%，聚集场景下降 18.36%，表明在紧凑区域内提升电池容量效果更显著。

进一步改变卡车节点比例（即需要人工操作的节点占比），结果如图10、11 所示。在线性场景中，随着卡车节点比例增加，总成本下降，因为卡车必须遍历整条线路，增加人工节点反而让无人机更灵活；而在聚集场景中，成本随比例增加上升，原因是卡车旅行距离增加且单位成本较高。任务完成时间在两种场景下均随比例增加而延长，这是因为无人机在卡车上等待的时间增长。

五、结论与创新点

• 首次考虑任务与设备的异质性：模型允许卡车携带多种类型无人机，适配不同监测任务。
• 联合优化车队配置与路径：与传统预定义方案相比，提出的联合优化显著降低了车辆启动数和行驶距离。
• 混合整数规划与自适应启发式结合：建立了完整的 MIP 模型并设计了 ALNS 算法以高效求解中大型实例。
• 全面的敏感性分析：揭示了电池容量和任务空间分布对系统成本的影响，提出在资源分散区域应优先配置大容量电池或增加无人机数量。

综上，本文从模型、算法和实验等方面系统地解决了异质监测任务的车–无人机协同路由问题，为未来的智慧监测和巡检系统提供了理论依据和实践参考。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。