In this paper, we describe the railway crew scheduling problem as a set covering model. Due to the large size of the problem and its intrinsic complexity, we propose an approach that starts with a decomposition phase to assign all trips to depots and gets a set of subproblems. A column generation algorithm is embed in genetic algorithm to get the lower bounds of the subproblems. In the second phase, we solve the linear programming relaxation of the models using a column generation scheme. Then we use a branch-and-bound technique to get satisfied integer solutions. The performance of this appraoch is compared with central solution by an instance. And our column geration based two-phase approach shows an improvement with respect to computation time.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Column Generation-Based Approach for Railway Crew Scheduling Problem


    Contributors:
    Wang, Ying (author) / Liu, Jun (author) / Miao, Jianrui (author) / Nie, Lei (author)

    Conference:

    Sixth International Conference of Traffic and Transportation Studies Congress (ICTTS) ; 2008 ; Nanning, China



    Publication date :

    2008-07-17




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English




    A column generation approach to airline crew scheduling

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



    Genetic Algorithm–Based Column Generation Approach to Passenger Rail Crew Scheduling

    Liu, Mindy / Haghani, Ali / Toobaie, Shahabeddin | Transportation Research Record | 2010


    Crew Scheduling Problem

    Vaidyanathan, Balachandran / Ahuja, Ravindra K. | Springer Verlag | 2015


    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