An Integrated Model for Crew, Aircraft and Passenger Recovery Problem: A Real Case Study

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran

2 Department of Industrial Engineering, Firoozkooh Branch, Islamic Azad University, Firoozkooh, Iran

10.22059/aie.2022.346585.1848

Abstract

Airlines try to reduce costs by improving the quality of their operational schedules. However, numerous uncontrollable factors make disruptions inevitable. A flight delay or cancellation caused by disruption may spread throughout the network and increase the operational costs by affecting the schedule of other flights, including aircraft, crew, and passengers’ itineraries. While previous researchers have focused on one of these aspects or sequential approaches, the resulted solutions cannot lead to a reliable operational solution due to the complex relationships between these factors in practice. Therefore, integrated recovery approaches are highly essential. The main objective of this research is to provide a fully integrated recovery model that contains various recovery scenarios to tackle the disruption and delay propagation with more flexibility and acceptable solution time. So, an integrated model for crew, aircraft, and passenger recovery problem is proposed in this paper. The proposed model is formulated as MILP, based on individual flight legs to achieve a more accurate schedule with better recovery solution. Options such as aircraft reassignment, crew swapping, reassignment of passengers, and ticket refunds are considered as alternatives to face disruption. Moreover, the considerations related to crew rest-time and maintenance requirements are also included in the model. Due to the NP-Hard nature of the problem, the Genetic algorithm is used as the solution approach successfully for the real-world data to limit delay propagation on various random flights.

Keywords


  • [1] Lenaerts, Allroggen F., Malina R., (2021), The economic impact of aviation: A review on the role of market access, Journal of Air Transport Management, Volume 91,102000.
  • [2] (2021), IATA-Economic-Performance-of-the-Industry-mid-year-2021-report.
  • [3] Bureau of transportation statistics 2022 report. https://www.transtats.bts.gov/homedrillchart.asp
  • [4] Schaefer, A., Johnson, E., Kleywegt, A. and Nemhauser, G. (2005), Airline crew scheduling under uncertainty,. Transportation Science, 39(3): 340–348.
  • [5] Eggenberg, N., S. M. (2009). Uncertainty Feature Optimization for the Airline Scheduling Problem. TRANSP-OR-REPORT-2009-005.
  • [6] Clausen J., L. A. (2010), Disruption management in the airline industry—Concepts, models and methods. Computers & Operations Research 37, 809 -- 821.
  • [7] Lan, C. (2006), Planning for robust airline operations: optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transportation Science, 40, 15–28.
  • [8] (2007), Airline Integrated Planning and Operations. Ph.D. Thesis Georgia Institute of Technology, 93-94.
  • [9] AhmadBeygi S., C. A. (2008), Analysis of the potential for delay propagation in passenger airline networks. Journal of Air Transport Management 14, 221– 236.
  • [10] Hassan K., Santos B.F., Vink J., (2021), Computers and Operations Research 127 105137
  • [11] Maher, J., (2015). A novel passenger recovery approach for the integrated airline recovery problem. School of Mathematics and Statistics, University of New South Wales. Published online. ‏
  • [12] , S. J. (2016), Solving the integrated recovery problem using column-and-row generation. Transportation Science. Published online.
  • [13] Arıkan, U., G. S. (2017), Flight Network-Based Approach for Integrated Airline Recovery with Cruise Speed Control. TRANSPORTATION SCIENCE, 1–29.
  • [14] Kohl N, L. A. (2007), Airline disruption management—perspectives, experiences and outlook. Journal of Air Transport Management, 13:149–62.
  • [15] Su Y, Xie K, Wang H, Liang Z, Chaovalitwongse W, Pardalos P. (2021), Airline Disruption Management: A Review of Models and Solution Methods.Engineering 7, 435-447.
  • [16] Andersson, T., (2006), Solving the flight perturbation problem with meta heuristics. Journal of Heuristics, 12:37–53.
  • [17] Hu Y, L. H. (2017), Multiple objective solution approaches for aircraft rerouting under the disruption of multi-aircraft. Expert Systems with Applications, 83.
  • [18] Liang Z., Xiao F. Qian X., Zhou L, Jin X., Lu X., Karichery S., (2018), A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility. Transportation Research Part B 113 70–90.
  • [19] Vink J, Santos BF, Verhagen WJC, Medeiros I, Filho R. 2020 Dynamic aircraft recovery problem—an operational decision support framework. Comput Oper Res;117:104892.
  • [20] Guo Y. (2005). Decision support systems for airline crew recovery. PhD thesis, University.
  • [21] Chang SC. (2012). A duty based approach in solving the aircrew recovery problem. J Air Transp Manage; 19:16–20.
  • [22] Bayliss, C., De Maere, G., Paelinck, M., (2019), Scheduling Airline Reserve Crew using a Probabilistic Crew Absence and Recovery Model. Journal of the Operational Research Society. Published online: 20 Apr 2019
  • [23] Scherp L., Janssen R., Santos B., (2019), Dynamic Design of Reserve Crew Duties for Long Haul Airline Crew. optimization-online.org
  • [24] Bratu, S., Barnhart. C., (2006), Flight operations recovery: new approaches considering passenger recovery. Journal of Scheduling, vol. 9, no. 3, pp. 279–298.
  • [25] Jafari, , Zegordi, H., (2011), Simultaneous recovery model for aircraft and passengers. Journal of the Franklin Institute, 348(7):1638–1655.
  • [26] Abdelghany, K.F., Abdelghany, A.F., Ekollu, G., (2008), An Integrated decision support tool for airlines schedule recovery during irregular operations, European Journal of Operational Research 185 825–848.
  • [27] McCarty L. (2012). Preemptive Rerouting of Airline Passengers under Uncertain Delays. PhD thesis, The University of Michigan.
  • [28] McCarty L., Cohn A., (2018), Preemptive rerouting of airline passengers under uncertain delays. Computers & Operations Research Volume 90, February Pages 1-11.
  • [29] Rashidi Komijan A., Tavakkoli-Moghadam R., Dalil S. A., (2019), A mathematical model for an integrated airline fleet assignment and crew scheduling problem solved by vibration damping optimization. Scientia Iranica, pp. -. doi: 10.24200/sci.2019.51516.2230
  • [30] Petersen, G. S. (2012), An optimization approach to airline integrated recovery. Transportation Science, 46(4):482–500.
  • [31] Sinclair K, C. (2014), Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem. Europian Journal of Operation Research, 233 (1), 234–245.
  • [32] Bisaillon, S., C. J. (2011), A large neighborhood search heuristic for the aircraft and passenger recovery problem. 4OR Quart. journal of operation research, 9 (2), 139–157.
  • [33] Sinclair K, C. J. (2015), A column generation post-optimization heuristic for integrated aircraft and passenger recovery problem. CIRRELT, 32.
  • [34] Arıkan U, S. G. (2014), Integrated aircraft and passenger recovery with cruise time controllability. Annual Operation Research 11, 236(2):295–317.
  • [35] Khiabani, A., Rashidi Komijan, A., Ghezavati, V. and Mohammadi Bidhandi, H. (2022), "A mathematical model for integrated aircraft and crew recovery after a disruption: A Benders’ decomposition approach", Journal of Modelling in Management, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/JM2-02-2022-0046
  • [36] Liang, Z., Zhou, L., Chou, CA. et al. (2020), Airline planning and scheduling: Models and solution methodologies. Front. Eng. Manag. 7, 1–26. https://doi.org/10.1007/s42524-020-0093-5
  • [37] Zhang D, H.Y.K.Henry Lau, ChuhangYuA., (2015). Two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems Comput. Ind. Eng. 87, 436–5310.1016/j.cie.2015.05.033.
  • [38] Aguiar B., Torres J., Castro A., (2013) Operational problems recovery in airlines – a specialized methodologies approachProg. Artif. Intell. 815410.1007/978-3-642-40669-0
  • [39] Kliewer N., Mellouli T., Suhl L.,(2006), A time–space network based exact optimization model for multi-depot bus scheduling, European Journal of Operational Research, Volume 175, Issue 3,Pages 1616-1627, ISSN 0377-2217.
  • [40] Barnhart C., Boland N.L., Clarke L.W., Johnson E.L., Nemhauser G.L. and Shenoi R.G. (1998), Flight String Models for Aircraft Fleeting and Routing. Transportation Science, vol. 32, issue 3, 208-220
  • [41] , (2004), Robust Airline Schedule Planning: Review and Development of Optimization Approaches. Master of Science Thesis Massachusetts Institute of Technology, 54-55
  • [42] Sherali Hanif D, Ki-Hwan Bae, Mohamed Haouari (2013) An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing. Transportation Science 47(4):455-476.
  • [43] Mei Long Le, Wu. (2013), Solving airlines disruption by considering aircraft and crew recovery simultaneously J. Shanghai Jiaotong Univ. (Science) 18 (2), 243–25210.1007/s12204-013-1389-y.
  • [44] Castro, Antonio J.M., Ana Paula Rocha, Eugenio Oliveira, (2014). A New Approach for Disruption Management in Airline Operations Control, Studies in Computational Intelligence, vol. 562. Springer, Berlin Heidelberg, Berlin, Heidelberg. doi: 10.1007/978-3-662-43373-7.
  • [45] Hu Y, Song Y, Zhao K, Xu B, (2016) Integrated recovery of aircraft and passengers after airline operation disruption based on a GRASP algorithm Transp. Res. E Logist. Transp. Rev. 87, 97–11210.1016/j.tre.2016.01.002.
  • [46] Zhu B., John PaulClarke, JinfuZhu., (2016), Real-time integrated flight schedule recovery problem using sampling-based approachJ. Comput. Theor. Nanosci. 13 (2), 1458–146710.1166/jctn.2016.5068
  • [47] Wu Z., Li B., Dang C., (2017), Solving Multiple Fleet Airline Disruption Problems Using a Distributed-Computation Approach to Integer Programming. IEEE 10.1109/ACCESS.2017.2747155
  • [48] Shaochang W., Weixia Y., Fei X., Zhe M., (2018), Application of Greedy Random Adaptive Search Algorithm (GRASP) in Flight Recovery Problem, 2nd International Conference on Sensor Network and Computer Engineering (ICSNCE 2018), Advances in Computer Science Research, volume 79
  • [49] Lee C.K.H., (2018), A review of applications of genetic algorithms in operations management, Engineering Applications of Artificial Intelligence, Volume 76, Pages 1-12,
  • [50] Chen R, Liang C-Y, Hong W-C, Gu D-X (2015) Forecasting holiday daily tourist flow based on seasonal support vector regression with adaptive genetic algorithm. Appl Soft Comput 26:434–443
  • [51] Sinclair K., Cordeau J., Laporte G., (2016), A rolling horizon heuristic for aircraft and passenger recovery
  • [52] Michalewicz Z, Schoenauer M (1996) Evolutionary algorithms for constrained parameter optimization problems. Evol Comput 4(1):1–32
  • [53] Katoch, S., Chauhan, S.S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 https://doi.org/10.1007/s11042-020-10139-6
  • [54] Liu TK, Jeng CR, Chang YH. (2008). Disruption management of an inequality-based multi-fleet airline schedule by a multi-objective genetic algorithm. Transp Plann Technol;31(6):613–39.
  • [55] Chiu HungChen, Jyh HorngChou. (2016). Multiobjective optimization of airline crew roster recovery problems under disruption conditions IEEE Trans. Syst. Man Cybern. Syst. 47 (1), 133 14410.1109/ TSMC..2560130.
  • [56] Abdelghany A., Abdelghany K., Azadian F., (2017) Airline flight schedule planning under competition, Computers & Operations Research, Volume 87, Pages 20-39, ISSN 0305-0548.