The aviation industry represents approximately 3% of global greenhouse gas emissions, however with significant growth expected over the coming decades this proportion is expected to increase. Continued governmental and social pressure to reduce global emissions is posing a challenging question to the industry; how to improve environmental efficiency and reduce emissions with increasing industry growth. The environmental impact of aviation globally is discussed, examining the significant emissions and protocols that exist and their relative impacts both environmentally and economically. The viability of alternative biofuels is discussed, determining the life cycle environmental impact of future replacements to kerosene based jet fuel. This thesis therefore aims to provide an understanding of the fundamentals of aviation emissions but also most importantly provide possible solutions to assist the industry in reducing its emissions ‘footprint’. An important factor in determining efficiency improvements is to understand the impact of particular stages of an aircraft life and the impact they have individually. This was achieved using an established methodology called Life Cycle Assessment (LCA), which is an efficient tool for the analytical consideration of the environmental impact of manufacturing, operation and decommissioning. The results of a comprehensive LCA study of an Airbus A320 are documented considering all phases of the service life. The study draws useful conclusions, indicating the significance of special materials such as carbon fibre reinforced plastic (CFRP) on the total manufacturing emissions of the aircraft and indicating its operational phase as the one contributing most in its environmental performance breakdown. The thesis also examines short-term efficiencies for emissions reduction in commercial aviation, focussing on improvements in aircraft routing. The initiation of the EU emissions trading system (ETS) within European aviation willincentivise airlines to reduce their annual CO2 emissions. An alternative routing strategy is proposed for selected long haul routes, which introduces multiple stages into the route utilising two aircraft and is shown to reduce total CO2 emissions by up to 13.7%. Combined with blended biofuel, this reduction was estimated to increase to 16.6% with a reduction in ticket fares estimated to be as high as $19 per passenger per flight.

Cette thèse développe des algorithmes pour les problèmes de plus court chemin sous cont-rain-tes de ressources, et les applique à l'optimisation des rotations des avions et des équipages d'une compagnie aérienne dans le cadre d'approches par génération de colonnes.Les problèmes de plus court chemin sous contraintes de ressources sont généralement résolus grâce à une énumération intelligente de tous les chemins non dominés. Les approches récentes utilisent des bornes sur les ressources des chemins pour éliminer des solutions partielles. L'efficacité de la méthode est conditionnée par la qualité des bornes utilisées. Notre principale contribution au domaine est l'introduction d'une procédure générique pour calculer des bornes qui s'applique à la plupart des problèmes de chemins sous contraintes, et en particulier les problèmes stochastiques. A cette fin, nous introduisons une généralisation du problème de plus court chemin sous contraintes dans laquelle les ressources des chemins appartiennent à un monoïde ordonné comme un treillis. La ressource d'un chemin est la somme des ressources de ses arcs, le terme somme désignant l'opérateur du monoïde. Le problème consiste à trouver parmi les chemins qui satisfont une contrainte donnée celui dont la ressource minimise une fonction de coût croissante de la ressource des chemins. Nous généralisons les algorithmes d'énumération à ce nouveau problème. La théorie des treillis nous permet de construire une procédure polynomiale pour trouver des bornes de qualité. L'efficacité pratique de la méthode est évaluée au travers d'une étude numérique détaillée sur des problèmes de chemins déterministes et stochastiques. Les procédures de calcul des bornes peuvent être interprétées comme des généralisations aux monoïdes ordonnés comme des treillis d'algorithmes de la littérature définis pour résoudre un problème de chemin pour lequel les ressources des chemins prennent leur valeur dans un semi-anneau.Nos algorithmes de chemins ont été appliqués avec succès au problème de crew pairing. Étant donné un ensemble de vols opérés par une compagnie aérienne, les problèmes d'aircraft routing et de crew pairing construisent respectivement les séquences de vols opérées par les avions et par les équipages de manière à couvrir tous les vols à moindre coût. Comme certaines séquences de vols ne peuvent être réalisées par un équipage que s'il reste dans le même avion, les deux problèmes sont liés. La pratique actuelle dans l'industrie aéronautique est de résoudre tout d'abord le problème d'aircraft routing, puis le problème de crew pairing, ce qui aboutit à une solution non-optimale. Des méthodes de résolution pour le problème intégré ont été développées ces dix dernières années. Nous proposons une méthode de résolution pour le problème intégré reposant sur deux nouveaux ingrédients : un programme linéaire en nombre entier compact pour le problème d'aircraft routing, ainsi que de nouveaux pour le problème esclave de l'approche usuelle par génération de colonnes du problème de crew pairing. Ces algorithmes pour le problème esclave sont une application de nos algorithmes pour le problème de plus court chemin sous contraintes. Nous généralisons ensuite cette approche de manière à prendre en compte des contraintes de probabilités sur la propagation du retard. Ces algorithmes permettent de résoudre quasiment à l'optimum les instances industrielles d'Air France / This thesis develops algorithms for resource constrained shortest path problems, and uses them to solve the pricing subproblems of column generation approaches to some airline operations problems.Resource constrained shortest path problems are usually solved using a smart enumeration of the non-dominated paths. Recent improvements of these enumeration algorithms rely on the use of bounds on path resources to discard partial solutions. The quality of the bounds determines the performance of the algorithm. Our main contribution to the topic is to introduce a standard procedure to generate bounds on paths resources in a general setting which covers most resource constrained shortest path problems, among which stochastic versions. In that purpose, we introduce a generalization of the resource constrained shortest path problem where the resources are taken in a lattice ordered monoid. The resource of a path is the monoid sum of the resources of its arcs. The problem consists in finding a path whose resource minimizes a non-decreasing cost function of the path resource among the paths that satisfy a given constraint. Enumeration algorithms are generalized to this framework. We use lattice theory to provide polynomial procedures to find good quality bounds. The efficiency of the approach is proved through an extensive numerical study on deterministic and stochastic path problems. Interestingly, the bounding procedures can be seen as generalizations to lattice ordered monoids of some algebraic path problem algorithms which initially work with resources in a semiring.Given a set of flight legs operated by an airline, the aircraft routing and the crew pairing problem build respectively the sequences of flight legs operated by airplanes and crews at minimum cost. As some sequences of flight legs can be operated by crews only if they stay in the same aircraft, the two problems are linked. The current practice in the industry is to solve first the aircraft routing, and then the crew pairing problem, leading to a non-optimal solution. During the last decade, solution schemes for the integrated problem have been developed. We propose a solution scheme for the integrated problem based on two new ingredients: a compact integer program approach to the aircraft routing problem, and a new algorithm for the pricing subproblem of the usual column generation approach to the crew pairing problem, which is based on our resource constrained shortest path framework. We then generalize the algorithm to take into account delay propagation through probabilistic constraints. The algorithms enable to solve to near optimality Air France industrial instances

Made available in DSpace on 2015-05-14T12:36:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 709171 bytes, checksum: 7408941a22a7c3807f1588fecdcfd70c (MD5) Previous issue date: 2012-03-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Operational research problems has growing in complexity in the last years, this has accentuated the necessity to develop of techniques witch can accelerate the process of decision making. This work covers the step of aircraft rotation problem, i.e., the sequencing of flights for each aircraft. The goal here is minimize the number of aircraft required to operate a given network of flights. This problem is combinatorial and it resolution is more difficult when the number of involved flights grows. However small changes in departure time, or the addition of a repositioning flight between two nearby airports can reduce the cost of solutions. We present a hybrid algorithm based on the metaheuristic GRASP, using the ILS and integer programing in the local search. The results has shown which this approach can generate good solutions. / Os problemas operacionais cresceram muito em complexidade nos últimos tempos, o que tem acentuado a necessidade do desenvolvimento de técnicas que possam agilizar os processos de tomada de decisão. Este trabalho trata da etapa de geração dos trilhos de aeronaves, ou seja, o sequenciamento de voos de cada aeronave. O objetivo aqui é minimizar o número de aeronaves necessárias para operar uma dada malha de voos. Esse problema possui é combinatoriamente explosivo e a sua resolução fica mais difícil à medida que a quantidade de voos envolvidos cresce. Pequenas modificações nos horários de partida desses voos, ou o acréscimo de algum voo de resposicionamento entre dois aeroportos próximos podem gerar soluções de melhor qualidade. Nós apresentamos um algoritmo híbrido baseado na metaheurística GRASP, com a utilização do ILS e de programação inteira na busca local. Os resultados tem mostrado que essa abordagem é capaz de gerar boas soluções.

Fractional aircraft ownership programs offer companies and individuals all the benefits of owning private jet, such as safety, consistency, and guaranteed availability, at a fraction of the cost of owning an aircraft. In the fractional ownership model, the partial owners of an aircraft are entitled to certain number of hours per year, and the management company is responsible for all the operational considerations and making sure an aircraft is available to the owners at the requested time and location. This thesis research proposes advance optimization techniques to help the management company to optimally operate its available resources and provides tools for strategic decision making. The contributions of this thesis are: (i) The development of optimization methodologies to assign and schedule aircraft and crews so that all flight requests are covered at the lowest possible cost. First, a simple model is developed to solve the crew pairing and aircraft routing problem with column generation assuming that a crew stays with one specific aircraft during its duty period. Secondly, this assumption is partially relaxed to improve resource utilization by revising the simple model to allow a crew to use another aircraft when its original aircraft goes under long maintenance. Thirdly, a new comprehensive model utilizing Benders decomposition technique and a fleet-station time line is proposed to completely relax the assumption that crew stays with one specific aircraft. It combines the fleet assignment, aircraft routing, and crew pairing problems. In the proposed methodologies, real world details are taken into consideration, such as crew transportation and overtime costs, scheduled and unscheduled maintenance effects, crew rules, and the presence of non-crew-compatible fleets. Scheduling with time windows is also discussed. (ii) The analysis of operational strategies to provide decision making support. Scenario analyses are performed to provide insights on improving business profitability and aircraft availability, such as impact of aircraft maintenance, crew swapping, effect of increasing demand by Jet-card and geographical business expansion, size of company owned aircraft, and strategies to deal with the stochastic feature of unscheduled maintenance and demand.

Целью исследования является совершенствование инструментария повышения эффективности деятельности авиакомпаний в сфере региональных воздушных перевозок. Предложен методический подход к повышению эффективности региональных воздушных перевозок, элементами которого являются выработка стратегических решений по совершенствованию структуры парка воздушных судов, тактических решений по их распределению по маршрутам региональных перевозок, обоснование направлений совершенствования системы полетного сервиса и методическое обеспечение этих элементов. Предложенные автором рекомендации позволяют повысить эффективность деятельности авиакомпаний в сфере региональных воздушных перевозок. / The aim of the work is to improve the instruments of operational efficiency in the regional airlines. Methods to improving operational efficiency in the regional airlines consist of the development of strategic solutions to improve air fleet efficiency, tactical decisions of aircraft routing on regional air traffic, the rationale for the flight services improvement and methodological support of these elements. The author’s methods make it possible to improving operational efficiency in the regional airlines.

The air transportation market has been growing steadily for the past three decades since the airline deregulation in 1978. With competition also becoming more intense, airline companies have been trying to enhance their market shares and profit margins by composing favorable flight schedules and by efficiently allocating their resources of aircraft and crews so as to reduce operational costs. In practice, this is achieved based on demand forecasts and resource availabilities through a structured airline scheduling process that is comprised of four decision stages: schedule planning, fleet assignment, aircraft routing, and crew scheduling. The outputs of this process are flight schedules along with associated assignments of aircraft and crews that maximize the total expected profit. Traditionally, airlines deal with these four operational scheduling stages in a sequential manner. However, there exist obvious interdependencies among these stages so that restrictive solutions from preceding stages are likely to limit the scope of decisions for succeeding stages, thus leading to suboptimal results and even infeasibilities. To overcome this drawback, we first study the aircraft routing problem, and develop some novel modeling foundations based on which we construct and analyze an integrated model that incorporates fleet assignment, aircraft routing, and crew pairing within a single framework. Given a set of flights to be covered by a specific fleet type, the aircraft routing problem (ARP) determines a flight sequence for each individual aircraft in this fleet, while incorporating specific considerations of minimum turn-time and maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenance operations. This stage is significant to airline companies as it directly assigns routes and maintenance breaks for each aircraft in service. Most approaches for solving this problem adopt set partitioning formulations that include exponentially many variables, thus requiring the design of specialized column generation or branch-and-price algorithms. In this dissertation, however, we present a novel compact polynomially sized representation for the ARP, which is then linearized and lifted using the Reformulation-Linearization Technique (RLT). The resulting formulation remains polynomial in size, and we show that it can be solved very efficiently by commercial software without complicated algorithmic implementations. Our numerical experiments using real data obtained from United Airlines demonstrate significant savings in computational effort; for example, for a daily network involving 344 flights, our approach required only about 10 CPU seconds for deriving an optimal solution. We next extend Model ARP to incorporate its preceding and succeeding decision stages, i.e., fleet assignment and crew pairing, within an integrated framework. We formulate a suitable representation for the integrated fleeting, routing, and crew pairing problem (FRC), which accommodates a set of fleet types in a compact manner similar to that used for constructing the aforementioned aircraft routing model, and we generate eligible crew pairings on-the-fly within a set partitioning framework. Furthermore, to better represent industrial practice, we incorporate itinerary-based passenger demands for different fare-classes. The large size of the resulting model obviates a direct solution using off-the-shelf software; hence, we design a solution approach based on Benders decomposition and column generation using several acceleration techniques along with a branch-and-price heuristic for effectively deriving a solution to this model. In order to demonstrate the efficacy of the proposed model and solution approach and to provide insights for the airline industry, we generated several test instances using historical data obtained from United Airlines. Computational results reveal that the massively-sized integrated model can be effectively solved in reasonable times ranging from several minutes to about ten hours, depending on the size and structure of the instance. Moreover, our benchmark results demonstrate an average of 2.73% improvement in total profit (which translates to about 43 million dollars per year) over a partially integrated approach that combines the fleeting and routing decisions, but solves the crew pairing problem sequentially. This improvement is observed to accrue due to the fact that the fully integrated model effectively explores alternative fleet assignment decisions that better utilize available resources and yield significantly lower crew costs. / Ph. D.