Evolutionary Algorithm with Geometrical Heuristics for Solving the Close Enough Traveling Salesman Problem: Application to the Trajectory Planning of an Unmanned Aerial Vehicle - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Journal Articles Algorithms Year : 2023

Evolutionary Algorithm with Geometrical Heuristics for Solving the Close Enough Traveling Salesman Problem: Application to the Trajectory Planning of an Unmanned Aerial Vehicle

Abstract

Evolutionary algorithms have been widely studied in the literature to find sub-optimal solutions to complex problems as the Traveling Salesman Problem (TSP). In such a problem, the target positions are usually static and punctually defined. The objective is to minimize a cost function as the minimal distance, time or energy. However, in some applications, as the one addressed in this paper—namely the data collection of buried sensor nodes by means of an Unmanned Aerial Vehicle— the targets are areas with varying sizes: they are defined with respect to the radio communication range of each node, ranging from a few meters to several hundred meters according to various parameters (e.g., soil moisture, burial depth, transmit power). The Unmanned Aerial Vehicle has to enter successively in these dynamic areas to collect the data, without the need to pass at the vertical of each node. Some areas can obviously intersect. That leads to solve the Close Enough TSP. To determine a sub-optimal trajectory for the Unmanned Aerial Vehicle, this paper presents an original and efficient strategy based on an evolutionary algorithm completed with geometrical heuristics. The performances of the algorithm are highlighted through scenarios with respectively 15 and 50 target locations. The results are analyzed with respect to the total route length. Finally, conclusions and future research directions are discussed.
Fichier principal
Vignette du fichier
2023_Cariou_Algotithms.pdf (2.89 Mo) Télécharger le fichier
Origin Publisher files allowed on an open archive
Licence

Dates and versions

hal-04072066 , version 1 (17-04-2023)

Licence

Identifiers

Cite

Christophe Cariou, Laure Moiroux-Arvis, François Pinet, Jean-Pierre Chanet. Evolutionary Algorithm with Geometrical Heuristics for Solving the Close Enough Traveling Salesman Problem: Application to the Trajectory Planning of an Unmanned Aerial Vehicle. Algorithms, 2023, 16 (1), pp.44. ⟨10.3390/a16010044⟩. ⟨hal-04072066⟩
55 View
142 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More