# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 1 Introduction  
The definitions of \"system performance\" and \"quality of service\" in railway traffic and transportation vary, but more recent reports, e.g., from the Boston Consultancy Group [1] and the European Commission [2], indicate that many European countries face challenges with regard to the reliability and punctuality of rail services. Several different factors contribute to these challenges, where the frequency and magnitude of disruptions and disturbances is one factor. The effectiveness in managing the disturbances and disruptions in railway traffic networks when they inevitably do occur is another aspect to consider. In this paper, we focus on the latter, and more specifically, on the problem of real-time train traffic re-scheduling, also referred to as train dispatching [3]. In general, the problem of re-scheduling train traffic in real-time is known to be a hard problem to solve by expert traffic dispatchers in practice, as well as by state-of-the-art scheduling software. There is thus often a trade-off that needs to be made regarding permitted computation time and expected solution quality. Heuristic approaches, or approaches based on, e.g., discrete-event simulation, are often rather quick, since they work in a greedy manner, but sometimes they fail to deliver a reasonable solution or even end up in deadlock. Exact approaches, based on, e.g., mixed-integer programming models solved by branch-and-cut algorithms are, on the other hand, less greedy, but can be very time-consuming, especially if the search space is large, and suffer from significant redundancy. Another aspect concerns the selected level of granularity of the traffic and infrastructure model, and this may indirectly affect the computation time and the quality of the solution as well. Over the latest three decades, a variety of algorithms and methods have been proposed to solve the train traffic re-scheduling (or, train dispatching) problem, see [3; 4; 5; 6] for more recent surveys. These previously proposed approaches have different strengths and limitations, depending on the intended application and context in mind. In Section 2, we provide a more comprehensive summary of state-of-the-art methods addressing this problem. In this paper, we propose a heuristic approach to solve the real-time train traffic re-scheduling problem. We view the problem as a blocking/no-wait, parallel-machine job-shop scheduling problem [3]. A job corresponds to a train's path along a pre-determined sequence of track sections (i.e., machines). Each part of that path corresponds to an operation. \"blocking/no-wait\" constraint refers to that there is no possibility to finish an operation if the next operation of the same job cannot get access to the required machine for processing, i.e. there is no storage space between machines that allows jobs and their current operation to wait for an occupied machine to become available. That is, when an operation of a job is completed, the next operation of that job must immediately start. This corresponds to the train needing at all times to have explicit access to a track section (independent of whether the train is moving or waiting). This problem is here modeled as a graph, where the graph is a hybrid between a mixed graph and an alternative graph. The benefit of using a hybrid graph is the possibility of reducing the number of required computations when constructing the graph. The problem is then solved by a heuristic algorithm. The proposed mixed graph model is discussed in Section 3, and the proposed heuristic algorithm is presented in detail in Section 4. The performance of the proposed approach is assessed in an experimental study, where the approach has been applied to solve a number of disturbance scenarios for a dense part of the Swedish southern railway network system. The performance assessment also includes a benchmark with the commercial optimization software Gurobi (v 6.5.1), using the corresponding mixed integer programming (MIP) model (which is presented in Appendix A).