Ant Colony Algorithm for Fast Sector Generation Based on Diagram Cutting

doi:10.3778/j.issn.1002-8331.2008-0277

Abstract

Abstract: 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.

Key words: sector partition, ant colony algorithm, 4D trajectory, Voronoi diagram, workload

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

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

YE Zhijian, WANG Jianzhong, ZHANG Zhaoyue, YANG Qunting, MU Longfang. Ant Colony Algorithm for Fast Sector Generation Based on Diagram Cutting[J]. Computer Engineering and Applications, 2022, 58(3): 297-307.

叶志坚, 王建忠, 张召悦, 杨群亭, 牟龙芳. 图切割快速生成扇区的蚁群算法[J]. 计算机工程与应用, 2022, 58(3): 297-307.

References

[1] KOPARDEKAR P，BILIMORIA K，SRIDHAR B.Initial concepts for dynamic airspace configuration[C]//7th AIAA Aviation Technology，Integration and Operations Conference，2007：7763.
[2] HIND H，EL OMRI A，ABGHOUR N，et al.Dynamic airspace configuration：review and open research issues[C]//2018 4th International Conference on Logistics Operations Management（GOL），2018：1-7.
[3] GIANAZZA D.Learning air traffic controller workload from past sector operations[C]//ATM Seminar，12th USA/Europe Air Traffic Management R&D Seminar，2017.
[4] 袁乐平，孙瑞山，刘露.基于DORATASK的管制员工作负荷测量方法研究[J].安全与环境学报，2014，14（3）：76-79.YUAN L P，SUN Ｒ S，LIU L.Measuring the workload of the air traffic controller based on DORATASK method[J].Journal of Safety and Environment，2014，14（3）：76-79.
[5] 李钱.基于改进DORATASK法的空中交通管制员配备与工作负荷评估[J].计算机与数字工程，2019，47（8）：1996-1998.
LI Q.Air traffic controller allocation and workload assessment based on improved doratask method[J].Computer and Digital Engineering，2019，47（8）：1996-1998.
[6] 武丁杰.基于空域复杂度的管制员工作负荷评估[J].科学技术与工程，2013，13（31）：9465-9470.
WU D J.Evaluation of the controller’s workload based on airspace complexity[J].Science Technology and Engineering，2013，13（31）：9465-9470.
[7] 靳慧斌，洪远，蔡亚敏.基于交互指标的空中交通管制员工作负荷实时测量方法研究[J].安全与环境工程，2015，22（3）：147-150.
JIN H B，HONG Y，CAI Y M.Research on real-time measuring method of air traffic controller workload based on interactive indicators[J].Safety and Environmental Engineering，2015，22（3）：147-150.
[8] 叶志坚，高伟，王莉莉.空中交通流监控警告参数的设置和使用[J].科学技术与工程，2014，14（11）：76-80.
YE Z J，GAO W，WANG L L.Monitor alert parameter setting and use in ATFM[J].Science Technology and Engineering，2014，14（11）：76-80.
[9] SOBIE E，GUATIMOSIM S，SONG L S，et al.The challenge of molecular medicine：complexity versus occam’s razor[J].The Journal of Clinical Investigation，2003，111：801-803.
[10] CHEN Y，BI H，ZHANG D，et al.Dynamic airspace sectorization via improved genetic algorithm[J].Journal of Modern Transportation，2013，21（2）：117-124.
[11] ZHANG D F，CHEN Y Z.Airspace sectorisation via a weighted graph model[J].Aeronautical Journal，2014，118（1201）：267-274.
[12] ZOU X，CHENG P，AN B，et al.Sectorization and configuration transition in airspace design[J].Mathematical Problems in Engineering，2016（6）.
[13] MARTINEZ S，CHATTERJI G，SUN D，et al.A weighted-graph approach for dynamic airspace configuration[C]//Proceedings of AIAA Guidance，Navigation and Control Conference and Exhibit，2007：6448.
[14] YOUSEFI A，DONOHUE G.Temporal and spatial distribution of airspace complexity for air traffic controller workload-based sectorization[C]//Proceedings of AIAA 4th Aviation Technology，Integration and Operations（ATIO） Forum，2004：822-835.
[15] DREW M.A method of optimally combining sectors[C]//9th AIAA Aviation Technology，Integration，and Operations Conference（ATIO） and Aircraft Noise and Emissions Reduction Symposium（ANERS），2009：7057.
[16] BLOEM M，GUPTA P.Configuring airspace sectors with approximate dynamic programming[C]//The 27th International Congress of the Aeronautical Sciences，2010.
[17] KULKARNI S，GANESAN R，SHERRY L.Static sectorization approach to dynamic airspace configuration using approximate dynamic programming[C]//Integrated Communications，Navigation and Surveilance Conference （ICNS），2011：1-9.
[18] J?GARE P.Airspace sectorisation using constraint programming[D].Faculty of Science and Technology，Sweden：Uppsala University，2011：27.
[19] GAO W，GONG T Y，YE Z J.Airspace sector dividing method to balance dynamic control workload[J].Journal of Aeronautics，Astronautics and Aviation，2015，47（1）：21-28.
[20] GIANAZZA D.Forecasting workload and airspace configuration with neural networks and tree search methods[J].Artificial Intelligence，2010，174（7/8）：530-549.
[21] YE Z，KONG F，ZHANG B，et al.A method framework for automatic airspace reconfiguration-Monte Carlo method for eliminating irregular sector shapes generated by region growth method[J].Sensors（Basel，Switzerland），2019，19（18）：1-41.
[22] XUE M.Airspace sector redesign based on voronoi diagrams[J].Journal of Aerospace Computing，Information and Communication，2009，6（12）：605-615.
[23] XUE M.Three-dimensional sector design with optimal number of sectors[J].Journal of Guidance，Control and Dynamics，2012，35（2）：609-618.
[24] GERDES I，TEMME A，SCHULTZ M.Dynamic airspace sectorisation for flight-centric operations[J].Transportation Research Part C-Emerging Technologies，2018（95）：460-480.
[25] WONG C S Y，SUNDARAM S，SUNDARARAJAN N.CDAS：a cognitive decision-making architecture for dynamic airspace sectorization for efficient operations[J].IEEE Transactions on Intelligent Transportation Systems，2019，20（5）：1659-1668.
[26] FAA.Facility operation and administration[S].USA：FAA，2007.
[27] FOMIN V N.An algorithm for finding the shortest distance from a given point to a convex polyhedron and its application in the problem of pattern recognition[J].Metody Vyisl，1971（7）：97-106.
[28] 罗军，吕焕亮.基于粒子群优化算法的扇区组合优化[J].科学技术与工程，2013，13（14）：4130-4133.
LUO J，LV H L.Sector optimum partition based on particle swarm optimization[J].Science Technology and Engineering，2013，13（14）：4130-4133.
[29] 张炳祥.基于加权Voronoi图的扇区优化研究[J].武汉理工大学学报（交通科学与工程版），2013，37（3）：570-573.ZHANG B X.Optimization research of sectors based on weighted Voronoi diagram[J].Journal of Wuhan University of Technology（Transportation Science & Engineering），2013，37（3）：570-573.
[30] 王莉莉，胡婧，高峥.基于复杂度加权的Voronoi图扇区边界划分研究[J].中国民航大学学报，2014，32（3）：23-26.
WANG L L，HU J，GAO Z.Research of sector boundary demarcation based on weighted complexity Voronoi diagram[J].Journal of Civil Aviation University of China，2014，32（3）：23-26.
[31] ARAFAT M Y，MOH S.Localization and clustering based on swarm intelligence in UAV networks for emergency communications[J].IEEE Internet of Things Journal，2019，6（5）：8958-8976.