图切割快速生成扇区的蚁群算法

扇区划分是平衡管制员工作负荷、提升空域通行能力的有效技术措施.采用Voronoi图自顶向下切割空域的方法具有自动保证扇区凸性、连通性和压缩性的特性,但计算时间过长.根据航迹状态计算工作负荷,构建了Voronoi图自顶向下切割空域模型,设计了动态步长蚁群搜索算法.测试结果表明,在太原高空划分成4个扇区的情况下,与MC-C...

Ant Colony Algorithm for Fast Sector Generation Based on Diagram Cutting

Sector partition is an effective technical measure to balance workload of controllers and improve airspace capacity. Using Voronoi diagram to cut the airspace from top to bottom has the characteristics of automatically ensuring sector convexity, connectivity and compressibility, but the long calculation time is a problem. Based on the method of calculating workload according to trajectory situation, a top-down Voronoi diagram cutting airspace model is established, and a dynamic step ant colony search algorithm is developed to solve the model. The experimental results show that compared with MC-CLFV algorithm, the dynamic step ant colony algorithm significantly reduces sector imbalance, as well reduces total workload by 11.2%. In large-scale repeated experiments, it is found that with the increase of the number of sectors, the quality difference of solutions decreases, while the efficiency difference increases. When 8 sectors are divided, the average computing time of dynamic step ant colony algorithm is only 1/10 of that of MC-CLFV algorithm. This shows that the algorithm has high quality and short calculation time when the number of partitions is small at one time. When multi-level planning sectors are used, the scheme with small number combination should be adopted. The research results lay a foundation for the formation of control sector by directly cutting airspace with Voronoi diagram.