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 NP-complete.
['Michael Gatto', 'Björn Glaus', 'Riko Jacob', 'Leon Peeters', 'Peter Widmayer']
Railway Delay Management: Exploring Its Algorithmic Complexity