Parallel algorithms for solving the train timetable rescheduling problem

In railways, it is essential to achieve high train punctuality. Thus, whenever disturbances occur, it is important to reschedule the trains effectively. This task is typically handled manually by traffic controllers in real-time. This thesis presents efficient computer algorithms for assisting traffic controllers in effectively rescheduling a train timetable during disturbances. The train timetable rescheduling problem is typically hard to solve as the solutions of interest, spread across a vast solution space, need to be searched quickly. Two main solution approaches involve using (i) exact algorithms, which typically search the entire solution space, and (ii) heuristic algorithms, which try to search for a good-enough solution quickly. Although research on competitive algorithms is prevalent, limited research exists on exploring the benefits and challenges of using parallel computing to tackle the problem. The primary objectives of this thesis are: (i) to model the train timetable rescheduling problem's search tree to be well-suited for parallel computing, (ii) to devise parallel heuristic search algorithms that can quickly and effectively solve the problem for one or many rescheduling objectives, (iii) to investigate the potential and limitations of parallel computing in the context of the problem, (iv) to investigate the comparison and evaluation of alternative solution approaches to analyze their strengths and limitations. In this thesis, we model the problem's search tree as a binary tree where the edges represent alternative rescheduling decisions and leaf nodes represent feasible timetables. We solve the problem by searching the tree using a parallel strategy that combines a depth-first search with simultaneous breadth-wise tree exploration. We evaluate our parallel algorithms for various disturbances on a Swedish railway network through experiments. The results of our research show that a parallel depth-first search algorithm can quickly search the devised search tree for solutions. With multiple rescheduling objectives, the parallel search algorithm obtained better solutions and showed higher speedups. Additional problem constraints often improved the search process by making the parallel algorithm reach the solutions faster. The results also show the potential and challenges of using graphics processing units for detecting conflicts in the timetable during the search. In conclusion, this thesis shows that parallel train timetable rescheduling algorithms can improve the search speed and the quality of the solution(s) obtained in real-time within the computational time limit