Interval-Aware Scheduling of Surveillance Drones: Exact and Heuristic Approaches

In recent years, the patrol security of facilities has faced various challenges, including labor shortages and rising labor costs. Drones, with their high mobility and advanced features such as high-resolution cameras, offer a promising alternative to human patrols. Moreover, establishing an optimal patrol schedule for drones is crucial for efficient security operations. This paper proposes four methods for determining the optimal patrol schedule for drones: the ILP-based method, the Greedy method, the Simulated Annealing method, and the Multi-stage method. In experiments, we evaluate each method by comparing total flight time and algorithm runtime. Compared to the ILP-based method, the Multi-stage method exhibited a maximum of 13.4% degradation in total flight time but significantly outperformed it in terms of algorithm runtime. In comparison to the Greedy method, the Multi-stage method achieved an average improvement of 37.8% in total flight time, while its algorithm runtime deteriorated by a maximum of 1.26 seconds. Compared to the Simulated Annealing method, the Multi-stage method achieved an average improvement of 37.8% in total flight time and consistently outperformed the Simulated Annealing method in solving all problems. Conversely, when operating with a single drone, the number of unsolved problems increased significantly when the number of patrol points exceeded 17. Subsequently, experiments were conducted by increasing the maximum number of drones to two and three. The total flight time was compared using the Multi-stage method. By expanding the drone fleet to three, the percentage of solvable problems increased by 87.9%, without compromising total flight time. As a case study, the Multi-stage method was applied to determine the optimal patrol schedule for drones at the Osaka-Ibaraki Campus of Ritsumeikan University.