A Parallel Re-Scheduling Algorithm for Railway Traffic Disturbance Management --- Initial Results
|Document type:||Conference Papers|
|Author(s):||Håkan Grahn, Johanna Törnquist Krasemann|
|Title:||A Parallel Re-Scheduling Algorithm for Railway Traffic Disturbance Management --- Initial Results|
|Conference name:||2nd International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS 2011)|
|Organization:||Blekinge Institute of Technology|
|Department:||School of Computing (Sektionen för datavetenskap och kommunikation)
School of Computing S-371 79 Karlskrona
+46 455 38 50 00
|Authors e-mail:||Hakan.Grahn@bth.se, Johanna.Tornquist@bth.se|
|Abstract:||In Sweden, the railway traffic and demand for track capacity have increased significantly the last years resulting in a high traffic density where even small disturbances propagate. This makes it hard for the traffic managers to overview the consequences of disturbances and their decisions when rescheduling the traffic.
In previous research, we have developed and experimentally evaluated a greedy depthfirst search
algorithm. This algorithm aims to support the traffic managers by computing alternative rescheduling solutions in order to minimize the train delays. The simulation experiments were based on real traffic data and the algorithm proved to be very effective for many types of disturbances and delivers optimal or close to optimal solutions in a few seconds. However, the experiments also indicated a need for improvements when solving more severe disturbances related to major infrastructure failures. The improvements concern primarily the need to explore larger parts of the search space quickly and to branch more effectively by avoiding exploring non-promising nodes.
This paper presents results from an analysis of where and when successful branching decisions are made. The analysis showed that the successful branching decisions were generally made quite far down in the search space tree, but somewhat higher up during more severe disturbance scenarios. We also present an improved version of the greedy algorithm and a parallel implementation of it. The parallelization is composed of eight different threads allocated to one processor each starting to branch at the highest branching level. The experimental results show that it improves the solutions for difficult disturbance scenarios.
Computer Science\Artificial Intelligence
|Keywords:||Railway traffic, Disturbance Management, Rescheduling, Parallel algorithm, Multiprocessor|