A Parallel Re-Scheduling Algorithm for Railway Traffic Disturbance Management --- Initial Results

Document type: Conference Papers
Peer reviewed: Yes
Full text:
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)
Year: 2011
City: Leuven, Belgium
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
Language: English
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.
Subject: Computer Science\General
Computer Science\Computersystems
Computer Science\Artificial Intelligence
Keywords: Railway traffic, Disturbance Management, Re­scheduling, Parallel algorithm, Multi­processor