# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 2 Related Work
### Train Rescheduling
Assumptions about railway infrastructure are also adopted in Reference [19], where two methods are proposed. The first one is based on MIP, while the second one uses Constraint Programming. Similarly, the timetable rescheduling, rolling stock rescheduling, and crew (train drivers) reschedulingproblems are formulated in Reference [20] using integer programming models. In the mentioned paper, the timetable rescheduling problem is treated as the job shop scheduling, the rolling stock rescheduling problem is presented using the multi-commodity flow in a graph model, and the crew rescheduling problem is seen as the extended set covering. Further research has been done in providing an approach of exchanging blocks of routes with permitted alternative blocks through the means of alternative graph formulations [21; 22]. One can also find adaptations of graph methods [23], such as time-space models [24]. As models considering the accurate description of railway infrastructure require too many computational resources to solve problems exactly in an acceptable amount of time, some more time efficient methods and heuristics are often applied. For example, in Reference [25], the authors propose a new approach based on the Statistical Analysis of Propagation of Incidents method, and, in Reference [26], a two-stage procedure is proposed. The first stage rests on the Simulated Annealing and the Tabu Search metaheuristics, whereas the second stage solves a simple integer programming problem. An approach based on MIP that incorporates a possibility of rerouting trains to enable minimizing the number of canceled and delayed trains, while adhering to infrastructure and rolling stock capacity constraints, is presented in Reference [27]. A proposition to apply MIP model to increase a robustness of the timetables is described by authors of Reference [28]. Considerations of the rescheduling problem on a single track unidirectional rail line that adheres to a cyclic schedule are included in Reference [29], where it is assumed that two types of trains (express and local) are dispatched from the origin in an alternating manner. The application of mixed integer programming to minimize combined length of shipping cycle and total dwell time of local trains at all stations is presented. In Reference [30], the authors consider the problem of adjusting the timetable in a case of partial or complete deadlocks. The integer programming formulation is given with the maximization of a service level. A recent macroscopic approach was presented in Reference [31], where boundary passenger runs within an urban network were tackled. The authors propose a mixed integer programming approach with the use of a space-time network. This is solved for large instances with the use of decomposition. In Reference [32], the authors turn to microscopic modeling of the railway network and consider a problem of rescheduling in dense railway systems which are subject to disturbances. A multi-objective optimization problem is solved heuristically. In Reference [33], a problem of deadhead routing in an urban transit line was tackled. The authors formulate it as an MIP problem which is solved with the use of a CPLEX solver with an embedded branch-and-cut algorithms.