Santin Rafael, Assis Luciana, Vivas Alessandro, Pimenta Luciano C A
Department of Computing, Universidade Federal dos Vales do Jequitinhonha e Mucuri, Rod. MGT 367, Km 583, 5000-Alto da Jacuba, Diamantina 39100-000, Brazil.
Graduate Program in Electrical Engineering, Universidade Federal de Minas Gerais, Av. Antônio Carlos 6627, Belo Horizonte 31270-901, Brazil.
Sensors (Basel). 2021 Mar 2;21(5):1705. doi: 10.3390/s21051705.
This paper presents matheuristics for routing a heterogeneous group of capacitated unmanned air vehicles (UAVs) for complete coverage of ground areas, considering simultaneous minimization of the coverage time and locating the minimal number of refueling stations. Whereas coverage path planning (CPP) is widely studied in the literature, previous works did not combine heterogeneous vehicle performance and complete area coverage constraints to optimize UAV tours by considering both objectives. As this problem cannot be easily solved, we designed high-level path planning that combines the multiobjective variable neighborhood search (MOVNS) metaheuristic and the exact mathematical formulation to explore the set of nondominated solutions. Since the exact method can interact in different ways with MOVNS, we evaluated four different strategies using four metrics: execution time, coverage, cardinality, and hypervolume. The experimental results show that applying the exact method as an intraroute operator into the variable neighborhood descent (VND) can return solutions as good as those obtained by the closest to optimal strategy but with higher efficiency.
本文提出了一种数学启发式算法，用于对一组异构的有容量限制的无人机（UAV）进行路径规划，以实现对地面区域的完全覆盖，同时考虑将覆盖时间最小化以及确定最少数量的加油站位置。虽然覆盖路径规划（CPP）在文献中已得到广泛研究，但先前的工作并未将异构车辆性能和完全区域覆盖约束相结合，以通过同时考虑这两个目标来优化无人机航迹。由于这个问题不容易解决，我们设计了一种高级路径规划方法，该方法将多目标变量邻域搜索（MOVNS）元启发式算法和精确数学公式相结合，以探索非支配解集合。由于精确方法可以与MOVNS以不同方式相互作用，我们使用四个指标评估了四种不同策略：执行时间、覆盖范围、基数和超体积。实验结果表明，将精确方法作为路由内算子应用于变量邻域下降（VND），可以得到与最接近最优策略所获得的解一样好的解，但效率更高。
