Airline crew scheduling under uncertainty

Airline crew scheduling is an extremely challenging large-scale logistics problem; there are no known methods to solve reasonably-sized instances. The vast majority of crew scheduling models use the planned cost of a crew schedule to measure its quality, which is a lower bound on the actual compensation an airline must pay pilots. We propose to measure the quality of a crew schedule by its cost in operations. Finding an optimal crew schedule under operations would involve solving an intractable large-scale stochastic and dynamic optimization problem. Instead, we propose several heuristics for this problem which replace the planned cost in the optimization methodology by costs which reflect operational considerations. One of these heuristics uses the expected cost of a pairing as its cost. We consider three fleets, and for each fleet this heuristic performs better than the traditional methodology. We give an approximate lower bound for the optimal solution to the stochastic optimization problem, and for two of these fleets our heuristic reduces the gap relative to this lower bound by at least 50%. We propose a method for perturbing the scheduled departure and arrival times of various legs to improve operational performance. We solve an integer program to give a best schedule perturbation while ensuring that the planned crew cost does not increase, and the plane, crew and passenger connections are maintained. We show that for any crew schedule perturbing the departure and arrival times can improve the operational crew cost as well as the on-time percentage.