In railway traffic systems, it is essential to achieve a high punctuality to satisfy the goals of the involved stakeholders. Thus, whenever disturbances occur, it is important to effectively reschedule trains while considering the perspectives of various stakeholders. The train rescheduling problem is a complex task to solve, both from a practical and a computational perspective. From the latter perspective, a reason for the complexity is that the rescheduling solution(s) of interest may be dispersed across a large solution space. This space needs to be navigated fast while avoiding portions leading to undesirable solutions and exploring portions leading to potentially desirable solutions. The use of parallel computing enables such a fast navigation of the search tree. Though competitive algorithmic approaches for train rescheduling are a widespread topic of research, limited research has been conducted to explore the opportunities and challenges in parallelizing them.

This thesis presents research studies on how trains can be effectively rescheduled while considering the perspectives of passengers along with that of other stakeholders. Parallel computing is employed, with the aim of advancing knowledge about parallel algorithms for solving the problem under consideration.

The presented research contributes with parallel algorithms that reschedule a train timetable during disturbances and studies the incorporation of passenger perspectives during rescheduling. Results show that the use of parallel algorithms for train rescheduling improves the speed of solution space navigation and the quality of the obtained solution(s) within the computational time limit.

This thesis consists of an introduction and overview of the work, followed by four research papers which present: (1) A literature review of studies that propose and apply computational support for train rescheduling with a passenger-oriented objective; (2) A parallel heuristic algorithm to solve the train rescheduling problem on a multi-core parallel architecture; (3) A conflict detection module for train rescheduling, which performs its computations on a graphics processing unit; and (4) A redesigned parallel algorithm that considers multiple objectives while rescheduling.

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.