# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 4 Joint Problem of Train Rescheduling and Track Closure Planning
### Mathematical Model
#### 4.5.3 Final Model and Its Analysis
To sum up, the following joint train rescheduling and track closure planning problem is considered and solved. Decisions are made in relation to the railway system which consists of a railway infrastructure and train runs described by **G**, **V**, **TR**, **TR\({}^{\text{OB}}\), **TT\({}^{\text{G}}\)**, **D**, \(CAP_{i}\), \(T_{i,p}^{\text{ARB}}\), \(T_{i,p}^{\text{DEP}}\), \(T_{i,p}^{\text{DP}}\), \(t_{i,p}^{\text{ID}}\), \(i,j\in\textbf{V}\), \(p\in\textbf{TR}\), \(\alpha\),\(\beta\). The planned closures are also given in the form of **C**, **C**, **C**OB, **O**, **S\({}^{\text{G}}\)(**S\({}_{n}=<R_{n}^{\text{C}},t_{n}^{\text{CES}},t_{n}^{\text{CLS}},T_{n}^{ \text{C}}>,n\in\textbf{C}\)**). The auxiliary data \(T^{\text{DL}}\), \(T^{\text{DE}}\), \(T^{\text{E}}\) are known, as well. It is necessary to determine the interconnected collection of decisions: \(\boldsymbol{\Delta t}^{\text{C}}\), \(\boldsymbol{y}\) constituting the resulted track closure plan, and \(\boldsymbol{r}^{\text{T}}\),\(\boldsymbol{\Delta t}^{\text{ARR}}\), \(\boldsymbol{\Delta t}^{\text{DEP}}\), \(\boldsymbol{x}\) defining the new timetable plan _TT_ subject to constraints (1)-(16) to minimize the criterion (17). The conducted analysis of the formulated nonlinear mixed integer optimization problem referred to as **PR** made it possible to put forward and prove the following theorem. Joint train rescheduling and track closure planning problem is NP-hard. Proof. : Let us consider the NP-hard problem of task scheduling around a common date presented in Reference [62]. Given one executor and \(J\) tasks, durations of tasks \(duration_{j}\geq 0,j=1,2,\ldots,J\) and a common deadline \(deadline\leq\sum_{j\in\{1,2,\ldots,J\}}duration_{j}\) find a schedule, i.e., task completion times \(finish_{j}\), that minimizes the total earliness and tardiness of each task, i.e., \(quality=\sum_{j\in\{1,2,\ldots,J\}}|finish_{j}-deadline|\). We show that this scheduling problem reduces, in polynomial time, to the investigated problem **PR**. We accomplish this by showing that we can reduce the scheduling problem to an equivalent problem **PR** with only single track and carefully selected set of closures. We take a time horizon sufficient to encompass the duration of all tasks (\(T^{\text{H}}=\sum_{j}duration_{j}\)). Let us assume that all closures and train runs are obligatory (\(y_{n}=1,x_{p}=1\)). Define the graph **G** so that there are 3 stations connected in a cycle \(0\to 1\to 2\to 0\), and that there are \(J+1\) tracks between stations 1 and 2. We take \(J\) trains, where each train moves once through the whole cycle of stations but through different track each: \(p\)th train takes \(p\)th track between stations 1 and 2 (\(R_{p,0,1,1}^{\text{T}}=1\), \(R_{p,1,2,p}^{\text{T}}=1\), \(R_{p,2,0,1}^{\text{T}}=1\)). The departure time for the artificial station is 0 for every train and so is the arrival in station 1. Departure time in station 1, as well as minimum dwelling time, is set to \(deadline-duration_{j}\). Arrival time in station 2 for the \(p\)th train is equal to \(deadline\). Minimum dwelling time in station 2 is 0. Maximal dwell times are set to be very large (\(T^{\text{DL}}=T^{\text{H}}\)). Note that the schedule is feasible. Let us further consider a set of \(J\) closures, where the \(n\)th closure takes up track \(n\) of the connection between stations 1 and 2 (\(R_{n,1,2,n}^{\text{C}}=1\)) with the earliest and the latest start times all bound by 0 and very large durations (\(t_{n}^{\text{CES}}=t_{n}^{\text{CLS}}=0,T_{n}^{\text{C}}=T^{\text{H}}\)). The addition of closures forces all the trains onto the last track \(J+1\), where they cannot proceed in parallel. Due to dwelling times in station 2, the quality criterion is equal to \(Q=\sum_{j\in\{1,2,\ldots,J\}}|\Delta t_{1,j}^{\text{DEP}}|+\sum_{j\in\{1,2, \ldots,J\}}|\Delta t_{2,j}^{\text{DEP}}|=2\sum_{j\in\{1,2,\ldots,J\}}|t_{2,j} ^{\text{DEP}}+\Delta t_{2,j}^{\text{DEP}}-deadline|\). Sum \(t_{2,j}^{\text{DEP}}+\Delta t_{2,j}^{\text{DEP}}\) is the moment the train run ends.