# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 2 Related Work
### Joint Approaches  
Some important suggestions for the joint consideration of the maintenance activities scheduling and the train run rescheduling are indicated in References [43, 44]. It is pointed out there that a single closure of a track indispensable for the completion of a maintenance activity could be treated as a particular type of train, but the idea has not been sufficiently developed. The concept of a system that helps to plan the closure of tracks with the simultaneous consideration of changes in the timetable is presented in Reference [45]. However, the solution is not based on a formal mathematical model, and the authors assume that new schedules are determined by external systems rail carriers. The joint scheduling of maintenance of the infrastructure (track closures) and rescheduling of train runs is also discussed in References [46, 47]. In Reference [47], the author addresses the case when train arrival and departure times may be changed, but train runs cannot be canceled. Two analytical approaches are proposed, i.e., MIP (additionally with the bound and price reduction) and Problem Space Search metaheuristic, which was also presented in Reference [46]. This heuristic allows to generate alternative timetables and then to combine obtained solutions into one final timetable. MIP models are also proposed in References [7, 48] for the joint closure planning and timetabling problem. This model includes the possibility of changing train routes, as well. However, it is assumed that such train rescheduling may be performed among a finite number of alternatives given in advance. Unlike in our work, in Reference [48], the authors assumed that all closures are obligatory and in Reference [49], the authors do not consider particular events concerning conflicts between train runs; instead, they apply flow-based approach which is modeled as MIP with implicit link usage variables and cumulative station entry/exit variables. This model is solved with a Gurobi solver in Python and tested on a set of self-generated instances. In Reference [50], a reformulation is made--link usage variables are made explicit, while entry/exit variables are now binary. This model is further extended in Reference [51] to include crew scheduling. Train scheduling and preventive maintenance are also jointly considered in Reference [52], where the sum of absolute arrival time deviations of real trains at destinations between the identical and actual timetables is minimized. A proactive approach to planning maintenance windows is presented as the authors try to ensure that maintenance work is already included in the schedule. The problem is formulated as an MIP and solved with the use of Lagrange relaxation. Another MIP approach presented in Reference [53] is aimed at incorporating new closures in a way that disturbs the original schedule the least. This approach is tested on date from a cut-out of the Netherlands railway system. An MIP approach tested on the French railway network can be found in Reference [54]. The authors of Reference [8] develop a microscopic approach, where timetabling and maintenance scheduling is formulated as a mixed integer programming problem. To alleviate computational difficulties of finding an exact solution, an iterative algorithm based on decomposition is proposed. It is shown that it results in near-optimal solutions for the tested cases. For Reference [55], an MIP formulation was applied to high-speed networks, where, in order to alleviated maintenance-induced problems, switches to normal-speed network were employed. Finally, in Reference [9], the authors use a dynamic constraint-generation technique coupled with Lagrangian relaxation for a double-track network with transmittable maintenances. The method was proven effective on a small section of a Chinese railway system. Mixing the microscopic and the macroscopic approaches leads to intermediate, so-called mesoscopic models.