Column generation and polyhedral combinatorics for airline crew scheduling

The airline crew scheduling problem is generally characterized by a set of scheduled flights and a set of rules governing the use of crews on those flights. The objective of the crew scheduling problem is to assign one crew to each scheduled flight leg such that the overall cost is minimized and all crew restrictions are satisfied. This thesis proposes and investigates the use of delayed column generation and polyhedral combinatorics as tools to drive towards an optimal solution to the airline crew scheduling problem.;Chapter 3 includes experimental data justifying the use of an extreme path approximation as a column generating tool. It is first compared to an exact solution of the bicriterion shortest path problem and then to a more traditional column generation approach. In certain cases we are able to improve the actual solution value by as much as 20% over standard techniques for this problem.;Chapter 4 discusses the interaction of column generation and polyhedral combinatorics in crew optimization by incorporating the column generation approach into a simple cutting plane process.;In Chapter 5, the model is better tuned to the airline operation by incorporating the airline's operational staffing limits, known as base constraints. We propose and develop the use of Lagrangian multipliers to relax these complicating constraints. Through extensive computational testing we demonstrate superiority of this approach over existing branch-and-bound and branch-and-cut methods on a variety of airline crew scheduling problems with base constraints.;In Chapter 2, linear programming duality is used to define a master problem and a subproblem in the crew scheduling context. The master problem performs repeated optimization of the crew schedule over some subset of crew pattern columns and provides the subproblem with information about missing data which could improve the solution value. The subproblem's task is crew pattern column generation, which is formulated as a bicriterion shortest path problem and subsequently solved with an extreme path approximation.