Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis

Abstract

When no more than one train is feasibly contained in the separation headway times of two other trains, a triangular gap problem-based method is used to compute the consumed capacity in linear time. This is a strong condition limiting its applicability, while real-world operations often feature mixed traffic of various speeds, creating more complex structures beyond the characterization of a triangular gap. In this paper, we attempt to investigate the multi-train gap scenario and provide a general solution to the railway timetable structure and capacity analysis problem. Given a timetable, we use an incidence graph, the so-called train contraction minor, for representing the consecutive train operations and show that a longest path for spanning the compressed timetable is any path in a graph induced by some topological subsequence of trains that connects the predefined vertices in the train contraction minor. By vector-valued vertex labeling of this minor, we acquire an efficient algorithm that computes the consumed capacity of the timetable. Our algorithm runs in O(mn) time, where m and n are the number of trains and stations, respectively, and is free from the limitation and outperforms the near-linear time policy iteration implementation in the max-plus system of train operations. A toy example and a real-world case study demonstrate the effectiveness and computational performance of the proposed method. The proposed method based on train contraction minor contributes to the railway operations community by promoting the efficient computation of railway line capacity into linear time.

Keywords

Graph minor / Railway capacity / Timetable analysis / Train gap problem

References

[1] UIC: UIC 406 - Capacity. International Union of Railways (2004)

[2] Zhong Q, Xu C, Yang R, Zhong Q. Equivalences between analytical railway capacity methods. J Rail Transp Plan Manag, 2023, 25

[3] Weik N, Niebel N, Nießen N. Capacity analysis of railway lines in Germany-a rigorous discussion of the queueing based approach. J Rail Transp Plan Manag, 2016, 6(2): 99-115.

[4] Niebel NA (2017) Berechnung der außerplanmäßigen wartezeit im drei-zug-modell. PhD thesis, RWTH Aachen

[5] Abril M, Barber F, Ingolotti L, Salido MA, Tormos P, Lova A. An assessment of railway capacity. Transp Res E Logist Transp Rev, 2008, 44(5): 774-806

[6] Pouryousef H, Lautala P, White T. Railroad capacity tools and methodologies in the us and Europe. J Modern Transp, 2015, 23: 30-42

[7] Weik N, Warg J, Johansson I, Bohlin M, Nießen N. Extending UIC 406-based capacity analysis-new approaches for railway nodes and network effects. J Rail Transp Plan Manag, 2020, 15

[8] Sameni MK, Moradi A. Railway capacity: a review of analysis methods. J Rail Transp Plan Manag, 2022, 24

[9] Stein EM, Shakarchi R. Real analysis: measure theory, integration, and Hilbert spaces, 2009, Princeton: Princeton University Press

[10] Jensen LW, Schmidt M, Nielsen OA (2020) Determination of infrastructure capacity in railway networks without the need for a fixed timetable. Transp Res Part C: Emerg Technol 119:102751

[11] Lordieck J, Nold M, Corman F (2024) Microscopic railway capacity assessment of heterogeneous traffic under real-life operational conditions. J Rail Transp Plan Manag 30:100446

[12] Yang H. Tielu Yunshu Zuzhi Xue ("Railway Operation Organization"), 2011, Beijing: China Railway Publishing House

[13] Li X, Huo Y, Yan Z (2023) A calculation method for high-speed railway capacity based on improved train deduction method. Transport 38(4):214–230

[14] UIC: UIC 406 - Capacity 2 ed. International Union of Railways (2013)

[15] Landex A, Kaas AH, Schittenhelm B, Schneider-Tilli J (2006) Evaluation of railway capacity. In: Proceedings from the annual transport conference at Aalborg University, vol 13

[16] Lindner T. Applicability of the analytical UIC code 406 compression method for evaluating line and station capacity. J Rail Transp Plan Manag, 2011, 1(1): 49-57.

[17] Cochet-Terrasson J, Cohen G, Gaubert S, McGettrick M, Quadrat J-P. Numerical computation of spectral elements in max-plus algebra. IFAC Proc Vol, 1998, 31(18): 667-674

[18] Goverde RM (2005) Punctuality of railway operations and timetable stability analysis. PhD thesis, Delft University of Technology

[19] Goverde RM. Railway timetable stability analysis using max-plus system theory. Transp Res B Methodol, 2007, 41(2): 179-201

[20] Dacierno L, Botte M, Pignatiello G (2019) A simulation-based approach for estimating railway capacity. Int J Transp Develop Integr 3(3):232–244. https://doi.org/10.2495/TDI-V3-N3-232-244

[21] Liao Z, Li H, Miao J, Corman F (2021) Railway capacity estimation considering vehicle circulation: integrated timetable and vehicles scheduling on hybrid time-space networks. Transp Res Part C: Emerg Technol 124:102961

[22] Liao Z, Li H, Miao J, Meng L (2024) Estimating the railway network capacity utilization with mixed train routes and stopping patterns: a multiobjective optimization approach. J Adv Transp 2024(1):5467767

[23] Schwanhausser W (1978) Die ermittlung der leistungsfähigkeit von großen fahrstraßenknoten und von teilen des eisenbahnnetzes

[24] Gast I, Niebel N, Nießen N. Zacken-Lücken-Problem in der Praxis. Deine Bahn DB, 2014, 42(12): 36-39.

[25] Korte B, Vygen J. Combinatorial optimization: theory and algorithms, 2018, Berlin: Springer 15-51

Funding

Key Programme(72171174)