Perhaps no single industry has benefited more from advancements in computation, analytics, and optimization than the airline industry. Operations Research (OR) is now ubiquitous in the way airlines develop their schedules, price their itineraries, manage their fleet, route their aircraft, and schedule their crew. These problems, among others, are well-known to industry practitioners and academics alike and arise within the context of the planning environment which takes place well in advance of the date of departure. One salient feature of the planning environment is that decisions are made in a frictionless environment that do not consider perturbations to an existing schedule. Airline operations are rife with disruptions caused by factors such as convective weather, aircraft failure, air traffic control restrictions, network effects, among other irregularities. Substantially less work in the OR community has been examined within the context of the real-time operational environment. While problems in the planning and operational environments are similar from a mathematical perspective, the complexity of the operational environment is exacerbated by two factors. First, decisions need to be made in as close to real-time as possible. Unlike the planning phase, decision-makers do not have hours of time to return a decision. Secondly, there are a host of operational considerations in which complex rules mandated by regulatory agencies like the Federal Administration Association (FAA), airline requirements, or union rules. Such restrictions often make finding even a feasible set of re-scheduling decisions an arduous task, let alone the global optimum. The goals and objectives of this thesis are found in Chapter 1. Chapter 2 provides an overview airline operations and the current practices of disruption management employed at most airlines. Both the causes and the costs associated with irregular operations are surveyed. The role of airline Operations Control Center (OCC) is discussed in which serves as the real-time decision making environment that is important to understand for the body of this work. Chapter 3 introduces an optimization-based approach to solve the Airline Integrated Recovery (AIR) problem that simultaneously solves re-scheduling decisions for the operating schedule, aircraft routings, crew assignments, and passenger itineraries. The methodology is validated by using real-world industrial data from a U.S. hub-and-spoke regional carrier and we show how the incumbent approach can dominate the incumbent sequential approach in way that is amenable to the operational constraints imposed by a decision-making environment. Computational effort is central to the efficacy of any algorithm present in a real-time decision making environment such as an OCC. The latter two chapters illustrate various methods that are shown to expedite more traditional large-scale optimization methods that are applicable a wide family of optimization problems, including the AIR problem. Chapter 4 shows how delayed constraint generation and column generation may be used simultaneously through use of alternate polyhedra that verify whether or not a given cut that has been generated from a subset of variables remains globally valid. While Benders' decomposition is a well-known algorithm to solve problems exhibiting a block structure, one possible drawback is slow convergence. Expediting Benders' decomposition has been explored in the literature through model reformulation, improving bounds, and cut selection strategies, but little has been studied how to strengthen a standard cut. Chapter 5 examines four methods for the convergence may be accelerated through an affine transformation into the interior of the feasible set, generating a split cut induced by a standard Benders' inequality, sequential lifting, and superadditive lifting over a relaxation of a multi-row system. It is shown that the first two methods yield the most promising results within the context of an AIR model.

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.