Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2025, Vol. 59 Issue (2): 413-422    DOI: 10.3785/j.issn.1008-973X.2025.02.019
    
Three-dimensional sector automatic design based on improved NSGA-II algorithm
Yingfei ZHANG1(),Xiaobing HU1,Hang ZHOU2,*(),Xuzeng FENG3
1. College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China
2. Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin 300300, China
3. Zhejiang Dahua Technology Limited Company, Hangzhou 310053, China
Download: HTML     PDF(1634KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

An improved non-dominated sorting genetic algorithm II (NSGA-II) was proposed in order to address the challenges of time-consuming manual airspace sectorization and the difficulty in comparing the quality of different sectorization schemes. A three-dimensional multi-objective optimization model for sectorization was established by using a grid-region-sector hierarchy in order to balance controllers’ workload within sectors and reduce workload differences between sectors. A fitness evaluation operator, a probability-adaptive combination crossover operator and a dynamic mutation operator were incorporated in the NSGA-II algorithm in order to enhance the number of feasible solutions, solution diversity and computational efficiency. A simulation was conducted for the automatic 3D sectorization of Xi'an high-altitude airspace. Results showed that the optimized scheme improved workload balance within sectors by 37% and reduced inter-sector workload by 24% compared with the current sectorization configuration. The proposed improved NSGA-II provided a broader range of options for decision-makers with varying preferences compared with traditional weighted multi-objective optimization algorithms.

Key words： air traffic control      three-dimensional sector design      multi-objective optimization      improved NSGA-II algorithm      selection strategy     
Received: 27 December 2023      Published: 11 February 2025
CLC:  V 355  
Fund:  天津市自然科学基金多元投入青年项目（23JCQNJC00080）；中央高校基本科研业务费中国民航大学专项资助项目（3122020075）.
Corresponding Authors: Hang ZHOU     E-mail: zhangyf9507@163.com;h-zhou@cauc.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Yingfei ZHANG
Xiaobing HU
Hang ZHOU
Xuzeng FENG
Cite this article:

Yingfei ZHANG,Xiaobing HU,Hang ZHOU,Xuzeng FENG. Three-dimensional sector automatic design based on improved NSGA-II algorithm. Journal of ZheJiang University (Engineering Science), 2025, 59(2): 413-422.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2025.02.019     OR     https://www.zjujournals.com/eng/Y2025/V59/I2/413


基于改进的NSGA-II算法的三维扇区自动划设

针对人工划分空域扇区耗时长且难以比较不同扇区划分方案优劣的问题，提出改进的快速非支配排序遗传算法(NSGA-II）. 以均衡管制员扇区内工作负荷和减少管制员扇区间工作负荷为目标，基于网格-区域块-扇区层级提出三维扇区划分多目标优化模型. 为了提高种群的可行解数量、多样性及算法的解算速度，在NSGA-II算法中引入适应度评估算子、变概率组合交叉算子和动态变异算子. 对西安高空空域进行三维扇区自动划设的仿真模拟. 结果表明，与实际划分构型相比，优化后的方案将扇区内工作负荷均衡性提高了37%，扇区间工作负荷减少了24%；与传统的加权多目标优化算法相比，基于改进的NSGA-II算法得到的扇区划分方案可以为不同偏好的决策者提供更广泛的选择.


关键词： 空中交通管制,  三维扇区划设,  多目标优化,  改进NSGA-II算法,  选择策略 
Fig.1 Illustration of airspace grid modeling
Fig.2 Illustration of airspace block modeling
Fig.3 Illustration of airspace sector modeling
Fig.4 Illustration of chromosome structure
Fig.5 Illustration of center point position mutation
Fig.6 Illustration of check correction operator
Fig.7 Flow chart of optimization of airspace sector
指标Nopts/s
最大值4280.34
最小值3077.06
平均值3578.52
标准差4.250.74
Tab.1 Statistical result of simulation for improved NSGA-II algorithm
方案$S_1^{{\text{inter}}}$$S_2^{{\text{inter}}}$$S_3^{{\text{inter}}}$$S_4^{{\text{inter}}}$$S_5^{{\text{inter}}}$$S_6^{{\text{inter}}}$$S_7^{{\text{inter}}}$$S_8^{{\text{inter}}}$$S_9^{{\text{inter}}}$$S_{10}^{{\text{inter}}}$TWL
当前构型243144135903427272171902611620
方案A14490901443065463126631531233
Tab.3 Inter-sector workload of 10 sectors under two solutions
方案$ S_1^{{\text{inner}}} $$S_2^{{\text{inner}}}$$S_3^{{\text{inner}}}$$S_4^{{\text{inner}}}$$S_5^{{\text{inner}}}$$S_6^{{\text{inner}}}$$S_7^{{\text{inner}}}$$S_8^{{\text{inner}}}$$S_9^{{\text{inner}}}$$S_{10}^{{\text{inner}}}$SD
当前构型197316641656648183016402054108511941216422
方案A165111601072165816371360957119113161742262
Tab.2 Inner-sector workload of 10 sectors under two solutions
Fig.8 Schematic diagram of actual configuration sector division
Fig.9 Schematic diagram of plan A sector division
Fig.10 Comparison of solution effect of three algorithm
算法RT/s
改进NSGA-II算法78.52
多目标遗传算法64.36
多目标模拟退火算法70.92
Tab.4 Average running time statistics of three algorithms
Fig.11 Illustration of sector solution selection strategy
[1]   YOUSEFI A, DONOHUE G. Temporal and spatial distribution of airspace complexity for air traffic controller workload-based sectorization [C]// AIAA 4th Aviation Technology, Integration and Operations Forum. Chicago: AIAA, 2004(2): 822-835.
[2]   戴福青, 王丹 基于改进区域生长算法的终端区扇区优化[J]. 中国民航飞行学院学报, 2017, 28 (3): 14- 18
DAI Fuqing, WANG Dan Terminal area sector operation optimization based on improved region growing algorithm[J]. Journal of Civil Aviation Flight University of China, 2017, 28 (3): 14- 18
[3]   TANG J, ALAM S, LOKAN C, et al A multi-objective approach for dynamic airspace sectorization using agent based and geometric models[J]. Transportation Research Part C: Emerging Technologies, 2012, 21 (1): 89- 121
doi: 10.1016/j.trc.2011.08.008
[4]   BRINTON C R, PLEDGIE S. Airspace partitioning using flight clustering and computational geometry [C]// Proceedings of 27th Digital Avionics Systems Conference. Washington, DC: IEEE, 2008: 3. B. 3- 1-3. B. 3-10.
[5]   高伟, 陈姝含, 叶志坚, 等 基于谱聚类的扇区划分[J]. 火力与指挥控制, 2021, 46 (12): 32- 38
GAO Wei, CHEN Shuhan, YE Zhijian, et al Spectral clustering based sector division[J]. Firepower and Command Control, 2021, 46 (12): 32- 38
[6]   林福根, 温祥西, 吴明功, 等 基于Voronoi图和改进K-means的扇区优化研究[J]. 西北工业大学学报, 2023, 41 (1): 170- 179
LIN Fugen, WEN Xiangxi, WU Minggong, et al Research on airspace sector optimization based on Voronoi diagram and improved K-means algorithm[J]. Journal of Northwestern Polytechnical University, 2023, 41 (1): 170- 179
doi: 10.1051/jnwpu/20234110170
[7]   徐灿, 田勇, 牛科新, 等 考虑空域功能性的终端区内三维扇区划设方法研究[J]. 科学技术与工程, 2022, 22 (28): 12674- 12682
XU Can, TIAN Yong, NIU Kexin, et al Three-dimensional sectorization in terminal area considering airspace function[J]. Science Technology and Engineering, 2022, 22 (28): 12674- 12682
[8]   王莉莉, 贾铧霏 基于复杂度分析的空域扇区划分[J]. 南京航空航天大学学报, 2017, 49 (1): 140- 146
WANG Lili, JIA Huafei Sector planning based on complexity analysis[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2017, 49 (1): 140- 146
[9]   姚虹翔, 叶博嘉, 程予 基于加权Voronoi图的管制扇区增开研究[J]. 航空计算技术, 2021, 51 (4): 45- 49
YAO Hongxiang, YE Bojia, CHENG Yu Research on the method of regulatory sector expansion based on weighted Voronoi diagram[J]. Aeronautical Computing Technique, 2021, 51 (4): 45- 49
[10]   叶志坚, 王建忠, 张召悦, 等 图切割快速生成扇区的蚁群算法[J]. 计算机工程与应用, 2022, 58 (3): 297- 307
YE Zhijian, WANG Jianzhong, ZHANG Zhaoyue, et al Ant colony algorithm for fast sector generation based on diagram cutting[J]. Computer Engineering and Applications, 2022, 58 (3): 297- 307
[11]   CHEN Y, ZHANG D Dynamic airspace configuration method based on a weighted graph model[J]. Chinese Journal of Aeronautics, 2014, 27 (4): 903- 912
doi: 10.1016/j.cja.2014.06.009
[12]   CHEN Y, BI H, ZHANG D, et al Dynamic airspace sectorization via improved genetic algorithm[J]. Journal of Modern Transportation, 2014, 21 (7): 117- 124
[13]   SERGEEVA M, DELAHAYE D, MANCEL C. 3D airspace sector design by genetic algorithm [C]// International Conference on Models and Technologies for Intelligent Transportation Systems . Piscataway: IEEE, 2015: 499-506.
[14]   ZHANG W, HU M, YIN J, et al Multi-objective 3D airspace sectorization problem using NSGA-II with prior knowledge and external archive[J]. Aerospace, 2023, 10 (3): 216
doi: 10.3390/aerospace10030216
[1] Yong LI,Yue WANG,Fuqiang LIU,Baiqing SUN,Kairu LI. Multi-task allocation framework in context of caregiver-robot collaborative elderly care[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(2): 375-383.
[2] Tingfang YU,Genli ZHANG,Jiapeng ZHOU,Yicun TANG. Performance analysis and optimization of supercritical CO2 Brayton cycle coupled with organic flash cycle[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(1): 130-140.
[3] Ruoqiong LI,Yuan WENG,Xin LI. Parameter optimization of fractional-order magnetically-coupled resonant bidirectional wireless power transfer system[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(1): 141-151.
[4] Qianlin YE,Wanliang WANG,Zheng WANG. Survey of multi-objective particle swarm optimization algorithms and their applications[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(6): 1107-1120.
[5] Yan ZHAN,Jieya CHEN,Weiguang JIANG,Jiansha LU,Hongtao TANG,Xinyu SONG,Lili XU,Saimiao LIU. Multi-objective workshop material distribution method based on improved NSGA-Ⅱ[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(12): 2510-2519.
[6] Xiao-yan CAO,Min YU,Jin ZHOU,Yun-zhi WANG. Multi-objective optimization design of adjustable rotary fluid damper parameter[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(7): 1439-1449.
[7] Ting-fang YU,Ling SONG. Performance analysis and optimization of supercritical CO2 Brayton cycle waste heat recovery system[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(2): 404-414.
[8] Wan-liang WANG,Zhong-kui CHEN,Fei WU,Zheng WANG,Meng-jiao YU. Dynamic multi-objective optimization algorithm based on individual prediction[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2133-2146.
[9] Wan-liang WANG,Ya-wen JIN,Jia-cheng CHEN,Guo-qing LI,Ming-zhi HU,Jian-hang DONG. Multi-objective particle swarm optimization algorithm with multi-role and multi-strategy[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(3): 531-541.
[10] Jun-heng XU,Xiao-jun YANG,Bing LI. Design of wing mechanism with variable camber based on cross-spring flexural pivots[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(3): 444-451, 509.
[11] Qi-lin DENG,Juan LU,Yong-hui CHEN,Jian FENG,Xiao-ping LIAO,Jun-yan MA. Optimization method of CNC milling parameters based on deep reinforcement learning[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(11): 2145-2155.
[12] Jun-jie CHEN,Hong-jun LI,Zhang-hua CAO. Performance-aware resource allocation algorithm for core network control plane[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(9): 1782-1787.
[13] Xiao-zhu LI,Wei-qing WANG. Bi-level robust game optimal scheduling of regional comprehensive energy system[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(1): 177-188.
[14] Kai-jun LOU,Feng YU,Tang-dai XIA,Jian MA. Stability analysis of diaphragm wall retained structure in clay[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(9): 1697-1705.
[15] Xiang-fei MENG,Ren-guang WANG,Yuan-li XU. Torque distribution strategy of pure electric driving mode for dual planetary vehicle[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(11): 2214-2223.