Mathematical model and math-heuristic for the aircraft recovery problem

Authors

  • Fábio Emanuel de Souza Morais University of São Paulo, São Paulo – Brazil
  • Nicolau Dionísio Fares Gualda University of São Paulo, São Paulo – Brazil https://orcid.org/0000-0003-3339-0554
  • Daniel Jorge Caetano University of São Paulo, São Paulo – Brazil

DOI:

https://doi.org/10.14295/transportes.v29i4.2234

Keywords:

Flight schedule, Recovery problem, Math-heurístic, Linear Programming, Multi-commodity network flow

Abstract

The aircraft recovery problem (ARP) arises when unexpected events such as storms, airport closures, and unscheduled aircraft maintenance cause delays and/or flight cancellations, dismantling the original aircraft schedule. This work initially presents a mathematical model for the recovery of an airline schedule. Given the NP-Hard nature of the problem, the mathematical model cannot solve large instances. It has led to the development of a two-part math-heuristic: a mixed-integer programming network flow model to obtain a new schedule with minimum flight cancellations and delays; and an integer linear programming model to minimize flight aircraft exchanges from the original schedule. Applications of the heuristic to instances with up to 470 flights presented, in less than one minute of processing, results differing less than 0.5% from the optimal results, which allows to conclude that the heuristic qualifies for application to real cases of considerable size.

Downloads

Download data is not yet available.

References

ANAC (2017) RESOLUÇÃO Nº 440, DE 9 DE AGOSTO DE 2017 [online] Disponível em: < www.anac.gov.br/assuntos/legislacao/legislacao-1/resolucoes/2017/resolucao-no-440-09-08-2017> (acesso em 01/07/2021).

Andersson, T. (2006) Solving the flight perturbation problem with metaheuristics. Journal of Heuristics, v. 12, p. 37–53. DOI: 10.1007/s10732-006-4833-4

Arguello, M.; J. Bard e G. Yu (1997) A grasp for aircraft routing in response to groundings and delays. Journal of Combinatorial Optimization, v. 5, p11–28. DOI: 10.1023/A:1009772208981

BBC News. (2011) Flight disruptions cost airlines $1.7bn, says IATA.[online] Disponível em: (acesso em 01/07/2021).

Belobaba, P.; A. Odoni e C. Barnhart (2009) The global airline industry. 1st edn. UK: Wiley. DOI:10.1002/9780470744734

Bradley, S.P.; A.C. Hax e T.L. Magnanti (1977) Applied Mathematical Programming. E-book library [online]. Disponível em: (acesso em 01/07/2021).

Classen, A. B.; C. Werner e M. Jung (2017) Modern airport management – fostering individual door-to-door travel. Transpor-tation Research Procedia, v. 25, p. 63–76. DOI: 10.1016/j.trpro.2017.05.382

Marla, L.; B. Vaaben e C. Barnhart (2016) 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

Morais, F. E. S. (2019) Estudo do Problema de Recuperação da Malha de Empresa Aérea. Dissertação de Mestrado Escola Politécnica da Universidade de São Paulo. DOI: 10.11606/D.3.2019.tde-07052019-100035

Petersen, J. D.; G. Sölveling; J. P. Clarke; E. L. Johnson e 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

Serrano, F. J. J. e A. Kazdab (2017) Airline disruption management: yesterday, today and tomorrow. Transportation Research Procedia, v. 28, p. 3–10. DOI: 10.1016/j.trpro.2017.12.162

Teodorovic, D. e C. S. Guberini (1984) Optimal dispatching strategy on an airline network after a schedule perturbation. European Journal of Operational Research, v. 15, p. 178–182. DOI: 10.1016/0377-2217(84)90207-8

Thengvall, B. G.; G. Yu e J. F. Bard (2001) Multiple fleet aircraft schedule recovery following hub closures. Transportation Research, Part A, v. 35, n. 4, p. 289–308. DOI: 10.1016/S0965-8564(99)00059-2

Uğur, A.; S. Gürel e M. S. Aktürk (2017) Flight Network-Based Approach for Integrated Airline Recovery with Cruise Speed Control. Transportation Science, 51(4) [online] Disponível em: (acesso em 01/07/2021).

Yan, S. e D. Yang (1996) A decision support framework for handling schedule perturbations. Transportation Research, Part B, v. 30, p. 405–419. DOI: 10.1016/0191-2615(96)00013-6

Yan, S. e H. Young (1996) A decision support framework for multi-fleet routing and multi-stop flight scheduling. Transporta-tion Research, Part A, v. 30, n. 5, p. 379–398. DOI: 10.1016/0965-8564(95)00029-1

Zhang, D.; C. Yu; J. H. Y. K. Desaib e H. Lau (2016) A math-heuristic algorithm for the integrated air service recovery. Trans-portation Research, Part B, v. 84, p. 211–236. DOI: 10.1016/j.trb.2015.11.016

Downloads

Published

2021-11-22

How to Cite

de Souza Morais, F. E. ., Gualda, N. D. F. ., & Caetano, D. J. (2021). Mathematical model and math-heuristic for the aircraft recovery problem. TRANSPORTES, 29(3), 2234. https://doi.org/10.14295/transportes.v29i4.2234

Issue

Vol. 29 No. 3 (2021)

Section

Artigos

License

Copyright (c) 2021 Nicolau Dionísio Fares Gualda, Fábio Emanuel Souza Morais, Daniel Jorge Caetano

Creative Commons License

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.