The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel 'rapid branching' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A column generation approach to airline crew scheduling


    Contributors:


    Publication date :

    2006


    Size :

    6 Seiten, 2 Tabellen, 12 Quellen



    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English




    Airline crew scheduling: a group theoretic approach.

    Thiriez, Hervé, 1944- | DSpace@MIT | 1970

    Free access

    Airline Crew Scheduling Under Uncertainty

    Schaefer, Andrew J. | Online Contents | 2005


    Airline Crew Scheduling Under Uncertainty

    Schaefer, A. J. / Johnson, E. L. / Kleywegt, A. J. et al. | British Library Online Contents | 2005


    Airline Crew Scheduling with Regularity

    Klabjan, D. / Johnson, E. L. / Nemhauser, G. L. et al. | British Library Online Contents | 2001


    Airline Crew Scheduling with Regularity

    Klabjan, Diego | Online Contents | 2001