基于最小圆覆盖法的无人机救灾航巡策略研究

Drone Patrol Strategy Based on Minimum Circle Coverage Method

摘要: 本文针对灾难应急响应系统问题，以波多黎各城市2017年发生的严重飓风灾难为例，在满足无人机种类组合最佳、系统响应时间最短、无人机运输救生包最大量的前提下，建立了动态多目标规划模型，得到最优无人机舰队配置。基于最小圆覆盖法，将波多黎各区域离散化，确定三个货物集装箱的最佳安置位置，即无人机舰队从三个集装箱位置出发运输货物以及巡航的路径最短。我们将波多黎各地图主要道路化曲为直，得到波多黎各主要路迹的线路图，基于欧拉回路和Dijkstra算法，得到最优无人机巡航路线，其侦察范围覆盖率达90%以上，遍历路径距离最短。

Abstract: For the disaster emergency response system problem, we take the severe hurricane disaster in the city of Puerto Rico in 2017 as an example, under the premise of satisfying the best combination of drone types, the shortest system response time, and the maximum amount of drone transport life-saving packages, the dynamic multi-objective programming model is used to obtain the optimal drone fleet configuration. Based on the minimum circle coverage method, the Puerto Rico region is discretized to determine the optimal placement position of the three cargo containers, that is, the drone fleet transports goods from three container locations and the cruising path is the shortest. We have transformed the main roads of Puerto Rico into straight lines, and obtained the route map of the main roads in Puerto Rico. Based on the Euler loop and the Dijkstra algorithm, we obtained the optimal UAV cruise route with a coverage range of over 90% and the traversing path distance is the shortest.