A multiple objective optimization model for aircraft arrival and departure scheduling on multiple runways

Ming Wei; Bo Sun; Wei Wu; Binbin Jing; Ming Wei; Bo Sun; Wei Wu; Binbin Jing

doi:10.3934/mbe.2020298

Mathematical Biosciences and Engineering

2020, Volume 17, Issue 5: 5545-5560. doi: 10.3934/mbe.2020298

Previous Article Next Article

Research article Special Issues

A multiple objective optimization model for aircraft arrival and departure scheduling on multiple runways

1.
School of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, China
2.
CAAC Key Laboratory of General Aviation Operation, Civil Aviation Management Institute of China, Beijing 102202, China
3.
School of Transportation, Nantong University, Nantong 226019, China

Received: 29 May 2020 Accepted: 30 July 2020 Published: 17 August 2020

This study proposes a multi-objective mixed integer linear programming (MOMILP) model for assigning a set of flights to different runways and determining their actual arrival and departure times. The proposed model envisages unique operation model of each runway (i.e., takeoff, landing, or mixed takeoff and landing). Further, interference in two flights between adjacent runways are also fully considered in this model. The work aims at reveal the optimal relationship between traffic stream characteristics, operation mode of each runway and flight scheduling to simultaneously minimizing flight delays and maximizing runway utilization. Since the problem of interest has a non-deterministic polynomial (NP-hard) complexity, a heuristic-based non-dominated sorting genetic algorithm (NSGA-Ⅱ) is also presented to find Pareto-optimal solutions in a reasonable amount of time, where coding structure and heuristic algorithm for producing initial population are defined. Finally, a real-world example is provided to compare the difference in quality between the proposed and traditional models, and reveal changes in trends between delay time of flights and idle time of the runways, which can verify the correctness of the model.

Keywords:

arrival and departure flight scheduling,
multi-objective mixed integer linear programming,
heuristic algorithm

Citation: Ming Wei, Bo Sun, Wei Wu, Binbin Jing. A multiple objective optimization model for aircraft arrival and departure scheduling on multiple runways[J]. Mathematical Biosciences and Engineering, 2020, 17(5): 5545-5560. doi: 10.3934/mbe.2020298

Related Papers:

[1]	Ancheng Deng, Xiaoqiang Sun . Dynamic gene regulatory network reconstruction and analysis based on clinical transcriptomic data of colorectal cancer. Mathematical Biosciences and Engineering, 2020, 17(4): 3224-3239. doi: 10.3934/mbe.2020183
[2]	Qian Li, Minawaer Hujiaaihemaiti, Jie Wang, Md. Nazim Uddin, Ming-Yuan Li, Alidan Aierken, Yun Wu . Identifying key transcription factors and miRNAs coregulatory networks associated with immune infiltrations and drug interactions in idiopathic pulmonary arterial hypertension. Mathematical Biosciences and Engineering, 2023, 20(2): 4153-4177. doi: 10.3934/mbe.2023194
[3]	Jiaxin Luo, Lin Wu, Dinghui Liu, Zhaojun Xiong, Linli Wang, Xiaoxian Qian, Xiaoqiang Sun . Gene regulatory network analysis identifies key genes and regulatory mechanisms involved in acute myocardial infarction using bulk and single cell RNA-seq data. Mathematical Biosciences and Engineering, 2021, 18(6): 7774-7789. doi: 10.3934/mbe.2021386
[4]	Youlong Lv, Jie Zhang . A genetic regulatory network based method for multi-objective sequencing problem in mixed-model assembly lines. Mathematical Biosciences and Engineering, 2019, 16(3): 1228-1243. doi: 10.3934/mbe.2019059
[5]	Changxiang Huan, Jiaxin Gao . Insight into the potential pathogenesis of human osteoarthritis via single-cell RNA sequencing data on osteoblasts. Mathematical Biosciences and Engineering, 2022, 19(6): 6344-6361. doi: 10.3934/mbe.2022297
[6]	Ming-Xi Zhu, Tian-Yang Zhao, Yan Li . Insight into the mechanism of DNA methylation and miRNA-mRNA regulatory network in ischemic stroke. Mathematical Biosciences and Engineering, 2023, 20(6): 10264-10283. doi: 10.3934/mbe.2023450
[7]	Cicely K. Macnamara, Mark A. J. Chaplain . Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences and Engineering, 2017, 14(1): 249-262. doi: 10.3934/mbe.2017016
[8]	Ignacio Alvarez-Castro, Jarad Niemi . Fully Bayesian analysis of allele-specific RNA-seq data. Mathematical Biosciences and Engineering, 2019, 16(6): 7751-7770. doi: 10.3934/mbe.2019389
[9]	David Iron, Adeela Syed, Heidi Theisen, Tamas Lukacsovich, Mehrangiz Naghibi, Lawrence J. Marsh, Frederic Y. M. Wan, Qing Nie . The role of feedback in the formation of morphogen territories. Mathematical Biosciences and Engineering, 2008, 5(2): 277-298. doi: 10.3934/mbe.2008.5.277
[10]	Shengjue Xiao, Yufei Zhou, Ailin Liu, Qi Wu, Yue Hu, Jie Liu, Hong Zhu, Ting Yin, Defeng Pan . Uncovering potential novel biomarkers and immune infiltration characteristics in persistent atrial fibrillation using integrated bioinformatics analysis. Mathematical Biosciences and Engineering, 2021, 18(4): 4696-4712. doi: 10.3934/mbe.2021238

Abstract

References

[1]	B. Sun, M. Wei, W. Wu, B. B. Jing. A novel group decision making method for airport operational risk management, Math. Biosci. Eng., 17 (2020), 2402-2417.
[2]	S. L. Wu, P. C. Chen, K. Y. Chang, C. C. Huang, Robust gain-scheduled control for vertical/short take-off and landing aircraft in hovering with time-varying mass and moment of inertia, Proc. Inst. Mech. Eng. Part G., 222 (2008), 473-482.
[3]	H. Nazini, T. Sasikala, Simulating aircraft landing and takeoff scheduling in distributed framework environment using Hadoop file system, Cluster. Comput., 22 (2019), 13463-13471.
[4]	Y. Ding, J. Valasek, Aircraft landing scheduling optimization for single runway noncontrolled airports: Static Case, J. Guid. Control Dynam., 30 (2007), 252-255.
[5]	M. Ahmed, S Alam, M. Barlow, A cooperative co-evolutionary optimization model for best-fit aircraft sequence and feasible runway configuration in a multi-runway airport, Aerospace, 5 (2018), 345-353.
[6]	L. Bianco, P. Dell'Olmo, S. Giordani, Scheduling models for air trafic control in terminal areas, J. Scheduling, 9 (2006), 180-197.
[7]	D. Briskorn, R. Stolletz, A dynamic programming approach for the aircraft landing problem with aircraft classes, Eur. J. Oper. Res., 43 (2015), 61-69.
[8]	R. G. Dear, The dynamic scheduling of aircraft in the near terminal area, MIT Libraries, (1976).
[9]	H. N. Psaraftis, A dynamic programming approach for sequencing identical groups of jobs, Oper. Res., 28 (1980), 1347-1359.
[10]	V. J. Hansen, Genetic search methods in air traffic control, Comput. Oper. Res., 31 (2004), 445- 459.
[11]	H. Pinol, J. E. Beasley, Scatter search and bionomic algorithms for the aircraft landing problem, Eur. J. Oper. Res., 171 (2006), 439-462.
[12]	A. Salehipour, L. M. Naeni, H. Kazemipoor, Scheduling aircraft landings by applying a variable neighborhood descent algorithm: runway-dependent landing time case, J. Appl. Oper. Res., 1 (2009), 39-49.
[13]	Y. H. Liu, A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem, Optim. Lett., 5 (2011), 229-245.
[14]	G. Bencheikh, J. Boukachour, A. E. H. Alaoui, Improved ant colony algorithm to solve the aircraft landing problem, Int. J. Comput. Theory Eng., 3 (2011), 224-233.
[15]	A. Salehipour, M. Modarres, L. Moslemi Naeni, An efficient hybrid meta-heuristic for aircraft landing problem, Comput. Oper. Res., 40 (2013), 207-213.
[16]	A. Faye, Solving the aircraft landing problem with time discretization approach, Eur. J. Oper. Res., 242 (2015), 1028-1038.
[17]	A. T. Ernst, M. Krishnamoorthy, R. H. Storer, Heuristic and exact algorithms for scheduling aircraft landings, Networks, 34 (1999), 229-241.
[18]	J. E. Beasley, M. Krishnamoorthy, Y. M. Sharaiha, D. Abramson, Scheduling aircraft landings - The static case, Transport. Sci., 34 (2000), 180-197.
[19]	H. N. Psaraftis, A dynamic programming approach for sequencing groups of identical jobs, Oper. Res., 28 (1980), 1347-1359.
[20]	C. S. Venkatakrishnan, A. Barnett, A. M. Odoni, Landings at Logan airport: Describing and increasing airport capacity, Transport. Sci., 27 (1993), 211-227.
[21]	F. Farhadi, A. Ghoniem, M. Al-Salem, Runway capacity management - an empiricalstudy with application to Doha international airport, Transp. Res. Part E: Logist. Transp. Rev., 68 (2014), 53-63.
[22]	F. Furini, M. P. Kidd, C. A. Persiani, P. Toth, State space reduced dynamic programming for the aircraft sequencing problem with constrained position shifting, Int. Symp. Comb. Optim. (ISCO), 2014 (2014), 267-279.
[23]	A. Ghoniem, F. Farhadi, M. Reihaneh, An accelerated branch-and-price algorithm for multiple-runway aircraft sequencing problems, Eur. J. Oper. Res., 246 (2015), 34-43.
[24]	A. Ghoniem, F. Farhadi, A column generation approach for aircraft sequencing problems: A computational study, J. Oper. Res. Soc., 66 (2015), 1717-1729.
[25]	H. Balakrishnan, B. Chandran, Algorithms for scheduling runway operations under constrained position shifting, Oper. Res., 58 (2010), 1650-1665.
[26]	D. Harikiopoulo, N. Neogi, Polynomial-time feasibility condition for multiclass aircraft sequencing on a single-runway airport, IEEE Trans. Intell. Transp. Syst., 12 (2011), 2-14.
[27]	A. Lieder. R. Stolletz, Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways, Transport. Res. E-Log., 88 (2016), 67-188.
[28]	M. Samà, A. D'Ariano, F. Corman, D. Pacciarelli, Coordination of scheduling decisions in the management of airport airspace and taxiway operations. Transport. Res. Pro., 23 (2017), 246- 262.
[29]	J. Jemai M. Zekri K. Mellouli, An NSGA-II algorithm for the green vehicle routing problem, Evo. Comput. Com. Opt., 2012 (2012), 37-48.
[30]	M. Wei, T. Liu, B. Sun, B. B. Jing, Optimal integrated model for feeder transit route design and frequency-setting problem with stop selection, J. Adv. Transport., 2020 (20200.
[31]	A. Slowik, H. Kwasnicka, Nature inspired methods and their industry Applications-Swarm intelligence algorithms, IEEE T. Ind. Inform., 14 (2018), 1004-1015.
[32]	M. A. Dulebenets, A comprehensive evaluation of weak and strong mutation mechanisms in evolutionary algorithms for truck scheduling at cross-docking terminals, IEEE Access, 6 (2018).
[33]	X. Zhao, C. Wang, J. Su, J. Wang, Research and application based on the swarm intelligence algorithm and artificial intelligence for wind farm decision system, Renew. Energ., 134 (2019), 681-697.
[34]	L. Brezonik, I. Fister, V. Podgorelec, Swarm intelligence algorithms for feature selection: A review, Appl. Sci., 8 (2018), 1521.
[35]	M. A. Dulebenets, A delayed start parallel evolutionary algorithm for just-in-time truck scheduling at a cross-docking facility, Int. J. Prod. Econ., 212 (2019), 236-258.
[36]	H. Anandakumar, K. Umamaheswari, A bio-inspired swarm intelligence technique for social aware cognitive radio handovers, Comput. Electr. Eng., 71 (2018), 925-937.
[37]	T. Li, G. Kou, Y. Peng, Y. Shi, Classifying with adaptive hyper-spheres: An incremental classifier based on competitive learning, IEEE Trans. Syst. Man Cybern. Syst., 50 (2020), 1218-1229.
[38]	G. Kou, C. S. Lin, A cosine maximization method for the priority vector derivation in AHP, Eur. J. Oper. Res., 235 (2014), 225-232.

This article has been cited by:

1.	William Chad Young, Ka Yee Yeung, Adrian E Raftery, Identifying dynamical time series model parameters from equilibrium samples, with application to gene regulatory networks, 2019, 19, 1471-082X, 444, 10.1177/1471082X18776577
2.	Feng Liu, Qicheng Mei, Fenglan Sun, Xinmei Wang, Hua O Wang, 2018, Stability and Neimark-Sacker Bifurcation Analysis for Single Gene Discrete System with Delay, 978-988-15639-5-8, 961, 10.23919/ChiCC.2018.8483728
3.	Xiao Liang, William Chad Young, Ling-Hong Hung, Adrian E. Raftery, Ka Yee Yeung, Integration of Multiple Data Sources for Gene Network Inference Using Genetic Perturbation Data, 2019, 26, 1557-8666, 1113, 10.1089/cmb.2019.0036
4.	Xiao Liang, William Chad Young, Ling-Hong Hung, Adrian E. Raftery, Ka Yee Yeung, 2018, Integration of Multiple Data Sources for Gene Network Inference using Genetic Perturbation Data, 9781450357944, 601, 10.1145/3233547.3233692
5.	Sanrong Liu, Haifeng Wang, 2019, Chapter 15, 978-981-15-0120-3, 186, 10.1007/978-981-15-0121-0_15
6.	Bei Yang, Yaohui Xu, Andrew Maxwell, Wonryull Koh, Ping Gong, Chaoyang Zhang, MICRAT: a novel algorithm for inferring gene regulatory networks using time series gene expression data, 2018, 12, 1752-0509, 10.1186/s12918-018-0635-1
7.	William Chad Young, Adrian E. Raftery, Ka Yee Yeung, Model-based clustering with data correction for removing artifacts in gene expression data, 2017, 11, 1932-6157, 10.1214/17-AOAS1051
8.	Nimrita Koul, Sunilkumar S Manvi, 2020, A Perturbation based Algorithm for Inference of Gene Regulatory Networks for Multiple Myeloma, 978-1-7281-4108-4, 862, 10.1109/ICESC48915.2020.9155886
9.	Clémence Réda, Emilie Kaufmann, Andrée Delahaye-Duriez, Machine learning applications in drug development, 2020, 18, 20010370, 241, 10.1016/j.csbj.2019.12.006
10.	Chengye Zou, Xiaopeng Wei, Qiang Zhang, Changjun Zhou, Passivity of Reaction–Diffusion Genetic Regulatory Networks with Time-Varying Delays, 2018, 47, 1370-4621, 1115, 10.1007/s11063-017-9682-7
11.	Wenxia Zhou, Xuejun Li, Lu Han, Shengjun Fan, 2021, Chapter 2, 978-981-16-0752-3, 35, 10.1007/978-981-16-0753-0_2

Reader Comments

Your name:*

Email:*
© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)