Skip to Main content Skip to Navigation

Demand based optimization for airline industry and load balancing

Abstract : 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.
Document type :
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Monday, April 4, 2022 - 4:49:19 PM
Last modification on : Monday, May 16, 2022 - 6:44:22 PM
Long-term archiving on: : Tuesday, July 5, 2022 - 8:09:46 PM


Version validated by the jury (STAR)


  • HAL Id : tel-03629986, version 1



Sébastien Deschamps. Demand based optimization for airline industry and load balancing. Optimization and Control [math.OC]. École des Ponts ParisTech, 2021. English. ⟨NNT : 2021ENPC0029⟩. ⟨tel-03629986⟩



Record views


Files downloads