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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2024-07-01


    Size :

    12553989 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




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

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

    Free access


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

    YASUMOTO MASAHIRO / HORI SATORU / SHIMURA AKITOSHI | European Patent Office | 2015

    Free access

    Program for Optimizing Diamond Interchanges in Oversaturated Conditions

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