Modelo e heurística matemática híbrida para o problema da recuperação de malha aérea

Autores

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

DOI:

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

Palavras-chave:

Programação de voos, Problema de recuperação, Heurística matemática, Programação linear, Fluxo em rede multiproduto

Resumo

O problema de recuperação de malha aérea surge quando eventos inesperados como tempestades, fechamento de aeroportos e manutenção não programada de aeronaves provocam atrasos e/ou cancelamento de voos, inviabilizando o cumprimento da programação original da aeronave. Este trabalho inicia pela apresentação de um modelo matemático para a recuperação da programação de uma empresa aérea. Devido à natureza NP-Hard do problema, o modelo matemático não é capaz de resolver grandes instâncias. Tal circunstância levou ao desenvolvimento de uma heurística matemática composta por dois modelos: um modelo de fluxo em rede com programação inteira mista para gerar uma nova programação com o menor número de cancelamentos e atrasos de voos; e um modelo de programação linear inteira para minimizar as trocas de aeronaves associadas aos voos com relação à programação original. São apresentadas aplicações da heurística a instâncias com até 470 voos, para as quais se obtém, em menos de um minuto de processamento, soluções que distam menos de 0,5% das soluções ótimas, o que permite concluir que a heurística se qualifica para aplicações em casos reais de magnitude considerável.

Downloads

Não há dados estatísticos.

Referências

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

Publicado

22-11-2021

Como Citar

de Souza Morais, F. E. ., Gualda, N. D. F. ., & Caetano, D. J. (2021). Modelo e heurística matemática híbrida para o problema da recuperação de malha aérea. TRANSPORTES, 29(4), 2234. https://doi.org/10.14295/transportes.v29i4.2234