Optimizing multi-drone patrol path planning under uncertain flight duration: A robust model and adaptive large neighborhood search with simulated annealing

When conducting drone path planning , the flight duration of drones is a critical factor influencing the planning solution. Given the characteristics of drone batteries , accurately predicting the actual flight duration is challenging. It is crucial to reduce the impact of uncertain flight duration on path feasibility. To solve this problem, this paper proposes a robust optimization method that constructs a budget uncertainty set to describe the uncertain flight duration. To facilitate the solution process of the model, the strong duality theorem is employed to transform the robust model into a mixed integer linear programming model . To efficiently handle large-scale path planning problems, a hybrid heuristic algorithm with robust feasibility check (ALSA-RFC) is proposed. This algorithm combines the advantages of adaptive large neighborhood search and simulated annealing. Furthermore, to ensure the robustness of the solution, a method for generating robust initial solutions quickly and a robust feasibility checking method for solutions are constructed. Numerical experimental results demonstrate that ALSA-RFC can quickly find high-quality robust solutions. Additionally, through Monte Carlo simulations , the impact of robust parameters on the robustness of the solution scheme is analyzed, evaluating the performance of the algorithm in different scenarios. Comparisons with chance-constrained programming methods revealed that ALSA-RFC can significantly reduce the sensitivity of path planning results to fluctuations in flight duration without substantially increasing flight costs. Finally, a case study is conducted to further validate the practicality of ALSA-RFC in real-world applications. • Proposed a robust optimization method for multi-drone patrol path planning under uncertain flight duration. • Transformed the robust model into a mixed-integer linear programming model using strong duality theorem. • Developed a hybrid heuristic algorithm with robust feasibility check for large-scale path planning problems. • Experimental results verify the superiority of ALSA-RFC in handling uncertain flight duration with minimal cost impact.