Airline Planning under Uncertainty.

Abstract

In this dissertation, we study the impact of uncertainty associated with potential delays on the operational performance of the airline plans, considering different stages of the airline planning process. In the first part of this dissertation, we investigate the potential for flight delays to propagate throughout a passenger airline network. We also define metrics to quantify delay propagation by analyzing the connections in a flight network. As the computational results demonstrate, delays can sometimes propagate substantially and have a major impact on network efficiency. Therefore, in the second part, we develop a linear programming approach to strategically use slack in the network in order to mitigate the impact of disruption without increasing cost. In these models we allow flight departure times to change within a given time window while keeping the original connections feasible but re-allocating slack where it can best be utilized. The motivation for the third part of this dissertation stems from the fact that re-timing the schedule per se cannot fully capture all the opportunities for improved robustness. Instead, it may also be necessary to change the fleet assignment and crew schedule. Thus, in a robust planning tool, it is necessary to schedule flights across all fleet-types simultaneously. This, in turn, increases the number of flights to be considered which dramatically impacts tractability. Therefore, it is essential to generate crew pairings (sequences of flights that can be covered by a single crew) on larger flight networks. In the third part, we present a new, integer programmingbased approach to supplement the existing techniques for generating crew pairings. To demonstrate the performance of this approach, computational experiments based on data from a major U.S. carrier are presented.