Disruptions and delays in railway traffic networks due to different types of disturbances is a frequent problem in many countries. When disruptions occur, the train traffic dispatchers may need to re-schedule the traffic and this is often a very demanding and complicated task. To support the train traffic dispatchers, we propose to use a parallelized multi-strategy based greedy algorithm. This paper presents three different parallelization approaches: (i) Single Strategy with a Partitioned List (i.e. the parallel processes originate from different starting points), (ii) Multiple Strategies with a Non-Partitioned List, and (iii) Multiple Strategies with a Partitioned List. We present an evaluation for a busy part of the Swedish railway network based on performance metrics such as the sum of all train delays at their final destinations and the number of delayed trains. The results show that parallelization helps to improve the solution quality. The parallel approach (iii) that combines all re-scheduling strategies with a partitioned list performs best among the three parallel approaches when minimizing the total final delay. The main conclusion is that the multi-strategy based parallel approach significantly improves the solution for 11 out of 20 disturbance scenarios, as compared to the sequential re-scheduling algorithm. The approach also provides an increased stability since it always delivers a feasible solution in short time.

Railway traffic disturbances occur and train dispatchers make re-scheduling decisions in order to reduce the delays. In order to support the dispatchers, good rescheduling strategies are required that could reduce the delays. We propose and evaluate re-scheduling strategies based on: (i) earliest start time, (ii) earliest track release time, (iii) smallest buffer time, and (iv) shortest section runtime. A comparative evaluation is done for a busy part of the Swedish railway network. Our results indicate that strategies based on earliest start time and earliest track release time have the best average performance.

Railways are an important part of the infrastructure in most countries. As the railway networks become more and more saturated, even small traffic disturbances can propagate and have severe consequences. Therefore, efficient re-scheduling support for the traffic managers is needed. In this paper, the train real-time re-scheduling problem is studied in order to minimize the total delay, subject to a set of safety and operational constraints. We propose a parallel greedy algorithm based on a depth-first branch-and-bound search strategy. A number of comprehensive numerical experiments are conducted to compare the parallel implementation to the sequential implementation of the same algorithm in terms of the quality of the solution and the number of nodes evaluated. The comparison is based on 20 disturbance scenarios from three different types of disturbances. Our results show that the parallel algorithm; (i) efficiently covers a larger portion of the search space by exchanging information about improvements, and (ii) finds better solutions for more complicated disturbances such as infrastructure problems. Our results show that the parallel implementation significantly improves the solution for 5 out of 20 disturbance scenarios, as compared to the sequential algorithm.