# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 2 Related Work  
[PERSON] [7] was, in 1973, one of the pioneers, adapting the job-shop scheduling (JSS) problem formulation for the train scheduling problem. This was later developed by other researchers such as [PERSON] et al. [8], [PERSON] et al. [9], [PERSON] and [PERSON] [10], [PERSON] and [PERSON] [11], and [PERSON] and [PERSON] [12]. The JSS paradigm is also explored in the mixed-integer linear programming (MILP) approach proposed by [PERSON] and [PERSON] in 2007 [13], where the primary focus was on creating and evaluating strategies for reducing the search space via model re-formulations. Different problem formulations were experimentally evaluated in several disturbance scenarios occurring on a double-tracked network with bi-directional traffic, and solved by commercial software for a time horizon of 60-90 min. The effectiveness of the approach and the different strategies were shown to be highly dependent on the size of the problem and type of disturbance. A heuristic approach based on a MILP formulation was also proposed in [14]. A time horizon of 30 to 60 min was defined for testing the disturbing scenarios. The commercial solver CPLEX was used to solve the problem, with an allowed computation time of 180 s. Significant effort was made to tune the heuristic algorithm, and the results were compared with exact ones. For up to a 40 min time horizon, the algorithm generated good results. A MIP model was also applied on a double-track railway corridor, where the focus is on local re-routing of trains to allow for bi-directional traffic and special constraints to respect the safety requirements [15]. As already mentioned, the real-time train traffic re-scheduling problem is a hard problem to solve. This is often an effect of the large solution space, which may be difficult to efficiently navigate in due to significant redundancy. That is, depending on the problem formulation and selected objective function,particularly, optimization solvers may find multiple equally good solutions and also have difficulties finding strong bounds. Finding optimal, or near-optimal, solutions may thus be very time-consuming. In order to reduce the computational time, one can partition the problem into a set of different sub-problems and solve them in parallel, in a distributed manner with some sort of coordination mechanism. The partitioning can be done in space (i.e., by dividing the infrastructure, or the associated constraints, into separate parts), or in time (i.e., rolling-time horizon). [PERSON] et al. (2016); [PERSON] et al. (2016); [PERSON] and [PERSON] (2016) proposed and benchmarked a centralized and a distributed re-scheduling approach for the management of a part of the Dutch railway network based on a branch-and-bound approach. These variations come from various static and dynamic priorities that are considered for scheduling. They also worked on a coordination system between multiple dispatching areas. The aim was to achieve a globally optimal solution by combining local solutions. Some constraints are defined for the border area and a branch-and-bound algorithm solves the coordinator problem. Another approach for reducing the complexity of the problem is to use classical decomposition techniques, which are becoming more frequently used to overcome the complexity (and the associated long computation times) of the train re-scheduling problem when using exact approaches. [PERSON] and [PERSON] proposed an exact method, which decomposes and solves the problem with a master-slave procedure using column generation [PERSON] and [PERSON] (2016). The master is associated with the line traffic control problem and the slaves with the station traffic control. Decomposition has also been used to reduce the complexity of the associated MIP model of the train re-scheduling problem [PERSON] and [PERSON] (2016). An iterative Lagrangian relaxation algorithm is used to solve the problem. [PERSON] et al.