1 Introduction

Railway traffic scheduling is often considered a difficult problem primarily due to its complexity regarding size and the significant interdependencies between the trains. The train timetables must be able to satisfy all traffic regulations [1]. However, in real-time, un-foreseen events may disrupt the timetable, due to equipment failures in infrastructure and rolling stock, fluctuation of passenger volumes, behaviour of railway personnel, weather conditions, etc. [2]. A train rescheduling system should be able to revise the schedule and find a new conflict-free schedule compatible with the real-time status of the network such that trains arrive and depart with the smallest possible delay [3]. Several strategies may be applied to reschedule the trains and resolve the conflicts such as delaying trains, cancellation/partial cancellation of services, route diversion, inclusion of additional services, changing the platform, relocating the stops, reshuffling train orders, etc. [4, 5].

The train rescheduling is currently an active research area in transportation and Operations Research [6]. The following reviews some recent literatures associated to the train rescheduling problem. Caprara et al. developed a model that takes into account some constraints that arise in real-world applications such as station capacities and maintenance operations [7]. Sato and Fukumura studied on train crew rescheduling in Japan. They formulated the problem as an IP model with set-covering constraints [8]. Rezanova and Ryan worked on a train driver recovery problem (TDRP) in disruption situation [9]. Cacchiani et al. presented a heuristic algorithm for scheduling extra freight trains on a railway network, in which passenger trains already have a prescribed timetable that cannot be changed [10]. Mu and Dessouky developed two mathematical formulations to reschedule freight trains: One assumes the path of each train is given and the other one relaxes this assumption. Several heuristics based on mixtures of the two formulations were proposed [11]. Fekete et al. proposed an IP rescheduling model which incorporates shifting and cancelling of trips based on four scenarios of service disruptions [12]. An approach proposed by Caimi et al. attempted to reschedule trains by a discrete-time control aiming at maximizing train punctuality and reliability [13]. Corman et al. proposed a bi-objective rescheduling model of minimizing train delays and missed connections [14]. Sato et al. focused on rescheduling of freight train locomotives when dealing with a disrupted situation. They formulated and solved the problems by column generation [15]. Narayanaswami et al. incorporate disruptions in an MILP model and using the conflicts-resolving constraints. Their model rescheduled only the trains disrupted, so that other ones retain their original schedules [16]. Albrecht et al. presented a verification rescheduling model that simultaneously considered track maintenance and trains. Their examples were based on maintenance scenarios for Queensland railways [17]. Almodovar et al. focused on vehicle re-scheduling problem (VRSP) for passenger railways in case of emergencies. They proposed an online optimization model carried on Madrid Railway network [18]. Louwerse et al. focused on adjusting the timetable of a passenger railway operator in case of both partial and complete blockades of a railway line. Given a forecast of the characteristics of the disruption, the main objective was to maximize the service level offered to the passengers. They presented integer programming formulations and tested their models using instances from Netherlands Railways [19]. Pellegrini, et al. proposed a mixed-integer linear programming formulation for tackling rescheduling problem, representing the infrastructure with fine granularity. They assessed the impact of this representation on the optimal solution by considering randomly generated instances and multiple perturbation scenarios in France railways [20]. Wang et al. suggested two approaches to solve the optimal trajectory planning problem for multiple trains under both fixed and moving block signalling systems. They proposed a mixed integer linear programming problem with minimising energy consumption as the objective function considered [21].

Most studies in train rescheduling have been carried out merely by applying delay strategy aimed at minimizing the average delays and total delays [22], but far little attention has been paid to take into account train cancelling strategy, as well. The aim of this study is to present a novel approach to reschedule the trains which simultaneously incorporates three rescheduling policies: cancelling, delaying and re-ordering trains. The Special privilege of this approach is to restrict the incident effects to a predetermined time threshold. So, the approach is called “restriction rescheduling approach”. Given the infrastructure situation, the characteristics of the incident as well as train delaying and cancellation costs, our goal is to determine an optimal conflict-free timetable, specifying which trains will be cancelled and which ones will still be delayed after occurrence of the incident.

The current paper is organized as follows: In Sect. 2 the main details of our proposed rescheduling approach are described. Based on this approach, a mixed-integer rescheduling model is developed in Sect. 3. In Sect. 4, a meta-heuristic solution method based on simulated annealing algorithm is proposed. In Sect. 5, the computational experiments from two real-world double-track railways are offered. Finally, the concluding remarks are given at the end to summarize the contributions of this article.

2 Restriction Rescheduling Approach

This study focuses on train rescheduling problem in the double-track railways. The studied degraded mode is the one in which an un-foreseen incident occurs in one of the block sections and makes it out-of-service over a specific time horizon. The time of incident occurrence is called beginning of incident (BOI) and the end time of the incident is called EOI. It is a common practice for the central traffic management to approximate the time EOI based on the incident type and previous statistics, since in fact it is dependent on them. The incident time horizon is the difference between EOI and BOI. This horizon is the duration required to re-open the temporarily out-of-service block section. The incidents investigated here are the ones which occur between two adjacent stations, not within a station. Such types of incidents are widespread in many railway systems. The incidents may disrupt the timetable and cause movement conflicts which need to be resolved effectively. As a matter of fact, the central traffic management is in charge of resolving the conflicts to revive the primary time-table as soon as possible. To that end, different variables must be comprehensively considered such as: time, position and type of the incident, incident time horizon, trains priorities, cancellation and delay costs, etc.

The primary time-table is composed of train schedules, each of which specifies the departure and arrival times of trains from/to stations. The schedule of each train must be designed so that no movement conflict appears in the entire timetable. In case an incident occurs, the disruptions in the timetable can be propagated to other trains. This implies that the whole duration in which the trains are affected by incident, is usually greater than the incident time horizon. The trouble is much more momentous for congested railways. In such railways, a short-term incident may disrupt a major part of the time-table. It must be pointed out that the less part of the timetable is modified, the better the re-scheduled timetable is [4, 23]. Therefore, to reach a suitable rescheduled time-table, the delay propagation must be limited effectively.

For more clarification, a simple instance is employed. Figure 1 presents the primary scheduling graph of a small hypothetical railway that consists of four block sections (numbered B1–B4) and seven trains (T1–T7). The horizontal axis is time and the vertical is block section. Each train is represented using a thick line where the start and the end of the line in each block section represent the departure and arrival times, respectively. Trains T1–T4 are displayed by continuous lines, whereas T5–T7 are shown by dotted lines. The origin and the destination of all trains are B1 and B4, respectively.

Fig. 1
figure 1

The primary graph of a hypothetical instance

Full size image

Now suppose that an un-foreseen incident occurs at the time BOI and makes B3 out-of-service. The approximated time to re-open this block section is the time EOI. Therefore, no train can pass the incident block section (B3) during the incident time horizon. As shown in Fig. 2, T1 and T2 are directly affected and consequently, the remaining trains (T3–T7) may be affected, so that the schedules of all trains would be deviated from the primary ones.

Fig. 2
figure 2

Rescheduled graph after the incident occurrence

Full size image

To limit the deviations of the trains, a novel approach entitled “restriction rescheduling approach” is proposed in this paper. We have restricted the domain of the deviations to a duration called duration affected by incident (DABI). Such a restriction prevents the delay propagation between a specific amount of trains and retains the original schedules for them. This approach guarantees the punctual revival of the original time-table. However, it limits the available time to reschedule the trains affected by the incident. Thus, some trains may confront large delays, so that cancellation becomes more justifiable for them.

In restriction rescheduling approach, DABI is terminated to a specific time named “Affecting Threshold”. This time must be determined by the central traffic management after incident occurrence. Based on the affecting threshold (AT), the trains can be divided into two categories:

  1. 1.

    Unchanged trains: for these trains, the departure time from the origin is after AT. In the rescheduling process, the schedules of such trains are guaranteed to remain unchanged, so that they travel exactly according to their original schedules. In other words, unchanged trains are not participated in the rescheduling process.

  2. 2.

    Rescheduled trains: all trains except the unchanged ones are rescheduled. Merely for such trains, rescheduling process is executed aiming at cost minimization, considering three strategies: Cancellation, Delaying and Re-ordering. In other words, each of these trains may be delayed, re-ordered or even cancelled.

Figure 3 illustrates the rescheduled graph of the hypothetical instance generated using restriction rescheduling approach when no trains are cancelled. As shown in this figure, trains T5–T7 (shown by dotted lines) are unchanged trains. For trains T1–T4 (the rescheduled ones), the train-block sections which are impossible to be planned before AT, must be accommodated in the possible time gaps between unchanged trains. As it is illustrated in Fig. 3, it is assumed that none of the rescheduled trains are cancelled in this instance. It is worth mentioning that the value of AT may be greater or less than or even equal to the time EOI.

Fig. 3
figure 3

Rescheduled graph generated by “restriction rescheduling approach”

Full size image

It should be mentioned that the inputs of the problem include: incident identifiers (BOI, EOI and incident block section), affecting threshold (AT), cancellation and delay costs as well as the primary time-table. The flowchart of restriction rescheduling approach is illustrated in Fig. 4.

Fig. 4
figure 4

Flowchart of the proposed rescheduling approach

Full size image

3 Rescheduling Optimization Model

The mathematical model of the rescheduling process in railway traffic control problem resembles that of job-shop scheduling problem.

In the formulation, block sections and trains correspond to machines and jobs in the job-shop scheduling, respectively. In the job-shop scheduling, the objective is to minimize the sum of the job completion times [24]. Correspondingly, minimizing the sum of running times (or deviation from scheduled arrival times) of trains, is the major index to evaluate a re-scheduled timetable.

To find a new conflict-free time-table compatible with the restriction rescheduling approach aiming at guaranteeing the optimal solution, we have developed a mixed-integer optimization model in this section. The model simultaneously incorporates three rescheduling policies: cancelling, delaying and re-ordering trains.

3.1 Definitions

The sets, parameters and variables used in the model are represented in Table 1.

Table 1 Employed symbols in the optimization model
Full size table

The duration between times BOI and EOI is called incident time horizon, in which incident block section (\( \tilde{b} \)) is out-of-service. The duration between times BOI and affecting threshold (AT) is known as DABI. The ratio of DABI to incident time horizon, is called “effect ratio” (ER):

$$ {\text{ER}} = \frac{{{\text{Duration}}\,{\text{affected}}\,{\text{by}}\,{\text{incident}}\, ( {\text{DABI)}}}}{{{\text{Incident}}\,{\text{time}}\,{\text{horizon}}}} = \frac{{{\text{AT}} - {\text{BOI}}}}{{{\text{EOI}} - {\text{BOI}}}} $$

It is worth mentioning that the less affecting threshold, the less the effect ratio and consequently, the faster the revival of primary time-table.

The ratio of cancellation cost of train i to cost of 1-min delay of train i, is called “cost ratio of train i” (CR i ):

$$ {\text{CR}}_{i} = \frac{{{\text{CC}}_{i} }}{{{\text{CD}}_{i} }} $$

3.2 Objective function and Constraints

$$ {\text{Min}}\,z = \sum\limits_{i \in R} {D_{i} } + \sum\limits_{i \in R} {({\text{CC}}_{i} \times Z_{i} )} $$
(1)
$$ D_{i} \le M \times (1 - Z_{i} )\quad\forall i \in R $$
(2)
$$ D_{i} \le {\text{CD}}_{i} \times (X_{{i,{\text{bd}}_{i} }} - \tilde{X}_{{i,{\text{bd}}_{i} }} ) + M \times Z_{i} \quad\forall i \in R $$
(3)
$$ D_{i} \ge {\text{CD}}_{i} \times (X_{{i,{\text{bd}}_{i} }} - \tilde{X}_{{i,{\text{bd}}_{i} }} ) - M \times Z_{i} \quad\forall i \in R $$
(4)
$$ Y_{i,b} \le M \times (1 - Z_{i} )\quad\forall i \in R,\forall b \in B_{i} $$
(5)
$$ X_{i,b} \le M \times (1 - Z_{i} )\quad\forall i \in R,\forall b \in B_{i} $$
(6)
$$ Y_{{i,bo_{i} }} \ge {\text{ETO}}_{i} - M \times Z_{i} \quad\forall i \in R $$
(7)
$$ {\text{STmin}}_{i,b} - M \times Z_{i} \le Y_{i,(b + 1)} - X_{i,b} \quad\forall i \in R,\forall b \in B_{i} - \{ {\text{bd}}_{i} \} $$
(8)
$$ \left({\frac{{d_{b}}}{{V\max_{i,b}}} \times (1 - Z_{i})} \right)\pounds X_{i,b} - Y_{i,b} \pounds\left({\frac{{d_{b}}}{{V\min_{i,b}}} \times (1 - Z_{i})} \right)\forall i \in R,\quad\forall b \in B_{i} $$
(9)
$$ Y_{i,b} \ge X_{i,(b - 1)} \quad\forall i \in R,\quad\forall b \in B_{i} ,b \ge bo_{i} + 1 $$
(10)
$$ Y_{j,b} + M \times (1 + Z_{i} + Z_{j} - A_{ijb} ) \ge X_{i,b} + H_{ijb} \quad\forall i,j \in R,\quad\forall b \in B_{i} \,,i \ne j $$
(11)
$$ Y_{i,b} + M \times (Z_{i} + Z_{j} + A_{ijb} ) \ge X_{j,b} + H_{ijb} \quad\;\forall i,j \in R,\quad\forall b \in B_{i} \,\,\,,i \ne j $$
(12)
$$ Y_{{i,\widetilde{b}}} > {\text{EOI}} - M \times Z_{i} \quad\forall i \in R $$
(13)

The objective function of the optimization model is in form of cost minimization and consists of two cost parts: The former part of the objective function is devoted to cost of deviation from the primary time-table and the second part is for the cost of train cancellation, as formulated in Eq. 1.

Constraints 2–4 represent the cost of deviation from the primary time-table. According to constraint 2, if train i is cancelled Z i  = 1), the deviation cost is zero for this train. Otherwise Z i  = 0), constraints 3 and 4 would be active, so that for train i, the deviation cost (D i) equals the product of: the cost of 1-min delay of train i (CD i ), and the difference between arrival times to the destination, in primary and rescheduling plans. By applying constraints 5 and 6, the departure/arrival times of the cancelled trains in all block sections change to zero. Constraints 7–13 are active for all non-cancelled trains: Constraint 7 ensures that the departure time of each train from its origin is not less than the earliest allowable time. Constraint 8 guarantees that the stopping time of trains at each station is greater than or equal to the corresponding minimum required stopping times. Constraint 9 signifies that the time length acceptable for each train to pass a block section is between the most and the least allowable time. Constraint 10 is specialized for the movement continuity of trains. It guarantees that the departure time of train i from start of block section b is greater than or equal to the arrival time of that train to end of the previous block section (b-1). The constraint ensures that the trains pass the block sections one after another. Constrains 11 and 12 guarantee no coincidence of the trains. If A ijb equals 1 (train i enters block section b before train j), constraint 11 would be active. Otherwise, constraint 12 would be active. So, the train re-ordering in all block sections is possible, by applying constraints 11 and 12.

Constraint 13 inhibits any movements of the trains through the incident block section during the incident time horizon. By using this constraint, the departure time of trains from start of the incident block section is postponed to a time after EOI.

3.3 Special Constraints for No Coincidence with Unchanged Trains

Although the unchanged trains are not participated in rescheduling process (as mentioned in Sect. 2), the rescheduling time-table must be free of possible conflicts due to coincidence between those trains and the rescheduled ones. The schedules of the unchanged trains remain fixed and therefore, the departure/arrival times of such trains in the block sections are considered to be the constraints for other trains. Rescheduled train i (\( i \in R \)) encountering unchanged train j (\( j \in R^{\prime} \)) in block section b, can possibly have one of four unacceptable positions (A-1, A-2, B-1 and B-2):

Position A: Departure time of train i is less than departure time of train j.

Position A-1: Arrival time of train i is between departure and arrival times of train j.

Position A-2: Arrival time of train i is greater than arrival times of train j.

Position B: Departure time of train i is greater than departure time of train j but less than arrival time of train j.

Position B-1: Arrival time of train i is greater than arrival times of train j.

Position B-2: Arrival time of train i is less than arrival times of train j.

In Fig. 5, the positions are illustrated. In this figure, rescheduled train i (\( i \in R \)) and unchanged train j (\( j \in R^{\prime} \)) are shown by continuous and dotted lines, respectively.

Fig. 5
figure 5

Possible unacceptable positions of rescheduled train i and unchanged train j

Full size image

The decision variables \( X_{i,b} \) and \( Y_{i,b} \) must be so determined that none of four unacceptable positions occurs. So, two conditions are presented as follows:

$$ IF\,:Y_{i,b} \le Y^{\sim }_{j,b} \Rightarrow X_{i,b} \le Y^{\sim }_{j,b} \quad\forall i \in R,\,\forall j \in R^{\prime},\forall b \in B_{i} $$
(14)
$$ IF\,:Y_{i,b} > Y^{\sim }_{j,b} \Rightarrow Y_{i,b} > X^{\sim }_{j,b} \quad\forall i \in R,\,\forall i \in R^{\prime},\forall b \in B_{i} $$
(15)

According to the condition presented in relation 14, for block section b, if the departure time of train i is less than that of unchanged train j, the arrival time of train i must be less than departure time of train j. By applying such a condition, positions A-1 and A-2 will not occur in any of the block sections. Also, according to the condition presented in relation 15, if the departure time of train i is greater than that of unchanged train j, the departure time of train i must also be greater than the arrival time of train j. By applying this condition, positions B-1 and B-2 will occur in none of the block sections. To develop the constraints corresponding to relations 14 and 15, the binary decision variable \( \lambda_{ijb} \) is defined as follows:

\( \lambda_{ijb} \) is 1 if \( Y_{i\,,b} \le \tilde{Y}_{j,b} \) and it is zero if \( Y_{i,b} > \tilde{Y}_{j,b} \).

Therefore, the appropriate constraints are as follows:

$$ X_{i,b} - M \times (1 + Z_{i} - \lambda_{ijb} ) \le \tilde{Y}_{j,b} \quad\forall i \in R,\forall j \in R^{\prime},\forall b \in B_{i} $$
(16)
$$ Y_{i,b} + M \times (Z_{i} + \lambda_{ijb} ) > \tilde{X}_{j,b} \quad\forall i \in R,\forall j \in R^{\prime},\forall b \in B_{i} $$
(17)

According to constraint 16, if \( \lambda_{ijb} \) equals 1, then the arrival time of train i is less than the departure time of unchanged train j. Constraint 16 is corresponding to relation 14.

According to constraint 17, if \( \lambda_{ijb} \) equals 0, then the departure time of train i is greater than the arrival time of unchanged train j. Constraint 17 is corresponding to relation 15. If train i is cancelled (Z i  = 1), both constraints 16 and 17 are inactive.

4 Metaheuristic Solution Method

Although it is possible to find the optimal solution of a problem via the optimization model, it may require an enormous amount of solving time with the increasing problem size due to the NP-hard nature [25]. In some cases, it is impractical to generate optimal solutions within a given (usually small) time bound [26]. Moreover, optimal solutions are not required usually in rescheduling problems. Since, for such problems, achieving a non-optimal suitable solution in a short time has more significance than finding the optimal solution. Consequently, a trade-off between optimality and solving time must be considered. According to Jafari and Zegordi [27], rescheduling solutions need to be generated in less than 3 min. D’Ariano [26] recommended a value of 10 min as a tolerable time bound for a train rescheduling problem. Consequently, in real-life situations, rescheduling must be performed in a restricted period of time.

In this section, we have developed a metaheuristic solution method. The specific distinction of this solution method is to provide a near-optimal solution of the rescheduling problem in much shorter time compared to the time taken by CPLEX software to solve MIP model described in Sect. 3. In this method, all different combinations of the cancellable trains are surveyed and corresponding to each one, a sub-problem is created. The sub-problems are solved using “simulated annealing algorithm”.

4.1 Main Structure of the Solution Method

As mentioned in Sect. 2, the trains can be divided into two categories, based on the affecting threshold: Unchanged and Rescheduled trains. The cancellable trains are merely the rescheduled ones in which, the departure time from the primary origin is greater than the beginning time of incident (BOI). In other words, at the time the incident occurs, the cancellable trains have not departed the origin. Now suppose there are n cancellable trains (\( n \ge 0 \)). Number of entire combinations of n cancellable trains is:

$$ \left( \begin{aligned} n \hfill \\ 0 \hfill \\ \end{aligned} \right) + \left( \begin{aligned} n \hfill \\ 1 \hfill \\ \end{aligned} \right) + \left( \begin{aligned} n \hfill \\ 2 \hfill \\ \end{aligned} \right) + \cdots + \left( \begin{aligned} n \hfill \\ n \hfill \\ \end{aligned} \right) = \sum\limits_{r = 1}^{n} {\frac{n!}{r!\,\,(n - r)!}} = 2^{n} $$
(18)

Corresponding to each combination, there is one sub-problem named in this article as: “combinatorial sub-problem”. In other words, there are \( \frac{n!}{r!\,\,(n - r)!} \) combinatorial sub-problems, each of which contains r cancelled trains (\( r \le n \)). Each of these sub-problems is solved by using simulated annealing algorithm. If the upper bound achieved after solving a combinatorial sub-problem is less than incumbent (best so-far solution achieved), the upper bound will be updated. Meanwhile, if the cancellation cost of a sub-problem exceeds the incumbent, then this sub-problem can be fathomed and there is no need to execute SA algorithm for that one. In Fig. 6, the structure of the solution method applied is illustrated.

Fig. 6
figure 6

Structure of the proposed solution method

Full size image

4.2 Simulated Annealing Algorithm

The basic structure of the simulated annealing algorithm is shown in Fig. 7. Temperature T, minimal temperature T 0 (T > T 0) and Alpha are given as inputs of this algorithm. To start the algorithm, a feasible initial solution is created. The algorithm loops around the temperature T, constantly reducing until it reaches a value near T 0. In this loop, an adjacent candidate solution is created at each iteration, by perturbing the current solution. This changes the solution to a neighboring solution, but at random. The new (adjacent) solution is accepted (by moving the new adjacent solution to the current one) according to the probability distribution, defined by Eq. 19:

Fig. 7
figure 7

Simulated annealing algorithm

Full size image
$$ P_{\text{accept}} \left( {S,S^{\prime},T} \right) = \left\{ \begin{aligned} 1\quad{\text{if}}\,f(S^{\prime}) - f(S) \hfill \\ \exp \left( {\frac{{f(S^{\prime}) - f(S)}}{T}} \right)\quad{\text{otherwise}} \hfill \\ \end{aligned} \right.\,, $$
(19)

where S and \( S^{\prime} \) represent the current and new solutions, correspondingly. The worse the new solution and the lower the tempreture, the less likely to accept the new solution.

The procedure applied for perturbing the current solution and creating an adjacent solution is described as follows:

  1. 1.

    Select a random block section (b_rand).

  2. 2.

    Fix the train- block sections, which are planned into the block sections prior to b_rand.

  3. 3.

    Select two random consecutive departed trains (Ta and Tb) in b_rand.

  4. 4.

    Change the departure order of trains Ta and Tb in b_rand.

  5. 5.

    Replan other train- block sections, considering all different constraints.

5 Computational Experiments

To evaluate the validity of the developed MIP model and meta-heuristic solution method, several computational experiments are carried on from a real-world double-track railway of Iranian network: Bafgh-Sirjan and Tehran-Mashhad railways. The first one is around 253 km long which consists of 10 block sections and services both freight and passenger trains. The latter one is the longest Iranian double-track railway with 924 km long dedicated to four types of passenger trains and consists of 49 block sections. To reschedule the randomly generated instances via the “restriction rescheduling approach”, the proposed model is implemented in JAVA language and executed on a PC equipped with a CPU at 2.66 GHz, 4 GB RAM and Windows 7 operating system. The model is coded in CPLEX 11 software which automatically generates optimal solutions.

Two incident scenarios with 12 experimental instances in Bafgh-Sirjan double-track railway are investigated. The scenarios are as follows:

Scenario 1: incident occurrence at block section # 4 and obstruction from minute 550–650 (09:10:00–10:50:00).

Scenario 2: incident occurrence at block section # 5 and obstruction from minute 600–800 (10:00:00–13:20:00).

For each scenario, two values of “cost ratio” and three values of “effect ratio” are considered. For each train, the origin and destination, earliest allowable time to depart from origin, minimum stopping times, travel times, cancellation costs, delay costs and the parameters of Simulated Annealing algorithm are considered as the inputs of the problem.

After executing several test problems, the following parameters were set for the simulated annealing algorithm: initial temperature = 2000, final temperature = 100 and cooling rate = 1.001.

Table 2 represents the results of experimental instances. In this table, instances 1–6 are corresponding to the first scenario and the others are related to the second one.

Table 2 The results of experimental instances in Bafgh-Sirjan railway corridor
Full size table

The results shown in Table 2 reveal that the less the value of the effect ratio gets, the fewer the rescheduled trains, and in turn, the greater the total rescheduling cost will be. For example, in instance 1 with the effect ratio of 0.5, one train is cancelled and the total rescheduling cost equals 4707 monetary units. Whereas in instance 5 with the effect ratio of 1.5, although two trains are cancelled, total rescheduling cost has reduced to 3664 monetary units. Figure 8a and b shows the rescheduling graphs generated by solving instances 1 and 5, respectively.

Fig. 8
figure 8

The rescheduling graphs generated by solving instances 1 and 5

Full size image

It must be pointed out that affecting threshold (AT) as an input of the problem is determined by the central traffic management. Therefore, it is concluded that the total rescheduling cost is a function of the decision of the central traffic management in determination of the affecting threshold. In other words, determination of affecting threshold is a trade-off between the total rescheduling cost and the time of revival of the primary time-table. Therefore, for the conditions in which, the central traffic management tends to revive the primary time-table faster, it is required to spend more costs and vice versa. As it can be understood from Table 2, increasing the cancellation cost, reduces the number of cancelled trains and instead, increases train delays. In point of fact, when cancellation cost is increased, the solving software need to make more effort to achieve the optimal solution. Therefore, it leads to an increase in computational time. For example, the only difference between instances 5 and 6 is the difference between values of their cost ratios (which are 500 and 2000, respectively). However, their computational times are 114 and 4928 s, respectively.

Moreover, although the proposed solution method does not necessarily find the optimal solution, it can achieve good solutions in much shorter times compared with the times taken by CPLEX to find the optimal solution. For any one of problems Ex. 8 to Ex. 12, CPLEX was not able to find the optimal solution after 3 h. However, the meta-heuristic method could solve all of them in a very short time. For these problems, not only the outputs of the solution method are better than the ones found by CPLEX after 15 min, but also their corresponding computation times are much less than 15 min.

To evaluate the effectiveness of the proposed meta-heuristic solution method for the large-scale cases, several problems based on Tehran-Mashhad railway corridor are investigated. Each problem is solved twice; once by using CPLEX 11 in a limited period of the time and then, by using the solution method. Different incident scenarios are used. Table 3 shows the results. In this table, both total rescheduling cost and computation time are presented. The computation time dedicated to solve each problem via CPLEX is limited to 30 min. According to the results shown by Table 3, the proposed solution method can achieve good solutions for different instances in short times, while for some large-scale problems, CPLEX cannot find even one feasible solution after half an hour.

Table 3 The results of experimental instances in Tehran-Mashhad railway corridor
Full size table

6 Conclusions and Future works

In this study, a novel train rescheduling approach named “restriction rescheduling approach” is proposed for the cases an incident occurs in the double-track railways. The approach simultaneously incorporates three rescheduling policies (cancelling, delaying and re-ordering) by restricting the effects of an incident to a specific time called affecting threshold. An innovative mixed-integer optimization model and a meta-heuristic solution method are proposed to find the solutions compatible with the proposed approach. In the proposed solution method, all different combinations of the cancellable trains are surveyed and corresponding to each one, a sub-problem is created. The sub-problems are solved using simulated annealing algorithm. An experimental analysis with two incident scenarios on Bafgh-Sirjan double-track railway is examined to test the performance of the model. According to the results, the less the value of the selected affecting threshold gets, the faster the recovery of the primary time-table is and instead, the greater the total rescheduling cost will be. Therefore, for the conditions in which, the central traffic management tends to remove the incident conflicts as soon as possible for quick recovery of the primary time-table, it is necessary to spend more costs. Evidence was also provided that increase in the cost of train cancellation eventuates the reduction in the number of the cancelled trains, along with the increase of the train delays and the computation times. The results of the analysis based on Tehran-Mashhad railway demonstrate the ability of the proposed solution method to solve large-scale problems.

In this study, we developed an optimization model and a meta-heuristic solution method to generate a solution for a problem, on the basis of the new proposed approach. The model is not usable in cases of large-scale problems. On the other hand, the solution method does not necessarily achieve the optimal solution. So, we suggest the researchers developing an efficient exact solution method based on the proposed “restriction rescheduling approach”, which is applicable specially for the cases of large-scale problems.