An efficient heuristic for train rescheduling and local rerouting

Abstract

In practice, unexpected events frequently cause delays, often leading to conflicts, since multiple trains simultaneously require the same infrastructure. Currently, such conflicts are manually resolved by dispatchers, although it is impossible for them to anticipate the impact of their actions on the entire network. Conflict detection and resolution tools can help dispatchers make informed decisions.
This research introduces a new heuristic that uses rescheduling and rerouting in station areas and is innovative due to strong similarities with real-life situations. The algorithm for rescheduling is based on limiting the total delay caused by conflicts, through analyzing the predicted progress over the following hour. If the conflict arises in a station area, an optimization procedure checks first whether rerouting leads to a solution with (almost) no delays. Because some trains have a needless amount of alternative routes, a routing filter is applied before the rerouting procedure. This rerouting procedure is based on a flexible job shop problem aiming to minimize the actual travel time of passengers. This fast and effective method is experimentally tested using a close-to-practice simulation tool and compared to commonly used dispatching rules.