Math-heuristic to solve the airline recovery problem considering aircraft and passenger networks
DOI:
https://doi.org/10.14295/transportes.v29i2.2166Keywords:
Recovery, Airline networks disruption, Math-heuristicAbstract
The airline recovery problem involves aircraft, crew and passenger networks impacted by disruptions. Models to solve the problem consider one or more of these networks, on an integrated way or not. It belongs to the NP-hard class, even considering only one network. This work presents a math-heuristic to solve the problem integrating the aircraft and the passenger networks. A model to restore the aircraft network with minimum cost was also developed. These two models compose a framework which permits the airline to obtain the cost impact of including the passenger network in the recovery problem. Both models were tested with real world ROADEF instances using an Intel i7 microcomputer (16Gb of RAM) and a high-performance cluster node (HPC) with 512 GB of RAM. The microcomputer solved instances with up to 85 aircraft and 276 impacted flights in less than 30 minutes (imposed limit). The faster high-performance server reached solutions with minimum gap of 0 to 0.7% for the instances with higher number of flights. Total costs considering aircraft and passenger networks were very close to the aircraft network recovery results, showing a cost compensation which highlights the importance of solving the recovery problem integrating aircraft and passenger networks.
Downloads
References
Abdelghany, K.; S. Shah; S. Raina and A. Abdelghany (2004) A model for projecting flight delays during irregular operation conditions. Journal of Air Transport Management, v.10, p.385-394. DOI: 10.1016/j.jairtraman.2004.06.008
Abdelghany, K.; A. Abdelghany and G. Ekollu (2008) An integrated decision support tool for Airlines schedule recovery during irregular operations. European Journal of Operational Research, v.185, n.2, p.825–848. DOI: 10.1016/j.ejor.2006.12.045
Arikan, U.; S. Gurel and M. Akturk (2016) Integrated aircraft and passenger recovery with cruise time controllability. Annals of Operations Research, v.236, n.2, p.295-317. DOI: 10.1007/s10479-013-1424-2
Artigues, C.; E. Bourreau E; M. Afsar; O. Briant and M. Boudia (2012) Disruption management for commercial airlines: methods and results for the ROADEF 2009 Challenge, European Journal of Industrial Engineering, v.6, n.6, p. 669 – 689. DOI: 10.1504/EJIE.2012.051072
Bisaillon, S.; J-F. Cordeau J-F; G. Laporte and F. Pasin (2011) A large neighborhood search heuristic for the aircraft and passenger recovery problem. 4OR: A Quarterly Journal of Operations Research, v.9, p.139-157. DOI: 10.1007/s10288-010-0145-5
Bratu, S. and C. Barnhart (2006) Flight operations recovery: new approaches considering passenger recovery. Journal of Scheduling, v.9, n.3, p.279–298. DOI: 10.1007/s10951-006-6781-0
Caetano, D.J. and N. D .F. Gualda N.D.F. (2011) MAGS - An Aco-based Model to Solve the Schedule Generation and Fleet Assignment Integrated Problem. In Proceedings of the International Conference on Evolutionary Computation Theory and Applications, v.1: ECTA, p.227-232, 2011, Paris, France. DOI: 10.5220/0003673502270232
Caetano, D. J. and N. D. F. Gualda (2012). An Integrated Model for Flight Scheduling and Fleet Assignment Based on the Ant Colony Meta-Heuristic. In Proceedings of the XVII Pan-American Conference of Traffic and Transportation Engineering and Logistics, v.1, p.1-19, 2012, Santiago, Chile.
Caserta, M.; A. Ramirez and S. Voß (2010) A Math-Heuristic for the Multi-Level Capacitated Lot Sizing Problem with Carryover. European Conference on the Applications of Evolutionary Computation, p.462-471, Springer-Verlag, Berlin. DOI: 10.1007/978-3-642-12242-2_47
Castro, A. (2014) How automated negotiation and learning help to manage disruptions in airline operations control, Intelligent transportation systems applied to logistics and transportation conference, session IX, MASDIMA, Lda., 2014, Cascais, Portugal.
Castro, A. and E. Oliveira (2009) Quantifying quality operational costs in a multi-agent system for airline operations recovery. International Review on Computers and Software (IRECOS), v.4, n.4. https://hdl.handle.net/10216/15925
Castro, A. and E. Oliveira (2011) Airline operations control: a new concept for operations recovery. In: Airline Industry: Strategies, Operations and Safety, p.61-97, Connor R. Walsh, ISBN: 978-1-61122-079-7 2011.
Castro, A.; A. Rocha and E. Oliveira (2014) A new approach for disruption management in airline operations control. Studies in Computational Intelligence, v.562, Springer-Verlag, ISBN: 978-3-662-43373-7.
Eggenberg N.; M. Salani and M. Bierlaire (2010) Constraint-specific recovery network for solving recovery problems. Computers and Operations Research, v.37, n.6, p.1014–1026. DOI: 10.1016/j.cor.2009.08.006
Gao, C. (2007) Airline Integrated Planning and Operations. Ph.D. thesis, Georgia Institute of Technology, Atlanta, USA. http://hdl.handle.net/1853/16292
Gao Q.; X. Tang and J. Zhu (2009) Research on Greedy Simulated Annealing Algorithm for Irregular Flight Schedule Recovery Model. Proceedings of 2009 IEEE International Conference on Grey Systems and Intelligent Services, Nanjing, China. DOI:10.1007/978-3-642-13938-3_44
Gomes, W. P. (2014) Modelagem integrada do problema de programação de tripulantes de aeronaves. Tese (Doutorado), Departamento de Engenharia de Transportes, Escola Politécnica da Universidade de São Paulo, São Paulo, SP. DOI: 10.11606/t.3.2014.tde-25112014-143703
Gomes, W. P. and N. D. F. Gualda (2011). A Hybrid Genetic Algorithm for the Airline Crew Assignment Problem. In: Interna-tional Conference on Evolutionary Computation Theory and Applications (ECTA), 2011, Paris. Proceedings of the ECTA. Paris: SciTePress, 2011. p.190-195. ISBN: 978-989-8425-83-6
Gomes, W. P. and N. D. F. Gualda (2015) Heuristics to solve the integrated airline crew assignment problem. The Journal of Transport Literature, v.9, p.25-29. DOI: 10.1590/2238-1031.jtl.v9n1a5
Hu, Y.; Y. Song; K. Zhao and B. Xu (2016) Integrated recovery of aircraft and passengers after airline operation disruption based on a GRASP algorithm, Transportation Research Part E: Logistics abd Transportation Review, v.87, p.97–112. DOI: 10.1016/j.tre.2016.01.002
Jafari, N. and S. Zegordi (2010) The airline perturbation problem: considering disrupted passengers. Transportation Planning and Technology v.33, n.2, p.203–220. DOI: 10.1080/03081061003643788
Jafari, N. and S. Zegordi (2011) Simultaneous recovery model for aircraft and passengers, Journal of the Franklin Institute, v.348, n.7, p.1638–1655. DOI: 10.1016/j.jfranklin.2010.03.012
Jozefowiez, N.; C. Mancel and F. Mora-Camino (2012) A heuristic approach based on shortest path problems for integrated flight, aircraft, and passenger rescheduling under disruptions. Journal of the Operational Research Society, v.64, n.3, p.384. DOI: 10.1057/jors.2012.20
Kohl, N.; A. Larsen; J. Larsen; A. Ross and A. Tiourine (2007) Airline disruption management – Perspectives, experiences and outlook. Journal of Transportation Management, v.13, p.149-162. DOI: 10.1016/j.jairtraman.2007.01.001
Maher, S. (2015) A novel passenger recovery approach for the integrated airline recovery problem. Computer and Operations Research, v.57, p.123-137. DOI: 10.1016/j.cor.2014.11.005
Maher, S. (2016) Solving the integrated airline recovery problem using column-and-row generation. Transportation Science, v. 50, n.1, p.216-239. DOI: 10.1287/trsc.2014.0552
Marla, L.; B. Vaaben and C. Barnhart (2017) Integrated Disruption Management and Flight Planning to Trade Off Delays and Fuel Burn. Transportation Science, v.51, n.1, p.88-111. DOI: 10.1287/trsc.2015.0609
Medau, J. C. and N. D. F. Gualda. Alocação de aeronaves a voos considerando restrições operacionais, de manutenção e de desempenho das aeronaves, Transportes, v.26, p.101-117, 2018. DOI: 10.14295/transportes.v26i2.1316
Morais, F.; D. Caetano and N. D. F. Gualda (2018) Math-heuristic para o problema de recuperação de malha aérea (Recovery Problem). https://www.researchgate.net/publication/328433545_MATH-HEURISTIC PARA O_PROBLEMA DE _RECUPERACAO_ DE_ MALHA_AEREA_ RECOVERY _PROBLEM, XVII AIR TRANSPORTATION SYMPOSIUM - SITRAER, 2018, Volume: Conference Program, p. 34, São Paulo. (Retrieved in 5 set 2019) .
Muligan J. (2019) Europe's flight delays cost €100 a minute, Business World, Independent.ie https://www.independent.ie/business/world/europes-flight-delays-cost-100-a-minute-37934906.html, March, 21, 2019, Ireland. (Retrieved in 5 set 2019).
Palpant, M.; M. Boudia; C-A. Robelin; S. Gabteni and F. Laburthe (2009) ROADEF 2009 Challenge: Disruption Management for Commercial Aviation, Amadeus S.A.S., Operations Research Division, France.
Petersen, J.; G. Solveling; E. J. Johnson; J-P. Clarke and S. Shebalov (2012) An optimization approach to airline integrated recovery. Transportation Science v.46, n.4, p.482–500. DOI: 10.1287/trsc.1120.0414
Sinclair, K.; J-F. Cordeau and G. Laporte (2014) Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem. European Journal of Operational Research, v.233, p. 234–245. DOI: 10.1016/j.ejor.2013.08.034
Yu, G. and X. Qi (2004) Disruption management: frameworks, models and applications, World Scientific Publishing Co., London. ISBN: 978-9812560179
Zegordi, S. and N. Jafari (2010) Solving the airline recovery problem by using ant colony optimization. International Journal of Industiral Engineering & Production Research, v.21, n.3, p.121–128. DOI: http://IJIEPR.iust.ac.ir/
Zhang, Y. (2008) Real-time intermodal substitution: strategy for airline recovery from schedule perturbation and for mitigation of airport congestion. PhD Dissertation, University of California, Berkeley, USA.
Zhang, D.; H. Lau and C. Yu (2015) A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems, Computers & Industrial Engineering, v.87, p.436–453. DOI: 10.1016/j.cie.2015.05.033
Zhang, D.; C. Yu C; J. Desai and H. Lau (2016) A math-heuristic algorithm for the integrated air service recovery, Transportation Research Part B, v.84, p.211–236. DOI: 10.1016/j.trb.2015.11.016
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Jose Carlos Fontoura Guimaraes, Nicolau Dionísio Fares Gualda
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.
- Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.
- Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.
- Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.
