Title: Column Generation and the Airline Crew Pairing Problem

The cost of flight crews is the second largest operating cost of an airline. Minimizing it is a fundamental problem in airline planning and operations, and one which has leant itself to mathematical optimization. We discuss several recent advances in the methods used to solve these problems. After describing the general approach taken, we discuss a new method which can be used to obtain approximate solutions to linear programs, dramatically improving the solution time of these problems. This is the so-called volume algorithm. We also describe several other ideas used to make it routinely possible to get very good solutions to these large mixed integer programs.

1991 Mathematics Subject Classification: 90B35, 90C09, 90C10

Keywords and Phrases: linear programming, integer programming, volume algorithm, crew pairing, column generation

Full text: dvi.gz 18 k, dvi 43 k, ps.gz 52 k.

Home Page of DOCUMENTA MATHEMATICA