Algorithm for inserting a single train in an existing timetable

Abstract: The purpose with this report is to develop a network based insertion algorithm and evaluate it on a real-case timetable. The aim of the algorithm is to minimize the effect that that train implementation cause on the other, already scheduled traffic. We meet this purpose by choosing an objective function that maximizes the minimum distance to a conflicting train path. This ensures that the inserted train receives the best possible bottleneck robustness. We construct a graph problem, which solve with a modified version of Dijkstra’s algorithm. The complexity of the algorithm is Ο(s^2 t log⁡(s^2 t). We applied the algorithm on a Swedish timetable, containing 76 stations. The algorithm performs well and manage to obtain the optimal solution for a range of scenarios, which we have evaluated in various experiments. Increased congestion seemed to reduce the problem size. The case also show that a solution’s robustness decreases with increasing total number of departures. One disadvantage with the algorithm is that it cannot detect the best solution among those using the same bottleneck. We propose a solution to this that we hope can be implemented in further studies.