When trains are finished with their transportation tasks during the day, they are moved to a shunting yard where they are routed, parked, cleaned, subject to regular maintenance checks and repaired during the night. The resulting Train Unit Shunting and Servicing problem motivates advanced research in planning and scheduling in general since it integrates several known individually hard problems while incorporating many real-life details. We developed an event-based simulator called TORS (Dutch acronym for Train Shunting and Servicing Simulator), that provides the user with a state and all feasible actions. After an action is picked, TORS calculates the result and the process repeats. This simulator facilitates research into a realistic application of multi-agent path finding.@en

In this paper we consider the train unit shunting problem extended with service task scheduling. This problem originates from Dutch Railways, which is the main railway operator in the Netherlands. Its urgency stems from the upcoming expansion of the rolling stock fleet needed to handle the ever-increasing number of passengers. The problem consists of matching train units arriving on a shunting yard to departing trains, scheduling service tasks such as cleaning and maintenance on the available resources, and parking the trains on the available tracks such that the shunting yard can operate conflict-free. These different aspects lead to a computationally extremely difficult problem, which combines several well-known NP-hard problems. In this paper, we present the first solution method covering all aspects of the shunting and scheduling problem. We describe a partial order schedule representation that captures the full problem, and we present a local search algorithm that utilizes the partial ordering. The proposed solution method is compared with an existing mixed integer linear program in a computational study on realistic instances provided by Dutch Railways. We show that our local search algorithm is the first method to solve real-world problem instances of the complete shunting and scheduling problem. It even outperforms current algorithms when the train unit shunting problem is considered in isolation, that is, without service tasks. Although our method was developed for the case of the Dutch Railways, it is applicable to any shunting yard or service location, irrespective of its layout, that uses self-propelling train units and that does not have to handle passing trains.@en