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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A column generation approach to airline crew scheduling


    Beteiligte:
    Borndörfer, Ralf (Autor:in) / Schelten, Uwe (Autor:in) / Schlechte, Thomas (Autor:in) / Weider, Steffen (Autor:in)


    Erscheinungsdatum :

    2006


    Format / Umfang :

    6 Seiten, 2 Tabellen, 12 Quellen



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch




    Airline Crew Scheduling With Regularity

    Klabjan, D. / Nemhauser, G. / Johnson, E. et al. | British Library Conference Proceedings | 1999


    Airline Crew Scheduling with Regularity

    Klabjan, Diego | Online Contents | 2001


    Airline Crew Scheduling Under Uncertainty

    Schaefer, Andrew J. | 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 Under Uncertainty

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