Demand based optimization for airline industry and load balancing
Modèles de demande et optimisation du programme des vols d'une compagnie aérienne et problème d'équilibrage de charges
Résumé
This thesis develops optimization methods applied in the airline industry, and has been conducted in collaboration with Air France. This partnership falls within a scientific chair between Air France and École des Ponts ParisTech. In this thesis we explore several research topics, namely aircraft routing, revenue estimation and optimization, and load balancing problems (which is not related to a problem linked with the airline industry).We introduce an aircraft routing problem which aims at building routes for the planes of the company. Those routes need to verify two main types of operational constraints: frequency constraints and gate constraints. The frequency constraints ensure that the different origin-destinations the company wants to serve are effectively served. The gate constraints form a new kind of constraints that arise because of the increase in plane traffic at the hub of the company. This increase has made the number of gate slots available at the hub a limiting constraint, which we take into account in our model. We show that the problem considered is NP-hard, and propose a mixed integer linear program to generate solutions efficiently.The revenue evaluation method used in such scheduling problems is usually leg-based, in the sense that an expected revenue by flight leg is defined. The revenue estimation is the sum of theses expected revenues on the flights operated. This method is an approximation since the revenues of a company are actually generated by the sales of tickets for itineraries, which are formed by successions of legs. We study a stochastic itinerary-based revenue model that aims at evaluating quickly the revenue generated by a schedule. We show that this model can be approximated as a linear program already known in the literature as the Sales Based Linear Program (SBLP). We propose a column generation based on the Dantzig--Wolfe reformulation of the SBLP that performs very well in practice. We also study the convergence of the stochastic model and show that it happens at an exponential rate.We also present a model that solves the aircraft routing with an itinerary-based revenue. The considered problem can be seen as joining the aircraft routing problem with frequency and gate constraints and the SBLP. Given the size and the structure of the problem, we propose a Benders decomposition method to solve it. We develop an advanced method that takes advantage of the column generation method used to solve the SBLP, to generate cuts for the Benders decomposition.Finally, this thesis has also been the opportunity to study some problems, independently of the research in the airline industry. We develop some theoretical results on load-balancing problems. Those problems aim at sharing ``fairly'' tasks among workers. We show that several ``fair'' objective functions are closely related. More particularly, we show that solving the problem with one of the objectives considered provides a solution for the other problems. We also generalize and extend these results to similar problems.Keywords: operations research, aircraft routing, revenue management, Dantzig-Wolfe decomposition, Benders decomposition, mixed-integer linear programming, load balancing.
Cette thèse développe des méthodes d'optimisation appliquées à l'industrie aérienne. Elle a été menée en collaboration avec Air France dans le cadre d'une chaire scientifique entre Air France et l'École des Ponts ParisTech. Cette thèse explore plusieurs sujets de recherches : la planification des programmes de vols, l'estimation et l'optimisation des revenus générés par ces plannings et l'équilibrage de charges de travail. Nous introduisons un problème de planification de programme de vols qui cherche à construire des routes pour les différents avions de la compagnie. Ces routes doivent principalement respecter deux contraintes opérationnelles~: une contrainte de fréquence et une contrainte de portes. La contrainte de fréquence s'assure que les différentes origines-destinations proposées par la compagnie sont effectivement desservies. La contrainte de portes s'inscrit dans une nouvelle classe de contraintes introduite en raison de l'augmentation du trafic aérien dans le hub de la compagnie. Cette augmentation a rendu essentielle la prise en compte du nombre limité de portes (pour l'embarquement et le débarquement des passagers) disponibles au hub, ce que l'on veut donc inclure dans le modèle. Nous prouvons que le problème ainsi considéré est NP-complet et nous proposons un programme linéaire en nombres entiers capable de trouver une solution efficacement. Les méthodes d'évaluation du revenu d'un planning de vols sont souvent approchées par une combinaison linéaire des revenus estimés pour chaque vol. Cette façon de faire est approximative puisque le revenu d'une compagnie est en réalité généré par la vente de billets associés à des itinéraires (formés d'une succession de vols). Nous étudions donc un modèle stochastique de revenu basé sur la vente d'itinéraires, qui vise à estimer rapidement le revenu généré par un planning de vols. Nous prouvons que ce modèle peut être approché par un autre problème connu dans la littérature sous le nom de "Sales Based Linear Program" (SBLP). Pour trouver une solution à ce problème, nous proposons d'utiliser une génération de colonnes basée sur sa reformulation de Dantzig-Wolfe. Cette méthode se révèle être très efficace en pratique. Nous étudions aussi l'arrivée dynamique des passagers, qui est utilisée pour l'estimation de revenu, et sa convergence vers une dynamique fluide approchée. Nous montrons qu'il existe une convergence exponentielle de l’espérance du nombre d'achats de billet vers la valeur donnée par la dynamique fluide quand la taille du problème augmente. Nous présentons également un modèle qui optimise le planning des vols avec une estimation des revenus basée sur la vente d'itinéraires. Au vu de la taille et de la structure du problème, nous utilisons une décomposition de Benders pour résoudre celui-ci. Afin de tirer parti de la génération de colonnes utilisée pour résoudre le SBLP, nous développons une méthode avancée pour générer des coupes de Benders. Pour finir, cette thèse a aussi été l'occasion d'étudier d'autres problèmes, indépendamment de ceux traités dans le monde de l'aérien. Ainsi, nous avons obtenu des résultats théoriques concernant des problèmes d'équilibrage de charges de travail. Ces problèmes cherchent à partager de façon "équitable" le temps passé sur différentes tâches entre des travailleurs. Nous prouvons que différents critères équitables sont étroitement liés. Plus précisément, nous montrons que résoudre le problème posé avec une fonction objectif particulière donne une solution pour d'autres fonctions objectif. Nous généralisons et étendons ces résultats à des problèmes similaires.
Origine : Version validée par le jury (STAR)