| Citation: | FENG X R，GAO Z D，WANG J，et al. Research on aircraft landing scheduling problem based on compact subsequence[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（8）：2421-2431 （in Chinese） doi: 10.13700/j.bh.1001-5965.2022.0656
|
The aircraft landing scheduling problem has been proven to be an NP-hard problem. A multi-aircraft optimization model with time window constraints is established for the fixed aircraft scheduling sequence considering more practical situations. The concept of compact subsequence, its properties, left shift, division and merging conditions are discussed. A compact subsequence algorithm (CSA) for fixed-order aircraft landing problems is proposed. Sort by the optimal landing time of the aircraft and calculate the landing time of each aircraft in this order using CSA. Adjust the fixed order using the circular linear exchange and cyclic linear interpolation strategies. Then, compute iteratively to get an approximation of the model’s ideal solution. The OR-Library dataset is used for verification. Comparable to the CPLEX, RH-HPSO-LS, and cellular automation-based optimization (CAO), the results demonstrate that CSA, when paired with a heuristic fine-tuning method, can yield much superior outcomes than DALP and bionomic algorithm (BA). The algorithm also shows better advantages in time efficiency. It is extremely obvious that the advantages of computing precision and speed on small-scale datasets. CSA is a deterministic method that does not depend on prior parameters and has higher robustness, it can ensure that the heuristic fine-tuning strategy approaches the optimal solution continuously.
| [1] |
民航局运行监控中心. 图解2021年民航航班运行情况[EB/OL]. (2022-01-12) [2022-04-21]. https://m.thepaper.cn/baijiahao_16254749.
Operation Monitoring Center of Civil Aviation Administration. Illustrating the operation of civil aviation flights in 2021[EB/OL]. (2022-01-12) [2022-04-21]. https://m.thepaper.cn/baijiahao_16254749 (in Chinese).
|
| [2] |
CIRIUM. The on-time performance review 2021[EB/OL]. (2021-12-31) [2022-04-21]. https://www.cirium.com/studios/on-time-performance.
|
| [3] |
BEASLEY J E, KRISHNAMOORTHY M, SHARAIHA Y M, et al. Scheduling aircraft landings: The static case[J]. Transportation Science, 2000, 34(2): 180-197. doi: 10.1287/trsc.34.2.180.12302
|
| [4] |
BEASLEY J E, KRISHNAMOORTHY M, SHARAIHA Y M, et al. Displacement problem and dynamically scheduling aircraft landings[J]. Journal of the Operational Research Society, 2004, 55(1): 54-64. doi: 10.1057/palgrave.jors.2601650
|
| [5] |
PINOL H, BEASLEY J E. Scatter search and bionomic algorithms for the aircraft landing problem[J]. European Journal of Operational Research, 2006, 171(2): 439-462. doi: 10.1016/j.ejor.2004.09.040
|
| [6] |
HU X B, CHEN W H. Genetic algorithm based on receding horizon control for arrival sequencing and scheduling[J]. Engineering Applications of Artificial Intelligence, 2005, 18(5): 633-642. doi: 10.1016/j.engappai.2004.11.012
|
| [7] |
HU X B, CHEN W H. Receding horizon control for aircraft arrival sequencing and scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2005, 6(2): 189-197. doi: 10.1109/TITS.2005.848365
|
| [8] |
ZHAN Z H, ZHANG J, LI Y, et al. An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11(2): 399-412. doi: 10.1109/TITS.2010.2044793
|
| [9] |
YU S P, CAO X B, ZHANG J. A real-time schedule method for aircraft landing scheduling problem based on cellular automation[J]. Applied Soft Computing, 2011, 11(4): 3485-3493. doi: 10.1016/j.asoc.2011.01.022
|
| [10] |
VADLAMANI S, HOSSEINI S. A novel heuristic approach for solving aircraft landing problem with single runway[J]. Journal of Air Transport Management, 2014, 40: 144-148. doi: 10.1016/j.jairtraman.2014.06.009
|
| [11] |
王满超. 动态飞机着陆调度及其经验粒子群算法研究[D]. 天津: 中国民航大学, 2015: 4-5.
WANG M C. Research on experiential particle swarm optimization for dynamic aircraft landing scheduling[D]. Tianjin: Civil Aviation University of China, 2015: 4-5(in Chinese).
|
| [12] |
SABAR N R, KENDALL G. An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem[J]. Omega, 2015, 56: 88-98.
|
| [13] |
GIRISH B S. An efficient hybrid particle swarm optimization algorithm in a rolling horizon framework for the aircraft landing problem[J]. Applied Soft Computing, 2016, 44: 200-221. doi: 10.1016/j.asoc.2016.04.011
|
| [14] |
BENNELL J A, MESGARPOUR M, POTTS C N. Dynamic scheduling of aircraft landings[J]. European Journal of Operational Research, 2017, 258(1): 315-327. doi: 10.1016/j.ejor.2016.08.015
|
| [15] |
JI X P, CAO X B, DU W B, et al. An evolutionary approach for dynamic single-runway arrival sequencing and scheduling problem[J]. Soft Computing, 2017, 21(23): 7021-7037. doi: 10.1007/s00500-016-2241-8
|
| [16] |
FAYE A. A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes[J]. European Journal of Operational Research, 2018, 270(3): 1148-1157. doi: 10.1016/j.ejor.2018.04.021
|
| [17] |
AHMED M, ALAM S, BARLOW M. A cooperative co-evolutionary optimisation model for best-fit aircraft sequence and feasible runway configuration in a multi-runway airport[J]. Aerospace, 2018, 5(3): 85. doi: 10.3390/aerospace5030085
|
| [18] |
IKLI S, MANCEL C, MONGEAU M, et al. An optimistic planning approach for the aircraft landing problem[C]//Proceedings of the ENRI International Workshop on ATM/CNS. Berlin: Springer, 2021: 173-188.
|
| [19] |
BALAKRISHNAN H, CHANDRAN B G. Algorithms for scheduling runway operations under constrained position shifting[J]. Operations Research, 2010, 58(6): 1650-1665. doi: 10.1287/opre.1100.0869
|
| [20] |
XU B. An efficient ant colony algorithm based on wake-vortex modeling method for aircraft scheduling problem[J]. Journal of Computational and Applied Mathematics, 2017, 317: 157-170. doi: 10.1016/j.cam.2016.11.043
|
| [21] |
DEAR R G, SHERIF Y S. An algorithm for computer assisted sequencing and scheduling of terminal area operations[J]. Transportation Research Part A: General, 1991, 25(2-3): 129-139. doi: 10.1016/0191-2607(91)90132-A
|
Figures(7) / Tables(7)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
