An integrated optimization mode for multi-type aircraft flight scheduling and routing problem

Ming Wei; Ligang Zhao; Zhijian Ye; Binbin Jing; Ming Wei; Ligang Zhao; Zhijian Ye; Binbin Jing

doi:10.3934/mbe.2020270

Mathematical Biosciences and Engineering

2020, Volume 17, Issue 5: 4990-5004. doi: 10.3934/mbe.2020270

Previous Article Next Article

Research article Special Issues

An integrated optimization mode for multi-type aircraft flight scheduling and routing problem

1.
School of Air traffic Management, Civil Aviation University of China, Tianjin 300300, China
2.
School of civil aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210000, China
3.
School of transportation, Nantong University, Nantong 226019, China
4.
Air traffic management center, Civil aviation administration, Beijing 100000, China

Received: 08 May 2020 Accepted: 10 July 2020 Published: 17 July 2020

This paper proposes an optimization model for the integrated aircraft flight scheduling and routing problem, which allows a simultaneous determination of the departure time of each flight trip and assignment of a set of aircraft located at different airports to perform all flight trips. The proposed model envisages that each flight trip is covered by its own particular aircraft type or a larger airplane. Further, departure and arrival times of each flight trip are within a flexible time window in its aircraft's route and origin/destination airports, and the number of airplanes firstly distributed in the base airports is fully accounted for in the model. The model not only can effectively minimize weighted operation costs for the number of airplanes and the total idle time for adjacent flight trips covered by an aircraft, but also can maximize the number of transported passengers. This paper further presents a two-stage heuristic approach based on the ant colony optimization algorithm, which efficiently finds the most acceptable solutions. The above algorithm is used to generate a series of aircraft routes, and a polynomial algorithm is designed to obtain their feasible flight trip timetable. Finally, the model is applied to a case study to design the integrated aircraft flight scheduling and routing plan for a real airline in China. A comparative analysis of the conventional and proposed models proved the latter's feasibility.
- flight scheduling,
- aircraft routing,
- multiple-aircraft type,
- multi-objective,
- heuristic algorithm
Citation: Ming Wei, Ligang Zhao, Zhijian Ye, Binbin Jing. An integrated optimization mode for multi-type aircraft flight scheduling and routing problem[J]. Mathematical Biosciences and Engineering, 2020, 17(5): 4990-5004. doi: 10.3934/mbe.2020270

Related Papers:

Abstract

This paper proposes an optimization model for the integrated aircraft flight scheduling and routing problem, which allows a simultaneous determination of the departure time of each flight trip and assignment of a set of aircraft located at different airports to perform all flight trips. The proposed model envisages that each flight trip is covered by its own particular aircraft type or a larger airplane. Further, departure and arrival times of each flight trip are within a flexible time window in its aircraft's route and origin/destination airports, and the number of airplanes firstly distributed in the base airports is fully accounted for in the model. The model not only can effectively minimize weighted operation costs for the number of airplanes and the total idle time for adjacent flight trips covered by an aircraft, but also can maximize the number of transported passengers. This paper further presents a two-stage heuristic approach based on the ant colony optimization algorithm, which efficiently finds the most acceptable solutions. The above algorithm is used to generate a series of aircraft routes, and a polynomial algorithm is designed to obtain their feasible flight trip timetable. Finally, the model is applied to a case study to design the integrated aircraft flight scheduling and routing plan for a real airline in China. A comparative analysis of the conventional and proposed models proved the latter's feasibility.

References

[1]	B. Sun, M. Wei, W. Wu, B. B. Jin, A novel group decision making method for airport operational risk management, Math. Biosci. Eng., 17 (2020), 2402-2417.
[2]	M. Liu, B. Liang, F. Zheng, F. Chu, Stochastic airline fleet assignment with risk aversion, IEEE Trans. Intell. Transp. Syst., 20 (2019), 3081-3090.
[3]	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.
[4]	Z. Liang, W. A. Chaovalitwongse, A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem, Transp. Sci., 47 (2012), 493-507.
[5]	P. Munari, A. Alvarez, Aircraft routing for on-demand air transportation with service upgrade and maintenance events: Compact model and case study, J. Air Transp. Manage., 75 (2019), 75-84.
[6]	S. Iknmeis, S. Das, An objective model for collaborative flight scheduling in a single mega-hub network, Transp. Plann. Technol., 43 (2020), 1-19.
[7]	A. E. E. Eltoukhy, F. T. S. Chan, S. H. Chung, Airline schedule planning: A review and future directions, Ind. Manage. Data Syst., 117 (2017), 1201-1243.
[8]	S. Vadlamani, S. Hosseini, A novel heuristic approach for solving aircraft landing problem with single runway, J. Air Transp. Manage., 40 (2014), 144-148.
[9]	N. Kenan, A. Jebali, A. Diabat, An integrated flight scheduling and fleet assignment problem under uncertainty, Comput. Oper. Res., 100 (2018), 333-342.
[10]	L. Cadarso, R. de Celis, Integrated airline planning: Robust update of scheduling and fleet balancing under demand uncertainty, Transp. Res. Part C, 81 (2017), 227-245.
[11]	X. Chen, H. Yu, K. Cao, J. Zhou, T. Wei, S. Hu, Uncertainty-Aware Flight Scheduling for Airport Throughput and Flight Delay Optimization, IEEE Trans. Aerosp. Electron. Syst., 56 (2020), 853-862.
[12]	R. W. Simpson, Scheduling and routing models for airline systems, Cambridge Mass, 1969, 33-75.
[13]	M. S. Daskin, N. D. Panayotopoulos, A lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks, Transp. Sci., 23 (1989), 91-99.
[14]	G. Desaulniers, J. Desrosiers, Y. Dumas, M. M. Solomon, F. Soumis, Daily aircraft routing and scheduling, Manage. Sci., 43 (1997), 841-855.
[15]	J. J. Salazar-González, Approaches to solve the fleet-assignment, aircraft-routing, crew-rostering problems of regional carrier, Omega, 43 (2014), 71-82.
[16]	V. Cacchiani, J. J. Salazar-González, Optimal solutions to a real-world integrated airline scheduling problem, Transp. Sci., 51 (2017), 250-268.
[17]	S. Lan, J. P. Clarke, C. Barnhart, Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions, Transp. Sci., 40 (2006), 15-28.
[18]	S. Ahmadbeygi, A. Cohn, M. Lapp, Decreasing airline delay propagation by re-allocating scheduled slack, IIE Trans., 42 (2010), 478-489.
[19]	O. Weide, D. Ryan, M. Ehrgott, An iterative approach to robust and integrated aircraft routing and crew scheduling, Comput. Oper. Res., 37 (2010), 833-844.
[20]	M. Dunbar, G. Froyland, C. L. Wu, Robust airline schedule planning: Minimizing propagated delay in an integrated routing and crewing framework, Transp. Sci., 46 (2012), 204-216.
[21]	H. D. Sherali, K. H. Bae, M. Haouari, An integrated approach for airline flight selection and timing, fleet assignment, and aircraft routing, Transp. Sci., 47 (2013), 455-476.
[22]	A. Jamili, A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem, J. Air Transp. Manage., 58 (2017), 21-30.
[23]	H. Gürkan, S. Gürel, M. S. Aktürk, An integrated approach for airline scheduling, aircraft fleeting and routing with cruise speed control, Transp. Res. Part C, 68 (2016), 38-57.
[24]	O. Faust, J. Gönsch, R. Klein, Demand-oriented integrated scheduling for point-to-point airlines, Transp. Sci., 51 (2017), 196-213.
[25]	S. Ahmadbeygi, A. Cohn, Y. Guan, P. Belobaba, Analysis of the potential for delay propagation in passenger airline networks, J. Air Transp. Manage., 14 (2008), 221-236.
[26]	L. Marla, V. Vaze, C. Barnhart, Robust optimization: Lessons learned from aircraft routing, Comput. Oper. Res., 98 (2018), 165-184.
[27]	M. Dunbar, G. Froyland, C. L. Wu, An integrated scenario-based approach for robust aircraft routing, crew pairing and re-timing, Comput. Oper. Res., 45 (2014), 68-86.
[28]	M. Dorigo, T. Stützle, The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, Handbook of Metaheuristics, 2002.

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)