We propose a common solution approach for different crew scheduling problems arising at the planning and operational levels in the airline industry. Specifically, the paper deals with crew pairing generation, crew rostering problems, preferential bidding problems, and the problem of repairing monthly work schedules during the operation. We first provide a formulation based on the Set Partitioning Problem where each column represents either a crew pairing or a crew member schedule. Given the large size of these real-world problems, we then suggest an optimization approach based on column generation in which the subproblem is shown to be a constrained shortest path problem on an associated graph. We finally report computational results obtained on a series of real-world problems that confirm both the computational efficiency and the practical applicability of this approach. We will discuss the particular difficulties of each type of problem and ways of overcoming these difficulties.
Published May 1997 , 20 pages
This cahier was revised in November 1997