Methodes de decomposition pour la planification integree des itineraires d'avions et des horaires d'equipages

The integrated aircraft routing and crew scheduling problem consists in determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied. While some side constraints involve only crews or aircraft, linking constraints impose minimum connection times for crews that depend on aircraft connections. More precisely, a connection that is not long enough to be made by a crew when the two associated legs are flown by different aircraft is said to be short. Hence, a model that integrates the aircraft routing and the crew pairing formulations must also include one linking constraint for each possible short connection.; In the first part of the thesis, after formally defining the problem, we present a review of the literature on optimization models to individually address fleet assignment, aircraft routing and crew scheduling. We then review some models that integrate some of the airline planning problems.; In the second part, we propose an enhanced model incorporating robustness to handle the short connection linking constraints and compare two Benders decomposition methods - one with the aircraft routing problem as the master problem and one with the crew pairing problem. A solution is said to be more robust when disruptions on the day of operations are less likely to delay the flights following the unforeseen event. We also study the impact of generating Pareto-optimal cuts on the speed of convergence of these methods. Computational experiments performed on test instances provided by two major airlines show that the proposed approach with the crew pairing problem as the Benders master problem yields high quality solutions in reasonable computing times and is clearly superior than the one with the aircraft routing problem as the master problem.; In the third part, we consider an additional level of integration by adding some flight scheduling decisions to the integrated aircraft routing and crew scheduling problem. In this integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Here, linking constraints ensure that the same schedule is chosen for both the aircraft routes and the crew pairings, and impose minimum connection times for crews that depend on aircraft connections and departure times. We propose a compact formulation of the problem and a Benders decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments performed on test instances provided by two major airlines show that allowing some flexibility on the departure times within an integrated model yields significant cost savings while ensuring the feasibility of the resulting aircraft routes and crew pairings.; When Benders decomposition is used with the crew pairing problem as the Benders master problem, the aircraft routing subproblem is, in fact, generating feasibility cuts that are added to the Benders crew pairing master problem. To solve the integrated aircraft routing and crew scheduling problem, one can also solve a constrained crew pairing problem iteratively, by adding feasibility cuts from a predefined family to the crew pairing problem until a solution is found where the short connection set used is maintenance feasible for the aircraft. In the last part of the thesis, we perform an in-depth theoretical comparison of different types of feasibility cuts for the integrated aircraft routing and crew scheduling problem. We also propose a simple procedure to strengthen these cuts. Computational experiments performed on test instances provided by two major airlines are presented to support the theoretical results.