Cost-Effective Parallel Cooperative Charging Scheduling for UAVs

Unmanned Aerial Vehicles (UAVs) have recently been widely used in various fields. However, both cooperative charging scheduling and insufficient charging facility problems in UAV charging scenarios have been rarely studied. This paper studies parallel cooperative charging scheduling of UAVs. We adopt cooperative charging to reduce the total cost and parallel scheduling to enable UAVs can be charged even if the number of UAVs is more than the number of charging facilities. We formulate the Parallel Cooperative Charging Scheduling for UAVs Problem (PCCSUP) for optimizing the total cost of whole charging system. We first investigate the special case of PCCSUP with single charging station, and use the approximation algorithm for Uniform Parallel Machines Scheduling Problem (UPMSP) to solve the special case. Then, a greedy approach based approximation algorithm is proposed to solve the PCCSUP, where we use the approximation algorithm for UPMSP to obtain the charging arrangements and the Set Covering Problem (SCP) optimization framework to obtain the charging groups. The results of extensive simulations demonstrate that our algorithm can reduce up to 59.81% total cost compared with the benchmark algorithms. Finally, we discuss and design the algorithms for three related problems: PCCSUP with different arrival times, PCCSUP withK-anonymity, and charging arrangements for excluded UAVs.