# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 5 Heuristic Solution Algorithm  
The optimization problem **PR** formulated in the previous section should be solved in a reasonable amount of time. For example in Poland, at least a single feasible solution is required within 48 h. It is very tough to fulfill such requirements due to the NP-hardness of **PR**, as well as its non-linearity and the huge dimension with respect both to the number of variables and to the number of constraints. The whole Polish railway network there is represented by over \(10^{12}\) binary and \(10^{8}\) integer variables. The transformation of the considered problem into MIP using 'big M' to solve it by a known solver failed. It resultedin the enormous growth of the problem's dimension, and, in consequence, the approach turned out useless due to the non-acceptable computation time. Another considered approach assumed the application of selected metaheuristics. It also failed as the significant calculation effort was mostly devoted to checking infeasible solutions. Unfortunately, there is no a simple method for the generation of any initial train runs timetable and a closure plan fulfilling all the constraints under consideration. The utmost case is possible for a metaheuristic-based solution algorithm when the feasible execution time can elapse before any solution is sought. Therefore, the problem-specific heuristic algorithm is proposed, which is based on some simplifications and decompositions neglecting some connections between variables and constraints. However, due to the complexity of the problem, the solution algorithm might not guarantee feasible solutions for some of the strongly constrained cases. The detailed presentation of the algorithm's components in the subsequent sub-sections follows the overview of the algorithm. A multi-level algorithm of the hierarchical parallel structure is proposed, as in Figure 3. There are four main levels of algorithms which are dependent on one another, i.e., an upper level algorithm requires (usually multiple) solutions of the lower level algorithm. Algorithm 1 is responsible for the selection of facultative closures. Algorithm 2 provides the selection of facultative train runs. Algorithm 3 is responsible for decomposition of the railway network into smaller, more manageable parts. This is done with the help of a separate Track Grouping Algorithm (TGA). Finally, Algorithm 4 is responsible for finding actual schedules under given closures, train runs and decomposition. Algorithm 4 itself is further divided into Algorithms 5, 6, and 7. Those sub-algorithms are run for every sub-network that was obtained with the use of Algorithm 3. Algorithm 1 sequentially approves individual closures for launching in such a way to ensure the generation of feasible timetables. The feasibility of a current closure is checked by all other algorithms. Algorithm 1 decides via \(y_{n}\) on the inclusion of the current closure into the set of accepted closures according to information returned by Algorithm 2. However, it is necessary to cover all obligatory closures. On the analogous basis, Algorithm 2 using \(x\) sequentially, i.e., one by one, forms the set of accepted trains for the new timetable. It takes into account information returned by Algorithm 3 which, in turn, is launched at every iteration of Algorithm 2. Algorithm 3 assumes the decomposition of a railway network performed by the Track Grouping Algorithm TGA into \(\eta\) groups (railway sub-networks). For each sub-network, Algorithm 4 is launched to obtain train runs and track closures time shifts \(\mathbf{\Lambda}t^{\text{ARR}}\), \(\mathbf{\Lambda}t^{\text{DEP}}\), and \(\mathbf{\Lambda}t^{\text{C}}\) for this fragment of the network. If rerouting is needed, then Algorithm 4 also returns the routes \(\mathbf{r}^{\text{T}}\). The following optimization tasks are performed by Algorithm 4 for every sub-network: a track order, a station order, and a time shift resolution, where first two tasks are Mixed Integer Linear Programming (MILP), while the last one is the Linear Programming (LP).