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

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...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms 2023-01, Vol.16 (1), p.44
Main Authors: Cariou, Christophe, Moiroux-Arvis, Laure, Pinet, François, Chanet, Jean-Pierre
Format: Article
Language:English
Subjects:
Automatic meter reading
Cities
Close Enough Traveling Salesman Problem
Computer Science
Cost function
Data collection
Environmental monitoring
evolutionary algorithm
Evolutionary algorithms
genetic algorithm
Genetic algorithms
Heuristic
Moisture effects
Neighborhoods
optimal trajectory planning
Optimization algorithms
Radio communications
Sensors
Soil moisture
Trajectory optimization
Trajectory planning
Travel
Traveling salesman problem
Unmanned Aerial Vehicle
Unmanned aerial vehicles
Wireless Underground Sensor Networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1999-4893
1999-4893
DOI:10.3390/a16010044