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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A Column Generation-Based Approach for Railway Crew Scheduling Problem


    Beteiligte:
    Wang, Ying (Autor:in) / Liu, Jun (Autor:in) / Miao, Jianrui (Autor:in) / Nie, Lei (Autor:in)

    Kongress:

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



    Erscheinungsdatum :

    17.07.2008




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Column generation with dual inequalities for railway crew scheduling problems

    Nishi, Tatsushi / Muroi, Yuki / Inuiguchi, Masahiro | Springer Verlag | 2011


    A column generation approach to airline crew scheduling

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



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

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


    Crew Scheduling Using Column Generation and Branch-and-Price Approach

    Ancheta, R. / Balakumar, M. / Collins, J. et al. | British Library Conference Proceedings | 1995