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 feat...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2024-09-01
|
| Series: | Urban Rail Transit |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s40864-024-00225-5 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850040412250570752 |
|---|---|
| author | Qinglun Zhong Ruihua Xu |
| author_facet | Qinglun Zhong Ruihua Xu |
| author_sort | Qinglun Zhong |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-5793d25159bc45fbb52b7e050c3d9ac4 |
| institution | DOAJ |
| issn | 2199-6687 2199-6679 |
| language | English |
| publishDate | 2024-09-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Urban Rail Transit |
| spelling | doaj-art-5793d25159bc45fbb52b7e050c3d9ac42025-08-20T02:56:06ZengSpringerOpenUrban Rail Transit2199-66872199-66792024-09-0111110812210.1007/s40864-024-00225-5Linear Time Train Contraction Minor Labeling for Railway Line Capacity AnalysisQinglun Zhong0Ruihua Xu1College of Transportation Engineering Tongji UniversityCollege of Transportation Engineering Tongji UniversityAbstract 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.https://doi.org/10.1007/s40864-024-00225-5Graph minorRailway capacityTimetable analysisTrain gap problem |
| spellingShingle | Qinglun Zhong Ruihua Xu Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis Urban Rail Transit Graph minor Railway capacity Timetable analysis Train gap problem |
| title | Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis |
| title_full | Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis |
| title_fullStr | Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis |
| title_full_unstemmed | Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis |
| title_short | Linear Time Train Contraction Minor Labeling for Railway Line Capacity Analysis |
| title_sort | linear time train contraction minor labeling for railway line capacity analysis |
| topic | Graph minor Railway capacity Timetable analysis Train gap problem |
| url | https://doi.org/10.1007/s40864-024-00225-5 |
| work_keys_str_mv | AT qinglunzhong lineartimetraincontractionminorlabelingforrailwaylinecapacityanalysis AT ruihuaxu lineartimetraincontractionminorlabelingforrailwaylinecapacityanalysis |