Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots

We consider a single Unmanned Aerial Vehicle (UAV) routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problemis 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 fuel required by the UAV is a minimum. We develop an approximation algorithm for the problem, and propose fast construction and improvement heuristics to solve the same. Computational results show that solutions whose costs are on an average within 1.4% of the optimum can be obtained relatively fast for the problem involving five depots and 25 targets. Note to Practitioners-The motivation for this paper stems from the need to develop path planning algorithms for small UAVs with resource constraints. Small autonomous UAVs are seen as ideal platforms for many monitoring applications. Small UAVs can fly at low altitudes and can avoid obstacles or threats at low altitudes more easily. These vehicles can also be hand launched by an individual without any reliance on a specific type of terrain. Even though there are several advantages with using small platforms, they also come with other resource constraints due to their size and limited payload. This paper addresses a path planning problem involving a small UAV with fuel constraints, and presents fast and efficient algorithms for finding good feasible solutions.