## 1 Introduction  
The recent advances in Unmanned Aerial Vehicles (UAVs), such as increased payload, operating time and autonomous flight capacities, enable today to consider their use in a growing number of applications. In automatic mode, they can even autonomously take off, follow a previously defined trajectory and landing, [1]. They can act, for example, in smart farming, environmental monitoring, emergency aid and parcel delivery [2, 3]. Moreover, combined with Wireless Sensor Networks (WSNs), they can collect data through radio communication, play the role of mobile gateway or communication relay in case of connectivity failure, and perform accurate operations, see [4, 5, 6].  
However, planning the trajectory to be followed by an Unmanned Aerial Vehicle (UAV) in automatic mode can rapidly become a challenging task, in particular when the minimization of a cost function, as distance, time or energy, is pursued due the limited flight time of the UAV. For example, in the case of several static waypoints to be visited by the UAV in a free-obstacle working space, the search for the optimal trajectory requires to solve the Traveling Salesman Problem (TSP) [7, 8, 9]. The waypoints can be regarded as the cities to be visited. The time complexity of the TSP increases exponentially with the number of cities according to \((nb_{clites}-1)!\), leading rapidly to prohibitive calculation costs. For example, 25 cities represent already \(24!\simeq 10^{23}\) possible routes. By considering a computer able to calculate 1 billion routes per second, it would take 10 million years to a brute force algorithm to calculate all the possible combinations (\(10^{23}/(10^{9}*60*60*24*365)\simeq 10^{7}\)) to next find the best solution. An alternative is to accept to not find the optimal solution and seek a sub-optimal solution. Numerous algorithms have been proposed to that end in the literature. Some of them are inspired by the natural selection (e.g., genetic algorithms [10]) or animal behavior (e.g., Ant Colony Optimization algorithms [11], Particle Swarm Optimization algorithms [12]). These approaches are non-deterministic, iteratively, and a criteria is required to stop the algorithm (e.g., number of iterations, threshold reached). Additional constraints can be considered, leading to variants of TSP. In the classical TSP problem, called Symmetric TSP (STSP), the route between two cities can be performed indifferently in one direction or the other. In the Asymmetric TSP (ATSP), the travel cost can be different to travel from city A to city B, than to travel from city B to city A--see [13]. In the Precedence Constrained TSP (TSP-PC), an additional constraint is that a city A should not be visited unless the city B was visited first--see [14]. We can also mention the Capacited Vehicle Routing Problem (CVRP) where the vehicle has limited carrying capacity, requiring to go back to the depot when the vehicle is full--see [15]. Another variant is that the cities are not represented by points, i.e., an exact location, but by areas with various shapes called neighborhoods--see [16]. In this case, the vehicle has to enter successively within the areas without the need to pass through the center. The problem is called TSP with Neighborhoods (TSPN). A similar problem is the Close Enough TSP (CETSP) where the areas are defined by circles of different radius--see [17; 18].