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.
Optimizing Train Timetable Under Oversaturated Demand Conditions: A Variable-Splitting Lagrangian Approach for Big-M Constraints
IEEE Transactions on Intelligent Transportation Systems ; 25 , 7 ; 7265-7280
2024-07-01
12553989 byte
Article (Journal)
Electronic Resource
English
Optimizing urban rail timetable under time-dependent demand and oversaturated conditions
Online Contents | 2013
|First-Train Timetable Synchronization in Metro Networks under Origin-Destination Demand Conditions
DOAJ | 2022
|Program for Optimizing Diamond Interchanges in Oversaturated Conditions
Online Contents | 2002
|European Patent Office | 2015
|Program for Optimizing Diamond Interchanges in Oversaturated Conditions
British Library Conference Proceedings | 2002
|