Konferensartikel

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