Groupe d’études et de recherche en analyse des décisions

G-97-26

Crew Scheduling in Air Transportation

, , et

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.

, 20 pages

Ce cahier a été révisé en novembre 1997