Research in railway operations has mostly focused on operations research methods. However, these real-world problems have a state-based nature, which makes them very suitable for AI models, such as the Multi-Agent Pathfinding problem, where agents move in a grid and need to be routed from their start to their goal location without colliding with each other. The core aspect of problems like train shunting and train dispatching is routing, which is often not the main focus of current mathematical formulations. Therefore, we apply the state-of-the-art algorithms to the railway problems of shunting and dispatching and study their usability for routing trains. The Multi-Agent Pathfinding problem is often solved with one of two algorithms: conflict-based search (a two-stage algorithm detecting conflicts between individual paths and using A* search to find new conflict-free paths), and branch-cut-and-price (a linear program adding cuts (row generation) based on problem-specific constraints, and finding new paths to be selected that satisfy all constraints using a pricer). We modify these algorithms to include more railway details. First, we allow for the matching of train units (i.e., ensure the necessary train units of a certain type are available for departure) by specifying goals for agent (type) groups instead of single agent goals. Moreover, we add goal sequences for servicing stations and agents of different sizes, and we study specific aspects of the railway infrastructure to exploit in the algorithm. Finally, we show the use of Multi-Agent Pathfinding solvers in different railway settings and analyze the conditions for success.

Train routing is sensitive to delays that occur in the network. When a train is delayed, it is imperative that a new plan be found quickly, or else other trains may need to be stopped to ensure safety, potentially causing cascading delays. In this paper, we consider this class of multi-agent planning problems, which we call Multi-Agent Execution Delay Replanning. We show that these can be solved by reducing the problem to an any-start-time safe interval path planning problem. When an agent has an any-start-time plan, it can react to a delay by simply looking up the precomputed plan for the delayed start time. We identify crucial real-world problem characteristics like the agent's speed, size, and safety envelope, and extend the any-start-time planning to account for them. Experimental results on real-world train networks show that any-start-time plans are compact and can be computed in reasonable time while enabling agents to instantly recover a safe plan.

The Train Unit Shunting Problem concerns the parking of trains outside their scheduled use on so-called shunting yards. This is an NP-hard problem, and the current algorithm used by the Netherlands Railways cannot detect whether an instance is infeasible. So, infeasible instances can cause needlessly long computation times. Therefore, this paper fills the gap by providing novel approaches to determine the feasibility. For this, the Pebble Motion problem is considered which moves pebbles from their starting node to their goal node in the graph, such that no two pebbles occupy a node at the same time. A variant of the Pebble Motion problem is proposed to model the Train Unit Shunting Problem, where train units are represented by pebbles and the arrival and departure of train unit combinations are also included. This paper specifically looks at dead-end track shunting yards, as they can be abstractly represented by trees, such that trains arrive and depart at the root node. Furthermore, trains cannot be reallocated between arrival and departure in the tree, since reallocation in practice is a very costly process as moves need to be performed by a small set of drivers. The conditions for realizing the departure order of trains are studied, and an efficient method to (partially) determine the feasibility of problem instances is given, which can find the minimal number of tracks required to park the trains. Furthermore, a special case with tracks of length two is shown to be polynomially solvable, while another subset of problem instances with tracks of length six or more is demonstrated to be NP-complete.