Exploring the potential of GPU computing in Train Rescheduling

Sai Prashanth Josyula
Department of Computer Science, Blekinge Institute of Technology, Sweden

Johanna Törnquist Krasemann
Department of Computer Science, Blekinge Institute of Technology, Sweden

Lars Lundberg
Department of Computer Science, Blekinge Institute of Technology, Sweden

Ladda ner artikel

Ingår i: RailNorrköping 2019. 8th International Conference on Railway Operations Modelling and Analysis (ICROMA), Norrköping, Sweden, June 17th – 20th, 2019

Linköping Electronic Conference Proceedings 69:32, s. 471-490

Visa mer +

Publicerad: 2019-09-13

ISBN: 978-91-7929-992-7

ISSN: 1650-3686 (tryckt), 1650-3740 (online)


One of the crucial factors in achieving a high punctuality in railway traffic systems, is the ability to effectively reschedule the trains during disturbances. Railway rescheduling is a complex problem to solve both from a practical and a computational perspective. Problems of practically relevant sizes have typically a very large search space, making it a challenge to arrive at the best possible solution within the available computational time limit. Though competitive algorithmic approaches are a widespread topic of research, not much research has been done to explore the opportunities and challenges in parallelizing them on Graphics processing units (GPUs). This paper presents a conflict detection module for railway rescheduling, which performs its computations on the GPU. The aim of the module is to improve the speed of solution space navigation and thus the solution quality within the computational time limit. The implemented algorithm proved to be more than twice as fast as the sequential algorithm. We conclude that for the problem under consideration, using a GPU for conflict detection likely gives rise to better solutions at the end of the computational time limit.


Real-time decision support, Train rescheduling, Conflict detection, Parallel algorithms, Graphics processing units


Inga referenser tillgängliga

Citeringar i Crossref