Matheuristics for Multi-UAV Routing and Recharge Station Location for Complete Area Coverage

Autor(es)

Santin, Rafael ^{[1, 2]} ; Assis, Luciana ^[2] ; Vivas, Alessandro ^[2] ; Pimenta, Luciano C. A. ^[3]

Afiliação do(s) autor(es)

^[1] Univ Fed Minas Gerais, Grad Program Elect Engn, Ave Antonio Carlos 6627, BR-31270901 Belo Horizonte, MG - Brazil

^[2] Univ Fed Vales Jequitinhonha & Mucuri, Dept Comp, Rod MGT 367, Km 583, 5000 Alto da Jacuba, BR-39100000 Diamantina - Brazil

^[3] Univ Fed Minas Gerais, Dept Elect Engn, BR-31270901 Belo Horizonte, MG - Brazil

• Tipo de documento: Artigo Científico
• Fonte: SENSORS; v. 21, n. 5 MAR 2021.
• Citações Web of Science: 0

Resumo

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. (AU)

• Processo FAPESP: 14/50851-0 - INCT 2014: Instituto Nacional de Ciência e Tecnologia para Sistemas Autônomos Cooperativos Aplicados em Segurança e Meio Ambiente
• Beneficiário: Marco Henrique Terra
• Modalidade de apoio: Auxílio à Pesquisa - Temático