Roteamento e localização de estações de recarga em tarefas de cobertura de área com múltiplos veículos aéreos não tripulados

Abstract

This work addresses the area coverage problem using a group of unmanned aerial vehicles (UAVs). The complete area coverage is fundamental for some applications, such as environmental monitoring, surveillance, search, and rescue, among many others, which cannot leave any space uncovered. Some applications also need urgency to finish the coverage mission, requiring proper path planning to minimize the coverage time facing each UAV particularity. However, standard UAVs are limited in flight time and their frequent recharges can negatively impact the mission time. Thus, it is also relevant to plan their batteries recharges, setting the recharging moment, the most appropriate places for installing the recharging stations, and the number of adequate stations to minimize the number of these facilities. Minimizing the number of such stations is relevant due to the installation costs. However, both objectives can be conflicting, so that reducing the number of recharge stations can increase coverage time. In this sense, the present work proposes solutions for the multi-objective complete area coverage problem with multiple heterogeneous UAVs to minimize the total time of the coverage operation and locate the minimum number of recharging stations. Due to the computational complexity of this problem, matheuristics characterized by integrating the exact method with multi-objective variable neighborhood search (MOVNS) are designed to exploit the synergy between the two methods to find good solutions. Computational experiments evaluated the different strategies according to runtime and hypervolume, metrics for solving several instances. The results showed that the proposed methods could obtain good solutions for intractable instances by the exact method.