This study aims to optimize train timetables with hour-dependent origin-destination passenger demand for an oversaturated high-speed rail corridor, where some passengers may be delayed to the next hour. By introducing arc-based binary variables and assignment-based integer variables in the elaborated space-time network, we formulate the problem under consideration as an integer linear programming model with the objective of minimizing passenger travel time. To transform nonlinear demand loading constraints, multiple sets of big- $M$ constraints linking different types of variables are established equivalently. While relaxing these big- $M$ constraints under the standard Lagrangian decomposition framework, a thorny issue is that the lower bounds are often not ideal due to the existence of big- $M$ values. To tackle this important and common computational challenge, a novel approach is employed to split the arc-based variables into train skip-stopping and departing variables. Furthermore, a series of valid constraints are proposed to augment the decomposed assignment subproblem. With the help of Lagrangian dual information, a dynamic programming heuristic is also developed to generate feasible solutions to the primal problem. Finally, several numerical experiments are conducted to assess the efficiency and effectiveness of the proposed approach. The results show that compared with traditional solution approaches, the proposed approach can obtain satisfactory solutions in acceptable computation times for all the instances, in which the optimality gaps are less than 5% and the travel time is reduced by 17.28% on average.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Optimizing Train Timetable Under Oversaturated Demand Conditions: A Variable-Splitting Lagrangian Approach for Big-M Constraints


    Beteiligte:
    Tian, Xiaopeng (Autor:in) / Niu, Huimin (Autor:in)


    Erscheinungsdatum :

    01.07.2024


    Format / Umfang :

    12553989 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    First-Train Timetable Synchronization in Metro Networks under Origin-Destination Demand Conditions

    Hetian Chai / Xiaopeng Tian / Huimin Niu | DOAJ | 2022

    Freier Zugriff


    Train timetable generation system, train timetable generation device, and train timetable generation method

    YASUMOTO MASAHIRO / HORI SATORU / SHIMURA AKITOSHI | Europäisches Patentamt | 2015

    Freier Zugriff

    Program for Optimizing Diamond Interchanges in Oversaturated Conditions

    Kowali, V. G. / Messer, C. J. / Chaudhary, N. A. et al. | British Library Conference Proceedings | 2002