Optimization of airport arrival procedures based on hybrid simulated annealing algorithm

doi:10.11772/j.issn.1001-9081.2021040586

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (2): 606-615.DOI: 10.11772/j.issn.1001-9081.2021040586

• Frontier and comprehensive applications • Previous Articles

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-21 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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

V355.1

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.

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

Figures/Tables 13

Fig. 1 Schematic diagrams of arrival procedure modeling

Fig. 2 Schematic diagram of merging structure of arrival procedures

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

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

Fig. 5 Schematic diagram of unreasonable merging modes

Tab. 1 Related parameters of simulated annealing algorithm

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

Tab. 1 Related parameters of simulated annealing algorithm

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

Tab. 2 Other user-defined parameters

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

Tab. 2 Other user-defined parameters

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

Fig. 6 Schematic diagrams of simulation results of example 1

Fig. 7 Schematic diagrams of simulation results of example 2

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

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

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

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

References 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]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[2]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[3]	ZHANG Kang, CHEN Jianping. Path planning algorithm in complex environment using self-adjusting sampling space [J]. Journal of Computer Applications, 2021, 41(4): 1207-1213.
[4]	WEI Bo, YANG Rong, SHU Sihao, WAN Yong, MIAO Jianguo. Path planning of mobile robots based on ion motion-artificial bee colony algorithm [J]. Journal of Computer Applications, 2021, 41(2): 379-383.
[5]	HUANG Shuzhao, TIAN Junwei, QIAO Lu, WANG Qin, SU Yu. Unmanned aerial vehicle path planning based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(2): 390-397.
[6]	WANG Jialiang, LI Shuhua, ZHANG Haitao. Obstacle avoidance path planning algorithm of quad-rotor helicopter based on Bayesian estimation and region division traversal [J]. Journal of Computer Applications, 2021, 41(2): 384-389.
[7]	Erchao LI, Kuankuan QI. Robot path planning based on B-spline curve and ant colony algorithm [J]. Journal of Computer Applications, 2021, 41(12): 3558-3564.
[8]	LI Wei, JIN Shijun. Optimal path convergence method based on artificial potential field method and informed sampling [J]. Journal of Computer Applications, 2021, 41(10): 2912-2918.
[9]	YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062.
[10]	LIU Sijia, TONG Xiangrong. Urban transportation path planning based on reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 185-190.
[11]	QI Xuanxuan, HUANG Jiajun, CAO Jian'an. Path planning for unmanned vehicle based on improved A^* algorithm [J]. Journal of Computer Applications, 2020, 40(7): 2021-2027.
[12]	XU Xiaoqiang, QIN Pinle, ZENG Jianchao. Orthodontic path planning based on improved particle swarm optimization algorithm [J]. Journal of Computer Applications, 2020, 40(7): 1938-1943.
[13]	HAN Yulao, FANG Dingyi. Multi-objective path planning algorithm for mobile charging devices jointing wireless charging and data collection [J]. Journal of Computer Applications, 2020, 40(6): 1745-1750.
[14]	XU Xiaoqiang, WANG Mingyong, MAO Yan. Path planning of mobile robot based on improved artificial potential field method [J]. Journal of Computer Applications, 2020, 40(12): 3508-3512.
[15]	QU Licheng, LYU Jiao, ZHAO Ming, WANG Haifei, QU Yihua. Multi-robot path planning algorithm based on 3D spatiotemporal maps and motion decomposition [J]. Journal of Computer Applications, 2020, 40(12): 3499-3507.

Optimization of airport arrival procedures based on hybrid simulated annealing algorithm

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 20

Related Articles 15

Recommended Articles

Metrics