Railway delay management: Exploring its algorithmic complexity. (English) Zbl 1095.68595
Hagerup, Torben (ed.) et al., Algorithm theory – SWAT 2004. 9th Scandinavian workshop on algorithm theory, Humlebæk, Denmark, July 8–10, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22339-8/pbk). Lecture Notes in Computer Science 3111, 199-211 (2004).
Summary: We consider delay management in railway systems. Given delayed trains, we want to find a waiting policy for the connecting trains minimizing the weighted total passenger delay. If there is a single delayed train and passengers transfer at most twice along fixed routes, or if the railway network has a tree structure, the problem can be solved by reduction to min-cut problems. For delayed passenger flows on a railway network with a path structure, the problem can be solved to optimality by dynamic programming. If passengers are allowed to adapt their route to the waiting policy, the decision problem is strongly \(\mathcal{NP}\)-complete.
For the entire collection see [Zbl 1056.68011].
For the entire collection see [Zbl 1056.68011].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90B06 | Transportation, logistics and supply chain management |
| 90B50 | Management decision making, including multiple objectives |
| 90C35 | Programming involving graphs or networks |
