Journal of Beijing University of Posts and Telecommunications

  • EI核心期刊

Journal of Beijing University of Posts and Telecommunications ›› 2024, Vol. 47 ›› Issue (1): 65-71.

Previous Articles     Next Articles

Optimization Method for Large-Scale Multi-Site Unmanned Aerial Vehicle mergency Rescue Based on Dynamic Divide-and-Conquer Strategy

SU Lichen1, ZHAO Haoran2, GUO Tong2, DU Wenbo2, LI Yumeng2   

  • Received:2023-02-22 Revised:2023-04-20 Online:2024-02-26 Published:2024-02-26

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

CLC Number: