# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm
### Managing of Train Runs  
The management of train runs is performed by Algorithms 2 and 3 supported by Algorithm TGA, as well as by the solution of an auxiliary sub-problem **ZP**[64]. It is focused on obtaining such a sub-set of train runs, which enables the presence of a given set of track closures. If any obligatory train run cannot be included into the timetable due to a failing of constraints, information of the closure set infeasibility is returned to the track closure management part. The initial proposition of a train run set for the inclusion into the solution is obtained by Algorithm 2. This algorithm uses the decomposition procedure (Algorithm 3) to check if all suggested train runs could be performed, what is represented by a new train timetable and a new track closure plan. If Algorithm 3 fails to find a feasible timetable and a track closure plan, Algorithm 2 is stopped returning the last feasible train timetable and track closure plan with information if all obligatory train runs are included in this timetable. Let us describe Algorithm 2 for indicating train runs to be placed into the new train timetable starting from the introduction of the following auxiliary variable \(U_{p}=\frac{\sum_{i}\sum_{j}\left(\sum_{k}R_{j,i,k}^{T}\right)\left(\sum_{ \varphi_{i}\
eq\text{\emph{ARR}},P^{\text{DEP}}_{j}\cap\left|\varphi_{i} \
eq\text{\emph{ARR}},P^{\text{DEP}}_{j}\right|\
eq\text{\emph{ARR}},P^{ \text{DEP}}_{j}\
eq\text{\emph{2}}}\right)}{\sum_{i}\sum_{j}\sum_{k}p_{i,k}^{ \text{DEP}}}\) referred to as conflicts index for the train run. The variable indicates how many other than \(p\) trains are located at the same time on the \(p\)'s train trail (or on the railway stations of this trail) in relation to the number of all tracks traveled by the \(p\)th train. The usage of Algorithm 2 allows estimating whether it is likely to have a feasible solution of train rescheduling and track closure planning for the whole railway network when the new closure or the new train run is added. In consequence, Algorithm 2 uses the solution of the parameterized sub-problem **ZP**, for which the formal definition is given in Reference [64]. **ZP** limits the whole network to a single trail affected by the current change in the closure plan or the set of accepted train runs. This change is accomplished by assigning start times of closures and making train run timetable for this trail. The aim is to settle if we can shift closures and train runs by no more than a given period \(\Delta\) (algorithm parameter), which eliminates conflicts. We also assume that each train run may change its track between considered stations, so the new track is indicated by the variable \(W_{p,k}\). Although **ZP** is a constraint satisfaction sub-problem, it may be easily solved by a linear programming solver, e.g., 'lpsolve' [63]. Notice that, even if the solution of the problem **ZP** can be found, it does not guarantee the existence of solution for the whole railway network. Whenever Algorithm 3 is launched, it uses the results of Algorithm TGA, which takes **G**, \(\boldsymbol{TT}\), and **TR** as an input and returns the number of groups \(\eta\) and set \(\mathbf{GR}=\mathbf{E}\times\{1,2,\ldots,\eta\}\), where \(\mathbf{E}=\{(i,j,k):e_{i,j,k}=1\}\). The set **GR** represents the assignments of each track to a number corresponding to the index of one of the defined groups. Algorithm 3 divides the railway network into sub-networks and, after the grouping of all tracks, complements them with artificial ones. Artificial tracks connect stations which were not yet connected but are consecutive stations of some train run in its route. Then, for each sub-network, Algorithm 4 is consecutively executed to obtain a new timetable and a track closure plan corresponding to this fragment of the network. If, for all sub-networks, the feasible solution is found, then all results are combined into a single train timetable and track closure plan, as well as returned together with information about the success.