Submitted by Maike Costa (maiksebas@gmail.com) on 2016-04-25T13:32:58Z No. of bitstreams: 1 arquivo total.pdf: 4525999 bytes, checksum: 439ef786ba011b8d141d0b5a92537aa3 (MD5) / Made available in DSpace on 2016-04-25T13:32:58Z (GMT). No. of bitstreams: 1 arquivo total.pdf: 4525999 bytes, checksum: 439ef786ba011b8d141d0b5a92537aa3 (MD5) Previous issue date: 2015-05-28 / The airlines that operate regular ights de ne in advance the airports to be operated and the landing and takeo schedule of its aircraft. This scheduling is likely to su er interruptions causing nancial losses due to delays and/or cancellations of ights. In these situations, the airlines usually use the experience of their professionals and seek to minimize the impacts by relocating the aircraft, crew and then passengers. There is no guarantee that such method will lead to good results from an economic point of view, especially in periods of high demands of passengers. Due to this di culty, several authors have studied the Airline Recovery Problem using di erent optimization techniques. This problem is basically composed of three sub-problems: Aircraft Recovery Problem (ARP), Crew Recovery Problem (CRP) and Passenger Recovery Problem (PRP). In order to de- ne the new least-cost aircraft scheduling of a Brazilian airline (in operation interruption situations) due to delays and/or cancellations of ights, this research presents an ARP solution proposal starting from the representation of ights through a network time-space and mathematical modeling analogous to the minimum cost ow problem. To analyze the ARP, data was used from a Brazilian airline for building the time-space networks with bands of 30, 20 and 15 minutes, and 100 instances were utilized to simulate the unavailability of up to 3 aircraft on di erent nodes of such networks. The solutions based on these bands were solved via Integer Linear Programming and with average improvements of 38.24%, 40.44% and 41.15%, respectively, with respect to the trivial solutions. The band of 15 min was more appropriate because it provided a more realistic analysis of takeo s and landings events and resulted in a greater di erence, on average, between the optimal solutions and the trivial ones. Other 95 instances were tested for a time-space network with 15 min band and a spare aircraft located at the busiest airport. In this case the results were 38.68% better than the situation without a spare aircraft, but it was not conclusive because an economic feasibility analysis on the acquisition and deployment of a new aircraft in the eet must be performed. / As companhias a ereas de voos regulares possuem previamente de nidos os aeroportos que ser~ao operados, os dias e os hor arios de pouso e decolagem das suas aeronaves. E poss vel que essa programa c~ao sofra interrup c~oes e causem preju zos nanceiros devido aos atrasos e/ou cancelamentos dos voos. Nessas situa c~oes, normalmente as companhias a ereas usam a experi^encia dos seus pro ssionais e procuram minimizar os impactos realocando as aeronaves, tripulantes e em seguida os passageiros. N~ao h a garantia que esse m etodo retorne um bom resultado do ponto de vista econ^omico, sobretudo em per odos de grande demanda por passageiros. Mediante essa di culdade, diversos autores t^em estudado o Airline Recovery Problem empregando diferentes t ecnicas de otimiza c~ao. Esse problema e composto basicamente por tr^es subproblemas: Aircraft Recovery Problem (ARP), Crew Recovery Problem (CRP) e Passenger Recovery Problem (PRP). Como forma de de nir o novo sequenciamento das aeronaves de uma companhia a erea brasileira que, em situa c~oes de interrup c~oes das opera c~oes, resulte no menor custo devido aos atrasos e/ou cancelamentos dos voos, esta pesquisa apresenta uma proposta de solu c~ao do ARP a partir da representa c~ao dos voos por uma rede tempo-espa co e modelagem matem atica an aloga ao problema do uxo de custo m nimo. Para a an alise do ARP, foram utilizados dados de uma companhia a erea brasileira para a constru c~ao das redes tempo-espa co com bandas de 30, 20 e 15 minutos e empregadas 100 inst^ancias que simularam a indisponibilidade de at e 3 aeronaves em diferentes n os dessas redes. As solu c~oes baseadas nessas bandas foram resolvidas via Programa c~ao Linear Inteira e apresentaram resultados m edios, respectivamente, 38; 24%; 40; 44% e 41; 15% melhores do que as solu c~oes triviais. A banda de 15 min mostrou-se mais adequada porque possibilitou uma an alise mais realista dos eventos de pousos e decolagens e resultou numa diferen ca m edia maior entre as solu c~oes otimas e as triviais. Outras 95 inst^ancias foram testadas para uma rede tempo-espa co com banda de 15 min e aeronave reserva localizada no aeroporto de maior movimento. O resultado foi 38; 68% melhor do que a situa c~ao sem aeronave reserva, mas n~ao conclusivo por ser necess aria uma an alise de viabilidade econ^omica sobre a aquisi c~ao e disponibiliza c~ao de uma nova aeronave na frota.

Perturbações na malha aérea ocorrem em todo o mundo e afetam econômica e operacionalmente as empresas aéreas. Em 2016, os gastos que essas perturbações causaram às empresas aéreas e aos seus clientes giraram em torno de US$60 bilhões, cerca de 8% da receita de todas as empresas aéreas do mundo. Este trabalho apresenta uma Heurística Matemática Híbrida, envolvendo otimização por programação inteira mista, para resolver o Problema da Recuperação da Malha Aérea de uma empresa, em até vinte minutos, para uso do Centro de Controle Operacional (CCO) da empresa aérea. A solução consiste em uma nova programação de voos que minimiza os custos da alteração da malha aérea e atenda as restrições impostas por um cenário de múltiplas perturbações, quais sejam: atrasos, cancelamentos de voos, fechamento ou redução de capacidade aeroportuária e manutenções não-programadas. Além da heurística, apresenta-se também um modelo de fluxo em rede com programação inteira para resolver de forma exata o Problema da Recuperação da Malha. Esse modelo obteve resultados em instância de até 500 voos, para todo tipo perturbação, em tempo de execução razoável, exceto para as instâncias em que a capacidade aeroportuária estava muito comprometida. A heurística matemática híbrida apresentou resultados com diferenças de até 5% com relação ao ótimo para as instâncias com até 6000 voos, independentemente do nível de perturbação imposta à malha aérea, com tempo de execução que permite o seu uso prático. / Schedule disruptions occurs worldwide and affect economically and operationally the airlines. In 2016, disruptions cost airlines and their customers around $60 billion, or about 8% of worldwide airline revenue. In this thesis, a Hybrid Math-Heuristic including a mixed-integer linear optimization is presented. It is aimed at assisting airlines to solve the Aircraft Recovery Problem through their Operations Control Centers (OCC) in up to twenty minutes. The solution consists in a new changed schedule that minimizes the cost of changes and deals with constraints related to a scenario with multiple disruptions: delays, flight cancelations, closures or airport capacity reduction and non-scheduled maintenance. Besides the heuristic, a network flow integer programming model is presented to provide exact solutions to the Aircraft Recovery Problem. The Exact Model achieved optimal results for instances with up to 500 flights subjected to all kinds of disruptions in reasonably times, except for instances with highly constrained airport capacity. The Hybrid Math-Heuristic achieved results with maximum optimal GAP of up to 5% for instances with up to 6.000 flights, no matter the level of the imposed disruption, with time of execution that permits its use in practice.