# An Algorithm for Rescheduling of Trains under Planned Track Closures
## 1 Introduction and Contributions
### Contributions and Structure of the Paper  
Unlike most of the existing works, we consider train rescheduling and closure planning as a joint optimization task modeled as the nonlinear mixed integer optimization problem. Due to its high complexity, we propose a heuristic algorithm which is based on a decomposition of the problem into smaller sub-problems.  
Current considerations refer to Reference [5] and extend it, taking into account the possibility of train rerouting. In our approach, a new route may be determined as any track sequence along a given path (sequence of stations), and it may also include the substitute transportation for some of them. Moreover, the proposed method of rerouting can be further enhanced, as it was done in Reference [6], where the authors analyze a rerouting mechanism that permits changes in the order and the number of tracks visited by a train.  
The novelty of our contribution is three-fold:  
* First, we formulate a novel joint train rescheduling and closure planning as the nonlinear mixed integer optimization problem valid for a wide class of railway networks with the possibility of rerouting and substitutive transport launching. Moreover, our model allows to control each event (e.g., each train runs conflict) independently, in contrast to the methods applying aggregated approach e.g., as the one presented in Reference [7]. The proposed model and resulting algorithms enable solving investigated decision-making problems for general railway networks, but they have been developed taking also into account the specificity of such networks in Poland.
* Second, due to the high complexity of the formulated initial problem, we propose a multi-level heuristic solution algorithm based on the decomposition allowing the solution of smaller-size sub-problems. The choice of the heuristic algorithm suitable for real-world applications is justified by the NP-hardness of the problem. The proposed formulation of the optimization problem allows for the rationale of this property.
* Third, we confirm the usefulness of the algorithm via the extensive simulation experiments using both randomly generated data but also data originated from the real-world railway network comprising almost 150 stations and 100 trains. The remainder of this paper is organized as follows. Closure planning practices in Poland are outlined in Section 3, and it follows a brief review of related work given in Section 2. The next section presents the model of the considered joint problem of train rescheduling and track closure planning which is based on the graph-matrix representation of a railway network, a train runs timetable, and track closures. Section 5 is devoted to the detailed description of proposed heuristic solution algorithm. The results of experimental evaluation of the algorithm, both for a single track and, first of all, for a real-world case, are given in Section 6. A real-world railway network consisting of up to 95 train runs and 149 train stations serves for the evaluation of the algorithm's quality with respect to different algorithm's, as well as problem's, parameters. Final remarks complete the paper.