# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 2 Related Work
### Train Rescheduling  
The train rescheduling task is a problem quite widely discussed in the literature. It is understood, in the most cases, as the response to a single unforeseen event that prevents the further realization of the transportation plan by the original timetable. As detailed in Reference [10], the problem of rescheduling can be handled as different (re-)scheduling paradigms: offline, done to establish a primary schedule; and online, done mainly to reestablish a schedule that is no longer acceptable (feasible). The main difference, from the standpoint of difficulty of solving is that the former approach can be performed over a significantly longer period of time, while the latter needs to be done quickly, so as not to allow operations on an invalid schedule. The latter approach can, and likely will, lead to such problem formulations and solution algorithms which, in general case, forgo optimality and focus on providing heuristic, sub-optimal solutions instead. It is this approach that we focus on in this paper, although the results can also be applied to formulate a primary schedule. Online approaches can be further divided into static (open-loop) and dynamic (closed-loop), where, in the dynamic cases, not all of the information is readily available during the decision-making process. As new information about decision execution becomes available, it is fed back to the rescheduling algorithm and (possibly) results in new solutions. Finally, prediction of future states of the system is taken into consideration in proactive approaches, as opposed to reactive ones. The mixed integer programming (MIP) model is proposed in Reference [11] for the train rescheduling problem when a train's initial delays are given, and the minimization of the total delay of all passengers is required. However, specific requirements resulting from the state of railway infrastructure are not taken into account in this work. It is assumed that every route can hold any number of train runs in the same period. The extension of this problem is presented in Reference [12], where the limited number of train runs traveling between two stations at a given time is considered. The problem is formulated using integer linear programming approach and solved using the branch and bound method. Real-world data provided by Deutsche Railways have made it possible to test this approach successfully. A similar model and solution algorithm based on the Lagrange relaxation is proposed in Reference [13]. As a consequence, the problem is decomposed into a sequence of simple optimization tasks each corresponding to one train run. Another integer programming model presented in Reference [14] considers the assumption that, between any two stations, there is no more than one track, which may be occupied by no more than one train run at the same time. However, the authors do not propose any solution to the formulated problem due to its computational complexity. The authors in Reference [15] assume that there are always two tracks between two connected stations, and each of them may be occupied by no more than one train run at the same time. In this case, the genetic algorithm is applied to solve the train rescheduling problem. The discrete dynamic optimization model for train rescheduling problem is given in Reference [16]. The main goal in this case is to maximize punctuality and station satisfaction degree. However, authors also limit their consideration to the single-track railway and, even for this simple scenario, apply the heuristic approach. More complex models of railway network infrastructure are presented in Reference [17], where it is taken into account that tracks are composed of blocks, and there may be any number of tracks between stations. The optimization model, formulated as a mixed linear programming task, consists of the minimization of two objectives: the total cost of delays and the total time of delays. The CPLEX software was applied to solve the problem. A similar approach is proposed in Reference [18].