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

Ant Colony Algorithm for Fast Sector Generation Based on Diagram Cutting

作　　者：叶志坚[1] 王建忠[1] 张召悦[1] 杨群亭[1] 牟龙芳 YE Zhijian;WANG Jianzhong;ZHANG Zhaoyue;YANG Qunting;MU Longfang(College of Air Traffic Management,Civil Aviation University of China,Tianjin 300300,China)

机构地区：[1]中国民航大学空中交通管理学院,天津300300

出　　处：《计算机工程与应用》2022年第3期297-307,共11页Computer Engineering and Applications

基　　金：国家自然科学基金(71571186);国家自然科学青年基金(61603396);中央高校基本科研业务费(3122013C001)。

摘　　要：扇区划分是平衡管制员工作负荷、提升空域通行能力的有效技术措施。采用Voronoi图自顶向下切割空域的方法具有自动保证扇区凸性、连通性和压缩性的特性,但计算时间过长。根据航迹状态计算工作负荷,构建了Voronoi图自顶向下切割空域模型,设计了动态步长蚁群搜索算法。测试结果表明,在太原高空划分成4个扇区的情况下,与MC-CLFV(Monte Carlo method by changing location of flexible vertices)算法相比较,采用动态步长蚁群搜索算法求解,扇区的不平衡性显著减少,总工作负荷也减少了11.2%。大规模重复实验表明,随扇区数量增加,解的质量差异减少,但解的效率差异却不断增大,划分8个扇区时,动态步长蚁群搜索算法的计算时间统计中位数值仅为MC-CLFV算法的1/10。这说明该算法在一次划分数量少的时候,质量高而且计算时间短,在采用多层规划扇区的时候,应该采用组合数字和较小的划分方案。研究结果为采用Voronoi图直接切割空域形成管制扇区奠定了基础。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.

关 键 词：扇区划分 蚁群算法 4维航迹 VORONOI图 工作负荷 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] V37[自动化与计算机技术—计算机科学与技术]