Mat-heurística para recuperação de malhas aéreas considerando aeronaves e passageiros
DOI:
https://doi.org/10.14295/transportes.v29i2.2166Palavras-chave:
Recuperação integrada de malha aérea, Perturbações em malhas aéreas, Mat-heurísticaResumo
O problema de recuperação da operação de companhia aérea impactada por uma interrupção envolve as malhas de aeronaves, de tripulantes e de passageiros. Modelos para resolvê-lo consideram uma ou mais dessas malhas, de forma integrada ou não. O problema é da classe NP hard, mesmo para apenas uma malha. Este trabalho apresenta uma heurística matemática para resolver o problema integrando as malhas da aeronaves e de passageiros, além de um modelo para restaurar a malha de aeronaves com custo mínimo. Esses dois modelos permitem avaliar o impacto da inclusão da malha de passageiros nos custos de recuperação. Os modelos foram testados com instâncias reais da ROADEF usando um microcomputador Intel i7 (16Gb de RAM) e um servidor de alto desempenho (HPC) com 512 GB de RAM. O microcomputador resolveu instâncias com até 85 aeronaves e 276 voos em menos de 30 minutos (limite imposto). O HPC resolveu as instâncias maiores com mínimum gap de 0 a 0,7%. Os custos da recuperação integrada foram muito próximos dos obtidos para a malha de aeronaves, com uma inesperada compensação de custos, o que destaca a importância de resolver o problema de recuperação integrando as malhas de aeronaves e de passageiros.
Downloads
Referências
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
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2021 Jose Carlos Fontoura Guimaraes, Nicolau Dionísio Fares Gualda
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:
- Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
- Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
- Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
- Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
- Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
- Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
