# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm
### Managing of Train Runs
Otherwise, the algorithm returns the original train timetable and track closure plan with information of the failure. The new train timetable \(\boldsymbol{TT}\) and track closure plan \(\boldsymbol{S}\) are represented by values of time shifts \(\boldsymbol{\Delta t}^{\text{\emph{ARR}}}\), \(\boldsymbol{\Delta t}^{\text{\emph{DEP}}}\) of train runs and time shifts \(\boldsymbol{\Delta t}^{\text{\emph{C}}}\) of track closures regarding the original timetable \(\mathbf{TR}^{\text{\emph{S}}}\) and closure plan \(\mathbf{C}^{\text{\emph{S}}}\). ```
0: Data of the problem, in particular sets \(\mathbf{C}^{\text{OB}}\), \(\mathbf{C}^{\text{F}}\) of obligatory, facultative closures, respectively. 0: Values of \(\boldsymbol{y}\), \(\boldsymbol{x}\), as well as closure plan \(\boldsymbol{S}\), and timetable \(\boldsymbol{TT}\). 1: Sort the elements of \(\mathbf{C}^{\text{OB}}\) in the ascending order with respect to ratio (18) and then sort resulting sequence to ensure precedence constraints given in matrix \(\boldsymbol{O}\) to have a sequence of obligatory closures \((z_{i})_{i=1,\ldots,C^{\text{OB}}}\) as a consequence. 2: Set \(y_{n}=0\), \(\Delta t_{n}^{\text{C}}=0\), \(n=1,2,\ldots,C\), \(x_{p}=0\), \(p\in\mathbf{TR}\), \(\boldsymbol{S}=\boldsymbol{S}^{\text{G}}\), \(\boldsymbol{TT}=\boldsymbol{TT}^{\text{G}}\). 3:for\(i=1,\ldots,C^{\text{OB}}\)do
4: Run Algorithm 2 for a set of selected closures \(\mathbf{C}^{\text{S}}=\{z_{1},z_{2},\ldots,z_{i}\}\), current timetable \(\boldsymbol{TT}\), and closure plan \(\boldsymbol{S}\) (together with \(\boldsymbol{y}\)), and currently considered closure \(n\stackrel{{\Delta}}{{=}}z_{i}\), to obtain updated \(\boldsymbol{TT}\), \(\boldsymbol{S}\), \(\boldsymbol{y}\), and the actual completion time of closure \(t_{n}^{\text{CE}}=t_{n}^{\text{CES}}+\Delta t_{n}^{\text{C}}+T_{n}^{\text{C}}\). 5:if\(t_{n}^{\text{CE}}=0\) or \((t_{n}^{\text{CE}}>t_{n+1}^{\text{CES}}\) when \(o_{n,n+1}=1\) and \(i<C^{\text{OB}})\)then
6: Stop the algorithm and return \"Cannot find a feasible solution for \(\mathbf{C}^{\text{OB}}\)\". 7:endif
8:endfor
9: Sort the elements of \(\mathbf{C}^{\text{F}}\) in the ascending order with respect to the ratio (18), and then sort resulting sequence to ensure precedence constraints given in matrix \(\boldsymbol{O}\) to have a sequence of facultative closures \((z_{i})_{i=1,\ldots,M}\) as a consequence. 10:for\(i=C^{\text{OB}}+1,\ldots,C-1\)do
11: Run Algorithm 2 for a set of selected closures \(\mathbf{C}^{\text{S}}=\{j=z_{m}:m\in\{1,\ldots,i\},\ y_{j}=1\}\), current \(\boldsymbol{TT}\), \(\boldsymbol{S}\), \(\boldsymbol{y}\), and currently considered closure \(n\stackrel{{\Delta}}{{=}}z_{i}\), to obtain updated \(\boldsymbol{TT}\), \(\boldsymbol{S}\), \(\boldsymbol{y}\), and \(t_{n}^{\text{CE}}=t_{n}^{\text{CES}}+\Delta t_{n}^{\text{C}}+T_{n}^{\text{C}}\). 12:if(\(t_{n}^{\text{CE}}>0\) and \(t_{n}^{\text{CE}}\leq t_{n+1}^{\text{CES}}\) when \(o_{n,n+1}=1\))then
13: Set \(y_{n}=1\). 14:endif
15:endfor
16: Run Algorithm 2 for a set of selected closures \(\mathbf{C}^{\text{S}}=\{j=z_{m}:m\in\{1,\ldots,C\},\ y_{j}=1\}\) current \(\boldsymbol{TT}\), \(\boldsymbol{S}\), \(\boldsymbol{y}\), and currently considered closure \(n\stackrel{{\Delta}}{{=}}z_{N}\), to obtain updated \(\boldsymbol{TT}\), \(\boldsymbol{S}\), \(\boldsymbol{y}\), and \(t_{n}^{\text{CE}}=t_{n}^{\text{CES}}+\Delta t_{n}^{\text{C}}+T_{n}^{\text{C}}\). 17:if\(t_{n}^{\text{CE}}>0\)then
18: Set \(y_{n}=1\)
19:endif
20:return\(\boldsymbol{y}\), \(\boldsymbol{x}\), \(\boldsymbol{S}\), \(\boldsymbol{TT}\) where \(\boldsymbol{x}\), \(\boldsymbol{S}\), and \(\boldsymbol{TT}\) are taken from the last run of Algorithm 2. ```  
**Algorithm 1** selection of closures```
1:Data of the problem, \(\mathbf{x}\), \(\mathbf{S}\), \(\mathbf{TT}\), \(\mathbf{C}^{\mathsf{S}}\), specified closure \(n\). 2:\(\mathbf{x}\), \(\mathbf{S}\), \(\mathbf{TT}\), \(t_{n}^{\text{CE}}\) for specified closure \(n\).