  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 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 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 5 depots and
25 targets.
