关键词: 无人机任务规划, 车辆路径规划, 混合整数规划, 邻域搜索算法

Abstract:  Since the emergency rescue tasks need tight time, large demand, and large scale of rescue points, a large-scale multi-site unmanned aerial vehicle emergency rescue optimization method based on dynamic divide and conquer is proposed. In particular, a multi-station unmanned aerial vehicle emergency rescue model is established with the goal of minimizing the cumulative resume time. Besides, the model consideres the unmanned aerial vehicle platform constraints and emergency rescue mission constraints. Based on the model, a dynamic divide-and-conquer optimization framework based on path similarity is established and spatial clustering is performed based on the coupling relationship of rescue points. Then, large-scale problems are decomposed into several smaller-scale sub-problems with low coupling degrees. Finally, a variable neighborhood search algorithm for adaptive perturbation neighborhoods is proposed to achieve efficient optimization of large-scale emergency delivery plans through collaborative search and dynamic interaction of multi-dimensional neighborhoods. The simulation takes typical samples as an example and compares the proposed method with the advanced metaheuristic method on samples of different sizes. It is verified that the proposed method can effectively shorten the emergency delivery time and provide technical support for efficient post-disaster emergency rescue missions.

Key words: mission planning of  ummanned aerial vehicle, vehicle routing problem, mixed integer programming, neighborhood search algorithm