Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Author(s): Johanna Törnquist Krasemann
Title: Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances
Journal: Transportation Research Part C: Emerging Technologies
Year: 2012
Volume: 20
Issue: 1
Pagination: 62-78
ISSN: 0968-090X
Publisher: Elsevier
URI/DOI: 10.1016/j.trc.2010.12.004
ISI number: 000297485300007
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
Language: English
Abstract: An attractive and sustainable railway traffic system is characterized by having a high security, high accessibility, high energy performance and offering reliable services with sufficient punctuality. At the same time, the network is to be utilized to a large extent in a cost-effective way. This requires a continuous balance between maintaining a high utilization and sufficiently high robustness to minimize the sensitivity to disturbances. The occurrence of some disturbances can be prevented to some extent but the occurrence of unpredictable events are unavoidable and their consequences then need to be analyzed, minimized and communicated to the affected users. Valuable information necessary to perform a complete consequence analysis of a disturbance and the re-scheduling is however not always available for the traffic managers. With current conditions, it is also not always possible for the traffic managers to take this information into account since he or she needs to act fast without any decision-support assisting in computing an effective re-scheduling solution. In previous research we have designed an optimization-based approach for re-scheduling which seems promising. However, for certain scenarios it is difficult to find good solutions within seconds. Therefore, we have developed a greedy algorithm which effectively delivers good solutions within the permitted time as a complement to the previous approach. 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.
Subject: Computer Science\General
Keywords: Disturbance management, Optimization, Railway traffic, Scheduling, Slot allocation, Timetabling