Load-Balanced Recipient Assignment and Time-Constrained Scheduling of Multiple Battery Mules for UAV Swarm Service Prolongation

The potential of unmanned aerial vehicle (UAV) collaboration extends far beyond traditional applications, offering versatile solutions across a wide range of scenarios. However, limited battery capacity of UAVs significantly restricts their continuous operational capabilities. On-board battery swapping by battery “refueler” or mule is a method that can effectively extend the service time of UAVs. However, it is still a challenging task for scheduling multiple battery mules to serve a UAV swarm. This paper formulates multi-mule scheduling as a 0-1 mixed integer programming problem. Then, a two-stage framework was put forward to schedule multiple battery mules for swapping batteries in a UAV swarm, in which the UAVs receiving battery swapping service are referred to as “recipients.” In the first stage, a greedy algorithm is leveraged to cluster recipients and assign them to all mules, achieving load balance and decomposing the original problem into multiple single-mule scheduling sub-problems. To address the non-convexity of mixed integer programming in the second stage for single-mule scheduling, a heuristic algorithm was designed that integrates time constraints into traveling salesman problem (TSP). A series of simulation experiments has been conducted. Results show that the proposed framework achieves at least 30.70% higher average continuous service ratio of UAVs than other benchmarks.