适用于多架无人飞行器在执行监控任务时的近似通用路由问题

《European Journal of Operational Research》：Close-enough general routing problem for multiple unmanned aerial vehicles in monitoring missions

　　我们提出了一个足够接近的实际多无人机（multi-UAV）通用路由问题。我们提出了一种两阶段迭代方法来解决该问题，并通过比较实验来验证所提方法的优化性能。

引言
无人驾驶飞行器（UAVs），也称为无人机，是一种无需人工飞行员在机上进行操作的飞行器。无人机可以由人类操作员远程控制，也可以自主运行。随着无人机技术的不断进步，其应用范围已经超出了军事领域，越来越多地应用于各种民用领域，例如包裹配送（Gómez-Lagos等人，2026年；Mulumba和Diabat，2024年）、海洋污染检测（Liu等人，2023年）、交通监控（Li等人，2018年）、基础设施检查（Liu等人，2026年）以及地图绘制（Chen等人，2021年；Glock和Meyer，2020年）等。在这些应用中，无人机监控是最有价值的新兴应用之一。与手动方法相比，它提供了更安全、更高效且成本更低的解决方案，特别是在实时环境中监控复杂目标时，如交通流和搜索幸存者。在本文中，我们专注于监控静态目标而不是动态目标。一般来说，这些目标可以分为节点、边和区域。当无人机监控一个区域时，它通常会遵循有效覆盖该区域的预定路径（Cao等人，2022年）。因此，被监控的目标主要被划分为节点和边进行分析。与节点路由问题不同，在弧路由问题中，边的遍历方向（即哪个节点作为入口点，哪个节点作为出口点）可能会显著影响总路线距离。例如，在路线0→3→(1→2)→0中遍历边(1, 2)的成本可能与沿着0→3→(2→1)→0反向遍历的成本不同。

许多研究都集中在无人机的节点路由和弧路由问题上。Fang等人（2023年）研究了多无人机路由问题，用于监控易发生滑坡的区域，并将其表述为一个具有强制访问要求的团队定向问题。他们开发了一种大规模邻域搜索算法，并结合了神经网络启发式方法来解决问题。Zhen等人（2019年）研究了无人机的车辆路由问题，其中被监控的目标根据飞行高度有不同的精度要求，他们设计了一种禁忌搜索算法来解决这个问题。Amorosi等人（2023年）提出了一个车辆辅助的多无人机协调监控框架，其中一辆飞机配备多架无人机来监控弧线。他们将这个问题表述为一个混合整数二阶锥规划模型，旨在最小化总体旅行时间，并提出了精确方法和一种数学启发式方法。

在复杂的场景中，通常会出现多种被监控的目标。例如，战场任务可能涉及检查特定点、沿线路巡逻以及绘制指定区域的地图（Atencia等人，2019年）。在交通监控中，重点关注高优先级区域非常重要，如关键道路、事故多发的交叉口和繁忙的站点。与监控同质目标相比，将异质目标（如节点和边）整合到单一路线中可以显著减少总体旅行距离（Campbell等人，2023年）。如何确定无人机执行的目标序列（涉及节点和边）可以定义为多无人机通用路由问题，这对于许多无人机监控应用至关重要。然而，关于这个问题的研究非常有限。

此外，配备传感器的无人机只能在一定范围内检测目标，而不能进行精确定位。换句话说，只要目标位于空中传感器的感知范围内，就可以识别出来。这种能力使无人机在访问节点目标时能够缩短其总体旅行距离。这种应用可以表述为经典的足够接近的旅行商问题（CETSP）。然而，当无人机需要监控边目标时，这种优势就不再明显了。这是因为边目标（例如电线、管道和边界）需要特定的观察角度来获取有效信息。例如，在电线检查过程中，无人机必须从适当的角度拍摄绝缘体、导体和配件，而热传感器则需要特定的视角才能准确检测热点（Guan等人，2021年；Li等人，2022年）。相比之下，在多无人机通用路由问题中尚未考虑在一定范围内检测节点目标的问题。为了解决这一限制，我们提出了一个足够接近的多无人机通用路由问题，并开发了一种两阶段迭代数学启发式方法来解决它。我们的主要贡献有三个方面：
- 据我们所知，我们是第一个解决足够接近的多无人机通用路由问题（CEMUAVGRP）的研究者，在这个问题中，一队同质的无人机执行包含节点和边的监控任务，每个节点都有自己的圆盘邻域。我们提出了一种嵌套的表述方法，外层是非线性规划，用于选择所需节点的代表点；内层是整数线性规划，用于在考虑无人机最大飞行范围的情况下最小化总体飞行距离。
- 我们提出了一种两阶段迭代数学启发式方法来解决CEMUAVGRP：(1) 两阶段迭代框架：问题解决过程分为一般路由阶段，在此阶段获得包含每个无人机所需节点和边的满意路线，而不考虑圆盘邻域；以及足够接近的路由阶段，在此阶段优化每个所需节点的代表点。一般路由阶段应用了变量邻域下降（VND）启发式方法，而在足够接近的路由阶段使用了二阶锥规划（SOCP）方法。这两个阶段在自适应迭代局部搜索（AILS）框架下迭代进行，直到满足预定义的终止条件。(2) 自适应机制：进一步设计了两种自适应机制以提高解决方案的质量和鲁棒性：(i) 一种自适应接受策略，当搜索陷入停滞时动态降低接受阈值，允许偶尔接受较差的解决方案以摆脱局部最优解；(ii) 一种自适应扰动策略，当连续迭代没有改进时增加破坏强度，从而提高多样性。

在没有任何圆盘邻域的CEMUAVGRP基准实例上进行的广泛实验（Campbell等人，2023年）展示了AILS-VND-SOCP的强大优化性能。对于所有150个基准实例，AILS-VND-SOCP获得的最佳解决方案与已知最佳解决方案的差距不超过2.5%，并且显著优于其中13个解决方案。此外，引入圆盘邻域（即覆盖监控策略）有效地减少了总体飞行距离。增加圆盘邻域半径不仅缩短了无人机的路线，还减少了使用的无人机数量。

本文的其余部分组织如下：第2节回顾了现有的相关文献。第3节正式描述了CEMUAVGRP并推导了嵌套表述。第4节详细介绍了所提出的AILS-VND-SOCP方法。第5节报告了计算结果。最后，第6节得出了结论。

**文献回顾**
近年来，涉及无人机的路由问题已成为学术界的热门话题。传统上，地面车辆受限于现有基础设施，必须沿着指定的路线行驶才能到达目的地。相比之下，无人机可以沿着更直接的路线飞行，从而可能显著降低旅行成本。然而，这种灵活性也增加了问题的复杂性。例如，无人机可以在任何点（甚至是中间点）进入一条边。

**问题描述**
在CEMUAVGRP中，每架无人机从仓库出发并在完成任务后返回仓库，这些任务包括所需的节点和边。目标是最小化总体飞行距离。为了更好地反映实际情况，这个问题考虑了两个关键因素：(1) 所需边：除了所需的节点外，还需要考虑所需的边，其入口和出口方向会影响无人机的飞行距离。(2) 覆盖监控

**解决方案方法**
由于CEMUAVGRP是NP难问题，因此获得最优解在计算上是不可行的，特别是对于大规模实例。为此，我们提出了一种两阶段迭代数学启发式方法，旨在高效生成高质量解决方案。这个问题可以分为两个独立的子问题：一个是通用路由问题，用于确定每架无人机的任务序列，连接节点和边而不考虑圆盘邻域；另一个是足够接近的路由问题。

**计算结果**
在本节中，我们通过将我们提出的AILS-VND-SOCP方法与已知最佳解决方案进行比较来评估其性能。我们还验证了覆盖监控策略在减少总体距离方面的有效性，然后评估了提高接受阈值的有效性，接着是对圆盘邻域半径的敏感性分析。所有实验都是在配备Intel Core i7-12700F 2.10 GHz CPU、32 GB内存的PC上使用Python语言实现的。

**结论**
在这项研究中，我们提出了CEMUAVGRP，其中一队同质的无人机执行包含节点（每个节点关联一个圆盘邻域，即覆盖监控策略）和边的监控任务，旨在最小化总体距离。覆盖监控策略和边路由显著增加了问题的复杂性，使其特别具有挑战性。为了解决这个问题，我们提出了一种两阶段迭代数学启发式方法，将CEMUAVGRP分解为...

**作者贡献声明**
Huan Liu：写作——原始草稿、可视化、验证、方法论。
Michel Gendreau：监督、方法论。
Binjie Xu：写作——审稿与编辑、调查、形式分析。
Guohua Wu：监督、资金获取、概念化。
Yi Gu：可视化。

**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文所述的工作。

**致谢**
本研究得到了中国国家自然科学基金项目（批准号62603350）的部分支持，南京信息科学研究院人才引进启动基金（批准号2026r006）的部分支持，中国国家自然科学基金项目（批准号62373380）的部分支持，以及湖南省自然科学基金项目（批准号2025JJ10007）的部分支持。