Next Article in Journal
A Novel Mixed Reality Solution Based on Learning Environment for Sutures in Minor Surgery
Next Article in Special Issue
Prediction of Peak Particle Velocity Caused by Blasting through the Combinations of Boosted-CHAID and SVM Models with Various Kernels
Previous Article in Journal
A Clinical-Based Diagnostic Approach to Cerebellar Atrophy in Children
Previous Article in Special Issue
Adaptive Multi-Level Search for Global Optimization: An Integrated Swarm Intelligence-Metamodelling Technique
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

An Algorithm for Rescheduling of Trains under Planned Track Closures

Department of Computer Science and Systems Engineering, Faculty of Computer Science and Management, Wroclaw University of Science and Technology, 27 Wyb. Wyspianskiego St., 50-370 Wroclaw, Poland
*
Author to whom correspondence should be addressed.
These authors contributed equally to this work.
Appl. Sci. 2021, 11(5), 2334; https://doi.org/10.3390/app11052334
Submission received: 30 January 2021 / Revised: 16 February 2021 / Accepted: 23 February 2021 / Published: 6 March 2021
(This article belongs to the Collection Heuristic Algorithms in Engineering and Applied Sciences)

Abstract

:
This work considered a joint problem of train rescheduling and closure planning. The derivation of a new train run schedule and the determination of a closure plan not only must guarantee the satisfaction of all the given constraints but also must optimize the number of accepted closures, the number of approved train runs, and the total time shift between the resultant and the original schedule. Presented is a novel nonlinear mixed integer optimization problem which is valid for a broad class of railway networks. A multi-level hierarchical heuristic algorithm is introduced due to the NP-hardness of the considered optimization problem. The algorithm is able, on an iterative basis, to jointly select closures and train runs, along with the derivation of a train schedule. Results obtained by the algorithm, launched for the conducted experiments, confirm its ability to provide acceptable and feasible solutions in a reasonable amount of time.

1. Introduction and Contributions

1.1. Introduction

Scheduling of trains resulting in customer-friendly timetables is a crucial management task in railway transportation. The determination of a schedule of trains is a complex and a challenging thing in itself, even if solved in the presence of full, crisp, and stable information, e.g., References [1,2,3,4]. Unfortunately, such information is unavailable in real-world conditions when different disruptions can occur. Despite a variety of reasons for the disruptions, all of them result in derogation from timetables and delayed arrivals at destinations for railway customers. The outages can be unplanned, e.g., due to infrastructure and facility breakdowns, the acts of God or planned, e.g., connected with the preventive maintenance of infrastructure. Considerations in the paper are focused on the latter case when planned closures of tracks (also named possessions) are taken into account. From now on, a closure is understood as a period when a part of a rail network, i.e., a defined collection of rail tracks, is not available for trains. A case with a given set of closures is only investigated in the paper. Each closure affects an ongoing timetable. A collection of closures can bring about the modification of trains’ arrival and departure times at stations (and other points on of the railway network—further called stations—where merging/division of tracks can take place or where trains can overtake one another or stop) or even the cancellation of some trains. The change of an ongoing timetable for trains is called the train rescheduling, which is obligatory due to the necessity to manage a given set of closures. Depending on a size of the set of closures, as well as durations of closures and their time and place relationships, the acceptance of all closures may not be possible. So, the proper closure planning is necessary as it allows for a trade-off between the possibly highest number of accepted closures and the as small as possible deterioration of the original timetable for trains. Such planning and the rescheduling of trains are two important tasks faced by railway transportation operators.

1.2. 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.

2. Related Work

The problem of train rescheduling under planned closures consists of two partial problems which can be treated separately, and those separate approaches are included in the literature survey. From the standpoint of this paper, however, simultaneous consideration of both partial problems is of greater importance, and, for that reason, the literature review focuses on the joint problem. Finally, since the paper targets the railway network in Poland, a portion of the review is dedicated to local models and methods.
Since the volume of papers dedicated to scheduling of trains and closure planning in railway transportation is considerable, only selected works can be included in a non-dedicated review paper. For additional survey of recent literature, we refer the reader to References [8,9].

2.1. Train Rescheduling

The train rescheduling task is a problem quite widely discussed in the literature. It is understood, in the most cases, as the response to a single unforeseen event that prevents the further realization of the transportation plan by the original timetable. As detailed in Reference [10], the problem of rescheduling can be handled as different (re-)scheduling paradigms: offline, done to establish a primary schedule; and online, done mainly to reestablish a schedule that is no longer acceptable (feasible). The main difference, from the standpoint of difficulty of solving is that the former approach can be performed over a significantly longer period of time, while the latter needs to be done quickly, so as not to allow operations on an invalid schedule. The latter approach can, and likely will, lead to such problem formulations and solution algorithms which, in general case, forgo optimality and focus on providing heuristic, sub-optimal solutions instead. It is this approach that we focus on in this paper, although the results can also be applied to formulate a primary schedule. Online approaches can be further divided into static (open-loop) and dynamic (closed-loop), where, in the dynamic cases, not all of the information is readily available during the decision-making process. As new information about decision execution becomes available, it is fed back to the rescheduling algorithm and (possibly) results in new solutions. Finally, prediction of future states of the system is taken into consideration in proactive approaches, as opposed to reactive ones.
The mixed integer programming (MIP) model is proposed in Reference [11] for the train rescheduling problem when a train’s initial delays are given, and the minimization of the total delay of all passengers is required. However, specific requirements resulting from the state of railway infrastructure are not taken into account in this work. It is assumed that every route can hold any number of train runs in the same period. The extension of this problem is presented in Reference [12], where the limited number of train runs traveling between two stations at a given time is considered. The problem is formulated using integer linear programming approach and solved using the branch and bound method. Real-world data provided by Deutsche Railways have made it possible to test this approach successfully. A similar model and solution algorithm based on the Lagrange relaxation is proposed in Reference [13]. As a consequence, the problem is decomposed into a sequence of simple optimization tasks each corresponding to one train run. Another integer programming model presented in Reference [14] considers the assumption that, between any two stations, there is no more than one track, which may be occupied by no more than one train run at the same time. However, the authors do not propose any solution to the formulated problem due to its computational complexity. The authors in Reference [15] assume that there are always two tracks between two connected stations, and each of them may be occupied by no more than one train run at the same time. In this case, the genetic algorithm is applied to solve the train rescheduling problem. The discrete dynamic optimization model for train rescheduling problem is given in Reference [16]. The main goal in this case is to maximize punctuality and station satisfaction degree. However, authors also limit their consideration to the single-track railway and, even for this simple scenario, apply the heuristic approach.
More complex models of railway network infrastructure are presented in Reference [17], where it is taken into account that tracks are composed of blocks, and there may be any number of tracks between stations. The optimization model, formulated as a mixed linear programming task, consists of the minimization of two objectives: the total cost of delays and the total time of delays. The CPLEX software was applied to solve the problem. A similar approach is proposed in Reference [18]. Assumptions about railway infrastructure are also adopted in Reference [19], where two methods are proposed. The first one is based on MIP, while the second one uses Constraint Programming. Similarly, the timetable rescheduling, rolling stock rescheduling, and crew (train drivers) rescheduling problems are formulated in Reference [20] using integer programming models. In the mentioned paper, the timetable rescheduling problem is treated as the job shop scheduling, the rolling stock rescheduling problem is presented using the multi-commodity flow in a graph model, and the crew rescheduling problem is seen as the extended set covering. Further research has been done in providing an approach of exchanging blocks of routes with permitted alternative blocks through the means of alternative graph formulations [21,22]. One can also find adaptations of graph methods [23], such as time-space models [24].
As models considering the accurate description of railway infrastructure require too many computational resources to solve problems exactly in an acceptable amount of time, some more time efficient methods and heuristics are often applied. For example, in Reference [25], the authors propose a new approach based on the Statistical Analysis of Propagation of Incidents method, and, in Reference [26], a two-stage procedure is proposed. The first stage rests on the Simulated Annealing and the Tabu Search metaheuristics, whereas the second stage solves a simple integer programming problem. An approach based on MIP that incorporates a possibility of rerouting trains to enable minimizing the number of canceled and delayed trains, while adhering to infrastructure and rolling stock capacity constraints, is presented in Reference [27]. A proposition to apply MIP model to increase a robustness of the timetables is described by authors of Reference [28]. Considerations of the rescheduling problem on a single track unidirectional rail line that adheres to a cyclic schedule are included in Reference [29], where it is assumed that two types of trains (express and local) are dispatched from the origin in an alternating manner. The application of mixed integer programming to minimize combined length of shipping cycle and total dwell time of local trains at all stations is presented. In Reference [30], the authors consider the problem of adjusting the timetable in a case of partial or complete deadlocks. The integer programming formulation is given with the maximization of a service level.
A recent macroscopic approach was presented in Reference [31], where boundary passenger runs within an urban network were tackled. The authors propose a mixed integer programming approach with the use of a space-time network. This is solved for large instances with the use of decomposition. In Reference [32], the authors turn to microscopic modeling of the railway network and consider a problem of rescheduling in dense railway systems which are subject to disturbances. A multi-objective optimization problem is solved heuristically. In Reference [33], a problem of deadhead routing in an urban transit line was tackled. The authors formulate it as an MIP problem which is solved with the use of a CPLEX solver with an embedded branch-and-cut algorithms.

2.2. Closure Planning

The papers on the closure planning and, more generally, maintenance scheduling problems or even the maintenance management usually take into account the need of introducing to train timetables a delay as little as possible. Considerations in Reference [34] are focused on the local impact of maintenance on the railway infrastructure. Moreover, the limitation to single routes is taken into account in References [35,36,37,38]. In these papers, the problem of timetable planning is not solved. Instead, the scheduling of maintenance activities is formulated to minimize their impact on a original schedule. According to the argumentation in Reference [36] that such a problem is NP-hard, the application of some heuristic algorithms is appropriate, e.g., in Reference [38], the authors proposed the ant colony optimization method. In Reference [39], authors formulate the problem of planning maintenance windows, which is a concept incorporated by Swedish railways. This particular idea consists of the inclusion of train-free time slots into the tracks during timetable planning. The time windows for potential track closures and their durations are determined in advance, while the train traffic is described regarding statistical flows instead of a final timetable. More detailed surveys on railway maintenance planning activities may be found in References [40,41].
More recently, in Reference [42], a problem of scheduling maintenances in a large-scale network of trams was considered. The authors formulate an MIP and solve it with the use of neighborhood search-like heuristic approach.

2.3. Joint Approaches

Some important suggestions for the joint consideration of the maintenance activities scheduling and the train run rescheduling are indicated in References [43,44]. It is pointed out there that a single closure of a track indispensable for the completion of a maintenance activity could be treated as a particular type of train, but the idea has not been sufficiently developed. The concept of a system that helps to plan the closure of tracks with the simultaneous consideration of changes in the timetable is presented in Reference [45]. However, the solution is not based on a formal mathematical model, and the authors assume that new schedules are determined by external systems rail carriers. The joint scheduling of maintenance of the infrastructure (track closures) and rescheduling of train runs is also discussed in References [46,47]. In Reference [47], the author addresses the case when train arrival and departure times may be changed, but train runs cannot be canceled. Two analytical approaches are proposed, i.e., MIP (additionally with the bound and price reduction) and Problem Space Search metaheuristic, which was also presented in Reference [46]. This heuristic allows to generate alternative timetables and then to combine obtained solutions into one final timetable. MIP models are also proposed in References [7,48] for the joint closure planning and timetabling problem. This model includes the possibility of changing train routes, as well. However, it is assumed that such train rescheduling may be performed among a finite number of alternatives given in advance.
Unlike in our work, in Reference [48], the authors assumed that all closures are obligatory and in Reference [49], the authors do not consider particular events concerning conflicts between train runs; instead, they apply flow-based approach which is modeled as MIP with implicit link usage variables and cumulative station entry/exit variables. This model is solved with a Gurobi solver in Python and tested on a set of self-generated instances. In Reference [50], a reformulation is made—link usage variables are made explicit, while entry/exit variables are now binary. This model is further extended in Reference [51] to include crew scheduling.
Train scheduling and preventive maintenance are also jointly considered in Reference [52], where the sum of absolute arrival time deviations of real trains at destinations between the identical and actual timetables is minimized. A proactive approach to planning maintenance windows is presented as the authors try to ensure that maintenance work is already included in the schedule. The problem is formulated as an MIP and solved with the use of Lagrange relaxation. Another MIP approach presented in Reference [53] is aimed at incorporating new closures in a way that disturbs the original schedule the least. This approach is tested on date from a cut-out of the Netherlands railway system. An MIP approach tested on the French railway network can be found in Reference [54].
The authors of Reference [8] develop a microscopic approach, where timetabling and maintenance scheduling is formulated as a mixed integer programming problem. To alleviate computational difficulties of finding an exact solution, an iterative algorithm based on decomposition is proposed. It is shown that it results in near-optimal solutions for the tested cases. For Reference [55], an MIP formulation was applied to high-speed networks, where, in order to alleviated maintenance-induced problems, switches to normal-speed network were employed. Finally, in Reference [9], the authors use a dynamic constraint-generation technique coupled with Lagrangian relaxation for a double-track network with transmittable maintenances. The method was proven effective on a small section of a Chinese railway system.
Mixing the microscopic and the macroscopic approaches leads to intermediate, so-called mesoscopic models. As an example, in Reference [56], the authors consider a two-stage algorithm as a means of problem decomposition which speeds-up the algorithm execution time. The algorithm is tested on a network of 66 stations in case of a single, full blockade of a selected connection. This approach is further explored in Reference [57], where online, closed-loop rescheduling is done with the use of model model predictive control.
Further integration of traffic control and train operation is considered in Reference [58], where train speeds are considered. The authors formulate a nonlinear integer programming problem which they then simplify by approximating the nonlinearities with piecewise linear functions. To solve the many formulated sub-problems, the authors use a solver, a genetic algorithm and a custom procedure. The method is tested on a railway network of 40 nodes. In Reference [59], the authors consider two control loops: inner, which is responsible for managing immediate train operation and outer, where traffic control is done. The authors focus on Automated Train Operation subsystem of the Automatic Train Control system, and they provide an extensive review on the subject.
In our paper, we propose a joint approach that focuses on specifics of the Polish Railways. This leads to a new decision-making problem, which is formulated with a unique combination of constraints, such as limits in total travel time extension and total distance extension, that might arise during rescheduling. This problem is, by nature, highly nonlinear, mainly due to to existence of a large number of binary variables, and it cannot be solved quickly to optimality (or, in fact, to feasibility), in the general case. We prove that property by showing that the problem is NP-hard. Our quality criterion consists of three types of sub-criteria: number of accepted train runs, number of accepted closures, and the total deviation of the new schedule from the original schedule. To solve such a problem, we propose a four level solution algorithm that attempts to iteratively include train runs and closures and optimizes the total deviation. This iterative character, if left unchecked, leads to long execution times. We reduce those times by providing a Track Grouping Algorithm that divides the railway network into smaller sub-networks which are easier to optimize.

3. Current Closure Planning Practices in Poland

In Poland, the national company Polish Railways is the owner of the whole railway infrastructure. Closures are planned due to either maintenance or investment works. All maintenance activities and investment works are scheduled by local departments and corresponding investment sections, even though the execution is outsourced. A closure planning is performed in three-time horizons, i.e.,
  • long-term planning—performed once a year; there is no initial timetable and only long term closures are known in advance and may be taken into consideration, the aim is to prepare an initial closure plan and a timetable; both may be slightly modified later during the year;
  • periodic planning—carried out every two months; the initial closure plan and a timetable which were prepared during long-term planning are given, but there is also number of new closure requests which have been appeared meantime; such closures impose changes in closure plan and timetable, so the aim is to obtain new closure plan and modified timetable; however, the new timetable cannot differ much from the initial one; and
  • weekly planning—performed once a week, the valid closure plan and timetable obtained during periodic planning are given, but some new, short-term closure requests may appear, and they can be added to the closure plan if only no changes in closure plan and timetable are required.
For each mentioned time horizon, closure plans are made according to the hierarchical organizational structure of the Polish Railways. Firstly, local departments prepare closures plans, and they are coordinated between neighboring local departments. Then, the plans are verified, corrected, and coordinated similarly at the regional level. The precise rules of the closure planning are defined in the particular instruction Ir-19 [60,61]. From the Polish Railways’ point of view, the most crucial is the periodic planning, since there are only 48 h to prepare final closure plan for the next two months having only limited changes in the initial timetable. Our approach is, first of all, designed just for such planning process.

4. Joint Problem of Train Rescheduling and Track Closure Planning

The formalization of the considered joint problem is discussed in this section. The graph-matrix representations of a railway network, a train timetable, and track closures are given in Section 4.2, Section 4.3 and Section 4.4, respectively. It follows the summarization of the most crucial notation in Section 4.1. The mathematical model of the joint problem presented in Section 4.5 is preceded by the introduction of corresponding models for sub-problems of the track closure planning and the train scheduling.

4.1. Notation

The mathematical model, which is presented in the next sub-sections, refers to a railway network, a train timetable, and closures. A unified style of notation is used for matrices and sets. Entries of matrices are indicated by subscripts, and their number shows the dimension of a matrix. For example, a single lower index indicates a vector. Superscripts are used exclusively for indicating the meaning of the variable. Each matrix itself is denoted by a bold italic type, and its elements are devoid of bold formatting. Sets and their cardinalities are represented by upper-case letters typed in bold and italics, respectively. The concise recapitulation of the most important notation is given in Table 1, Table 2 and Table 3.

4.2. Representation of a Railway Network

Tracks and stations are basic elements of a railway network for the considered problem. A track is a link connecting directly two different stations. Every pair of stations i and j can be linked by K tracks of the same length, i.e., d i , j = d j , i ( d i , j is an element of a matrix D = [ d i , j ] i , j V ). Track numbers constitute a set K = { 0 , 1 , 2 , , K } the same for every pair of stations. A railway network is described by a multigraph G = < V , E > . The stations from a set V = { 0 , 1 , 2 , , V } represent railway stations, while entries of the incidence matrix E = [ e i , j , k ] i , j V , k K express tracks between particular railway stations. A virtual railway station denoted as ‘0’ is distinguished to serve as the beginning and the end of each train run in the model. It is located in zero-distance to other stations ( d 0 , j = d j , 0 = 0 ). The existence of the track number ‘0’ enables taking into account a substitute transport between stations of the same distance as real-world links. Consequently, a current entry e i , j , k of E is equal 1(0) if there exists track k from i to j (otherwise), as in Figure 1.
Each station i, as a place where trains can stop, start, or finish their runs, has limited capacity C A P i restricting the number of trains which are allowed to dwell on there at the same time. Additionally, it is assumed that each train fits every slot at a station, and a single train may occupy only one station slot. A virtual station ( i = 0 ) can hold up to C A P 0 = T R trains.

4.3. Representation of Train Timetable

In the paper, the train transport is considered to handle the flow of people traveling between stations. Many time demands and restrictions are imposed on resources (trains) and infrastructure (railway network) involved in such transport. They are reflected in a timetable, which takes into account not only constraints resulting from the joint use of resources and infrastructure, as well as their availability, but also nationally oriented regulations, along with other technical limitations. The railway transport is organized as a set of T R train runs (or trains) TR = { 1 , 2 , , T R } which have specified routes with distinguished origins, destinations, and stopping stations provided with departure and arrival times at each station.
More specifically, each train p TR consists of a set of stations and a connected available set of tracks. They are organized in routes denoted by R p T = [ R p , i , j , k T ] i , j V , k K , where R p , i , j , k T = 1 ( 0 ) if train p goes from station i to j by track k (otherwise). The timetable determines when the train p arrives and departures at station i, which is a part of a route R p T . The arrival and departure times of p at station i belonging to route R p T are denoted by t i , p ARR , t i , p DEP , respectively. Besides the virtual station i = 0 , some obvious relations among the times are valid, like every departure time at a station must be not less than the corresponding arrival time, and an arrival time of the consecutively visited station i specified in R p T must be not less than the departure time from the previous one. Moreover, maximal arrival T i , p ARR or departure T i , p DEP lateness are given for some stations. A minimal dwell time T i , p D is defined for each station i and train p. Zero dwell times mean no stops at stations. The maximal dwell time during the train run for each station (except station 0) is common and equal to T DL .
The timetable for train run p is represented by a tuple T T p G = < R p T , ( t i , p ARR , t i , p DEP ) i V > , which forms for all trains the original timetable denoted by TT G = [ T T p G ] p TR . The timetable is not valid if, for any train run, any station exceeds its capacity C A P i (see Formula (7)). For stations that do not belong to the train route, all arrival and departure times are equal 0.

4.4. Representation of Track Closures

Some maintenance tasks of a railway infrastructure require track closures when no train is allowed to use servicing tracks. Consequently, track closures may affect timetables. Closures can be brought in periodically during a day or night for short periods, or they may be planned for longer periods: days, weeks, or even months. They can be assumed as a factor competing for a track possession together with train runs included in a timetable, as in Figure 2.
Let C = { 1 , 2 , , C } be a set of C track closures envisaged for the implementation. It is composed of C OB obligatory closures and C C OB optional closures, i.e., C = { 1 , 2 , , C OB , C OB + 1 , C OB + 2 , , C } . The obligatory closures have to be included in the maintenance plan, unlike latter ones, which can be discarded if they interfere greatly the original timetable. An individual closure n C is defined by a tuple S n G = < R n C , t n CES , t n CLS , T n C > . All closures information is gathered in S G = [ S n G ] n C . A binary symmetric matrix R n C = [ R n , i , j , k C ] i , j V , k K \ { 0 } informs on track possessions by closures, i.e., the current entry R n , i , j , k C = 1 ( 0 ) if track k between stations i and j is planned to be possessed by the nth track closure (otherwise). Other elements of the tuple comprise time information on closure n that is T n C , t n CES and t n CLS represent, respectively, its duration, the earliest starting time and the latest starting time. If parameters t n CES and t n CLS have the same value, the start time of the closure is firm. Otherwise, it can vary between those two values. Moreover, closures may exist which have to be performed according to a given order expressed by a matrix O = [ o n , m ] n , m C , where o n , m = 1 ( 0 ) if closure n has to be completed directly before launching closure m.

4.5. Mathematical Model

At first, sub-problems of track closure planning and train rescheduling together with their mathematical models are separately introduced in Section 4.5.1 and Section 4.5.2, respectively. Then, in Section 4.5.3, the joint problem is stated in the form of the corresponding mathematical model as the composition of the models of sub-problems. All optimization (decision) variables defined in this subsection is summarized in Table 4. Their verbal descriptions are only given in this subsection.

4.5.1. Track Closure Planning

The problem of track closure planning deals with finding of the possibly largest set of track closures (containing all obligatory closures) with fixed start times of closures that can be performed without interfering with a train run timetable. To this end, a binary decision vector y = [ y n ] n C responsible for the planning of closures is introduced, where y n = 1 ( 0 ) if the nth closure is selected for the execution (otherwise). A positive-valued time shift (shift) of the closure earliest starting time Δ t C = [ Δ t n C ] n C is the second decision variable for planning the track closures. When the time shift is determined, the closure must start at the earliest starting time plus shift. Decision variables Δ t C and y define the resulted track closure plan S = [ S n ] n C , where S n = < R n , i , j , k C · y n , max { t n CES , t n CES + Δ t n C } , min { t n CLS , t n CLS + Δ t n C } , T n C > , and have to satisfy the constraints concerning obligatoriness, disjointness, and starting times of closures (see Formulas (2)–(4)). The track closure planning has to take into account the existing train timetable, which can affect likely conflicts in the track possessions by trains and closures.

4.5.2. Train Rescheduling

In fact, the train rescheduling deals with the elaboration of decision variables in the form of a new route plan r T = [ r p T ] p TR , r p T = [ r p , i , j , k T ] i , j V , k K , where r p , i , j , k T = 1 ( 0 ) if train p is planned to run by track k between stations i and j (otherwise). Moreover, arrival time shifts Δ t i , p ARR and departure time shifts Δ t i , p DEP constitute the respective matrices of decision variables Δ t ARR = [ Δ t i , p ARR ] i V , p TR and Δ t DEP = [ Δ t i , p DEP ] i V , p TR , as well as a new timetable TT = [ T T p ] p TR , where T T p = < r p T , ( t i , p ARR + Δ t i , p ARR , t i , p DEP + Δ t i , p DEP ) i V > is a new timetable for train run p. Both time shifts, together with the arrival and departure times from the original timetable TT G , define new arrival and departure times. The existence of some planned closures, unknown while preparing the original timetable TT G , is the only reason for rescheduling that is for the elaboration of a new timetable TT . No other unexpected events justifying possible rescheduling are taken into account in this paper. The considered track closures may directly affect train runs by their delaying, accelerating, or even canceling. The latter possibility is expressed in the model by an auxiliary decision variable x = [ x p ] p TR influencing TT by constraint (see Formula (9), where x p = 1 ( 0 ) if the pth train run is present in the new timetable (otherwise). It is important to point out that some train runs denoted by T R OB TR may exist and have to be obligatorily inserted into TT . The train rescheduling has to obey some regulations on any train travel time extensions concerning timetable TT G . They assure that the total travel time extension cannot exceed the given limit T E , and the travel time extension on a given distance D L cannot exceed the given limit T DE (see Formulas (10) and (11)).
The matrices r T , Δ t ARR , Δ t DEP , and x , or equivalently TT , comprise all decisions made while rescheduling of trains.

4.5.3. Final Model and Its Analysis

Two groups of decisions y , Δ t C , as well as TT , together with x introduced in two previous sub-sections, are mutually dependent. The plan of track closures y , Δ t C usually entails changes in the timetable TT G , like the cancellation of trains and the shift of departure and (or) arrival times at stations. On the other hand, it is necessary to bear in mind strong limitations that are imposed on the plan of track closures by the original timetable TT G being the basis and the source of technical restrictions for TT . So, the claim is entitled that Δ t C and y directly influences TT , and the indirect opposite impact is also valid, which forces the joint making of both groups of decisions Δ t C , y and TT . In the paper, the decisions are taken in the time horizon limited to the interval [ 0 , T H ] , where T H = max ( max i V , p TR t i , p ARR + T E , max n C ( t n CLS + T n C ) ) is the greater of times: the latest possible arrival of a train to the destination railway station according to the timetable TT G and the greatest completion time of all the possible closures. All mentioned and resulted time variables have to belong to this interval. However, time shifts Δ t i , p ARR and Δ t i , p DEP can be negative.
To achieve a feasible solution, the following constraints are imposed on the decision variables:
all obligatory closures are performed (1),
all closure starting times are feasible (2),
every pair of closures has to be disjoint (3),
obligatory train runs from set TR OB are present in the new timetable (4),
run times between adjacent stations are fixed (5),
substitute transport is allowable for selected paths specified in matrix E and only possible if other tracks are not free (6),
capacities of stations are limited (only in artificial station ‘0’ capacity is unlimited) (7),
at most one train can occupy one track at every time moment (8),
the train cannot run by any track if it is canceled (9),
the total travel time extension cannot exceed the given limit T E (10),
the travel time extension on a given distance D L cannot exceed the given limit T DE  (11),
standing times of trains at stations are limited by the minimum and maximum feasible values (12),
trains in both original and new timetables go through the same path of stations, but they may go through different tracks (13),
departure and arrival lateness at selected stations are bounded (14),
the arrival time of every train at every station must not be later than corresponding departure time (15), and
no train can occupy a track during a closure (16).
Constraints imposed on track closures:
y n = 1 , n = 1 , 2 , , C OB ,
t n CES + Δ t n C t n CLS + M ( 1 y n ) , Δ t n C 0 , n C ,
min { y n ( t n CES + Δ t n C + T n C ) , y m ( t m CES + Δ t m C + T m C ) } max { y n ( t n CES + Δ t n C ) , y m ( t m CES + Δ t m C ) } , ( n , m ) C CON = { ( n , m ) C × C : n m , i , j V , k K ( R n , i , j , k C + R m , i , j , k C = 2 ) } .
Constraints imposed on train runs:
x p = 1 , p TR OB .
Constraints imposed on train routes:
k K ( R p , i , j , k T r p , i , j , k T ) ( Δ t j , p ARR Δ t i , p DEP ) = 0 , i , j V , p TR ,
x p r p , i , j , 0 T min { e i , j , 0 , 1 + k K \ { 0 } ( q TR i , j , p CON x q r q , i , j , k T + q TR j , i , p CON r q , j , i , k T x q + n C i , j , p CON r n , i , j , k C y n ) ( 1 + k K \ { 0 } e i , j , k ) } , i , j V , p TR ,
TR i , j , p CON = Δ { r TR \ { p } : t i , p DEP + Δ t i , p DEP t i , r DEP + Δ t i , r DEP t j , p ARR + Δ t j , p ARR t i , r DEP + Δ t i , r DEP t i , p ARR + Δ t i , p ARR Δ t i , r ARR + Δ t i , r ARR } ,
C i , j , p CON = Δ { n C : t i , p DEP + Δ t i , p DEP t n CES + Δ t n C t j , p ARR + Δ t j , p ARR t n CES + Δ t n C t i , p ARR + Δ t i , p ARR t n CES + Δ t n C + T n C } ,
j V k K \ { 0 } x p max ( r p , j , i , k T , r p , i , j , k T ) ( 1 + q TR i , p CON l V m K \ { 0 } x q max ( r q , i , l , m T , r q , l , i , m T ) C A P i , i V \ { 0 } , p TR ,
min { r p , i , j , k T x p ( t i , p DEP + Δ t i , p DEP ) + r p , j , i , k T x p ( t i , p ARR + Δ t i , p ARR ) , r q , i , j , k T x q ( t j , q ARR + Δ t j , q ARR ) + r q , j , i , k T x q ( t i , q ARR + Δ t i , q ARR ) } max { r p , i , j , k T x p ( t i , p DEP + Δ t i , p DEP ) + r p , j , i , k T x p ( t j , p DEP + Δ t j , p DEP ) , r q , i , j , k T x q ( t i , q DEP + Δ t i , q DEP ) + r q , j , i , k T x q ( t j , q DEP + Δ t j , q DEP ) } , r p , i , j , k T ( t i , p DEP + Δ t i , p DEP ) r p , i , j , k T ( t j , p ARR + Δ t j , p ARR ) , p , q TR , i , j V , k K \ { 0 } .
Constraint imposed on train run times:
r p , i , j , k T x p , p TR , i , j V , k K ,
( Δ t 0 , p ARR Δ t 0 , p DEP ) · x p T E , p TR ,
( Δ t j , p DEP Δ t i , p ARR ) · x p T DE , ( i , j ) D p L , p TR ,
T i , p D t i , p DEP + Δ t i , p DEP ( t i , p ARR + Δ t i , p ARR ) T DL , i V , p TR ,
k K R p , i , j , k T = k K r p , i , j , k T , i , j V , p TR ,
Δ t i , p DEP T i , p DEP , Δ t i , p ARR T i , p ARR , i V , p TR ,
t i , p ARR + Δ t i , p ARR t i , p DEP + Δ t i , p DEP , i V \ { 0 } , p TR .
Constraint imposed on both train runs and track closures:
min { r p , i , j , k T x p ( t j , p ARR + Δ t j , p ARR ) , y n ( t n CES + Δ t n C + T n C ) } max { r p , i , j , k T x p ( t i , p DEP + Δ t i , p DEP ) , y n ( t n CES + Δ t n C ) } , p TR , n C , i , j V , k K \ { 0 } : r n , i , j , k C = 1 .
The auxiliary notions used in (17) and (16) have the following meanings: M—big number,
  • C CON = { ( n , m ) C × C : n m , i , j V , k K ( R n , i , j , k C + R m , i , j , k C = 2 ) } —set of closures reporting possession of the same track,
  • TR i , p CON = { q { 1 , 2 , , T R } : t i , p ARR t i , q DEP t i , p DEP t i , p ARR t i , q ARR t i , p DEP } —sub-set of trains with dwell time on the station i coinciding with that of the train run p,
  • TR i , j , p CON = Δ { r TR \ { p } : t i , p DEP + Δ t i , p DEP t i , r DEP + Δ t i , r DEP t j , p ARR + Δ t j , p ARR t i , r DEP + Δ t i , r DEP t i , p ARR + Δ t i , p ARR Δ t i , r ARR + Δ t i , r ARR } —sub-set of train runs going from i to j in time coincided with the run of train p,
  • C i , j , p CON = Δ { n C : t i , p DEP + Δ t i , p DEP t n CES + Δ t n C t j , p ARR + Δ t j , p ARR t n CES + Δ t n C t i , p ARR + Δ t i , p ARR t n CES + Δ t n C + T n C } —sub-set of track closures on the path from i to j in time coincided with the run of train p,
  • TR i , p CON = { q { 1 , 2 , , T R } : t i , p ARR + Δ t i , p ARR t i , q DEP + Δ t i , q DEP t i , p DEP + Δ t i , p DEP t i , p ARR + Δ t i , p ARR t i , q ARR + Δ t i , q ARR t i , p DEP + Δ t i , p DEP } —sub-set of train runs waiting at station i in time coincided with the run of train p,
  • D p L = { ( i , j ) TR 2 : D L r p , j , i ( l ) , k T · d j , i ( l ) r p , i , i 1 , k T · d i , i 1 + r p , i 1 , i 2 , k T · d i 1 , i 2 + + r p , i ( l 1 ) , j , k T · d i ( l 1 ) , j < D L } —set of stations, for which train run p runs a distance less than D L , but it will reach or exceed this value on arrival to the next station.
Many interconnections between two groups of decisions Δ t C , y , and TT are also visible while analyzing the constraints, e.g., (16). They are the additional justification for joint determination of both groups of decisions.
To evaluate the decisions y , Δ t C , as well as TT , the following criterion is proposed:
Q = α n = C OB + 1 C y n + p TR \ TR OB x p β i V , p TR Δ τ i , p D E P , ,
where α and β are positive-valued coefficients satisfying the inequalities α > T R T R OB , β < 1 / [ T R ( V + 1 ) T H ] , e.g., α = T R T R OB + 1 , β = 1 / [ T R ( V + 1 ) T H + 1 ] .
The introduced criterion reflects the Polish Railways expectations. The most important is to perform as many closures as possible, since they are crucial for maintenance of railway tracks and affect the long-term rail traffic management. Thus, the first element of (17) evaluate number of closures which are to be performed according to the solution. The α parameter chosen according to the imposed constraint ensures that every closure is more important than any acceptable change in timetable. While we cannot increase the number of closures, we should try to limit the number of the train runs that are to be canceled. Thus, the second element of (17) evaluates number of train runs which remain in the new timetable. The β parameter chosen according to the given constraint provides that not canceling any train run is more important than introducing any changes in the departure times in the new timetable. At last, when we can increase neither the number of closures nor the number of train runs, we should try to minimize the total time changes in the new timetable, which is reflected by the last element of the objective function. Such form of the criterion ensures the hierarchy of the decisions, i.e., the acceptance of optional closures is the most important, whereas the differences of departure times in the timetables are the least important.
To sum up, the following joint train rescheduling and track closure planning problem is considered and solved. Decisions are made in relation to the railway system which consists of a railway infrastructure and train runs described by G , V , TR , T R OB , TT G , D , C A P i , T i , p ARR , T i , p DEP , T i , p D , i , j V , p TR , α , β . The planned closures are also given in the form of C , C, C OB , O , S G ( S n = < R n C , t n CES , t n CLS , T n C > , n C ) . The auxiliary data T DL , T DE , T E are known, as well. It is necessary to determine the interconnected collection of decisions: Δ t C , y constituting the resulted track closure plan, and r T , Δ t ARR , Δ t DEP , x defining the new timetable plan TT subject to constraints (1)–(16) to minimize the criterion (17).
The conducted analysis of the formulated nonlinear mixed integer optimization problem referred to as PR made it possible to put forward and prove the following theorem.
Theorem 1.
Joint train rescheduling and track closure planning problem is NP-hard.
Proof. 
Let us consider the NP-hard problem of task scheduling around a common date presented in Reference [62]. Given one executor and J tasks, durations of tasks d u r a t i o n j 0 , j = 1 , 2 , , J and a common deadline d e a d l i n e j { 1 , 2 , , J } d u r a t i o n j find a schedule, i.e., task completion times f i n i s h j , that minimizes the total earliness and tardiness of each task, i.e., q u a l i t y = j { 1 , 2 , , J } | f i n i s h j d e a d l i n e | . We show that this scheduling problem reduces, in polynomial time, to the investigated problem PR. We accomplish this by showing that we can reduce the scheduling problem to an equivalent problem PR with only single track and carefully selected set of closures.
We take a time horizon sufficient to encompass the duration of all tasks ( T H = j d u r a t i o n j ). Let us assume that all closures and train runs are obligatory ( y n = 1 , x p = 1 ). Define the graph G so that there are 3 stations connected in a cycle 0 1 2 0 , and that there are J + 1 tracks between stations 1 and 2. We take J trains, where each train moves once through the whole cycle of stations but through different track each: pth train takes pth track between stations 1 and 2 ( R p , 0 , 1 , 1 T = 1 , R p , 1 , 2 , p T = 1 , R p , 2 , 0 , 1 T = 1 ). The departure time for the artificial station is 0 for every train and so is the arrival in station 1. Departure time in station 1, as well as minimum dwelling time, is set to d e a d l i n e d u r a t i o n j . Arrival time in station 2 for the pth train is equal to d e a d l i n e . Minimum dwelling time in station 2 is 0. Maximal dwell times are set to be very large ( T DL = T H ). Note that the schedule is feasible.
Let us further consider a set of J closures, where the nth closure takes up track n of the connection between stations 1 and 2 ( R n , 1 , 2 , n C = 1 ) with the earliest and the latest start times all bound by 0 and very large durations ( t n CES = t n CLS = 0 , T n C = T H ). The addition of closures forces all the trains onto the last track J + 1 , where they cannot proceed in parallel. Due to dwelling times in station 2, the quality criterion is equal to Q = j { 1 , 2 , , J } | Δ t 1 , j DEP | + j { 1 , 2 , , J } | Δ t 2 , j DEP | = 2 j { 1 , 2 , , J } | Δ t 2 , j DEP | = 2 j { 1 , 2 , , J } | t 2 , j DEP + Δ t 2 , j DEP d e a d l i n e | .
Sum t 2 , j DEP + Δ t 2 , j DEP is the moment the train run ends. Thus, we equate it to f i n i s h j . Then, q u a l i t y = 1 2 Q . Please note that all the transformations can be made in the polynomial time. □

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 resulted in 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 η groups (railway sub-networks). For each sub-network, Algorithm 4 is launched to obtain train runs and track closures time shifts Δ t ARR , Δ t DEP , and Δ t C for this fragment of the network. If rerouting is needed, then Algorithm 4 also returns the routes r 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). All of them are iteratively solved with the combined use of a greedy algorithm and the numerical solver ‘lp_solve’ [63], giving solutions of resulted LP. As a consequence, the decision variables of the considered problem, i.e., y , x and Δ t C , r T , Δ t ARR , Δ t DEP are the results of Algorithms 1, 2, 3, 4, together with TGA, respectively. The matrices r T , Δ t ARR , Δ t DEP , along with x , form the new timetable TT = [ < x p · [ r p , i , j , k T ] i , j V , k K , [ t i , p ARR + Δ t i , p ARR ] i V , [ t i , p DEP + Δ t i , p DEP ] i V > ] p TR . Similarly, the time shifts for closures Δ t C , together with y , define the resulted track closure plan S = [ S n ] n C , where S n = < r n C , t n CSE , t n CSL , T n C > , r n C = R n , i , j , k C · y n , t n CSE = max { t n CES , t n CES + Δ t n C } , t n CSL = min { t n CLS , t n CLS + Δ t n C } .
Algorithms 1, 2, 3, 4 and TGA are introduced in the next subsections. The detailed description of Algorithm TGA can be found in Reference [5]. It is assumed that all algorithms have access to all data concerning infrastructure, train runs, and track closures. The necessary auxiliary notation is given in Table 5.

5.1. Managing of Closures

Algorithm 1 checks serially the ordered sequences of obligatory and facultative closures. Each track closure n is numerically evaluated by the ratio
T n C R n , i , j , k C p = 1 T R R p , i , j , k T k = 1 K p = 1 T R ( t j , p ARR t i , p DEP ) R p , i , j , k T
being the proportion of daily cumulated time of the closure to a daily time occupation by trains in the original timetable TT G of the trail between stations i and j. The cumulated time of closure is equal to time T n C multiplied by the number of trains using the track during T n C . The trail is understood as all tracks between adjacent stations. Additionally, both sequences are sorted to take into account precedence constraints among closures given in matrix O . A closure is selected on the basis of the real-world completion time of closure t n CE returned by the lower level Algorithm 2. The non-positive returned value of t n CE means that some constraints do not hold, and closure n cannot be approved. Algorithm 1 is stopped when whichever obligatory closure cannot be performed. As a result, the algorithm returns the selected set of track closures, the set of train runs together with new train timetable and track closure plans obtained, or information that the solution does not exists. The returned set of train runs defined by x , together with train timetable TT and a set of closures defined by y , together with closure plan S , are obtained with the use of all subsequent algorithms.

5.2. 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 = i j k R p , i , j , k T q : [ t i , p ARR , t j , p DEP ] [ t i , q ARR , t j , q DEP ] 1 i j k R p , i , j , k T 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 pth 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 Δ (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 , TT , and TR as an input and returns the number of groups η and set GR = E × { 1 , 2 , η } , where 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. Otherwise, the algorithm returns the original train timetable and track closure plan with information of the failure. The new train timetable TT and track closure plan S are represented by values of time shifts Δ t ARR , Δ t DEP of train runs and time shifts Δ t C of track closures regarding the original timetable TR S and closure plan C S .
Algorithm 1 selection of closures
Require: Data of the problem, in particular sets C OB , C F of obligatory, facultative closures, respectively.
Ensure: Values of y , x , as well as closure plan S , and timetable TT .
1:
Sort the elements of C OB in the ascending order with respect to ratio (18) and then sort resulting sequence to ensure precedence constraints given in matrix O to have a sequence of obligatory closures ( z i ) i = 1 , , C OB as a consequence.
2:
Set y n = 0 , Δ t n C = 0 , n = 1 , 2 , , C , x p = 0 , p TR , S = S G , TT = TT G .
3:
for i = 1 , , C OB do
4:
      Run Algorithm 2 for a set of selected closures C S = { z 1 , z 2 , , z i } , current timetable TT , and closure plan S (together with y ), and currently considered closure n = Δ z i , to obtain updated TT , S , y , and the actual completion time of closure t n CE = t n CES + Δ t n C + T n C .
5:
      if t n CE = 0 or ( t n CE > t n + 1 CLS when o n , n + 1 = 1 and i < C OB ) then
6:
           Stop the algorithm and return “Cannot find a feasible solution for C OB ”.
7:
        
       end if
8:
      
  End for
9:
Sort the elements of C F in the ascending order with respect to the ratio (18), and then sort resulting sequence to ensure precedence constraints given in matrix O to have a sequence of facultative closures ( z i ) i = 1 , , M as a consequence.
10:
for i = C OB + 1 , , C 1 do
11:
      Run Algorithm 2 for a set of selected closures C S = { j = z m : m { 1 , , i } , y j = 1 } , current TT , S , y , and currently considered closure n = Δ z i , to obtain updated TT , S , y , and t n CE = t n CES + Δ t n C + T n C .
12:
      if ( t n CE > 0 and t n CE t n + 1 CLS when o n , n + 1 = 1 ) then
13:
            Set y n = 1 .
14:
          
         end if
15:
     
    End for
16:
Run Algorithm 2 for a set of selected closures C S = { j = z m : m { 1 , , C } , y j = 1 } current TT , S , y , and currently considered closure n = Δ z N , to obtain updated TT , S , y , and t n CE = t n CES + Δ t n C + T n C .
17:
if t n CE > 0 then
18:
      Set y n = 1
19:
    
   end if
20:
return y , x , S , TT where x , S , and TT are taken from the last run of Algorithm 2.
Algorithm 2 selection of trains
Require: Data of the problem, x , S , TT , C S , specified closure n.
Ensure: x , S , TT , t n CE for specified closure n.
1:
Let FT be the list of train runs that are allowed to be canceled and sorted in not ascending order with respect to index U p . Set x p = 1 ( 0 ) if p TR OB (otherwise). Let TR S = { p TR : x p = 1 } .
2:
Solve the task ZP( ( i , j ) , x , S , TT , C S , TR S , n), where i, j satisfies: k K R n , i , j , k C = 1
3:
if the feasible solution is not found in Step 2 then
4:
      return “No solution”
5:
else
6:
      Run Algorithm 3 for current S , TT , TR S , C S and Null (as currently considered facultative train run) and obtain new S and TT
7:
      if the solution is found in Step 6 then
8:
            calculate t n CE basing on current S
9:
      else
10:
          return “No solution”
11:
        
        end if
12:
    
   end if
13:
if the list FT is empty then
14:
      go to Step 33.
15:
    
   end if
16:
Take the first train run out from the list FT and obtain its index p.
17:
Set x p = 1
18:
Set TR S = { p TR : x p = 1 } .
19:
for each pair of stations ( i , j ) such that k K R p , i , j , k T = 1 do
20:
      solve ZP( ( i , j ) , x , S , TT , C S , TR S , n)
21:
      if the feasible solution is not found in Step 20 then
22:
           Set x p = 0
23:
           go to step 13.
24:
        
    end if
25:
    
   end for
26:
Run Algorithm 3 for current S , TT , TR S , and C S , p, and obtain new S and TT .
27:
if the feasible solution is not found in Step 26 then
28:
      Set x p = 0
29:
else
30:
      calculate t n CE basing on current S
31:
    
   end if
32:
go to step 13
33:
return x , S , TT , and t n CE for specified closure n.
Algorithm 3 decomposition of the railway network
Require: Data of the problem, in particular sets C S , TR S of selected closures and train runs, respectively, selected train run for rerouting q TR S , current train timetable TT and track closure plan S .
Ensure: Closure plan S , train timetable TT .
1:
Set S = S and TT = TT , get from Algorithm TGA results: grouping set GR, which associates each track with a group number to which it belongs, and a number of groups η .
2:
for n = 1 , , η do
3:
      Construct a railway network G n = < V n , E n > (not necessary connected) where
        V n = { v V : w V , k K , ( ( v , w , k ) , n ) , ( ( w , v , k ) , n ) GR } ,
        E n = [ e n , i , j , k ] i , j V , k K { K + 1 , K + 2 , , K + T R } , and e n , i , j , k = 1 for ( ( i , j , k ) , n ) GR 0 for otherwise
4:
      for each m T R S do
5:
           Construct a path π n , m (string of stations v V n ) composed of stations of the route of the train run m that belong also to V n .
6:
           if π n , m exists then
7:
                 for each pair of consecutive stations ( v a , v b ) from the path π n , m . do
8:
                      if for any track k connecting stations a with b, there is no connection indicated in matrix E n ( k K ( e n , a , b , k = = 0 ) ) then
9:
                           Add a virtual track to E n (set e n , a , b , K + m = 1 ).
10:
                   
                       end if
11:
               
                  end for
12:
               add train run m to a set TR n S TR S ( TR n S = TR n S { m } )
13:
           
            end if
14:
        
       end for
15:
    for each c l C S do
16:
         if a closure c l is planned on some track in connection indicated in matrix E n
      ( { k K , v a , v b V n , e n , a , b , k = 1 , R c l , a , b , k C = 1 } ) then
17:
                 Add closure c l to C n S C S ( C n S = C n S { c l } ).
18:
           
              end if
19:
        
      end for
20:
    Execute Algorithm 4 for C n S , TR n S , TR S , G n , q, S , and TT , to obtain time shifts of the train runs and closures.
21:
    if Algorithm 4 returned “No solution” then
22:
         Stop the algorithm and return “Cannot find a feasible solution”.
23:
        
      end if
24:
   Include time shifts of the train runs and closures obtained by Algorithm 4 into new train timetable TT , and closure plan S .
25:
    
   end for
26:
Update TT by recalculating Δ t i , p ARR = j V ( Δ t j , p DEP · k K r p , j , i , k T )
27:
return S = S and TT = TT .

5.3. 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 θ i , j , k = [ θ q i , j , k ] q { 1 , 2 , , Θ 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 Θ i , j , k is the number of runs and closures on that track. Let us define a series Ψ i , j , k = [ Ψ q i , j , k ] q { 1 , 2 , , Θ i , j , k } with elements Ψ q i , j , k = 0 ( 1 ) if there is a train run (if it is a closure) on the position q of the ordering θ i , j , k . Furthermore, for each station, let us denote the order in which train runs enter the station as λ i = [ λ q i ] q { 1 , 2 , , Λ i } , where i is the index of the station, and Λ i is the number of runs entering the station. Determination of orders θ i , j , k and λ 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 θ i , j , k . For this purpose, a local criterion being a particular case of criterion (17) is introduced:
Q 1 i , j , k = p TR i , j , k | Δ t i , p DEP | + p TR j , i , k | Δ t j , p DEP | ,
where TR i , j , k = { p TR n S : R p , i , j , k 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. Furthermore, let us define by 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 TR n S _ SUB , which is a sub-set of TR n 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 θ 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 λ i is fixed; this leads to another linear problem of time shift determination (times when train enters the station). Finally, under fixed values of θ i , j , k for each track and of λ 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 λ i . Analogously to the first set of sub-problems, a local criterion based on (17) is defined.
Q 2 i = p T R i | Δ t i , p ARR | ,
where TR i = k K ( TR i , j , k TR j , i , 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 K i ADJ = { ( l , j , k ) : l , j V n , k K , TR l , i , k TR i , j , k } . 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 Δ t j , p ARR , the time shifts Δ t i , p DEP have to be accordingly changed be Algorithm 4 to satisfy p TR i ( Δ t i , p DEP Δ t j , p ARR ) k K r p , i , j , k T = 0 .
The complexity of Algorithm 4 is dependent on the complexity of the selected linear programming routine. Assuming Karmarkar’s algorithm [65] is used, then the complexity is given as follows O [ ( T R + C ) 3.5 B E 2 + T R 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 { ( T R C [ ( T R + C ) 3.5 B E 2 + T R 3.5 B V 2 ] } .
Algorithm 4 determination of time shifts for train runs and closures
Require: Data for the sub-network: G n , C n S , TR n S . Train run q ( q TR n S ) selected for rerouting. Closure ordering matrix O .
Ensure: Time shifts Δ t i , p DEP , Δ t n C , and new train routes r p , i , j , k T for i , j V n , p TR n S , n C n S .
1:
if q N U L L then
2:
       return solution of Algorithm 5 for G n , C n S , TR n S , q, and O .
3:
else
4:
       Set Δ t i , p DEP , Δ t n C , r p , i , j , k T for i , j V n , p TR n S , n C n S using values returned by Algorithm 5.
5:
       Let p = 1 .
6:
       Let TR n S _ SUB = TR n S TR n S ( p ) , where TR n S ( p ) is the pth element of TR n S .
7:
       Let q = TR n S ( p ) .
8:
       Execute Algorithm 5 for G n , C n S , TR n S _ SUB , q, and O .
9:
       if solution does not exist then
10:
           return no solution.
11:
      else
12:
           Update Δ t i , p DEP , Δ t n C , r p , i , j , k T for i , j V n , p TR n S , n C n S using values returned by Algorithm 5.
13:
        
        end if
14:
      if p < | TR n S | then
15:
            Let p = p + 1 .
16:
            go to 5.
17:
        
        end if
18:
    
   end if
19:
return Δ t i , p DEP , Δ t n C , r p , i , j , k T for i , j V n , p TR n S , n C n S .
Algorithm 5 determination of time shifts for train runs and closures
Require: Data for the sub-network: G n , C n S , TR n S _ SUB . Train run q ( q TR n S ) selected for rerouting. Closure ordering matrix O .
Ensure: Time shifts Δ t i , p DEP , Δ t n C , and new train routes r p , i , j , k T for i , j V n , p TR n S _ SUB , n C n S .
1:
Let p TR n S _ SUB , i V n : Δ t i , p DEP = 0 , n C n S : Δ t n C = 0 .
2:
for each ( i , j , k ) E n , i < j do
3:
       Obtain ordering θ i , j , k using Algorithm 6.
4:
       if no ordering was found then
5:
            go to 11.
6:
        
        end if
7:
    
 end if
8:
for each p V n do
9:
       Obtain ordering λ i using Algorithm 7.
10:
     if no ordering was found then
11:
           go to 11.
12:
        
        end if
13:
    
   end if
14:
Solve the linear problem of time shift determination for given orderings (4.lin).
15:
if no solution was found and q TR n S _ SUB then
16:
      Let TR n S _ SUB : = TR n S _ SUB \ { q } .
17:
      go to 1.
18:
else
19:
      if no solution was found then
20:
            for each pair of stations ( i , j ) on the route for the run q. do
21:
                  Find a feasible track k K .
22:
                  if no track was found and b i , j = 1 then
23:
                        Verify if track k = 0 is feasible.
24:
                 
                    end if
25:
                  if a feasible track was found then
26:
                       Set Δ t i , p DEP to the lowest feasible value, set r q , i , j , k T = 1 , l k : r q , i , j , l T = 0 .
27:
                  else
28:
                      return no solution.
29:
                    
                      end if
30:
           
                end for
31:
        
         end if
32:
    
   end if
33:
return Δ t i , p DEP , Δ t n C , r p , i , j , k T for i , j V n , p TR n S _ SUB , n C n S .
Algorithm 6 track usage ordering determination
Require: Selected track ( i , j , k ) . Data for the sub-network: G n , C n S , TR n S . Closure ordering matrix O , sets of train runs TR i , j , k and closures C i , j , k on the track.
Ensure: Locally optimal ordering θ i , j , k , Ψ i , j , k or no solution.
1:
Empty the ordering θ i , j , k ( ) , Ψ i , j , k ( )
2:
while either TR i , j , k or C i , j , k is nonempty do
3:
      From the sets of every train run TR i , j , k and every closure C i , j , k and every possible position in θ i , j , k , Ψ i , j , k find those that minimize Q 1 i , j , k by solving ) linear time shift resolution problems for a single track (4.1.lin). Preserve ordering given by O .
4:
      Add selected train run or closure to θ i , j , k , Ψ i , j , k . Remove it from TR i , j , k or C i , j , k .
5:
      if no train run or closure could be added then
6:
           return no solution.
7:
        
       end if
8:
    
 end while
9:
return θ i , j , k , Ψ i , j , k .
Algorithm 7 station usage ordering determination
Require: Selected station i. Data for the sub-network: G n , C n S , TR n S . The ordering of runs and closures θ i , j , k for tracks K i ADJ .
Ensure: Locally optimal ordering λ i if one was obtained.
1:
Empty the ordering λ i ( ) .
2:
while TR i is nonempty do
3:
      From the set of every train run TR i and every possible position in λ i find those that minimize Q 2 i by solving linear time shift resolution problems for a single station (4.2.lin).
4:
      Add selected train run to λ i and remove it from TR i .
5:
      if no train run or closure could be added then
6:
            return no solution.
7:
        
       end if
8:
    
 end while
9:
return λ i .

6. Simulation Experiments

The heuristic algorithm presented in the previous section was tested via simulation experiments for particular structures of railway networks. The experiments have consisted of two parts, i.e., for a single track and a real-world network of tracks. The former experiments have aimed at providing the comparison of solutions obtained with the only use of Algorithm 4 to optimal solutions. The latter experiments were conducted to provide the insight into properties of the heuristic algorithm treated as a whole. Due to the complexity of the underlying problem, the comparison with optimal solutions was omitted for the second part. Computations for the first part were performed on a PC with Intel i7-4790K 4 GHz, single core, 2.5 GB RAM; the second part of simulations was done with the use of a PC with Intel i7-4720HQ 2.6GHz, 16 GB RAM. Calculations were made with the use of a single processor core only. The software implementation in both cases was made with the use of Python 2.7 and lpsolve [63].

6.1. Single Track Case

Optimal ordering of runs can change following the addition of closures, even for a single track case. Unlike for the more complex structure of a train run network, here, it is possible to obtain, in a reasonable amount of time, optimal solutions to the time shift resolution problem. The authors find it valuable to exploit this opportunity to relate the dedicated algorithm to an optimal one in a series of experiments, which were constructed as follows.
The overall time interval was limited to a single day, i.e., T H = 1440 min. The network consisted of three stations (one artificial) V = { 0 , 1 , 2 } with a single track between the two non-artificial stations K 1 , 2 = 1 . The number of runs T R varied with the experiment. Standing times were set to T DL = 15 , T i , p D = 1 for all runs p and stations i. No substitutive transportation was allowed. Each experiment introduced a single closure with parameters t 1 CES = t 1 CLS = ( T H T 1 C ) / 2 , where closure duration T 1 C varied with experiment. Moreover, two additional parameters ξ and the movement time c p , 1 , 2 were introduced for each experiment to increase the flexibility of runs. Values of the former and the latter parameter were fixed by hand and randomly generated from the interval [ c ̲ , c ¯ ] , respectively. Then, both parameters were the basis for the generation of arrival time t 1 , p ARR from the interval [ ξ , T H ξ c p , 1 , 2 2 T i , p D ] , as well as for the setting other variables, namely: t 0 , p DEP τ ¯ 0 , p = t 1 , p ARR ξ , t 1 , p DEP = t 1 , p ARR + T i , p D , t 2 , p ARR = t 1 , p DEP + c p , 1 , 2 , t 2 , p DEP = t 2 , p ARR + T i , p D , t 0 , p ARR = t 2 , p DEP + ξ , T 2 , p DEP = ξ . Values of other parameters were set to T i , p DEP = T i , p ARR = T E = T DE = T H , c ¯ i = T R , b i , j = 0 . Tested were combinations of values ξ , T 1 C , T R , c ̲ , c ¯ . The following cases were chosen for further presentation.
Case 1. ξ = 60 , T 1 C = 60 , T R = { 5 , 6 , , 10 } , [ c ̲ , c ¯ ] = [ 15 , 15 ] .
Case 2. ξ = 60 , T 1 C = 120 , T R = { 5 , 6 , , 10 } , [ c ̲ , c ¯ ] = [ 15 , 15 ] .
Case 3. ξ = 240 , T 1 C = 120 , T R = { 5 , 6 , , 10 } , [ c ̲ , c ¯ ] = [ 60 , 180 ] .
Case 4. ξ = 240 , T 1 C = 60 , T R = { 5 , 6 , , 10 } , [ c ̲ , c ¯ ] = [ 60 , 240 ] .
The criterion Q ˜ = i V , p TR | Δ t i , p DEP | used during this experiment is the negative of the last part of (17), which should be minimized and only evaluates solutions obtained by Algorithm 4. The other evaluation is the computational time of the algorithm T ˜ . Due to the random nature of the experiments, for each case and for each T R , the experiment was repeated ten times. Results, both the execution time T ˜ and the quality Q ˜ were averaged. We present the results in Table 6 and Table 7, and Figure 4 and Figure 5, where we provide: the quality for the optimal algorithm, the quality of the Algorithm 4 algorithm, the execution time for the optimal algorithm, and execution time for the Algorithm 4 algorithm. They are denoted as Q ˜ a v g , Q ˜ a v g , T ˜ a v g , T ˜ a v g , respectively. For some instances, the Algorithm 4 algorithm failed to provide a solution. The number of such instances is given in the table columns labeled ‘ F a i l ’. All such instances are excluded from the calculation of averages. Times Q ˜ , and T ˜ are given, respectively, in minutes and seconds. Figure 4 and Figure 5 incorporate data aggregated over multiple experiments presented with the use of horizontal curly braces. The average values are represented by dots, as well as minimum, and maximum ones are given by error bars. For the purpose of comparing results obtained with the use of Algorithm 4 with optimal solutions, an exhaustive search was used to obtain the latter ones.
As can be seen in Figure 5 and Table 7, computational time of Algorithm 4 grows in a nearly linear manner concerning the number of runs. This property is crucial to the computational time of the heuristic algorithm, which uses Algorithm 3 repeatedly and for sub-problems of varying sizes. We notice from Figure 4 and Table 6 that Q ˜ varies significantly, with much greater values obtained for longer expected train movement times. This remark gives a clear message that it is easier to permit closures on the tracks for fast passenger trains. Slow trains will likely have to change their route or be canceled. Comparison with optimal solutions leads to a natural conclusion that the Algorithm 4 provides similar results for the majority of all the tested cases. As it can be apparently seen from Table 6, all of the results obtained by the algorithm were optimal for Cases 1 and 2. For Cases 3 and 4, the algorithm failed to find a solution in 5% of the experiments even though one existed. The overall difference in quality between the solution provided by Algorithm 4 and the optimal solution was under 1% of the latter. The cause of those minor differences lies in potential sub-optimality of the orderings obtained with the use of greedy Algorithms 6 and 7.
From the experiments, it is clear that increasing duration of train movement between stations decreases the efficiency of Algorithm 4. Nevertheless, for the majority of tested cases, the difference between Algorithm 4 and the optimal solution is slight.

6.2. Single Track Timetable

Let us consider a single track case as in the previous section for closure with the following parameters T 0 C = 50 , t 0 CES = 0 , t 0 CLS = 105 , R 0 , 1 , 2 , 1 C , and four trains with timetable as follows:
  • Run p = 0 station visit order: 0 , 1 , 2 , 0 , arrival and departure times t 0 , 0 DEP = t 1 , 0 ARR = 0 , t 1 , 1 DEP = 5 , t 2 , 0 ARR = 55 , t 2 , 0 DEP = t 0 , 0 ARR = 60 , t 2 , 0 ARR 300 .
  • Run p = 1 station visit order: 0 , 1 , 2 , 0 , arrival and departure times t 0 , 1 DEP = t 1 , 1 ARR = 50 , t 1 , 1 DEP = 55 , t 2 , 1 ARR = 105 , t 2 , 1 DEP = t 0 , 1 ARR = 110 , t 2 , 1 ARR 300 .
  • Run p = 2 station visit order: 0 , 1 , 2 , 0 , arrival and departure times t 0 , 2 DEP = t 1 , 1 ARR = 50 , t 1 , 2 DEP = 105 , t 2 , 2 ARR = 155 , t 2 , 2 DEP = t 0 , 2 ARR = 160 , t 2 , 2 ARR 300 .
  • Run p = 3 station visit order: 0 , 2 , 1 , 0 , arrival and departure times t 0 , 3 DEP = t 2 , 3 ARR = 155 , t 2 , 3 DEP = 160 , t 1 , 3 ARR = 210 , t 1 , 3 DEP = t 0 , 3 ARR = 215 , t 2 , 3 ARR 300 .
The timetables of train runs before and after the closure are in Figure 6 and Figure 7. The figures represent the connection between the time and the distance traveled between nodes (stations) 1 and 2 for different trains. Red represents the time of the closure.

6.3. Network of Tracks Case

The second part of experiments was performed on a multi-station network. The considered network is based on the part of the Polish Railway Network from the region of Kielce consisting of 167 tracks connecting 149 stations as it is depicted in Figure 8, and there were originally 95 train runs in the official timetable for one day. The simulations have been performed for different numbers of train runs T R (i.e., for T R = 10 , 11 , 12 , 13 , 14 , 15 , 20 , 30 ) using the same railway network. Ten different sub-sets of the original set of train runs selected at random according to the uniform probability distribution have been generated for a given number of train runs. Each train run was assumed as obligatory. The standing times have been set to T DL = 15 , T i , p D = 1 for all runs p and stations i. We also assumed that there were three closures in the railway network. Each closure was also assumed as obligatory. Unless otherwise stated, the closures’ duration times have been set to 2h (i.e., T n C = 2 h for all n). For each simulation, the closures’ tracks have been randomly chosen according to the uniform distribution and the closures’ beginning times have also been chosen analogously from the interval ( 0 , T H 2 h ) . These assumptions correspond to the periodic and weekly closure planning when short-term closures caused by the regular maintenance works are taken into consideration. We have limited our consideration to the determination of the plan for one day assuming that the train runs timetable and the closures plan should be repeatable. There stations’ capacities have been unlimited. As for a single track case, the overall time interval was also limited to a single day, i.e., T H = 1440 min. The results are briefly presented in Figure 9, Figure 10, Figure 11 and Figure 12 and in corresponding Table 8, Table 9, Table 10 and Table 11. Dots, as well as error bars, represent the average value, as well as minimal and maximal values, respectively. The dimensionless performance index Q ^ = Q Q ˜ , where Q ˜ stands for the best value of (17) found for the particular problem instance along with the computation time T ˜ , evaluates the heuristic algorithm. Analogously as in Section 6.1, we denote the average, minimum, and maximum values of Q ^ by Q ^ a v g , Q ^ m i n , Q ^ m a x , respectively.
We can observe in Figure 9 and Figure 11 that the growing number of groups η has the significant influence on the deterioration of solution quality, and it does not improve much the computation time (Figure 10 and Figure 12), i.e., the computation time for a fixed number of train runs does not decrease significantly with increasing number of groups. The increase in the number of groups from 2 to 20 deteriorates the quality of solution up to 320%, with only about 26% saving of the computational time. However, when the aim is to check fast the existence of any feasible solution, and the quality of the solution is meaningless, the decomposition into smaller groups may be justified.
The growth of the number of groups (railway sub-networks) η deteriorates the obtained solutions for the same number of train runs T R (Figure 13 and Table 12). A similar situation occurs when the number of train runs T R grows for the fixed number of groups η (Figure 14 and Table 13). Nevertheless, the worsening is less significant in the latter case.
The performance indexes Q ^ values are jointly compared with the computational time T ˜ in Figure 15 and Table 14, while the performance index Q ˜ are jointly compared with the computational time T ˜ in Figure 16 and Table 15. The values of Q ^ are marked on the abscissa axis, and Q ˜ values are represented by dots, in Figure 15. The opposite presentation is used in Figure 16, where values of Q ˜ are represented on the logarithmic abscissa axis, while Q ^ are marked by dots. Both figures present the comparison for different values of T R and η . As it can be observed there, the impact of the number of groups η on the computation time is slight, unlike the solution quality Q ˜ . So, it is not recommended to decompose the problem into many sub-problems, as it deteriorates inadmissibly the quality.
However, it is worth noting that the main challenge consists of answering the question if there is any feasible solution, and it is necessary to obtain the answer in the limited time. So, the most important issue is to obtain any solution in such time. On the other hand, the decision-maker has to be aware that the decreasing of computational time by applying bigger values of η can result in the lack of any solution. Even though the feasible solution of the considered problem may exist, the algorithm can fail to find it. Such a situation can be observed in Table 16, where the algorithm for η 20 did not find any solution in 20% of all examined cases.

7. Final Remarks

The selected management problem on railway transportation under anticipated track closures is considered. Taking into account the planned closures, caused mainly by the maintenance of tracks and stations, requires the elaboration of a new timetable for trains. In consequence, the problems of track closure planning and train rescheduling are jointly considered in the paper as the strongly multivariable and nonlinear mixed integer optimization problem. A novel approach based on the decomposition is applied, which results in the heuristic solution algorithm. The conducted simulation experiments confirmed the usefulness of the algorithm regarding both the performance index applied and the computational time. In particular, the experiments performed on single tracks have shown that the results generated by the heuristic algorithm are quite close to the optimal ones. Such experiments involving optimal solutions are impossible for greater instances of the problem. Hence, the profound simulation experiments were performed for the real-world example including 95 train runs. The results confirmed the effectiveness of the algorithm for a wide range of the algorithm’s parameters, first of all for the different number of groups (railway sub-networks) being the result of the applied decomposition. The computational time did not exceed a half an hour for the real-world instance considered. So, it is possible to effectively launch the algorithm for substantially big problem instances. The proposed solution algorithm with the number of railway sub-networks η as the algorithm’s parameter also allows for fast checking of the existence of any feasible solution neglecting the optimization of the criterion. Such property of the algorithm seems to be very important for real-world applications.
The verification of the current model is now considered for the case when a substitutive transport with resulted additional costs is possible. Planned further works will consist mainly of the generalization of the model proposed in Section 3, by taking into account additional facets important for railway networks management as different categories of trains and priorities in their running, as well as additional constraints on station capacities and track forks.

Author Contributions

Conceptualization, G.F., D.G., M.H., and J.J.; methodology, G.F., D.G., M.H., and J.J.; software, D.G., and M.H.; validation, G.F., D.G., M.H., and J.J.; formal analysis, G.F., D.G., M.H., and J.J.; investigation, D.G. and M.H.; writing—original draft preparation, G.F., D.G., M.H., and J.J.; writing—review and editing, G.F., D.G., M.H., and J.J.; visualization, G.F., D.G., and M.H. All authors have read and agreed to the published version of the manuscript.

Funding

The research presented in this paper was partially supported by the European Union within the European Regional Development Fund program Number POIG.01.03.01-02-079/12.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Arenas, D.; Chevrier, R.; Rodriguez, J.; Dhaenens, C.; Hanafi, S. Application of a co-evolutionary genetic algorithm to solve the periodic railway timetabling problem. In Proceedings of the 2013 IEEE International Conference on Industrial Engineering and Systems Management (IESM), Agdal, Morocco, 28–30 October 2013. [Google Scholar]
  2. Goverde, R.M.; Besinovic, N.; Binder, A.; Cacchiani, V.; Quaglietta, E.; Roberti, R.; Toth, P. A three-level framework for performance-based railway timetabling. In Proceedings of the 6th International conference on Railway Operations Modelling and Analysis, RailTokyo 2015, Narashimo, Japan, 23–26 March 2015. [Google Scholar]
  3. Niu, H.; Zhou, X. Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transp. Res. Part C Emerg. Technol. 2013, 36, 212–230. [Google Scholar] [CrossRef]
  4. Barrena, E.; Canca, D.; Coelho, L.C.; Laporte, G. Exact formulations and algorithm for the train timetabling problem with dynamic demand. Comput. Oper. Res. 2014, 44, 66–74. [Google Scholar] [CrossRef]
  5. Filcek, G.; Gąsior, D.; Hojda, M.; Józefczyk, J. Joint Train Rescheduling and Track Closures Planning: Model and Solution Algorithm. In Information Systems Architecture and Technology: Proceedings of 36th International Conference on Information Systems Architecture and Technology—ISAT 2015–Part I; Springer International Publishing: Berlin/Heidelberg, Germany, 2016; pp. 215–225. [Google Scholar]
  6. Hojda, M.; Filcek, G. A Joint Problem of Track Closure Planning and Train Run Rescheduling with Detours. In Advances in Intelligent Systems and Computing—Advances in Systems Science 539; Springer International Publishing: Berlin/Heidelberg, Germany, 2017; pp. 285–294. [Google Scholar]
  7. Bach, L.; Dollevoet, T.; Huisman, D. Integrating timetabling and crew scheduling at a freight railway operator. Transp. Sci. 2016, 50, 878–891. [Google Scholar] [CrossRef] [Green Version]
  8. Zhang, Y.; D’Ariano, A.; He, B.; Peng, Q. Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling. Transp. Res. Part B Methodol. 2019, 127, 237–278. [Google Scholar] [CrossRef]
  9. Zhang, C.; Gao, Y.; Yang, L.; Gao, Z.; Qi, J. Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation. Transp. Res. Part B Methodol. 2020, 134, 64–92. [Google Scholar] [CrossRef]
  10. Corman, F.; Meng, L. A Review of Online Dynamic Models and Algorithms for Railway Traffic Management. IEEE Trans. Intell. Transp. Syst. 2015, 16, 1274–1284. [Google Scholar] [CrossRef]
  11. Schobel, A. A model for the delay management problem based on Mixed Integer Programming. Electron. Notes Theor. Comput. Sci. 2001, 50, 1–10. [Google Scholar] [CrossRef] [Green Version]
  12. Schobel, A. Capacity constraints in delay management. J. Public Transp. 2009, 1, 135–154. [Google Scholar] [CrossRef] [Green Version]
  13. Brännlund, U.; Lindberg, P.O.; Nõu, A.; Nilsson, J.-E. Railway timetabling using Lagrangian relaxation. Transp. Sci. 1998, 32, 358–369. [Google Scholar] [CrossRef]
  14. Petersen, E.; Taylor, A. Line block prevention in rail line dispatch and simulation models. Inf. Syst. Oper. Res. 1983, 21, 46–51. [Google Scholar] [CrossRef]
  15. Ping, L.; Axin, N.; Limin, J.; Fuzhang, W. Study on intelligent train dispatching. In Proceedings of the IEEE Intelligent Transportation Systems Conference Proceedings, Oakland, CA, USA, 25–29 August 2001. [Google Scholar]
  16. Zhang, Z.; Zhu, C.; Ma, W. Discrete Optimization on Train Rescheduling on Single-Track Railway: Clustering Hierarchy and Heuristic Search. J. Adv. Transp. 2020, 2020. [Google Scholar] [CrossRef]
  17. Tornquist, J.; Persson, J. N-tracked railway traffic rescheduling during disturbances. Transp. Res. Part B 2007, 41, 342–362. [Google Scholar] [CrossRef]
  18. Dessouky, M.M.; Lu, Q.; Zhao, J.; Leachman, R.C. An exact solution procedure to determine the optimal dispatching times for complex rail networks. IIE Trans. 2006, 38, 141–152. [Google Scholar] [CrossRef]
  19. Acuna-Agost, R.; Michelon, P.; Feillet, D.; Guaye, S. Constraint Programming and Mixed Integer Linear Programming for Rescheduling Trains under Disrupted Operations A Comparative Analysis of Models, Solution Methods, and Their Integration. Springer Lect. Notes Comput. Sci. 2009, 5547/2009, 312–313. [Google Scholar]
  20. Cacchiani, V.; Huisman, D.; Kidd, M.; Kroon, L.; Toth, P.; Veelentruf, L.; Wagenaar, J. An overview of recovery models and algorithms for real-time railway rescheduling. Transp. Res. Part B Methodol. 2014, 63, 15–37. [Google Scholar] [CrossRef] [Green Version]
  21. Mascis, A.; Pacciarelli, D. Job shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. 2002, 143, 498–517. [Google Scholar] [CrossRef]
  22. Sama, M.; Pellegrini, P.; D’Ariano, A.; Rodriguez, J.; Pacciarelli, D. The potential of the routing selection problem in real-time railway traffic management. In Proceedings of the 7th International Conference on Railway Operations Modelling and Analysis, Lille, France, 4–7 April 2017. [Google Scholar]
  23. Harrod, S. Modeling network transition constraints with hypergraphs. Transp. Sci. 2011, 45, 81–97. [Google Scholar] [CrossRef]
  24. He, B.; Song, R.; He, S.; Xu, Y. High-Speed Rail Train Timetabling Problem: A Time-Space Network Based Method with an Improved Branch-and-Price Algorithm. Math. Probl. Eng. 2014, 2014, 15. [Google Scholar] [CrossRef] [Green Version]
  25. Acuna-Agost, R. Mathematical Modeling and Methods for Rescheduling Trains under Disrupted Operations; Universitéd’Avignon et des Pays de Vaucluse: Avignon, France, 2010. [Google Scholar]
  26. Tornquist, J.; Persson, J.A. Train traffic deviation handling using Tabu Search and Simulated Annealing. In Proceedings of the 38th Hawaii International Conference on System Sciences (HICSS38), Big Island, HI, USA, 3–6 January 2005. [Google Scholar]
  27. Veelenturf, L.P.; Kidd, M.P.; Cacchiani, V.; Kroon, L.G.; Toth, P. A railway timetable rescheduling approach for handling large-scale disruptions. Transp. Sci. 2015, 50, 841–862. [Google Scholar] [CrossRef] [Green Version]
  28. Andersson, E.; Peterson, A.; Törnquist Krasemann, J. Improved Railway Timetable Robustness for Reduced Traffic Delays–a MILP approach. In Proceedings of the 6th International conference on Railway Operations Modelling and Analysis, RailTokyo 2015, Narashimo, Japan, 23–26 March 2015. [Google Scholar]
  29. Heydar, M.; Petering, M.E.; Bergmann, D.R. Mixed integer programming for minimizing the period of a cyclic railway timetable for a single track with two train types. Comput. Ind. Eng. 2013, 66, 171–185. [Google Scholar] [CrossRef]
  30. Louwerse, I.; Huisman, D. Adjusting a railway timetable in case of partial or complete blockades. Eur. J. Oper. Res. 2014, 235, 583–593. [Google Scholar] [CrossRef] [Green Version]
  31. Wang, Y.; Wei, Y.; Zhang, Q.; Shi, H.; Pang, P. Scheduling overnight trains for improving both last and first train services in an urban subway network. Adv. Mech. Eng. 2019, 11, 1–19. [Google Scholar] [CrossRef] [Green Version]
  32. Altazin, E.; Dauzère-Pérès, S.; Ramond, F.; Tréfond, S. A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems. Eur. J. Oper. Res. 2020, 286, 662–672. [Google Scholar] [CrossRef]
  33. Zhong, Q.; Zhang, Y.; Wang, D.; Zhong, Q.; Wen, C.; Peng, Q. A Mixed Integer Linear Programming Model for Rolling Stock Deadhead Routing before the Operation Period in an Urban Rail Transit Line. J. Adv. Transp. 2020, 1–18. [Google Scholar] [CrossRef]
  34. Dekker, R. Applications of maintenance optimization models: A review and analysis. Reliab. Eng. Syst. Saf. 1996, 51, 229–240. [Google Scholar] [CrossRef] [Green Version]
  35. Higgins, A.; Ferreira, L.; Lake, M. Scheduling rail track maintenance to minimise overall delays. In Proceedings of the 14th International Symposium on Transportation and Traffic Theory, Jerusalem, Israel, 20–23 July 1999. [Google Scholar]
  36. Budai, G.; Huisman, D.; Dekker, R. Scheduling preventive railway main- tenance activities. J. Oper. Res. Soc. 2006, 57, 1035–1044. [Google Scholar] [CrossRef] [Green Version]
  37. Higgins, A. Scheduling of railway track maintenance activities and crews. J. Oper. Res. Soc. 1998, 49, 1026–1033. [Google Scholar] [CrossRef]
  38. Khalouli, S.; Benmansour, R.; Hanafi, S. An ant colony algorithm based on opportunities for scheduling the preventive railway maintenance. In Proceedings of the Control, Decision and Information Technologies (CoDIT), Saint Julian’s, Malta, 6–8 April 2016. [Google Scholar]
  39. Lidén, T.; Joborn, M. Dimensioning windows for railway infrastructure maintenance: Cost efficiency versus traffic impact. J. Rail Transp. Plan. Manag. 2016, 6, 32–47. [Google Scholar] [CrossRef] [Green Version]
  40. Lidén, T. Railway infrastructure maintenance-a survey of planning problems and conducted research. Transp. Res. Procedia 2015, 10, 574–583. [Google Scholar] [CrossRef] [Green Version]
  41. Lidén, T. Survey of Railway Maintenance Activities from a Planning Perspective and Literature Review Concerning the Use of Mathematical Algorithms for Solving Such Planning and Scheduling Problems; Technical Report; Department of Science and Technology, Linköping University: Linköping, Sweden, 2014. [Google Scholar]
  42. Kiefer, A.; Schilde, M.; Doerner, K. Scheduling of maintenance work of a large-scale tramway network. Eur. J. Oper. Res. 2018, 270, 1158–1170. [Google Scholar] [CrossRef]
  43. Jovanovic, D.; Harker, P.T. Tactical scheduling of rail operations: The SCAN I system. Transp. Sci. 1991, 25, 46–64. [Google Scholar] [CrossRef]
  44. Kraay, D.R.; Harker, P.T. Real-time scheduling of freight railroads. Transp. Res. Part B 1995, 29, 213–229. [Google Scholar] [CrossRef]
  45. Van Zante-de Fokkert, J.I.; den Hertog, D.; van den Berg, F.J.; Verhoeven, J.H.M. The Netherlands schedules track maintenance to improve track workers’ safety. Interfaces 2007, 37, 133–142. [Google Scholar] [CrossRef]
  46. Albrecht, A.R.; Panton, D.M.; Lee, D.H. Rescheduling rail networks with maintenance disruptions using problem space search. Comput. Oper. Res. 2013, 40, 703–712. [Google Scholar] [CrossRef]
  47. Albrecht, A. Integrating Railway Track Maintenance and Train Timetables. Ph.D. Thesis, University of South Australia, Adelaide, Australia, 2009. [Google Scholar]
  48. Forsgren, M.; Aronsson, M.; and Gestrelius, S. Maintaining tracks and traffic flow at the same time. J. Rail Transp. Plan. Manag. 2013, 3, 111–123. [Google Scholar] [CrossRef]
  49. Lidén, T.; Joborn, M. An optimization model for integrated planning of railway traffic and network maintenance. Transp. Res. Part C Emerg. Technol. 2017, 74, 327–347. [Google Scholar] [CrossRef] [Green Version]
  50. Lidén, T. Reformulations for Integrated Planning of Railway Traffic and Network Maintenance. In Proceedings of the 18th Workshop on Algorithmic Approaches for Transp. Modelling, Optimization, and Systems, Helsinki, Finland, 23–24 August 2018; Borndörfer, R., Storandt, S., Eds.; Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany, 2018; pp. 1:1–1:10. [Google Scholar]
  51. Lidén, T.; Kalinowski, T.; Waterer, H. Resource considerations for integrated planning of railway traffic and maintenance windows. J. Rail Transp. Plan. Manag. 2018, 8, 1–15. [Google Scholar] [CrossRef]
  52. Luan, X.; Miao, J.; Meng, L.; Corman, F.; Lodewijks, G. Integrated optimization on train scheduling and preventive maintenance time slots planning. Transp. Res. Part C Emerg. Technol. 2017, 80, 329–359. [Google Scholar] [CrossRef]
  53. Aken, S.V.; Bešinović, N.; Goverde, R.M.P. Designing alternative railway timetables under infrastructure maintenance possessions. Transp. Res. Part B Methodol 2017, 98, 224–238. [Google Scholar] [CrossRef]
  54. Arenas, D.; Pellegrini, P.; Hanafi, S.; Rodriguez, J. Timetable rearrangement to cope with railway maintenance activities. Comput. Oper. Res. 2018, 95, 123–138. [Google Scholar] [CrossRef]
  55. Zhang, C.; Gao, Y.; Yang, L.; Kumar, U.; Gao, Z. Integrated optimization of train scheduling and maintenance planning on high-speed railway corridors. Omega 2019, 87, 86–104. [Google Scholar] [CrossRef]
  56. Cavone, G.; Blenkers, T.; van den Boom, T.; Dotoli, M.; Seatzu, C.; De Schutter, B. Railway disruption: A bi-level rescheduling algorithm. In Proceedings of the 6th International Conference on Control, Decision and Information Technologies (CoDIT’19), Paris, France, 23–26 April 2019; pp. 54–59. [Google Scholar]
  57. Cavone, G.; van den Boom, T.; Blenkers, L.; Dotoli, M.; Seatzu, C.; De Schutter, B. An MPC-Based Rescheduling Algorithm for Disruptions and Disturbances in Large-Scale Railway Networks. IEEE Trans. Autom. Sci. Eng. 2020; in print. [Google Scholar]
  58. Luan, X.; Wang, Y.; De Schutter, B.; Meng, L.; Lodewijks, G.; Corman, F. Integration of real-time traffic management and train control for rail networks—Part 1: Optimization problems and solution approaches. Transp. Res. Part B 2018, 115, 41-–71. [Google Scholar] [CrossRef]
  59. Yin, J.; Tang, T.; Yang, L.; Xun, J.; Huang, Y.; Gao, Z. Research and development of automatic train operation for railway transportation systems: A survey. Transp. Res. Part C 2017, 85, 548––572. [Google Scholar] [CrossRef]
  60. Zasady Organizacji i Udzielania Zamknięć Torowych Ir-19. 2015. Available online: http://www.plk-sa.pl/files/public/user_upload/pdf/Akty_prawne_i_przepisy/Instrukcje/Wydruk/Ir-19.pdf (accessed on 30 August 2016).
  61. Zasady Organizacji i Udzielania Zamknięć Torowych Ir-19. 2018. Available online: https://www.plk-sa.pl/files/public/user_upload/pdf/Akty_prawne_i_przepisy/Instrukcje/Wydruk/Instrukcja_Ir-19.pdf (accessed on 7 September 2020).
  62. Hoogeveen, J.; van de Velde, S. Scheduling around a small common due date. Eur. J. Oper. Res. 1991, 55, 237–242. [Google Scholar] [CrossRef] [Green Version]
  63. lp_solve Reference Guide. Available online: http://lpsolve.sourceforge.net/5.5/ (accessed on 30 October 2016).
  64. Filcek, G.; Gasior, D.; Hojda, M.; Jozefczyk, J. An Algorithm for Rescheduling of Trains under Planned Track Closures—Auxiliary Problem Formulations; ResearchGate: Berlin, Germany, 2017. [Google Scholar] [CrossRef]
  65. Gonzaga, C. On the Complexity of Linear Programming. Resenhas IME-USP 1995, 2, 197–207. [Google Scholar]
Figure 1. Illustration of a very simple railway network.
Figure 1. Illustration of a very simple railway network.
Applsci 11 02334 g001
Figure 2. Illustration of an example of a track closure.
Figure 2. Illustration of an example of a track closure.
Applsci 11 02334 g002
Figure 3. Structure of multi-level algorithm.
Figure 3. Structure of multi-level algorithm.
Applsci 11 02334 g003
Figure 4. Dependence of Q ˜ a v g (minutes) on the number of train runs for selected cases.
Figure 4. Dependence of Q ˜ a v g (minutes) on the number of train runs for selected cases.
Applsci 11 02334 g004
Figure 5. Dependence of T ˜ a v g (seconds) on the number of train runs for selected cases.
Figure 5. Dependence of T ˜ a v g (seconds) on the number of train runs for selected cases.
Applsci 11 02334 g005
Figure 6. Timetable before closures.
Figure 6. Timetable before closures.
Applsci 11 02334 g006
Figure 7. Timetable after closures.
Figure 7. Timetable after closures.
Applsci 11 02334 g007
Figure 8. The considered part of the Polish Railway Network in the area of Kielce (only selected main stations are indicated by dots).
Figure 8. The considered part of the Polish Railway Network in the area of Kielce (only selected main stations are indicated by dots).
Applsci 11 02334 g008
Figure 9. Dependence of Q ^ on the number of groups for selected numbers of train runs.
Figure 9. Dependence of Q ^ on the number of groups for selected numbers of train runs.
Applsci 11 02334 g009
Figure 10. Dependence of T ˜ (seconds) on the number of groups for selected numbers of train runs.
Figure 10. Dependence of T ˜ (seconds) on the number of groups for selected numbers of train runs.
Applsci 11 02334 g010
Figure 11. Dependence of Q ^ on the number of train runs for selected numbers of groups.
Figure 11. Dependence of Q ^ on the number of train runs for selected numbers of groups.
Applsci 11 02334 g011
Figure 12. Dependence of T ˜ (seconds) on the number of train runs for selected numbers of groups.
Figure 12. Dependence of T ˜ (seconds) on the number of train runs for selected numbers of groups.
Applsci 11 02334 g012
Figure 13. Dependence of Q ^ on the number of groups for 10 train runs.
Figure 13. Dependence of Q ^ on the number of groups for 10 train runs.
Applsci 11 02334 g013
Figure 14. Dependence of Q ^ on the number of train runs for 4 groups.
Figure 14. Dependence of Q ^ on the number of train runs for 4 groups.
Applsci 11 02334 g014
Figure 15. Relation between Q ^ and T ˜ (seconds) for selected numbers of train runs and groups (at stations).
Figure 15. Relation between Q ^ and T ˜ (seconds) for selected numbers of train runs and groups (at stations).
Applsci 11 02334 g015
Figure 16. Relation between Q ^ and T ˜ (seconds) for selected closure durations for 10, 20, 30 train runs and for 3 groups.
Figure 16. Relation between Q ^ and T ˜ (seconds) for selected closure durations for 10, 20, 30 train runs and for 3 groups.
Applsci 11 02334 g016
Table 1. Notation regarding railway network model.
Table 1. Notation regarding railway network model.
SymbolDescriptionSymbolDescription
D matrix of distances between stations (tracks lengths) V set of stations in a railway network
d i , j element of D representing distance between stations i and j (tracks length)Vnumber of stations in a railway network
K set of numbers indicating tracks between two stations (by default K = { 0 , 1 , 2 } , “0” means a substitute connection which is not a track) E incidence matrix describing existence of tracks between stations
Kmaximal number of tracks allowed between two stations (by default K = 2 ) e i , j , k element of E indicating the existence of track k connecting stations i and j
G multigraph representing railway network C A P i capacity of station i (the number of trains that can possess the station in the same time moment)
Table 2. Notation regarding train run model.
Table 2. Notation regarding train run model.
SymbolDescriptionSymbolDescription
TR set of train runs (trains) in the timetable T DL maximal dwell time of a train at a station
T R number of trains in the timetable TT G vector describing the original timetable of trains
R p T binary matrix representing the routes of trains T T p G element of TT G describing the timetable of train p (route with corresponding arrival/departure times)
R p , i , j , k T element of R p T referring to track k connecting stations i and j and being a part of the route of train p. TR OB set of obligatory trains
t i , p ARR planned arrival time of train p at station i T R OB number of obligatory trains
t i , p DEP planned departure time of train p from station i T E limit of the total travel time extension of a train regarding the original timetable TT G
T i , p ARR maximal lateness of arrival of train p to station i D L travel distance extension of the train regarding the original timetable TT G used to limit travel time
T i , p DEP maximal lateness of departure of train p from station i T DE limit of the travel time extension relating to the distance D L
T i , p D minimal dwell time of train p at station i
Table 3. Notation regarding track closure model.
Table 3. Notation regarding track closure model.
SymbolDescriptionSymbolDescription
C set of all closures T n C duration of closure n
Cnumber of all closures t n CES earliest start time of closure n
C OB number of obligatory closures t n CLS latest start time of closure n
S G matrix of closure parameters O binary matrix of precedence constraints among closures
S n G element of S G representing a tuple describing closure n o n , m element of O representing a precedence constraint between closures n and m
R n C matrix of tracks blocked by closure n T H time horizon of the investigated problem
R n , i , j , k C element of R n C representing the existence of a blockade of track k between stations i and j to be performed by closure n
Table 4. Decision variables.
Table 4. Decision variables.
SymbolDescriptionSymbolDescription
y binary matrix of closure planning Δ t i , p ARR N element of Δ t ARR representing time shift of train p arrival to station i
y n { 0 , 1 } element of y indicating the status of closure n Δ t DEP matrix with time shifts of train departures from stations
Δ t C matrix with time shifts of closure start moments S matrix representing the plan of track closures
Δ t n C N element of Δ t C representing the start time shift of closure n S n element of S representing plan for closure n
r T matrix describing routes of all trains r n C tracks to be closed during closure n
r p T matrix describing the route of train p being the element of r T TT vector with timetable of trains
r p , i , j , k T { 0 , 1 } element of r p T describing the connection between stations i and j is used in the route of train p T T p element of TT given by a tuple representing the timetable of train p
Δ t ARR matrix with time shifts of train arrivals to stations x binary matrix describing inclusion of trains into timetable TT
Δ t i , p DEP N element of Δ t DEP representing time shift of train p departure from station i x p { 0 , 1 } element of x indicating the possible inclusion of train p into timetable TT
Table 5. Decision variables.
Table 5. Decision variables.
Notation Used in Algorithm 1
SymbolDescriptionSymbolDescription
r n C tracks to be closed during closure n C OB set of obligatory closures
t n CE actual completion time of closure n C F set of facultative closures
z i sequence of obligatory closures C S set of selected closures to be passed to Algorithm 2
Notation Used in Algorithm 2
SymbolDescriptionSymbolDescription
TR S selected train runs to be passed to Algorithm 3 W p , k variable indicating the run of train p by track k between given stations
Δ parameter of Algorithm 2 representing the limit of time shifts of closures or trains U p conflict index for the train run p
Notation Used in Algorithm 3
SymbolDescriptionSymbolDescription
S temporary closure plan V n set of stations of the decomposed sub-network n
TT temporary train timetable η number of sub-networks in the decomposition
GR set of track assignments to groups used for the decomposition π n , p string of stations representing the path of train p
E set of tuples describing each arc that exists in network G C n S set of closures in the decomposed sub-network n
G n graph representing the decomposed railway sub-network n. TR n S set of trains in decomposed sub-network n
E n matrix of tracks (matrix extended by virtual tracks) for the decomposed sub-network nqtrain run marked for rerouting
Notation Used in Algorithm 4
SymbolDescriptionSymbolDescription
Ψ i , j , k series of elements indicating tracks that have trains or track closures and their order C i , j , k set of closures on the given track
Ψ m i , j , k element of Ψ i , j , k indicating if tracks have trains or track closures at position m TR i , j , k set of trains going through track ( i , j , k )
θ i , j , k matrix representing the order of track usage by either trains or closures TR n S _ SUB sub-set of TR n S ,
θ m i , j , k element of θ i , j , k Q 1 i , j , k total time shift for trains limited to a single track at a time
Θ i , j , k number of trains and closures on track k connecting stations i and j TR i set of trains on tracks adjacent to station i.
λ i matrix representing the order of trains entering station i K i ADJ set of tracks adjacent to station i.
λ m i element of λ i indicating number of train entering station i in the order m Q 2 i total time shift of trains for station i.
Λ i number of trains entering station i
Table 6. Dependence of Q ˜ on T R for all cases.
Table 6. Dependence of Q ˜ on T R for all cases.
TR Case 1Case 2Case 3Case 4
Q ˜ avg Q ˜ avg Fail Q ˜ avg Q ˜ avg Fail Q ˜ avg Q ˜ avg Fail Q ˜ avg Q ˜ avg Fail
54.64.6013.613.60597601.80420.1420.10
621.721.7045.445.40380.22380.221562.78570.781
722.922.9039.639.605415412702.67747.561
818.218.20101.2101.20320.44320.441698.4699.70
959.259.2060.160.10924.1924.20565.71569.573
1034.334.3064.564.501360.221361.3311158.81162.80
Table 7. Dependence of T ˜ on T R for all cases.
Table 7. Dependence of T ˜ on T R for all cases.
TR Case 1Case 2Case 3Case 4
T ˜ avg T ˜ avg Fail T ˜ avg T ˜ avg Fail T ˜ avg T ˜ avg Fail T ˜ avg T ˜ avg Fail
50.020.0900.020.0700.130.100.090.090
60.040.1300.050.1100.350.1310.370.141
70.110.1900.10.1701.310.5521.850.211
80.450.2800.490.2306.440.4117.160.310
91.540.3800.870.32026.60.39060.850.43
102.360.501.360.80193.690.521168.750.520
Table 8. Dependence of Q ^ on η for different T R .
Table 8. Dependence of Q ^ on η for different T R .
η TR = 10 TR = 11 TR = 12 TR = 13
Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max
2111111111111
3111111.09111111
41.2611.641.291.021.791.3211.821.2711.73
101.61.22.651.991.472.842.231.682.982.171.42.75
202.171.353.142.431.583.242.521.673.332.661.623.34
η TR = 14 TR = 15 TR = 20 TR = 30
Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max
21111111.0411.15111.04
31111111.1411.331.0111.14
41.38121.2211.651.341.151.491.391.291.72
102.872.173.322.111.122.512.6822.962.672.572.84
202.8723.512.81.563.363.192.523.823.323.33.36
Table 9. Dependence of T ˜ on η for different T R .
Table 9. Dependence of T ˜ on η for different T R .
η TR = 10 TR = 11 TR = 12 TR = 13
T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max
2151416141414141414141414
3141315131313131313131313
4131314131313131313131313
10131314131313131313131313
20131314131313131313131313
η TR = 14 TR = 15 TR = 20 TR = 30
T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max
2323035656067339275421130811931419
3312936646167316251415125712011341
4312934535963300234401120611191250
1031283350466126721032612169871233
20292831483958242107326301151351
Table 10. Dependence of Q ^ on T R for different η .
Table 10. Dependence of Q ^ on T R for different η .
TR η = 2 η = 3 η = 4 η = 10 η = 20
Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max Q ^ avg Q ^ min Q ^ max
101111111.2611.641.61.22.652.171.353.14
11111111.091.291.021.791.991.472.842.431.583.24
121111111.3211.822.231.682.982.521.673.33
131111111.2711.732.171.42.752.661.623.34
141111111.38122.872.173.322.8723.51
151111111.2211.652.111.122.512.81.563.36
201.0411.151.1411.331.341.151.492.6822.963.192.523.82
30111.041.0111.141.391.291.722.672.572.843.323.33.36
Table 11. Dependence of T ˜ on T R for different η .
Table 11. Dependence of T ˜ on T R for different η .
TR η = 2 η = 3 η = 4 η = 10 η = 20
T ˜ avg T ˜ min T ˜ max T ˜ a v g T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max T ˜ avg T ˜ min T ˜ max
10151416141315131314131314131314
11141414131313131313131313131313
12141414131313131313131313131313
13141414131313131313131313131313
14323035312936312934312833292831
15656067646167535963504661483958
20339275421316251415300234401267210326242107326
3013081193141912571201134112061119125012169871233301151351
Table 12. Dependence of Q ^ on η for different T R = 10 .
Table 12. Dependence of Q ^ on η for different T R = 10 .
η Q ^ avg Q ^ min Q ^ max
2111
3111
41.6411.26
102.651.21.6
203.141.352.17
Table 13. Dependence of Q ^ on T R for different η = 4 .
Table 13. Dependence of Q ^ on T R for different η = 4 .
TR Q ^ avg Q ^ min Q ^ max
101.6411.26
201.491.151.34
301.721.291.38
Table 14. Dependence of Q ^ and T ˜ for selected T R and η .
Table 14. Dependence of Q ^ and T ˜ for selected T R and η .
η TR = 10 TR = 20 TR = 30 avg
Q ^ avg T ˜ avg Q ^ avg T ˜ avg Q ^ avg T ˜ avg Q ^ avg T ˜ avg
21151.05339113081.02554
31141.153151.0112571.05529
41.27131.343001.412061.34506
101.6131.692672.6812161.99499
202.17132.22423.333012.56202
Table 15. Dependence of Q and T ˜ for T n { 2 , 4 , 6 } , T R { 10 , 20 , 30 } , and η = 3 .
Table 15. Dependence of Q and T ˜ for T n { 2 , 4 , 6 } , T R { 10 , 20 , 30 } , and η = 3 .
T n TR = 10 TR = 20 TR = 30
Q avg T ˜ avg Q avg T ˜ avg Q avg T ˜ avg
2239132052264112311292
4474144123274214521290
6931147905271430411301
Table 16. Number of cases with feasible solutions found for selected T R and η .
Table 16. Number of cases with feasible solutions found for selected T R and η .
TR η = 2 η = 3 η = 4 η = 10 η = 20 η = 25
10101010101010
20101010101010
301010101088
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Filcek, G.; Gąsior, D.; Hojda, M.; Józefczyk, J. An Algorithm for Rescheduling of Trains under Planned Track Closures. Appl. Sci. 2021, 11, 2334. https://doi.org/10.3390/app11052334

AMA Style

Filcek G, Gąsior D, Hojda M, Józefczyk J. An Algorithm for Rescheduling of Trains under Planned Track Closures. Applied Sciences. 2021; 11(5):2334. https://doi.org/10.3390/app11052334

Chicago/Turabian Style

Filcek, Grzegorz, Dariusz Gąsior, Maciej Hojda, and Jerzy Józefczyk. 2021. "An Algorithm for Rescheduling of Trains under Planned Track Closures" Applied Sciences 11, no. 5: 2334. https://doi.org/10.3390/app11052334

APA Style

Filcek, G., Gąsior, D., Hojda, M., & Józefczyk, J. (2021). An Algorithm for Rescheduling of Trains under Planned Track Closures. Applied Sciences, 11(5), 2334. https://doi.org/10.3390/app11052334

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop