A multi-objective fuzzy optimization model for multi-type aircraft flight scheduling problem
Abstract
This study proposes a multi-objective optimization model for an Aircraft Flight Scheduling Problem (AFSP) for assigning a set of aircraft located at different airports to conduct all flight trips. The proposed model features each flight trip with its own special aircraft type and fuzzy flight time. Moreover, a flight trip with a small aircraft being covered by a larger one is fully accounted for in the model. The model can effectively reduce the number of aircraft and achieve the minimum total idle time for adjacent flight trips covered by an aircraft. A novel heuristic algorithm based on the Non-dominated Sorting Genetic Algorithm (NSGA-II) is further designed to yield meta-optimal solutions efficiently for such a Non-deterministic Polynomial (NP) problem. Finally, a real airline scheduling example in China is conducted using CPLEX and the proposed heuristic algorithm to evaluate the difference between the proposed and traditional models. The results show that the given scheduling problem effectively enhances the operational efficiency of the aircraft fleet.
First published online 28 January 2025
Keyword : aircraft flight scheduling, fuzzy flight time, heuristic algorithm, multiple aircraft type, multi-objective
How to Cite
Wei, M., Yang, S., Wu, W., & Sun, B. (2024). A multi-objective fuzzy optimization model for multi-type aircraft flight scheduling problem. Transport, 39(4), 313–322. https://doi.org/10.3846/transport.2024.20536
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Abara, J. 1989. Applying integer linear programming to the fleet assignment problem, Interfaces 19(4): 20–28. https://doi.org/10.1287/inte.19.4.20
Abualigah, L. M. Q.; Hanandeh, E. S. 2015. Applying genetic algorithms to information retrieval using vector space model, International Journal of Computer Science, Engineering and Applications 5(1): 19–28. https://doi.org/10.5121/ijcsea.2015.5102
Badi, I.; Abdulshahed, A. 2019. Ranking the Libyan airlines by using full consistency method (FUCOM) and analytical hierarchy process (AHP), Operational Research in Engineering Sciences: Theory and Applications 2(1): 1–14. Available from Internet: https://oresta.org/menu-script/index.php/oresta/article/view/9
Bardenhagen, A.; Rakov, D. 2019. Advanced morphological approach in aerospace design during conceptual stage, Facta Universitatis, Series: Mechanical Engineering 17(3): 321–332. https://doi.org/10.22190/FUME180110005B
Barma, P. S.; Dutta, J.; Mukherjee, A. 2019. A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem, Decision Making: Applications in Management and Engineering 2(2): 112–125. https://doi.org/10.31181/dmame1902089b
Berge, M. E.; Hopperstad, C. A. 1993. Demand driven dispatch: a method for dynamic aircraft capacity assignment, models and algorithms, Operations Research 41(1): 153–168. https://doi.org/10.1287/opre.41.1.153
Cacchiani, V.; Salazar-González, J.-J. 2017. Optimal solutions to a real-world integrated airline scheduling problem, Transportation Science 51(1): 250–268. https://doi.org/10.1287/trsc.2015.0655
Cadarso, L.; De Celis, R. 2017. Integrated airline planning: robust update of scheduling and fleet balancing under demand uncertainty, Transportation Research Part C: Emerging Technologies 81: 227–245. https://doi.org/10.1016/j.trc.2017.06.003
Clarke, L. W.; Hane, C. A.; Johnson, E. L.; Nemhauser, G. L. 1996. Maintenance and crew considerations in fleet assignment, Transportation Science 30(3): 249–260. https://doi.org/10.1287/trsc.30.3.249
Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6(2): 182–197. https://doi.org/10.1109/4235.996017
Faust, O.; Gönsch, J.; Klein, R. 2017. Demand-oriented integrated scheduling for point-to-point airlines, Transportation Science 51(1): 196–213. https://doi.org/10.1287/trsc.2016.0693
Fry, D. G. 2015. Demand Driven Dispatch and Revenue Management. MSc Thesis. Massachusetts Institute of Technology, MA, US. 154 p. Available from Internet: https://dspace.mit.edu/handle/1721.1/99548
Gui, D.; Le, M.; Huang, Z.; D′Ariano, A. 2024. A decision support framework for aircraft arrival scheduling and trajectory optimization in terminal maneuvering areas, Aerospace 11(5): 405. https://doi.org/10.3390/aerospace11050405
Hane, C. A.; Barnhart, C.; Johnson, E. L.; Marsten, R. E.; Nemhauser, G. L.; Sigismondi, G. 1995. The fleet assignment problem: Solving a large-scale integer program, Mathematical Programming 70(1–3): 211–232. https://doi.org/10.1007/BF01585938
Huang, W.; Wang, W. J.; Bai, F. L.; Zhang, X. H. 2011. Study on optimization of multi-type aircraft scheduling robust model, Applied Mechanics and Materials 40–41: 347–353. https://doi.org/10.4028/www.scientific.net/AMM.40-41.347
Jamili, A. 2017. A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem, Journal of Air Transport Management 58: 21–30. https://doi.org/10.1016/j.jairtraman.2016.08.008
Jiang, H.; Barnhart, C. 2009. Dynamic airline scheduling, Transportation Science 43(3): 336–354. https://doi.org/10.1287/trsc.1090.0269
Kaucic, M.; Moradi, M.; Mirzazadeh, M. 2019. Portfolio optimization by improved NSGA-II and SPEA 2 based on different risk measures, Financial Innovation 5: 26. https://doi.org/10.1186/s40854-019-0140-6
Kenan, N.; Jebali, A.; Diabat, A. 2018a. An integrated flight scheduling and fleet assignment problem under uncertainty, Computers & Operations Research 100: 333–342. https://doi.org/10.1016/j.cor.2017.08.014
Kenan, N.; Jebali, A.; Diabat, A. 2018b. The integrated aircraft routing problem with optional flights and delay considerations, Transportation Research Part E: Logistics and Transportation Review 118: 355–375. https://doi.org/10.1016/j.tre.2018.08.002
Lahooti Eshkevari, M.; Rashidi Komijan, A.; Baradaran, V. 2025. A flight-leg-based crew recovery model for disruptions management: a tabu search approach, International Journal of Research in Industrial Engineering (in press). https://doi.org/10.22105/riej.2025.468020.1456
Lalla-Ruiz, E.; Voß, S. 2020. A POPMUSIC approach for the multi-depot cumulative capacitated vehicle routing problem, Optimization Letters 14(3): 671–691. https://doi.org/10.1007/s11590-018-1376-1
Lan, S.; Clarke, J.-P.; Barnhart, C. C. 2006. Planning for robust airline operations: optimizing aircraft routings and flight departure times to minimize passenger disruptions, Transportation Science 40(1): 15–28. https://doi.org/10.1287/trsc.1050.0134
Li, K.; Chen, R.; Fu, G.; Yao, X. 2019. Two-archive evolutionary algorithm for constrained multiobjective optimization, IEEE Transactions on Evolutionary Computation 23(2): 303–315. https://doi.org/10.1109/TEVC.2018.2855411
Listes, O.; Dekker, R. 2005. A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacity allocation, Transportation Science 39(3): 367–382. https://doi.org/10.1287/trsc.1040.0097
Pamucar, D.; Ćirović, G. 2018. Vehicle route selection with an adaptive neuro fuzzy inference system in uncertainty conditions, Decision Making: Applications in Management and Engineering 1(1): 13–37. https://doi.org/10.31181/dmame180113p
Petrović, D.; Puharić, M.; Kastratović, E. 2018. Defining of necessary number of employees in airline by using artificial intelligence tools, International Review 3(4): 77–89. https://doi.org/10.5937/IntRev1804077P
Roy, A.; Manna, A.; Maity, S. 2019. A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique, Decision Making: Applications in Management and Engineering 2(2): 100–111. https://doi.org/10.31181/dmame1902076r
Rushmeier, R. A.; Kontogiorgis, S. A. 1997. Advances in the optimization of airline fleet assignment, Transportation Science 31(2): 159–169. https://doi.org/10.1287/trsc.31.2.159
Salazar-González, J.-J. 2014. Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier, Omega 43: 71–82. https://doi.org/10.1016/j.omega.2013.06.006
Sherali, H. D.; Bae, K.-H.; Haouari, M. 2013. A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture, Annals of Operations Research 210(1): 213–244. https://doi.org/10.1007/s10479-011-0906-3
Sherali, H. D.; Bish, E. K.; Zhu. X. 2005. Polyhedral analysis and algorithms for a demand-driven refleeting model for aircraft assignment, Transportation Science 39(3): 349–366. https://doi.org/10.1287/trsc.1040.0090
Sherali, H. D.; Zhu, X. 2008. Two-stage fleet assignment model considering stochastic passenger demands, Operations Research 56(2): 383–399. https://doi.org/10.1287/opre.1070.0476
Wei, M.; Chen, X.; Sun, B.; Zhu, Y.-Y. 2015. Model and algorithm for resolving regional bus scheduling problems with fuzzy travel times, Journal of Intelligent & Fuzzy Systems 29(6): 2689–2696. https://doi.org/10.3233/IFS-151972
Yang, Y.; Wei, G.; Zhou, B.; Zhang, X. 2011. Distribution network planning based on fuzzy expected value model, Transactions of China Electrotechnical Society 26(4): 200–207. (in Chinese).
Zhou, S.-Z.; Zhan, Z.-H.; Chen, Z.-G.; Kwong, S.; Zhang, J. 2020. A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction, IEEE Transactions on Intelligent Transportation Systems 22(11): 6784–6798. https://doi.org/10.1109/TITS.2020.2994779
Abualigah, L. M. Q.; Hanandeh, E. S. 2015. Applying genetic algorithms to information retrieval using vector space model, International Journal of Computer Science, Engineering and Applications 5(1): 19–28. https://doi.org/10.5121/ijcsea.2015.5102
Badi, I.; Abdulshahed, A. 2019. Ranking the Libyan airlines by using full consistency method (FUCOM) and analytical hierarchy process (AHP), Operational Research in Engineering Sciences: Theory and Applications 2(1): 1–14. Available from Internet: https://oresta.org/menu-script/index.php/oresta/article/view/9
Bardenhagen, A.; Rakov, D. 2019. Advanced morphological approach in aerospace design during conceptual stage, Facta Universitatis, Series: Mechanical Engineering 17(3): 321–332. https://doi.org/10.22190/FUME180110005B
Barma, P. S.; Dutta, J.; Mukherjee, A. 2019. A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem, Decision Making: Applications in Management and Engineering 2(2): 112–125. https://doi.org/10.31181/dmame1902089b
Berge, M. E.; Hopperstad, C. A. 1993. Demand driven dispatch: a method for dynamic aircraft capacity assignment, models and algorithms, Operations Research 41(1): 153–168. https://doi.org/10.1287/opre.41.1.153
Cacchiani, V.; Salazar-González, J.-J. 2017. Optimal solutions to a real-world integrated airline scheduling problem, Transportation Science 51(1): 250–268. https://doi.org/10.1287/trsc.2015.0655
Cadarso, L.; De Celis, R. 2017. Integrated airline planning: robust update of scheduling and fleet balancing under demand uncertainty, Transportation Research Part C: Emerging Technologies 81: 227–245. https://doi.org/10.1016/j.trc.2017.06.003
Clarke, L. W.; Hane, C. A.; Johnson, E. L.; Nemhauser, G. L. 1996. Maintenance and crew considerations in fleet assignment, Transportation Science 30(3): 249–260. https://doi.org/10.1287/trsc.30.3.249
Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6(2): 182–197. https://doi.org/10.1109/4235.996017
Faust, O.; Gönsch, J.; Klein, R. 2017. Demand-oriented integrated scheduling for point-to-point airlines, Transportation Science 51(1): 196–213. https://doi.org/10.1287/trsc.2016.0693
Fry, D. G. 2015. Demand Driven Dispatch and Revenue Management. MSc Thesis. Massachusetts Institute of Technology, MA, US. 154 p. Available from Internet: https://dspace.mit.edu/handle/1721.1/99548
Gui, D.; Le, M.; Huang, Z.; D′Ariano, A. 2024. A decision support framework for aircraft arrival scheduling and trajectory optimization in terminal maneuvering areas, Aerospace 11(5): 405. https://doi.org/10.3390/aerospace11050405
Hane, C. A.; Barnhart, C.; Johnson, E. L.; Marsten, R. E.; Nemhauser, G. L.; Sigismondi, G. 1995. The fleet assignment problem: Solving a large-scale integer program, Mathematical Programming 70(1–3): 211–232. https://doi.org/10.1007/BF01585938
Huang, W.; Wang, W. J.; Bai, F. L.; Zhang, X. H. 2011. Study on optimization of multi-type aircraft scheduling robust model, Applied Mechanics and Materials 40–41: 347–353. https://doi.org/10.4028/www.scientific.net/AMM.40-41.347
Jamili, A. 2017. A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem, Journal of Air Transport Management 58: 21–30. https://doi.org/10.1016/j.jairtraman.2016.08.008
Jiang, H.; Barnhart, C. 2009. Dynamic airline scheduling, Transportation Science 43(3): 336–354. https://doi.org/10.1287/trsc.1090.0269
Kaucic, M.; Moradi, M.; Mirzazadeh, M. 2019. Portfolio optimization by improved NSGA-II and SPEA 2 based on different risk measures, Financial Innovation 5: 26. https://doi.org/10.1186/s40854-019-0140-6
Kenan, N.; Jebali, A.; Diabat, A. 2018a. An integrated flight scheduling and fleet assignment problem under uncertainty, Computers & Operations Research 100: 333–342. https://doi.org/10.1016/j.cor.2017.08.014
Kenan, N.; Jebali, A.; Diabat, A. 2018b. The integrated aircraft routing problem with optional flights and delay considerations, Transportation Research Part E: Logistics and Transportation Review 118: 355–375. https://doi.org/10.1016/j.tre.2018.08.002
Lahooti Eshkevari, M.; Rashidi Komijan, A.; Baradaran, V. 2025. A flight-leg-based crew recovery model for disruptions management: a tabu search approach, International Journal of Research in Industrial Engineering (in press). https://doi.org/10.22105/riej.2025.468020.1456
Lalla-Ruiz, E.; Voß, S. 2020. A POPMUSIC approach for the multi-depot cumulative capacitated vehicle routing problem, Optimization Letters 14(3): 671–691. https://doi.org/10.1007/s11590-018-1376-1
Lan, S.; Clarke, J.-P.; Barnhart, C. C. 2006. Planning for robust airline operations: optimizing aircraft routings and flight departure times to minimize passenger disruptions, Transportation Science 40(1): 15–28. https://doi.org/10.1287/trsc.1050.0134
Li, K.; Chen, R.; Fu, G.; Yao, X. 2019. Two-archive evolutionary algorithm for constrained multiobjective optimization, IEEE Transactions on Evolutionary Computation 23(2): 303–315. https://doi.org/10.1109/TEVC.2018.2855411
Listes, O.; Dekker, R. 2005. A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacity allocation, Transportation Science 39(3): 367–382. https://doi.org/10.1287/trsc.1040.0097
Pamucar, D.; Ćirović, G. 2018. Vehicle route selection with an adaptive neuro fuzzy inference system in uncertainty conditions, Decision Making: Applications in Management and Engineering 1(1): 13–37. https://doi.org/10.31181/dmame180113p
Petrović, D.; Puharić, M.; Kastratović, E. 2018. Defining of necessary number of employees in airline by using artificial intelligence tools, International Review 3(4): 77–89. https://doi.org/10.5937/IntRev1804077P
Roy, A.; Manna, A.; Maity, S. 2019. A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique, Decision Making: Applications in Management and Engineering 2(2): 100–111. https://doi.org/10.31181/dmame1902076r
Rushmeier, R. A.; Kontogiorgis, S. A. 1997. Advances in the optimization of airline fleet assignment, Transportation Science 31(2): 159–169. https://doi.org/10.1287/trsc.31.2.159
Salazar-González, J.-J. 2014. Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier, Omega 43: 71–82. https://doi.org/10.1016/j.omega.2013.06.006
Sherali, H. D.; Bae, K.-H.; Haouari, M. 2013. A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture, Annals of Operations Research 210(1): 213–244. https://doi.org/10.1007/s10479-011-0906-3
Sherali, H. D.; Bish, E. K.; Zhu. X. 2005. Polyhedral analysis and algorithms for a demand-driven refleeting model for aircraft assignment, Transportation Science 39(3): 349–366. https://doi.org/10.1287/trsc.1040.0090
Sherali, H. D.; Zhu, X. 2008. Two-stage fleet assignment model considering stochastic passenger demands, Operations Research 56(2): 383–399. https://doi.org/10.1287/opre.1070.0476
Wei, M.; Chen, X.; Sun, B.; Zhu, Y.-Y. 2015. Model and algorithm for resolving regional bus scheduling problems with fuzzy travel times, Journal of Intelligent & Fuzzy Systems 29(6): 2689–2696. https://doi.org/10.3233/IFS-151972
Yang, Y.; Wei, G.; Zhou, B.; Zhang, X. 2011. Distribution network planning based on fuzzy expected value model, Transactions of China Electrotechnical Society 26(4): 200–207. (in Chinese).
Zhou, S.-Z.; Zhan, Z.-H.; Chen, Z.-G.; Kwong, S.; Zhang, J. 2020. A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction, IEEE Transactions on Intelligent Transportation Systems 22(11): 6784–6798. https://doi.org/10.1109/TITS.2020.2994779