Greedy algorithm for railway traffic re-scheduling during disturbances: a Swedish case

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Full text:
Author(s): Johanna Törnquist Krasemann
Title: Greedy algorithm for railway traffic re-scheduling during disturbances: a Swedish case
Translated title: En girighetsalgoritm för omplanering av tågtrafik vid trafikstörningar
Journal: IET Intelligent Transport Systems
Year: 2010
Volume: 4
Issue: 4
Pagination: 375–386
ISSN: 1751-956X
Publisher: The Institution of Engineering and Technology
URI/DOI: 10.1049/iet-its.2009.0122
ISI number: 000284307500017
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:
Language: English
Abstract: The positive trend of increased use of railway transportation in Europe has resulted in an increased sensitivity to and occurrence of traffic disturbances. In addition to the need for extensions of the infrastructure, the need to effectively limit and predict the effects of disturbances becomes apparent.
The kernel of the disturbance management problem is to revise the original timetable in line with the new conditions and decide where, when and how trains should overtake or meet to minimise the negative effect of the disturbance.

In previous research, the author has designed optimisation-based approach for rescheduling, which seems promising, but for some scenarios it is difficult to find good solutions within seconds. Also, more detailed constraints will have to be included, which makes the problem even more complex and difficult to solve. Therefore the author developed a greedy algorithm that effectively delivers good solutions within the permitted time. To quickly retrieve a feasible solution, the algorithm performs a depth-first search using an evaluation function to prioritise when conflicts arise and then branches according to a set of criteria. A performance analysis of the algorithm was carried out using simulated experiments showing its strengths and weaknesses.
Subject: Mathematics\Discrete Mathematics
Computer Science\Computersystems
Keywords: Railway traffic, Scheduling, Timetabling, Slot allocation, Disturbance management, Optimisation