Abstract The railway crew scheduling problem is to determine an optimal crew assignment for the railway timetable data by minimizing the required number of crew members in order to satisfy the set covering constraints. Column generation is one of the optimization methods that can solve the problem efficiently. In order to improve the convergence of column generation, we propose dual inequalities for a Dantzig-Wolfe decomposition of railway crew scheduling problems to reduce the number of replications in the column generation procedure. The dual inequalities are generated from the characteristic of the given railway timetable data. Computational results demonstrate the effectiveness of the proposed method compared with the conventional column generation for an actual railway timetable data.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Column generation with dual inequalities for railway crew scheduling problems


    Contributors:

    Published in:

    Public Transport ; 3 , 1 ; 25-42


    Publication date :

    2011-02-01


    Size :

    18 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A Column Generation-Based Approach for Railway Crew Scheduling Problem

    Wang, Ying / Liu, Jun / Miao, Jianrui et al. | ASCE | 2008


    Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling

    Potthoff, D. / Huisman, D. / Desaulniers, G. | British Library Online Contents | 2010



    Results Obtained with Crew-Opt: A Column Generation Method for Transit Crew Scheduling

    Rousseau, J.-M. / Desrosiers, J. / University of Lisbon et al. | British Library Conference Proceedings | 1995


    A column generation approach to airline crew scheduling

    Borndörfer, Ralf / Schelten, Uwe / Schlechte, Thomas et al. | Tema Archive | 2006