Scheduling of Multiple UAVs in BVLoS Operations along Unidirectional and Bidirectional Paths

Unmanned aerial vehicles (UAVs) are crucial in various civilian applications, especially in Beyond Visual Line of Sight (BVLoS) operations. However, current regulations restrict BVLoS flights to specific corridors for safety reasons. This paper investigates the Drone Path Scheduling Problem (DPSP) whose goal is to assign time slots to each UAV by considering the corridors that UAVs need to traverse, and their starting time slot, in order to reach their destination such that the maximum slot for which all UAVs accomplished their mission is minimized. Time slots guarantee that each UAV accesses a corridor at a unique time, preventing multiple UAVs from using the same corridor simultaneously. We propose the REC and the HEAPBASED algorithms for unidirectional paths, demonstrating their optimality. For bidirectional paths, we offer sub-optimal solutions using HEAP-BASED and a 2-approximation algorithm called BIALG. Furthermore, we present an Integer Linear Programming (ILP) formulation to optimally solve DPSP on unidirectional and bidirectional paths. Performance evaluations show the efficacy and scalability of our proposed algorithms compared to the ILP formulation.