# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm
### Managing of Train Runs
12:endif
13:endif
14:endfor
15:add train run \(m\) to a set \(\mathbf{TR}^{\text{S}}_{n}\subseteq\mathbf{TR}^{\text{S}}\) (\(\mathbf{TR}^{\text{S}}_{n}=\mathbf{TR}^{\text{S}}_{n}\cup\{m\}\))
16:endif
17:endfor
18:for each\(cl\in\mathbf{C}^{\text{S}}\)do
19:if a closure \(cl\) is planned on some track in connection indicated in matrix \(\boldsymbol{E}_{n}\) (\(\{k\in\mathbf{K},v_{a},v_{b}\in\mathbf{V}_{n},e_{n,a,b,k}=1,R^{\text{C}}_{cl,a,b,k}=1\}\
eq\emptyset\)) then
20: Add closure \(cl\) to \(\mathbf{C}^{\text{S}}_{n}\subseteq\mathbf{C}^{\text{S}}\) (\(\mathbf{C}^{\text{S}}_{n}=\mathbf{C}^{\text{S}}_{n}\cup\{cl\}\)). 21:endif
22:endfor
23:Execute Algorithm 4 for \(\mathbf{C}^{\text{S}}_{n}\), \(\mathbf{TR}^{\text{S}}_{n}\), \(\left|\mathbf{TR}^{\text{S}}\right|\), \(\mathbf{G}_{n}\), \(q\), \(\boldsymbol{S}^{\prime}\), and \(\boldsymbol{TT^{\prime}}\), to obtain time shifts of the train runs and closures. 24:if Algorithm 4 returned \"No solution\" then
25: Stop the algorithm and return \"Cannot find a feasible solution\". 26:endif
27: Include time shifts of the train runs and closures obtained by Algorithm 4 into new train timetable \(\boldsymbol{TT^{\prime}}\), and closure plan \(\boldsymbol{S}^{\prime}\). 28:endfor
29:Update \(\boldsymbol{TT^{\prime}}\) by recalculating \(\Delta t^{\text{ARR}}_{i,p}=\sum_{j\in\mathbf{V}}(\Delta t^{\text{DEP}}_{j, p}\cdot\sum_{k\in\mathbf{K}}r^{\text{T}}_{p,j,k})\)
30:return\(\boldsymbol{S}=\boldsymbol{S}^{\prime}\) and \(\boldsymbol{TT}=\boldsymbol{TT^{\prime}}\). ```

**Algorithm 3** decomposition of the railway network

### Determining of Time Shifts for Train Runs and Closures

Even after preceding decompositions, the remaining non-linear optimization problem is still hard to solve in a reasonable amount of time for realistically sized instances. To obtain a solution quickly, it is necessary to perform further simplifications. Two-stage decomposition is proposed. Firstly, three types of sub-problems are derived via a decomposition. Secondly, relatively quick solution algorithms, referred to as Algorithm 4, Algorithm 6, Algorithm 7, are used to solve each sub-problem. Decomposition is carried out through the introduction of additional decision variables. At each track separately, let the order of track usage by either train runs or closures be denoted as \(\theta^{i,j,k}=[\theta_{q}^{i,j,k}]_{q\in\{1,2,\ldots,\Theta^{i,j,k}\}}\), where \(i\) is the departure station, \(j\) is the arrival station, \(k\) is the index of a specific track between stations, and \(\Theta^{i,j,k}\) is the number of runs and closures on that track. Let us define a series \(\boldsymbol{\Psi}^{i,j,k}=[\Psi_{q}^{i,j,k}]_{q\in\{1,2,\ldots,\Theta^{i,j,k}\}}\) with elements \(\Psi_{q}^{i,j,k}=0(1)\) if there is a train run (if it is a closure) on the position \(q\) of the ordering \(\boldsymbol{\theta}^{i,j,k}\). Furthermore, for each station, let us denote the order in which train runs enter the station as \(\boldsymbol{\Lambda}^{i}=[\lambda_{q}^{i}]_{q\in\{1,2,\ldots,\Lambda^{i}\}}\), where \(i\) is the index of the station, and \(\Lambda^{i}\) is the number of runs entering the station. Determination of orders \(\boldsymbol{\theta}^{i,j,k}\) and \(\boldsymbol{\Lambda}^{i}\) for every track and every station reduces the problem of determining the time shifts for train runs and closures into a linear programming problem which can be solved with exact methods (i.e., an LP solver). The first set of sub-problems is solved separately for every track to obtain the orders \(\boldsymbol{\theta}^{i,j,k}\). For this purpose, a local criterion being a particular case of criterion (17) is introduced:

\[Q_{1}^{i,j,k}=\sum_{p\in\mathbf{TR}_{i,j,k}}|\Delta t_{i,p}^{\text{DEP}}|+\sum _{p\in\mathbf{TR}_{j,k}}|\Delta t_{j,p}^{\text{DEP}}|, \tag{19}\]

where \(\mathbf{TR}_{i,j,k}=\{p\in\mathbf{TR}_{n}^{\text{S}}:R_{p,i,j,k}^{\text{T}}+ e_{n,i,j,k}=2\}\) is the set of train runs going through track \((i,j,k)\). This criterion is the total time shift for train runs limited to a single track at a time.