On the Scheduling of Spatio-Temporal Charging Windows for Autonomous Drone Fleets

The availability of low-cost unmanned aerial vehicles (UAVs), or drones, has made their organisation in fleets more feasible. The required coordination for managing these fleets comes with an increased complexity. When used for long-durability, autonomous inspection missions, it is necessary to recharge the drones due to their limited battery capacity. By providing a set of nearby charging stations, the fleets can autonomously recharge and sustain indefinite missions. In order to reduce congestion at these charging stations, effective scheduling of charging cycles can have a significant impact on the mission execution time. In this paper, we propose a novel centralized method for scheduling charging time windows, taking into account the travel distances and occupation of charging stations. We formulate a mixed-integer linear program (MILP) model with two extensions to reduce the computational complexity. The solution to this problem assigns a set of charging windows to each drone, minimizing the mission execution time and ensuring batteries will not fully deplete. The performance of our proposed method is evaluated through a series of experiments, based on a discrete-event simulator. Our results reveal a clear benefit over a greedy approach, reducing the mission execution time by up to 39.8%. Through careful parameter selection, a trade-off between mission execution time and scheduling time can be found.