Optimizing High-Speed Train Timetabling with Consideration of Sta-tion Carrying Capacity

Chunxiao Chen; Wenjing Li

doi:10.31181/dmame8120251317

Authors

Chunxiao Chen School of Rail Transit transportation, Hunan Railway Professional Technology College, Zhuzhou 412001, China https://orcid.org/0000-0002-2709-4962
Wenjing Li School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China https://orcid.org/0000-0001-5190-5246

DOI:

https://doi.org/10.31181/dmame8120251317

Keywords:

High-Sped Railway, Train Timetabling, Car-rying Capacity, Genetic Algorithm

Abstract

The extensive development of high-speed railways (HSR) in China has transformed the railway system from one constrained by limited capacity to a more adaptable network, significantly mitigating previous capacity shortages. Nevertheless, the demand for high-speed rail services exhibits considerable variability, with peak travel periods—such as the Spring Festival, summer holidays, and extended weekends—increasingly becoming regular occurrences. During these peak times, passenger flows become highly concentrated, resulting in temporary congestion at certain high-traffic HSR stations. Current methodologies for assessing the carrying capacity of HSR stations predominantly rely on approaches originally designed for conventional railways. These methods often fail to adequately consider the unique characteristics of individual stations, their equipment, and operational specifics. The parameters employed are frequently broad and lack precision, underscoring the necessity for more refined techniques to calculate station capacity and develop accurate HSR timetables that can better accommodate peak travel demands. This research initially integrates the train dispatching principles of HSR station CTC (Centralised Traffic Control) systems with automatic point sampling principles to conduct a comprehensive analysis of critical parameters. These parameters include train occupancy durations on arrival and departure tracks, train occupancy times in throat areas, and daily idle periods. The values of these parameters are refined and standardised to ensure that the outcomes of the comprehensive analysis method align more closely with actual operational requirements. Subsequently, with the objective of minimising total travel time, this study formulates a single-objective mathematical programming model for generating HSR timetables that incorporate station carrying capacity constraints. A genetic algorithm is also developed to solve this model. Utilising operational data from the Shanghai-Hangzhou East HSR, the study constructs a timetable under the constraints of station capacity, assesses the influence of both the timetable and the algorithm on the results, and verifies the efficacy of the proposed model and algorithm.

Downloads

Download data is not yet available.

References

[1] China, N. (2014). Code for design of high speed railway. China Ministry of Railways, TB, 10621-2014.

[2] Serafini, P. and W. Ukovich. (1989). A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4), 550-581. https://doi.org/10.1137/0402049

[3] Schrijver, A. and A. Steenbeek, Dienstregelingontwikkeling voor Railned (timetable construction for Railned). 1994, Technical report, CWI, Center for Mathematics and Computer Science ….

[4] Mbah, O. and Q. Zeeshan. (2023). Optimizing path planning for smart vehicles: a comprehensive review of metaheuristic algorithms. J Eng Manage Syst Eng, 2(4), 231-271. https://doi.org/10.56578/jemse020405

[5] Odijk, M.A. (1996). A constraint generation algorithm for the construction of periodic railway timetables. Transportation Research Part B: Methodological, 30(6), 455-464. https://doi.org/10.1016/0191-2615(96)00005-7

[6] El Chaal, R., S. Bouchefra, and M. Aboutafail. (2023). Stochastic dynamics and extinction time in SIR epidemiological models. Acadlore Trans. Appl Math. Stat, 1(3), 181-202. https://doi.org/10.56578/atams010305

[7] Li, K., H. Huang, and P. Schonfeld. (2018). Metro Timetabling for Time‐Varying Passenger Demand and Congestion at Stations. Journal of Advanced Transportation, 2018(1), 3690603. https://doi.org/10.1155/2018/3690603

[8] Wang, Y., et al. (2015). Passenger-demands-oriented train scheduling for an urban rail transit network. Transportation Research Part C: Emerging Technologies, 60, 1-23. https://doi.org/10.1016/j.trc.2015.07.012

[9] Shi, F., et al. (2012). Optimization method for train diagram of high-speed railway considering the turnover of multiple units and the utilization of arrival-departure tracks. Zhongguo Tiedao Kexue, 33(2), 107-114.

[10] Zhou, X. and M. Zhong. (2007). Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds. Transportation Research Part B: Methodological, 41(3), 320-341. https://doi.org/10.1016/j.trb.2006.05.003

[11] Berbiche, N., et al. (2024). An Integrated Inventory-Production-Distribution Model for Crisis Relief Supply Chain Optimization: A Systematic Review and Mixed Integer Programming Formulation. Journal Européen des Systèmes Automatisés, 57(3). https://doi.org/10.18280/jesa.570329

[12] Lu, C., L. Zhou, and R. Chen. (2018). Optimization of high-speed railway timetabling based on maximum utilization of railway capacity. J. Railw. Sci. Eng, 15(11), 2746-2754.

[13] Higgins, A., E. Kozan, and L. Ferreira. (1996). Optimal scheduling of trains on a single line track. Transportation research part B: Methodological, 30(2), 147-161. https://doi.org/10.1016/0191-2615(95)00022-4

[14] Muniasamy, K., P. Venugopal, and G. Pakkirisamy. (2023). Genetic Algorithm-Driven Optimization of Scheduling and Preventive Measures in Parallel Machines. Mathematical Modelling of Engineering Problems, 10(5). https://doi.org/10.18280/mmep.100533

[15] Du, Y., et al. (2024). An investigation into multi-stage, variable-batch scheduling across multiple production units. Journal of Engineering Management and Systems Engineering, 3(1), 1-20. https://doi.org/10.56578/jemse030101

[16] Brännlund, U., et al. (1998). Railway timetabling using Lagrangian relaxation. Transportation science, 32(4), 358-369. https://doi.org/10.1287/trsc.32.4.358

[17] Caprara, A., et al. (2006). A Lagrangian heuristic algorithm for a real-world train timetabling problem. Discrete applied mathematics, 154(5), 738-753. https://doi.org/10.1016/j.dam.2005.05.026

[18] Zhou, W. and H. Teng. (2016). Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition. Transportation Research Part B: Methodological, 94, 409-439. https://doi.org/10.1016/j.trb.2016.10.010

[19] Zhou, W., et al. (2017). Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition. Transportation Research Part B: Methodological, 105, 144-173. https://doi.org/10.1016/j.trb.2017.08.005

[20] Cacchiani, V., A. Caprara, and P. Toth. (2008). A column generation approach to train timetabling on a corridor. 4or, 6, 125-142. https://doi.org/10.1007/s10288-007-0037-5

[21] Pan, H., L. Yang, and Z. Liang. (2023). Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: A column-generation-based approach. European Journal of Operational Research, 305(1), 184-206. https://doi.org/10.1016/j.ejor.2022.05.039

[22] Cai, X. and C. Goh. (1994). A fast heuristic for the train scheduling problem. Computers & Operations Research, 21(5), 499-510. https://doi.org/10.1016/0305-0548(94)90099-X

[23] Neamah, N.M., B.A. Kalaf, and W. Mansoor. (2023). Solving Tri-criteria: Total Completion Time, Total Earliness, and Maximum Tardiness Using Exact and Heuristic Methods on Single-Machine Scheduling Problems. Mathematical modelling of engineering problems, 11(4), 987-995. https://doi.org/10.18280/mmep.110415

[24] Lee, Y. and C.-Y. Chen. (2009). A heuristic for the train pathing and timetabling problem. Transportation Research Part B: Methodological, 43(8-9), 837-851. https://doi.org/10.1016/j.trb.2009.01.009

[25] Karoonsoontawong, A. and A. Taptana. (2017). Branch-and-bound-based local search heuristics for train timetabling on single-track railway network. Networks and Spatial Economics, 17, 1-39. https://doi.org/10.1007/s11067-015-9316-4

[26] Puška, A., et al. (2024). Optimising AGV routing in container terminals: Nearest neighbor vs. Tabu search. Mechatronics and Intelligent Transportation Systems (MITS), 3(4), 203-211. https://doi.org/10.56578/mits030401

[27] Zhou, W., et al. (2011). Method of integrated optimization of train operation plan and diagram for network of dedicated passenger lines. Journal of the China Railway Society, 2.

[28] Kaspi, M. and T. Raviv. (2013). Service-oriented line planning and timetabling for passenger trains. Transportation Science, 47(3), 295-311. https://doi.org/10.1287/trsc.1120.0424

[29] Yang, L., et al. (2016). Collaborative optimization for train scheduling and train stop planning on high-speed railways. Omega, 64, 57-76. https://doi.org/10.1016/j.omega.2015.11.003

[30] Yue, Y., et al. (2016). Optimizing train stopping patterns and schedules for high-speed passenger rail corridors. Transportation Research Part C: Emerging Technologies, 63, 126-146. https://doi.org/10.1016/j.trc.2015.12.007

[31] Niu, H., X. Zhou, and R. Gao. (2015). Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints. Transportation Research Part B: Methodological, 76, 117-135. https://doi.org/10.1016/j.trb.2015.03.004

[32] Jiang, F., V. Cacchiani, and P. Toth. (2017). Train timetabling by skip-stop planning in highly congested lines. Transportation Research Part B: Methodological, 104, 149-174. https://doi.org/10.1016/j.trb.2017.06.018