Combining robustness and recovery for airline schedules

In this thesis, we address different aspects of the airline scheduling problem. The main difficulty in this field lies in the combinatorial complexity of the problems. Furthermore, as airline schedules are often faced with perturbations called disruptions (bad weather conditions, technical failures, congestion, crew illness…), planning for better performance under uncertainty is an additional dimension to the complexity of the problem. Our main focus is to develop better schedules that are less sensitive to perturbations and, when severe disruptions occur, are easier to recover. The former property is known as robustness and the latter is called recoverability. We start the thesis by addressing the problem of recovering a disrupted schedule. We present a general model, the constraint-specific recovery network, that encodes all feasible recovery schemes of any unit of the recovery problem. A unit is an aircraft, a crew member or a passenger and its recovery scheme is a new route, pairing or itinerary, respectively. We show how to model the Aircraft Recovery Problem (ARP) and the Passenger Recovery Problem (PRP), and provide computational results for both of them. Next, we present a general framework to solve problems subject to uncertainty: the Uncertainty Feature Optimization (UFO) framework, which implicitly embeds the uncertainty the problem is prone to. We show that UFO is a generalization of existing methods relying on explicit uncertainty models. Furthermore, we show that by implicitly considering uncertainty, we not only save the effort of modeling an explicit uncertainty set: we also protect against possible errors in its modeling. We then show that combining existing methods using explicit uncertainty characterization with UFO leads to more stable solutions with respect to changes in the noise's nature. We illustrate these concepts with extensive simulations on the Multi-Dimensional Knapsack Problem (MDKP). We then apply the UFO to airline scheduling. First, we study how robustness is defined in airline scheduling and then compare robustness of UFO models against existing models in the literature. We observe that the performance of the solutions closely depend on the way the performance is evaluated. UFO solutions seem to perform well globally, but models using explicit uncertainty have a better potential when focusing on a specific metric. Finally, we study the recoverability of UFO solutions with respect to the recovery algorithm we develop. Computational results on a European airline show that UFO solutions are able to significantly reduce recovery costs.