1.摘要

本文提出了一种能源高效的无人机路径规划方法（EURP）用于监测分散的地质灾害易发区域，通过建立无人机飞行模式的能耗模型，并采用近似细胞分解技术将区域离散为方格网，以提高图像获取精度。为解决EURP问题，本文设计了一个混合元启发式算法（EGHM），结合大邻域搜索（LNS）和可变邻域下降（VND）进行优化。

2.问题描述与数学模型

参数定义

An illustrative small example of the problem

本文探讨了无人机在多个地质灾害易发区域监测中的能源高效路径规划问题，该问题涉及一队无人机从仓库出发，对多个目标区域进行监控，并在电池限制内返回。采用近似细胞分解技术将区域离散为方格网格，通过设定能耗模型考虑不同飞行模式的能量消耗。目标是确定最优路径，最小化整体能耗。假设包括无人机具有垂直起降能力，路径无碰撞，并保持恒定飞行高度。

The processes of geohazard-prone area gridding

本文通过近似细胞分解方法对地质灾害易发区域进行网格化，将区域划分为正方形网格单元，每个单元由中心点和边长定义。只有与凸多边形P重叠的单元格中心点被视为无人机访问的节点。采用绕数算法验证中心点是否位于凸多边形内部，若不在内部，则检查是否与多边形的边相交，以确定是否为有效节点。最终，生成一个均匀的矩形网格覆盖整个地质灾害易发区域。

无人机能源消耗模型描述了无人机在飞行中的能量消耗，涵盖直线飞行、转向和悬停三种飞行模式。在直线飞行模式下，能量消耗与飞行距离和速度相关；转向时的能量消耗由转向角度决定，并通过余弦定理计算；悬停时的能量消耗与悬停时间和相关比率有关。

数学模型

3.能源网格混合元启发式算法

能源网格混合元启发式算法包括：预计算阶段、构造算法生成初始解、通过大邻域搜索框架（LNS）进行解增强、基于可变邻域下降方法（VND）优化解。通过破坏与修复算子、邻域算子等方法，算法在区域和节点层面逐步改进解，最终输出最佳解。

在预计算过程中，定义地质灾害易发区域的近似距离矩阵通过虚拟质心之间的旅行距离来近似区域间的距离。确定每个地质灾害易发区域的虚拟质心：
$x‾l=∑i∈Nlxi∣Nl∣,y‾l=∑i∈Nlyi∣Nl∣\overline{x}_{l}=\frac{\sum_{i\in N_{l}}x_{i}}{|N_{l}|},\quad\overline{y}_{l}=\frac{\sum_{i\in N_{l}}y_{i}}{|N_{l}|}$

破坏算子移除整个地质灾害易发区域，以保持目标区域内节点分组。设计了两种主要的破坏算子：最差尖角移除（WSAR）和最差区域转向角移除（WATAR），旨在通过减少转向和尖角来降低无人机能量消耗。除此之外，还设计了四种有效的破坏算子，包括随机破坏移除（RDR）、相关破坏（ReD）、最差破坏（WD）和路线破坏（RoD），这些算子通过移除区域或路径来优化解决方案，增强算法的解的质量。

Intra-area route generated using grid-based repair with the entry node (EnN) and exit node (ExN)

本文为重新插入移除的地质灾害易发区域，设计了三种修复算子：最近修复、路径成本优先修复和网格基础修复。最近修复按插入最少的原则将区域插入部分解；路径成本优先修复优先插入成本最高的区域；网格基础修复利用波形算法和深度限制搜索，重新规划区域内路径。

4.结果展示

论文仿真

5.参考文献

[1] Han Z, Fang C, Wang W, et al. Energy-Efficient UAV routing problem based on approximate cellular decomposition for geohazards monitoring[J]. Computers & Operations Research, 2025: 107154.