Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2025, Vol. 59 Issue (2): 413-422    DOI: 10.3785/j.issn.1008-973X.2025.02.019
航空航天技术     
基于改进的NSGA-II算法的三维扇区自动划设
张盈斐1(),胡小兵1,周航2,*(),冯序增3
1. 中国民航大学 安全科学与工程学院，天津 300300
2. 中国民航大学 中欧航空工程师学院，天津 300300
3. 浙江大华技术股份有限公司，浙江 杭州 310053
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
 全文: PDF(1634 KB)   HTML
摘要：

针对人工划分空域扇区耗时长且难以比较不同扇区划分方案优劣的问题，提出改进的快速非支配排序遗传算法(NSGA-II）. 以均衡管制员扇区内工作负荷和减少管制员扇区间工作负荷为目标，基于网格-区域块-扇区层级提出三维扇区划分多目标优化模型. 为了提高种群的可行解数量、多样性及算法的解算速度，在NSGA-II算法中引入适应度评估算子、变概率组合交叉算子和动态变异算子. 对西安高空空域进行三维扇区自动划设的仿真模拟. 结果表明，与实际划分构型相比，优化后的方案将扇区内工作负荷均衡性提高了37%，扇区间工作负荷减少了24%；与传统的加权多目标优化算法相比，基于改进的NSGA-II算法得到的扇区划分方案可以为不同偏好的决策者提供更广泛的选择.
关键词： 空中交通管制;  三维扇区划设;  多目标优化;  改进NSGA-II算法;  选择策略    
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
收稿日期: 2023-12-27 出版日期: 2025-02-11
CLC:  V 355  
基金资助: 天津市自然科学基金多元投入青年项目（23JCQNJC00080）；中央高校基本科研业务费中国民航大学专项资助项目（3122020075）.
通讯作者: 周航     E-mail: zhangyf9507@163.com;h-zhou@cauc.edu.cn
作者简介: 张盈斐（1995—），女，博士生，从事航空安全、智能计算的研究. orcid.org/0000-0003-1629-3373. E-mail：zhangyf9507@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
张盈斐
胡小兵
周航
冯序增

引用本文:

张盈斐,胡小兵,周航,冯序增. 基于改进的NSGA-II算法的三维扇区自动划设[J]. 浙江大学学报(工学版), 2025, 59(2): 413-422.

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.

链接本文:

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

图 1  空域网格化建模的示意图
图 2  空域区域块建模的示意图
图 3  空域扇区建模的示意图
图 4  染色体结构的示意图
图 5  中心点位置变异的示意图
图 6  检查修正算子的示意图
图 7  空域扇区优化的划分流程
指标Nopts/s
最大值4280.34
最小值3077.06
平均值3578.52
标准差4.250.74
表 1  改进的NSGA-II算法的仿真结果统计
方案$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
表 3  2种方案下10个扇区的扇区间工作负荷
方案$ 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
表 2  2种方案下10个扇区的扇区内工作负荷
图 8  实际构型扇区划分的示意图
图 9  方案A扇区划分的示意图
图 10  3种算法的优化效果对比
算法RT/s
改进NSGA-II算法78.52
多目标遗传算法64.36
多目标模拟退火算法70.92
表 4  3种算法的平均运行时间统计
图 11  扇区方案选择策略的示意图
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] 李勇,王跃,柳富强,孙柏青,李恺如. 护工-机器人协作养老情境下的多任务分配框架[J]. 浙江大学学报(工学版), 2025, 59(2): 375-383.
[2] 余廷芳,张艮离,周嘉鹏,汤一村. 超临界CO2布雷顿循环耦合有机闪蒸循环的性能分析及优化[J]. 浙江大学学报(工学版), 2025, 59(1): 130-140.
[3] 李若琼,翁源,李欣. 分数阶磁耦合谐振双向无线电能传输系统参数优化[J]. 浙江大学学报(工学版), 2025, 59(1): 141-151.
[4] 叶倩琳,王万良,王铮. 多目标粒子群优化算法及其应用研究综述[J]. 浙江大学学报(工学版), 2024, 58(6): 1107-1120.
[5] 詹燕,陈洁雅,江伟光,鲁建厦,汤洪涛,宋新禹,许丽丽,刘赛淼. 基于改进NSGA-Ⅱ的多目标车间物料配送方法[J]. 浙江大学学报(工学版), 2024, 58(12): 2510-2519.
[6] 曹晓彦,于敏,周瑾,王运志. 可调旋转式流体阻尼器参数多目标优化设计[J]. 浙江大学学报(工学版), 2023, 57(7): 1439-1449.
[7] 余廷芳,宋凌. 超临界CO2布雷顿循环余热回收系统性能分析与优化[J]. 浙江大学学报(工学版), 2023, 57(2): 404-414.
[8] 王万良,陈忠馗,吴菲,王铮,俞梦娇. 基于个体预测的动态多目标优化算法[J]. 浙江大学学报(工学版), 2023, 57(11): 2133-2146.
[9] 王万良,金雅文,陈嘉诚,李国庆,胡明志,董建杭. 多角色多策略多目标粒子群优化算法[J]. 浙江大学学报(工学版), 2022, 56(3): 531-541.
[10] 徐钧恒,杨晓钧,李兵. 基于交叉簧片式铰链的变弯度机翼机构设计[J]. 浙江大学学报(工学版), 2022, 56(3): 444-451, 509.
[11] 邓齐林,鲁娟,陈勇辉,冯健,廖小平,马俊燕. 基于深度强化学习的数控铣削加工参数优化方法[J]. 浙江大学学报(工学版), 2022, 56(11): 2145-2155.
[12] 陈俊杰,李洪均,曹张华. 性能感知的核心网控制面资源分配算法[J]. 浙江大学学报(工学版), 2021, 55(9): 1782-1787.
[13] 李笑竹,王维庆. 区域综合能源系统两阶段鲁棒博弈优化调度[J]. 浙江大学学报(工学版), 2021, 55(1): 177-188.
[14] 楼恺俊,俞峰,夏唐代,马健. 黏土中地下连续墙支护结构的稳定性分析[J]. 浙江大学学报(工学版), 2020, 54(9): 1697-1705.
[15] 黄华,邓文强,李源,郭润兰. 基于空间动力学优化的机床结构件质量匹配设计[J]. 浙江大学学报(工学版), 2020, 54(10): 2009-2017.