# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm
### Managing of Train Runs
3:Let \(\mathbf{FT}\) be the list of train runs that are allowed to be canceled and sorted in not ascending order with respect to index \(U_{p}\). Set \(x_{p}=1(0)\) if \(p\in\mathbf{\mathrm{TR}}^{\text{OB}}\) (otherwise). Let \(\mathbf{\mathrm{TR}}^{\text{S}}=\{p\in\mathbf{\mathrm{TR}}:x_{p}=1\}\). 4:Solve the task \(\mathbf{\mathrm{ZP}}((i,j)\), \(\mathbf{x}\), \(\mathbf{S}\), \(\mathbf{TT}\), \(\mathbf{C}^{\mathsf{S}}\), \(\mathbf{\mathrm{TR}}^{\text{S}}\), \(n\)), where \(i\), \(j\) satisfies: \(\sum_{k\in\mathbf{\mathrm{K}}}R_{n,i,j,k}^{\text{CE}=1}\)
5:if the feasible solution is not found in Step 2 then
6:return \"No solution\"
7:else
8: Run Algorithm 3 for current \(\mathbf{S}\), \(\mathbf{TT}\), \(\mathbf{\mathrm{TR}}^{\text{S}}\), \(\mathbf{C}^{\mathsf{S}}\) and Null (as currently considered facultative train run) and obtain new \(\mathbf{S}\) and \(\mathbf{TT}\)
9:if the solution is found in Step 6 then
10: calculate \(t_{n}^{\text{CE}}\) basing on current \(\mathbf{S}\)
11:else
12:return \"No solution\"
13:endif
14:endif
15:endif
16:if the list \(\mathbf{FT}\) is empty then
17:go to Step 33. 18:endif
19:Take the first train run out from the list \(\mathbf{FT}\) and obtain its index \(p\). 20:Set \(x_{p}=1\)
21:Set \(\mathbf{\mathrm{TR}}^{\text{S}}=\{p\in\mathbf{\mathrm{TR}}:x_{p}=1\}\). 22:for each pair of stations \((i,j)\) such that \(\sum_{k\in\mathbf{\mathrm{K}}}R_{p,i,j,k}^{\text{TE}=1}\)do
23: solve \(\mathbf{\mathrm{ZP}}((i,j)\), \(\mathbf{x}\), \(\mathbf{S}\), \(\mathbf{TT}\), \(\mathbf{C}^{\mathsf{S}}\), \(n\))
24:if the feasible solution is not found in Step 20 then
25: Set \(x_{p}=0\)
26:go to step 13. 27:endif
28:endfor
29:Run Algorithm 3 for current \(\mathbf{S}\), \(\mathbf{TT}\), \(\mathbf{\mathrm{TR}}^{\text{S}}\), and \(\mathbf{C}^{\mathsf{S}}\), \(p\), and obtain new \(\mathbf{S}\) and \(\mathbf{TT}\). 30:if the feasible solution is not found in Step 26 then
31: Set \(x_{p}=0\)
32:else
33: calculate \(t_{n}^{\text{CE}}\) basing on current \(\mathbf{S}\)
34:endif
35:go to step 13
36:return \(\mathbf{x}\), \(\mathbf{S}\), \(\mathbf{TT}\), and \(t_{n}^{\text{CE}}\) for specified closure \(n\). ```

**Algorithm 2** selection of trains
```
1:Data of the problem, in particular sets \(\mathbf{C}^{\text{S}}\), \(\mathbf{TR}^{\text{S}}\) of selected closures and train runs, respectively, selected train run for rerouting \(q\in\mathbf{TR}^{\text{S}}\), current train timetable \(\boldsymbol{TT}\) and track closure plan \(\boldsymbol{S}\). 2:Closure plan \(\boldsymbol{S}\), train timetable \(\boldsymbol{TT}\). 3:Set \(\boldsymbol{S}^{\prime}=\boldsymbol{S}\) and \(\boldsymbol{TT^{\prime}}=\boldsymbol{TT}\), get from Algorithm TGA results: grouping set \(\mathbf{GR}\), which associates each track with a group number to which it belongs, and a number of groups \(\eta\). 4:for\(n=1,\ldots,\eta\)do
5: Construct a railway network \(\mathbf{G}_{n}=<\mathbf{V}_{n},\boldsymbol{E}_{n}>\) (not necessary connected) where \(\mathbf{V}_{n}=\{v\in\mathbf{V}:w\in\mathbf{V},k\in\mathbf{K},((v,w,k),n),((w,v,k),n)\in\mathbf{GR}\}\), \(\boldsymbol{E}_{n}=[e_{n,i,j,k}]_{i,j\in\mathbf{V},k\in\mathbf{K}\cup\{k+1,K+2, \ldots,K+TR\}}\), and \(e_{n,i,j,k}=\left\{ \begin{array}{cl}1&\text{for}&((i,j,k),n)\in\mathbf{GR}\\ 0&\text{for}&\text{otherwise}\end{array} \right.\)
6:for each\(m\in\mathbf{TR}^{\text{S}}\)do
7: Construct a path \(\pi_{n,m}\) (string of stations \(v\in\mathbf{V}_{n}\)) composed of stations of the route of the train run \(m\) that belong also to \(\mathbf{V}_{n}\). 8:if\(\pi_{n,m}\) exists then
9:for each pair of consecutive stations \((v_{a},v_{b})\) from the path \(\pi_{n,m}\). do
10:if for any track \(k\) connecting stations \(a\) with \(b\), there is no connection indicated in matrix \(\boldsymbol{E}_{n}\) (\(\forall_{k\in\mathbf{K}}(e_{n,a,b,k}==0)\)) then
11: Add a virtual track to \(\boldsymbol{E}_{n}\) (set \(e_{n,a,b,K+m}=1\)).