A Multi-objective Metaheuristic for a Green UAV Grid Routing Problem

This paper deals with Unmanned Aerial Vehicle (UAV) routing in dynamic grid scenarios with limited battery autonomy and multiple charging stations. The problem is inspired by real-world constraints, specially designed for overcoming challenges of a limited vehicle driving range. Recently, these kinds of vehicles have started to be used for delivering and collecting products, requiring experts in several knowledge fields to manage this novel logistics. Inspired by a multi-criteria view of real systems, we consider different objective functions introduced in the literature. A multi-objective variant of Variable Neighborhood Search is considered for finding a set of non-dominated solutions, while respecting the navigation over forbidden areas and also battery capacity. A case of study was developed where one UAV has to attend clients spread throughout a grid representing a map. The drone 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 delivery). Any sequence of valid adjacent points forms a route, but since this yields a huge number of combinations, a pre-processing technique is proposed to pre-compute distances in a given dynamic scenario. Computational results demonstrate the performance of different variants of the proposed algorithm.