Route planning algorithms for unmanned aerial vehicles with refueling constraints

Small UAVs are currently used in several monitoring applications to monitor a set of targets and collect relevant data. One of the main constraints that characterize a small UAV is the maximum amount of fuel the vehicle carry. In this article, we consider a single UAV routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total cost of the edges present in the path is a minimum. We first develop a mixed integer, linear programming formulation to solve the problem optimally. We also propose fast and efficient construction and improvement heuristics to solve the same. Computational results are also presented to corroborate the solution quality and the running times of all the algorithms.