A stochastic programming formulation of the stochastic crew scheduling problem.

Traditional methods model the billion-dollar airline crew scheduling problem as deterministic and do not explicitly include information on potential disruptions. Unfortunately, the effort used to optimize crew schedules and reduce crew costs is often wasted as flight schedules are frequently disrupted. Consequently, airlines spend a great deal of time and money optimizing crew schedules in the planning phase, eliminating as much waste as possible, only to change and readjust the crew schedules in the operational phase in response to disruptions. Millions of dollars have been invested in this recovery problem. Disruptions are expensive and lead to loss of time, money, and customer goodwill. We wish to integrate the planning problem and the recovery problem. Instead of modeling the crew scheduling problem as deterministic, we consider a stochastic crew scheduling model and devise a solution methodology for integrating disruptions in the evaluation of crew schedules. The goal is to use that information to find robust solutions that better withstand disruptions. Such an approach is important because we can proactively consider the effects of certain scheduling decisions. By identifying more robust schedules, cascading delay effects will be minimized. In this dissertation we describe a stochastic integer programming model for the airline crew scheduling problem. We present a novel two-stage model formulation with recourse where first stage and second stage variable interactions are nonlinear. We offer a branching algorithm to address the nonlinearity. The algorithm identifies expensive flight connections and finds alternative, less expensive solutions. The branching algorithm uses the structure of the problem to branch simultaneously on multiple variables without invalidating the optimality of the algorithm. We present computational results demonstrating the effectiveness of our branching algorithm.PhDApplied SciencesIndustrial engineeringMathematicsOperations researchPure SciencesUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/124302/2/3001073.pd