Return to search

Algorithm for inserting a single train in an existing timetable

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.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-141192
Date January 2017
CreatorsLjunggren, Fredrik, Persson, Kristian
PublisherLinköpings universitet, Kommunikations- och transportsystem, Linköpings universitet, Tekniska högskolan, Linköpings universitet, Kommunikations- och transportsystem, Linköpings universitet, Tekniska högskolan
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.002 seconds