Aircraft route recovery based on distributed integer programming method

Luyao Yang; Zhikang Wang; Haochen Yu; Baoping Jiang; Zhengtian Wu; Luyao Yang; Zhikang Wang; Haochen Yu; Baoping Jiang; Zhengtian Wu

doi:10.3934/mbe.2023571

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 7: 12802-12819. doi: 10.3934/mbe.2023571

Previous Article Next Article

Research article Special Issues

Aircraft route recovery based on distributed integer programming method

School of Electronic and Information Engineering, Suzhou University of Science and Technology, Suzhou, China

Academic Editor: Xiaodi Li

Received: 01 April 2023 Revised: 11 May 2023 Accepted: 15 May 2023 Published: 31 May 2023

In order to further promote the application and development of unmanned aviation in the manned field, and reduce the difficulty that airlines cannot avoid due to unexpected factors such as bad weather, aircraft failure, and so on, the problem of restoring aircraft routes has been studied. To reduce the economic losses caused by flight interruption, this paper divides the repair problem of aircraft operation plans into two sub problems, namely, the generation of flight routes and the reallocation of aircraft. Firstly, the existing fixed-point iteration method proposed by Dang is used to solve the feasible route generation model based on integer programming. To calculate quickly and efficiently, a segmentation method that divides the solution space into mutually independent segments is proposed as the premise of distributed computing. The feasible route is then allocated to the available aircraft to repair the flight plan. The experimental results of two examples of aircraft fault grounding and airport closure show that the method proposed in this paper is effective for aircraft route restoration.
- flight interruption,
- fixed-point iteration,
- integer programming,
- distributed computing
Citation: Luyao Yang, Zhikang Wang, Haochen Yu, Baoping Jiang, Zhengtian Wu. Aircraft route recovery based on distributed integer programming method[J]. Mathematical Biosciences and Engineering, 2023, 20(7): 12802-12819. doi: 10.3934/mbe.2023571

Related Papers:

Abstract

In order to further promote the application and development of unmanned aviation in the manned field, and reduce the difficulty that airlines cannot avoid due to unexpected factors such as bad weather, aircraft failure, and so on, the problem of restoring aircraft routes has been studied. To reduce the economic losses caused by flight interruption, this paper divides the repair problem of aircraft operation plans into two sub problems, namely, the generation of flight routes and the reallocation of aircraft. Firstly, the existing fixed-point iteration method proposed by Dang is used to solve the feasible route generation model based on integer programming. To calculate quickly and efficiently, a segmentation method that divides the solution space into mutually independent segments is proposed as the premise of distributed computing. The feasible route is then allocated to the available aircraft to repair the flight plan. The experimental results of two examples of aircraft fault grounding and airport closure show that the method proposed in this paper is effective for aircraft route restoration.

References

[1]	J. Clausen, A. Larsen, J. Larsen, N. J. Rezanova, Disruption management in the airline industry—Concepts, models and methods, Comput. Oper. Res., 37 (2010), 809–821. https://doi.org/10.1016/j.cor.2009.03.027 doi: 10.1016/j.cor.2009.03.027
[2]	B. Jiang, Z. Wu, H. R. Karimi, A distributed dynamic event-triggered mechanism to HMM-based observer design for H∞ sliding mode control of Markov jump systems, Automatic, 142 (2022), 110357. https://doi.org/10.1016/j.automatica.2022.110357 doi: 10.1016/j.automatica.2022.110357
[3]	T. K. Liu, C. R. Jeng, Y. H. Chang, Disruption management of an inequality-based multi-fleet airline schedule by a multi-objective genetic algorithm, Transp. Plann. Technol., 31 (2008), 613–639. https://doi.org/10.1080/03081060802492652 doi: 10.1080/03081060802492652
[4]	Z. Wu, B. Jiang, H. R. Karimi, A logarithmic descent direction algorithm for the quadratic knapsack problem, Appl. Math. Comput., 369 (2020), 124854. https://doi.org/10.1016/j.amc.2019.124854 doi: 10.1016/j.amc.2019.124854
[5]	D. Teodorović, S. Guberinić, Optimal dispatching strategy on an airline network after a schedule perturbation, Eur. J. Oper. Res., 15(1984), 178–182. https://doi.org/10.1016/0377-2217(84)90207-8 doi: 10.1016/0377-2217(84)90207-8
[6]	A. I. Jarrah, G. Yu, N. Krishnamurthy, A. Rakshit, A decision support framework for airline flight cancellations and delays, Transp. Sci., 27 (1993), 266–280. https://doi.org/10.1287/trsc.27.3.266 doi: 10.1287/trsc.27.3.266
[7]	J. M. Cao, A. Kanafani, Real‐time decision support for integration of airline flight cancellations and delays part Ⅰ: mathematical formulation, Transp. Plann. Technol., 20 (1997), 183–199. https://doi.org/10.1080/03081069708717588 doi: 10.1080/03081069708717588
[8]	T. Zhou, J. Lu, W. Zhang, P. He, B. Niu, Irregular flight timetable recovery under covid-19: An approach based on genetic algorithm, in Data Mining and Big Data: 6th International Conference, (2021), 240–249. https://doi.org/10.1007/978-981-16-7476-1_22
[9]	S. Wang, F. Xu, W. Yang, Z. Ma, Application of greedy random adaptive search algorithm (GRASP) in flight recovery problem, Int. J. Adv. Network Monit. Controls, 3 (2018), 39–44. https://doi.org/10.21307/ijanmc-2018-008 doi: 10.21307/ijanmc-2018-008
[10]	H. Lin, Z. Wang, Fast variable neighborhood search for flight rescheduling after airport closure, IEEE Access, 6 (2018), 50901–50909. https://doi.org/10.1109/ACCESS.2018.2869842 doi: 10.1109/ACCESS.2018.2869842
[11]	N. Kenan, A. Jebali, A. Diabat, The integrated aircraft routing problem with optional flights and delay considerations, Transp. Res. Part E, 118 (2018), 355–375. https://doi.org/10.1016/j.tre.2018.08.002 doi: 10.1016/j.tre.2018.08.002
[12]	H. Lin, Z. Wang, Flight scheduling for airport closure based on sequential decision, in 2018 4th International Conference on Information Management (ICIM), (2018), 241–245. https://doi.org/10.1109/INFOMAN.2018.8392843
[13]	D. Teodorović, G. Stojković, Model for operational daily airline scheduling, Transp. Plann. Technol., 14 (1990), 273–285. https://doi.org/10.1080/03081069008717431 doi: 10.1080/03081069008717431
[14]	D. Teodorović, G. Stojković, Model to reduce airline schedule disturbances, J. Transp. Eng., 121 (1995), 324–331. https://doi.org/10.1061/(ASCE)0733-947X(1995)121:4(324) doi: 10.1061/(ASCE)0733-947X(1995)121:4(324)
[15]	Z. Wu, H. R. Karimi, C. Dang, An approximation algorithm for graph partitioning via deterministic annealing neural network, Neural Networks, 117 (2019), 191–200. https://doi.org/10.1016/j.neunet.2019.05.010 doi: 10.1016/j.neunet.2019.05.010
[16]	Z. Wu, Q. Gao, B. Jiang, H. R. Karimi, Solving the production transportation problem via a deterministic annealing neural network method, Appl. Math. Comput., 411 (2021), 126518. https://doi.org/10.1016/j.amc.2021.126518 doi: 10.1016/j.amc.2021.126518
[17]	Z. Wu, H. R. Karimi, C. Dang, A deterministic annealing neural network algorithm for the minimum concave cost transportation problem, IEEE Trans. Neural Networks Learn. Syst., 31 (2019), 4354–4366. https://doi.org/10.1109/TNNLS.2019.2955137 doi: 10.1109/TNNLS.2019.2955137
[18]	L. B. Fogaça, E. Henriqson, G. C. Junior, F. Lando, Airline disruption management: A naturalistic decision-making perspective in an operational control centre, J. Cognit. Eng. Decis. Making, 16 (2022), 3–28. https://doi.org/10.1177/15553434211061024 doi: 10.1177/15553434211061024
[19]	J. Lee, L. Marla, P. Vaishnav, The impact of climate change on the recoverability of airline networks, Transp. Res. Part D, 95 (2021), 102801. https://doi.org/10.1016/j.trd.2021.102801 doi: 10.1016/j.trd.2021.102801
[20]	S. Bouarfa, J. Müller, H. Blom, Evaluation of a multi-agent system approach to airline disruption management, J. Air Transp. Manage., 71 (2018), 108–118. https://doi.org/10.1016/j.jairtraman.2018.05.009 doi: 10.1016/j.jairtraman.2018.05.009
[21]	M. F. Argüello, J. F. Bard, G. Yu, A GRASP for aircraft routing in response to groundings and delays, J. Comb. Optim., 1 (1997), 211–228. https://doi.org/10.1023/A:1009772208981 doi: 10.1023/A:1009772208981
[22]	Z. Wu, B. Li, C. Dang, F. Hu, Q. Zhu, B. Fu, Solving long haul airline disruption problem caused by groundings using a distributed fixed-point computational approach to integer programming, Neurocomputing, 269 (2017), 232–255. https://doi.org/10.1016/j.neucom.2017.02.091 doi: 10.1016/j.neucom.2017.02.091
[23]	C. Dang, An increasing-mapping approach to integer programming based on lexicographic ordering and linear programming, in The Ninth International Symposium on Operations Research and Its Applications. Lecture Notes in Operations Research, 12 (2010), 55–60. https://doi.org/10.1201/b17196-11
[24]	C. Dang, Y. Ye, A fixed point iterative approach to integer programming and its distributed computation, Fixed Point Theory Appl., 1 (2015), 1–15. https://doi.org/10.1186/s13663-015-0429-8 doi: 10.1186/s13663-015-0429-8

Reader Comments

Your name:*

Email:*
© 2023 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)