# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm
### Managing of Train Runs
6: Let \(\mathbf{TR}^{\text{S,SUB}}_{n}=\mathbf{TR}^{\text{S}}_{n}\cup\mathbf{TR}^{ \text{S}}_{n}(p)\), where \(\mathbf{TR}^{\text{S}}_{n}(p)\) is the \(p\)th element of \(\mathbf{TR}^{\text{S}}_{n}\). 7: Let \(q=\mathbf{TR}^{\text{S}}_{n}(p)\). 8: Execute Algorithm 5 for \(\mathbf{G}_{n}\), \(\mathbf{C}^{\text{S}}_{n}\), \(\mathbf{TR}^{\text{S,SUB}}_{n}\), \(q\), and \(\boldsymbol{O}\). 9:if solution does not exist then
10:return no solution. 11:else
12: Update \(\Delta t^{\text{DEP}}_{i,p}\), \(\Delta t^{\text{C}}_{n}\), \(r^{\text{T}}_{p,i,j,k}\) for \(i,j\in\mathbf{V}_{n},p\in\mathbf{TR}^{\text{S}}_{n},n\in\mathbf{C}^{\text{S}}_ {n}\) using values returned by Algorithm 5. 13:endif
14:if\(p<|\mathbf{TR}^{\text{S}}_{n}|\)then
15: Let \(p=p+1\). 16:go to 5. 17:endif
18:endif
19:return\(\Delta t^{\text{DEP}}_{i,p}\), \(\Delta t^{\text{C}}_{n}\), \(r^{\text{T}}_{p,i,j,k}\) for \(i,j\in\mathbf{V}_{n},p\in\mathbf{TR}^{\text{S}}_{n},n\in\mathbf{C}^{\text{S}}_ {n}\). ```

**Algorithm 4** determination of time shifts for train runs and closures

```
0: Data for the sub-network: \(\mathbf{G}_{n}\), \(\mathbf{C}_{n}^{\text{S}}\), \(\mathbf{TR}_{n}^{\text{S,SUB}}\). Train run \(q\) (\(q\in\mathbf{TR}_{n}^{\text{S}}\)) selected for rerouting. Closure ordering matrix \(\mathbf{O}\). 0: Time shifts \(\Delta t_{i,p}^{\text{DEP}}\), \(\Delta t_{n}^{\text{C}}\), and new train routes \(r_{p,i,j,k}^{\text{T}}\) for \(i,j\in\mathbf{V}_{n}\), \(p\in\mathbf{TR}_{n}^{\text{S,SUB}},n\in\mathbf{C}_{n}^{\text{S}}\). 1: Let \(\forall p\in\mathbf{TR}_{n}^{\text{S,SUB}},i\in\mathbf{V}_{n}:\Delta t_{i,p}^ {\text{DEP}}=0\), \(\forall n\in\mathbf{C}_{n}^{\text{S}}:\Delta t_{n}^{\text{C}}=0\). 2:for each\((i,j,k)\in\mathbf{E}_{n},i<j\)do
3: Obtain ordering \(\boldsymbol{\theta}^{i,j,k}\) using Algorithm 6. 4:if no ordering was found then
5: go to 11. 6:endif
7:endfor
8:for each\(p\in\mathbf{V}_{n}\)do
9: Obtain ordering \(\lambda^{i}\) using Algorithm 7. 10:if no ordering was found then
11: go to 11. 12:endif
13:endfor
14: Solve the linear problem of time shift determination for given orderings (**4.lin**). 15:if no solution was found and \(q\in\mathbf{TR}_{n}^{\text{S,SUB}}\)then
16: Let \(\mathbf{TR}_{n}^{\text{S,SUB}}:=\mathbf{TR}_{n}^{\text{S,SUB}}\backslash\{q\}\). 17: go to 1. 18:else
19:if no solution was found then
20:for eachpair of stations \((i,j)\) on the route for the run \(q\).do
21: Find a feasible track \(k\in\mathbf{K}\). 22:if no track was found and \(b_{i,j}=1\)then
23: Verify if track \(k=0\) is feasible. 24:endif
25:if a feasible track was found then
26: Set \(\Delta t_{i,p}^{\text{DEP}}\) to the lowest feasible value, set \(r_{q,i,j,k}^{\text{T}}=1\), \(\forall l\
eq k:r_{q,i,j,l}^{\text{T}}=0\). 27:else
28:return no solution. 29:endif
30:endfor
31:endif
32:endif
33:return\(\Delta t_{i,p}^{\text{DEP}}\), \(\Delta t_{n}^{\text{C}}\), \(r_{p,i,j,k}^{\text{T}}\) for \(i,j\in\mathbf{V}_{n},p\in\mathbf{TR}_{n}^{\text{S,SUB}},n\in\mathbf{C}_{n}^{ \text{S}}\). ```

**Algorithm 5** determination of time shifts for train runs and closures```
1: Selected track \((i,j,k)\). Data for the sub-network: \(\mathbf{G}_{n}\), \(\mathbf{C}_{n}^{\text{S}}\), \(\mathbf{TR}_{n}^{\text{S}}\). Closure ordering matrix \(\boldsymbol{O}\), sets of train runs \(\mathbf{TR}_{i,j,k}\) and closures \(\mathbf{C}_{i,j,k}\) on the track. 2: Locally optimal ordering \(\boldsymbol{\theta}^{i,j,k}\), \(\boldsymbol{\Psi}^{i,j,k}\) or no solution. 3: Empty the ordering \(\boldsymbol{\theta}^{i,j,k}\leftarrow()\), \(\boldsymbol{\Psi}^{i,j,k}\leftarrow()\)
4:while either \(\mathbf{TR}_{i,j,k}\) or \(\mathbf{C}_{i,j,k}\) is nonempty do
5: From the sets of every train run \(\mathbf{TR}_{i,j,k}\) and every closure \(\mathbf{C}_{i,j,k}\) and every possible position in \(\boldsymbol{\theta}^{i,j,k}\), \(\boldsymbol{\Psi}^{i,j,k}\) find those that minimize \(Q_{1}^{i,j,k}\) by solving ) linear time shift resolution problems for a single track (**4.1.lin**). Preserve ordering given by \(\boldsymbol{O}\).