# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm
### Managing of Train Runs
Furthermore, let us define by \(\mathbf{C}_{i,j,k}\) the set of closures on a given track. Algorithm 6, applied for solving the sub-problem of finding the usage order for a single track, uses, in addition to problem data passed on to Algorithm 4, set \(\mathbf{TR}_{n}^{\text{S}}\), which is a sub-set of \(\mathbf{TR}_{n}^{\text{S}}\), determined during the execution of Algorithm 4. The following Algorithm 6, as well as other algorithms presented next in this subsection, uses solutions of problems **4.1.lin**, **4.2.lin**, and **4.lin**, which are described in Reference [64]. The problem **4.1.lin** is the problem of determining the time shifts for a single track under the assumption that the order of train run or closure execution is fixed (the variable \(\boldsymbol{\theta}^{i,j,k}\) is fixed). Under the assumption, the problem of time shift determination (times when train enters the track or the closure starts) becomes a linear programming problem and can be solved quickly and exactly. Similarly, in the problem **4.2.lin**, we consider a single station and assume that the variable \(\boldsymbol{\Lambda}^{i}\) is fixed; this leads to another linear problem of time shift determination (times when train enters the station). Finally, under fixed values of \(\boldsymbol{\theta}^{i,j,k}\) for each track and of \(\boldsymbol{\lambda}^{i}\) for each station, the problem of time-shift determination for the whole network, i.e., **4.lin**, is also linear. The second set of sub-problems is solved separately for every station to obtain orderings \(\boldsymbol{\lambda}^{i}\). Analogously to the first set of sub-problems, a local criterion based on (17) is defined. \[Q_{2}^{j}=\sum_{p\in TR_{i}}|\Delta t_{i,p}^{\text{ARR}}|, \tag{20}\]

where \(\mathbf{TR}_{i}=\bigcup\limits_{k\in\mathbf{K}}(\mathbf{TR}_{i,j,k}\cup \mathbf{TR}_{j,j,k})\) is the set of train runs on tracks adjacent to station \(i\). This criterion expresses the total time shift for train runs on a single station. Let us denote the tracks adjacent to \(i\) as \(\mathbf{K}_{i}^{\text{ADI}}=\{(l,j,k):l,j\in\mathbf{V}_{n},k\in\mathbf{K}, \mathbf{TR}_{i,j,k}\cup\mathbf{TR}_{i,j,k}\
eq\emptyset\}\). Algorithm 7, used for solving the sub-problem of finding the ordering of train runs entering a single station, is given as follows. Finally, the full Algorithm 4 with a distinct auxiliary Algorithm 5 are both given as follows. Please note that, if Algorithm 7 changes \(\Delta t^{\text{ABEP}}_{i,p}\), the time shifts \(\Delta t^{\text{DEP}}_{i,p}\) have to be accordingly changed be Algorithm 4 to satisfy \(\forall_{p\in\mathbf{TR}_{i}}(\Delta t^{\text{DEP}}_{i,p}-\Delta t^{\text{ AARR}}_{i,p})\sum_{k\in\mathbf{K}}r^{\text{T}}_{p,i,j,k}=0\). The complexity of Algorithm 4 is dependent on the complexity of the selected linear programming routine. Assuming [PERSON]'s algorithm [65] is used, then the complexity is given as follows \(O[(TR+C)^{3.5}*B*E^{2}+TR^{3.5}*B*V^{2}]\), where \(B\) is the number of bits needed to encode the longer of train and closure data. The complexity of the whole multi-level algorithm is, therefore, \(O\{(TR*C*[(TR+C)^{3.5}*B*E^{2}+TR^{3.5}*B*V^{2}]\}\). ```
0: Data for the sub-network: \(\mathbf{G}_{n}\), \(\mathbf{C}^{\text{S}}_{n}\), \(\mathbf{TR}^{\text{S}}_{n}\). Train run \(q\) (\(q\in\mathbf{TR}^{\text{S}}_{n}\)) selected for rerouting. Closure ordering matrix \(\boldsymbol{O}\). 0: Time shifts \(\Delta t^{\text{DEP}}_{i,p}\), \(\Delta t^{\text{C}}_{n}\), and new train routes \(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}\). 1:if\(q\
eq NULL\)then
2:return solution of Algorithm 5 for \(\mathbf{G}_{n}\), \(\mathbf{C}^{\text{S}}_{n}\), \(\mathbf{TR}^{\text{S}}_{n}\), \(q\), and \(\boldsymbol{O}\). 3:else
4: Set \(\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. 5: Let \(p=1\).