The Column Generation Principle And The Airline Crew Scheduling Problem

Abstract

The generation and selection of a good set of pairings is a complex, costly and very central part of the airline crew scheduling process. We propose a column-generating type algorithm which, based on reduced costs manipulations, finds such a good set of pairings, namely the set containing the optimal solution to the linear relaxation of the set covering formulation of the problem.