Research on airspace sector optimization based on Voronoi diagram and improved K-means algorithm

基于Voronoi图和改进K-means的扇区优化研究

¹ Air Traffic Control and Navigation College, Air Force Engineering University, Xi'an 710051, China
² National Key Laboratory of Air Traffic Collision Prevention, Xi'an 710051, China

Received: 11 April 2022

Abstract

Sector partition is an important task of air traffic control, and a reasonable sector partition can improve the utilization rate of airspace and protect the flight safety of aircrafts. Since the sector partition during flat hours is not well suited to the complex air situation, this paper proposes a sector optimization method based on Voronoi diagram and improved K-means. Firstly, a conflict network is constructed based on the air situation, and a comprehensive sector control workload measurement method is proposed by combining aircraft velocity obstacle relationship and complex network theory. Based on the workload value, a cluster center is determined as the generating element of Voronoi diagram by using the improved K-means method, and then the sector is optimized by using the division method of Voronoi diagram. In this paper, the data of Xiamen airspace control sectors are collected as a simulation scenario for calculation and analysis. The simulation results show that the average variance of the optimized sector control workload is reduced by 66.04% during the peak hours and 13.88% during the flat hours compared with the original sector. The method achieves the purpose of balancing the sector workload, verifies the effectiveness of the sector optimization method, and provides a reference basis for the existing sector partition work.

摘要

扇区划分是空中交通管制的一项重要工作, 合理的扇区划分能够提高空域的使用率, 保障航空器的飞行安全。鉴于平峰时段的扇区划设不能很好适用于复杂空情的现状, 提出一种基于Voronoi图和改进K-means的扇区优化方法。依据空情态势构建冲突网络, 结合航空器速度障碍关系和复杂网络理论提出了扇区综合管制负荷计量方式。依据负荷值采用改进K-means聚类方法确定了合理的聚类中心作为Voronoi图的生成元, 从而使用Voronoi图的划分方法生成合理边界来优化扇区。采集厦门空域管制扇区数据作为仿真场景进行了计算分析, 结果表明, 在繁忙时段, 优化后的扇区管制负荷平均方差相比原扇区降低了66.04%, 平峰时段降低了13.88%, 达到了均衡扇区负荷的目的, 验证了扇区优化方法的有效性, 为现有的扇区划设工作提供了参考依据。