A two-phase multi-objective metaheuristic for a green UAV grid routing problem: Optimization Letters

This paper deals with Unmanned Aerial Vehicle (UAV) routing in dynamic grid scenarios with limited battery autonomy and multiple charging stations. Inspired by a multi-criteria view of real systems, we consider different objective functions, while respecting the navigation over forbidden areas and also a real-time flight autonomy. A multi-objective variant of Variable Neighborhood Search is considered for finding sets of non-dominated solutions. Twelve neighborhood structures were developed in order to explore the solution space, including learning techniques. The latter stores known routes in order to speed up the search. A case of study was developed where UAVs have to serve clients spread throughout a grid, representing a map. Each UAV starts in a given grid point with a given battery charge, where the grid is composed by four different kinds of points: a regular one and three special (prohibited, recharge and client). Any update can happen on the routes on real-time, so the metaheuristic should handle real-time information and update the plan and graphics user interface accordingly. Any sequence of valid adjacent points forms a route, but since this yields a huge number of combinations, a preprocessing technique is proposed to pre-compute distances in a given dynamic scenario. Computational results demonstrate the performance of different variants of the proposed algorithms. © 2023, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.