Improved Simulated Annealing Algorithm for UAV Path Planning with Uncertain Flight Time

Efficient multiple unmanned aerial vehicles (UAVs) path planning is crucial for improving mission completion efficiency in UAV operations. However, during the actual flight of UAVs, the flight time between nodes is always influenced by external factors, making the original path planning solution ineffective. In this paper, the multi-depot multi-UAV path planning problem with uncertain flight time is modeled as a robust optimization model with a budget uncertainty set. Then, the robust optimization model is transformed into a mixed integer linear programming model by the strong duality theorem, which makes the problem easy to solve. To effectively solve large-scale instances, a simulated annealing algorithm with a robust feasibility check (SA-RFC) is developed. The numerical experiment shows that the SA-RFC can find high-quality solutions within a few seconds. Moreover, the effect of the task location distribution, depot counts, and variations in robustness parameters on the robust optimization solution is analyzed by using Monte Carlo experiments. The results demonstrate that the proposed robust model can effectively reduce the risk of the UAV failing to return to the depot without significantly compromising the profit.