  Unmanned aerial vehicles (UAVs) have been widely used in many applications.
The limited flight time of UAVs, however, still remains as a major challenge.
Although numerous approaches have been developed to recharge the battery of
UAVs effectively, little is known about optimal methodologies to deploy
charging stations. In this paper, we address the charging station deployment
problem with an aim to find the optimal number and locations of charging
stations such that the system performance is maximized. We show that the
problem is NP-Hard and propose UBAT, a heuristic framework based on the ant
colony optimization (ACO) to solve the problem. Additionally, a suite of
algorithms are designed to enhance the execution time and the quality of the
solutions for UBAT. Through extensive simulations, we demonstrate that UBAT
effectively performs multi-objective optimization of generation of UAV
trajectories and placement of charging stations that are within 8.3% and 7.3%
of the true optimal solutions, respectively.
