基于混合模拟退火算法的机场进场程序优化

doi:10.11772/j.issn.1001-9081.2021040586

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (2): 606-615.DOI: 10.11772/j.issn.1001-9081.2021040586

基于混合模拟退火算法的机场进场程序优化

陈昇¹, 周隽¹^,²(), 胡小兵²^,³, 马霁¹^,²

^1.中国民航大学中欧航空工程师学院, 天津 300300
^2.中国民航大学中法联合空管应用数学研究中心, 天津 300300
^3.中国民航大学电子信息与自动化学院, 天津 300300

收稿日期:2021-04-15 修回日期:2021-06-15 接受日期:2021-06-17 发布日期:2022-02-11 出版日期:2022-02-10
通讯作者: 周隽
作者简介:陈昇（1996—），男，福建莆田人，硕士研究生，主要研究方向：路径规划、启发式算法；
周隽（1988—），女，吉林长春人，讲师，博士，主要研究方向：路径规划、组合优化；
胡小兵（1975—），男，四川攀枝花人，教授，博士，主要研究方向：多目标优化、智能优化算法；
马霁（1992—），女，云南昆明人，讲师，博士，主要研究方向：机场场面运行优化。
基金资助:
中国民航大学科研启动基金资助项目(2017QD02S);中国民航大学中央高校基本业务费资助项目(3122019179)

Optimization of airport arrival procedures based on hybrid simulated annealing algorithm

Sheng CHEN¹, Jun ZHOU¹^,²(), Xiaobing HU²^,³, Ji MA¹^,²

^1.Sino-European Institute of Aviation Engineering，Civil Aviation University of China，Tianjin 300300，China
^2.China-France Joint Research Center of Applied Mathematics for Air Traffic Management，Civil Aviation University of China，Tianjin 300300，China
^3.College of Electronic Information and Automation，Civil Aviation University of China，Tianjin 300300，China

Received:2021-04-15 Revised:2021-06-15 Accepted:2021-06-17 Online:2022-02-11 Published:2022-02-10
Contact: Jun ZHOU
About author:CHEN Sheng， born in 1996， M. S. candidate. His research interests include path planning， heuristic algorithm.
ZHOU Jun， born in 1988， Ph. D.， lecturer. Her research interests include path planning， combinatorial optimization.
HU Xiaobing， born in 1975， Ph. D.， professor. His research interests include multi-objective optimization， intelligent optimization algorithm.
MA Ji， born in 1992， Ph. D.， lecturer. Her research interests include airport surface operation optimization.
Supported by:
Scientific Research Staring Foundation of Civil Aviation University of China(2017QD02S);CAUC Project of Fundamental Research Funds for the Central Universities(3122019179)

摘要/Abstract

摘要：

针对人工设计机场进场程序耗时较长且很难定量优化路径长度的问题，提出多条进场程序的三维自动优化设计方法。首先，根据区域导航规范（RNAV）对进场程序的几何构型及汇聚结构进行建模；然后，综合考虑机场布局以及障碍物规避、航路间隔等航空器运行约束，以最小化进场程序总长度为目标，建立了完整的数学模型；最后，开发了基于模拟退火算法和改进A^*算法的混合算法，以对进场程序的汇聚结构进行自动优化设计。仿真结果表明，在基于瑞典阿兰达（Arlanda）机场的实验中，与现有相关的整数规划方法相比，混合模拟退火算法规划出的路径长度缩短了3%，且计算耗时减少了87%；在基于上海浦东机场的实验中，与实际进场程序相比，所提算法规划出的路径长度缩短了6.6%。从这些结果可以看出，该算法能够有效设计多条三维进场程序，可以为程序设计人员提供初步决策支持。

关键词: 航空运输, 路径规划, 进场程序, 模拟退火算法, A^*算法

Abstract:

Concerning the problem that the manual design of airport arrival procedures is time consuming and it is difficult to optimize the path length quantitatively， a three-dimensional automatic optimization design method of multiple arrival procedures was proposed. Firstly， based on the specifications of RNAV （Rules for implementation of area NAVigation）， the geometric configuration and the merging structure of the arrival procedures were modeled. Then， considering airport layout and aircraft operation constraints such as obstacle avoidance and route separation， with the goal of minimizing the total length of arrival procedures， a complete mathematical model was established. Finally， a hybrid algorithm based on simulated annealing algorithm and improved A^* algorithm was developed to automatically optimize the merging structure of arrival procedures. Simulation results show that， in the experiment based on Sweden Arlanda Airport， compared with the existing related integer programming method， the hybrid simulated annealing algorithm can shorten the total path length by 3% and reduce the computing time by 87%. In the experiment based on Shanghai Pudong Airport， compared with the actual arrival procedures， the length of the routes designed by the proposed algorithm is reduced by 6.6%. These results indicate that the proposed algorithm can effectively design multiple three-dimensional arrival procedures， and can provide preliminary decision support for the procedure designers.

Key words: air transport, path planning, arrival procedure, simulated annealing algorithm, A^* algorithm

中图分类号:

V355.1

陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 计算机应用, 2022, 42(2): 606-615.

Sheng CHEN, Jun ZHOU, Xiaobing HU, Ji MA. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm[J]. Journal of Computer Applications, 2022, 42(2): 606-615.

图/表 13

图1 进场程序建模示意图

Fig. 1 Schematic diagrams of arrival procedure modeling

图2 进场程序汇聚结构示意图

Fig. 2 Schematic diagram of merging structure of arrival procedures

图3 进场点、汇聚点编号示意图

Fig. 3 Schematic diagram of arrival points and merging points numbering

图4 汇聚点位置的取值范围示意图

Fig. 4 Schematic diagram of value range for locations of merging points

图5 不合理的汇聚方式的示意图

Fig. 5 Schematic diagram of unreasonable merging modes

表1 模拟退火算法的相关参数

Tab. 1 Related parameters of simulated annealing algorithm

参数	值
初始温度 $T 0$	100
终止温度 $T f$	0.1
温度衰减系数 $β$	0.95
每个温度迭代次数K	100
汇聚决策检测概率 $P 0$	0.5

表1 模拟退火算法的相关参数

Tab. 1 Related parameters of simulated annealing algorithm

参数	值
初始温度 $T 0$	100
终止温度 $T f$	0.1
温度衰减系数 $β$	0.95
每个温度迭代次数K	100
汇聚决策检测概率 $P 0$	0.5

表2 其他用户设置参数

Tab. 2 Other user-defined parameters

参数	值
最小水平安全距离 $δ H$	3 n mile
最小竖直安全距离 $δ V$	1 000 ft
最大航向角改变量 $θ m a x$	45°
弧弦比阈值 $ε 1$	1.5
航向角改变量的绝对值之和阈值 $ε 2$	180

表2 其他用户设置参数

Tab. 2 Other user-defined parameters

参数	值
最小水平安全距离 $δ H$	3 n mile
最小竖直安全距离 $δ V$	1 000 ft
最大航向角改变量 $θ m a x$	45°
弧弦比阈值 $ε 1$	1.5
航向角改变量的绝对值之和阈值 $ε 2$	180

图6 算例1仿真结果的示意图

Fig. 6 Schematic diagrams of simulation results of example 1

图7 算例2仿真结果的示意图

Fig. 7 Schematic diagrams of simulation results of example 2

图8 上海浦东机场的仿真结果示意图

Fig. 8 Schematic diagrams of simulation results of Shanghai Pudong Airport

表3 算例1的10次仿真结果统计

Tab. 3 Result statistics of 10 simulations of example 1

指标	目标函数值/n mile	仿真时间/s
最小值	277.02	127.24
最大值	278.94	177.89
平均值	277.37	155.29
标准差	0.57	14.35

表4 算例2的10次仿真结果统计

Tab. 4 Result statistics of 10 simulations of example 2

指标	目标函数值/n mile	仿真时间/s
最小值	280.26	1 185.13
最大值	283.85	1 422.32
平均值	281.11	1 291.34
标准差	1.33	88.30

表5 上海浦东机场的10次仿真结果统计

Tab. 5 Result statistics of 10 simulations of Shanghai Pudong Airport

指标	目标函数值/n mile	仿真时间/s
最小值	392.35	1 761.25
最大值	403.82	2 035.36
平均值	396.08	1 898.32
标准差	3.55	78.70

参考文献 20

1	United States Standard for Performance Based Navigation （PBN） instrument procedure design： 8260.58B［S］. Washington， DC： Federal Aviation Administration， 2020： 4-1-. 10.1016/j.echo.2005.10.005
	4-19. 10.1016/j.echo.2005.10.005
2	刘崇军，王岁文.飞行程序设计转弯区外边界画法比较［J］.航空计算技术， 2015， 45（6）： 113-116. 10.3969/j.issn.1671-654X.2015.06.028
	LIU C J， WANG S W. Drawing method of turn outer boundary［J］. Aeronautical Computing Technique， 2015， 45（6）： 113-116. 10.3969/j.issn.1671-654X.2015.06.028
3	陈忠会.传统飞行程序辅助设计算法研究［D］.天津：中国民航大学， 2017： 50-56. 10.5176/2301-394x_ace17.47
	CHEN Z H. Research on aided design algorithm of traditional flight procedure［D］. Tianjin： Civil Aviation University of China， 2017： 50-56. 10.5176/2301-394x_ace17.47
4	MAC T T， COPOT C， TRAN D T， et al. Heuristic approaches in robot path planning： a survey［J］. Robotics and Autonomous Systems， 2016， 86： 13-28. 10.1016/j.robot.2016.08.001
5	杨俊成，李淑霞，蔡增玉.路径规划算法的研究与发展［J］.控制工程， 2017， 24（7）： 1473-1480. 10.14107/j.cnki.kzgc.160032
	YANG J C， LI S X， CAI Z Y. Research and development of path planning algorithm［J］. Control Engineering of China， 2017， 24（7）： 1473-1480. 10.14107/j.cnki.kzgc.160032
6	PIERRE S， DELAHAYE D， CAFIERI S. Aircraft trajectory planning with dynamical obstacles by artificial evolution and convex hull generations［M］// Electronic Navigation Research Institute. Air Traffic Management and Systems II： Selected Papers of the 4th ENRI International Workshop， 2015， LNEE 420. Tokyo： Springer， 2017： 49-67.
7	柏硌，赵刚要.基于MapReduce与蚁群优化的航路规划算法［J］.计算机工程， 2015， 41（5）： 38-44， 55. 10.3969/j.issn.1000-3428.2015.05.007
	BO L， ZHAO G Y. Route planning algorithm based on MapReduce and ant colony optimization［J］. Computer Engineering， 2015， 41（5）： 38-44， 55. 10.3969/j.issn.1000-3428.2015.05.007
8	李楠，张建华.基于改进遗传算法的无人机航路规划［J］.计算机仿真， 2016， 33（4）： 91-94， 170. 10.3969/j.issn.1006-9348.2016.04.021
	LI N， ZHANG J H. Path planning for unmanned aerial vehicles based on improved genetic algorithm［J］. Computer Simulation， 2016， 33（4）： 91-94， 170. 10.3969/j.issn.1006-9348.2016.04.021
9	冯国强，赵晓林，高关根，等.基于A^*蚁群算法的无人机航路规划［J］.飞行力学， 2018， 36（5）： 49-52， 57. 10.13645/j.cnki.f.d.20180614.001
	FENG G Q， ZHAO X L， GAO G G， et al. Path planning of UAVs using A^* ant colony algorithm［J］. Flight Dynamics， 2018， 36（5）： 49-52， 57. 10.13645/j.cnki.f.d.20180614.001
10	李楠，刘朋，邓人博，等.基于改进遗传算法的无人机三维航路规划［J］.计算机仿真， 2017， 34（12）： 22-25， 35. 10.3969/j.issn.1006-9348.2017.12.006
	LI N， LIU P， DENG R B， et al. Three dimensional path planning for unmanned aerial vehicles based on improved genetic algorithm［J］. Computer Simulation， 2017， 34（12）： 22-25， 35. 10.3969/j.issn.1006-9348.2017.12.006
11	ZHOU J， CAFIERI S， DELAHAYE D， et al. Optimizing the design of a route in terminal maneuvering area using branch and bound［M］// Electronic Navigation Research Institute： Selected Papers of the 4th ENRI International Workshop， 2015， LNEE 420. Tokyo： Springer， 2017： 171-184.
12	黄书召，田军委，乔路，等.基于改进遗传算法的无人机路径规划［J］.计算机应用， 2021， 41（2）： 390-397.
	HUANG S Z， TIAN J W， QIAO L， et al. Unmanned aerial vehicle path planning based on improved genetic algorithm［J］. Journal of Computer Applications， 2021， 41（2）： 390-397.
13	PFEIL D M. Optimization of airport terminal-area air traffic operations under uncertain weather conditions［D］. Cambridge： Massachusetts Institute of Technology， 2011： 115-137.
14	ZHOU J， CAFIERI S， DELAHAYE D， et al. Optimization-based design of departure and arrival routes in terminal maneuvering area［J］. Journal of Guidance， Control， and Dynamics， 2017， 40（11）： 2889-2904. 10.2514/1.g002728
15	晁绵博，赵向领，李鹏程，等.终端区点融合进近程序设计方法研究［J］.航空计算技术， 2016， 46（2）： 10-14， 18. 10.3969/j.issn.1671-654X.2016.02.003
	CHAO M B， ZHAO X L， LI P C， et al. Research on point merge approach procedure design in terminal area［J］. Aeronautical Computing Technique， 2016， 46（2）： 10-14， 18. 10.3969/j.issn.1671-654X.2016.02.003
16	赵向领，雷碧玉.点汇聚进近飞行程序近地风险评估方法研究［J］.中国安全科学学报， 2017， 27（3）： 157-162.
	ZHAO X L， LEI B Y. Research on method for assessing risk in ground approach under point merging procedure［J］. China Safety Science Journal， 2017， 27（3）： 157-162.
17	王超，郑旭芳，王蕾.交汇航路空中交通流的非线性特征研究［J］.西南交通大学学报， 2017， 52（1）： 171-178. 10.3969/j.issn.0258-2724.2017.01.024
	WANG C， ZHENG X F， WANG L. Research on nonlinear characteristics of air traffic flows on converging air routes［J］. Journal of Southwest Jiaotong University， 2017， 52（1）： 171-178. 10.3969/j.issn.0258-2724.2017.01.024
18	CHOI S， MULFINGER D G， ROBINSON J E， III， et al. Design of an optimal route structure using heuristics-based stochastic schedulers［J］. Journal of Aircraft， 2015， 52（3）： 764-777. 10.2514/1.c032645
19	GRANBERG T A， POLISHCHUK T， POLISHCHUK V， et al. Automatic design of aircraft arrival routes with limited turning angle ［C］// Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling， Optimization， and Systems. Wadern： Schloss Dagstuhl — Leibniz-Zentrum für Informatik， 2016： No.9.
20	CHEVALIER J， DELAHAYE D， SBIHI M， et al. Departure and arrival routes optimization near large airports［J］. Aerospace， 2019， 6（7）： No.80. 10.3390/aerospace6070080

[1]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[2]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[3]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[4]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[5]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[6]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[7]	邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860.
[8]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[9]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.
[10]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[11]	王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3816-3823.
[12]	刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296.
[13]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[14]	李智, 薛建彬. C‑V2X车联网中基于模拟退火算法的任务卸载与资源分配[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3140-3147.
[15]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.

基于混合模拟退火算法的机场进场程序优化

Optimization of airport arrival procedures based on hybrid simulated annealing algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 20

相关文章 15

编辑推荐

Metrics