Change search
ReferencesLink to record
Permanent link

Direct link
A Parallel Re-Scheduling Algorithm for Railway Traffic Disturbance Management --- Initial Results
Blekinge Institute of Technology, School of Computing.
Blekinge Institute of Technology, School of Computing.
2011 (English)Conference paper (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Leuven, Belgium, 2011.
Keyword [en]
Railway traffic, Disturbance Management, Re­scheduling, Parallel algorithm, Multi­processor
National Category
Computer Science
URN: urn:nbn:se:bth-7154Local ID: diva2:834736
2nd International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS 2011)
Available from: 2012-11-28 Created: 2012-01-05 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(603 kB)21 downloads
File information
File name FULLTEXT01.pdfFile size 603 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Grahn, Håkan
By organisation
School of Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 21 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link