1 Introduction

In general, railway planning affairs are categorized into: analyzing passenger’s demand, line planning, train scheduling, rolling stock planning, and crew scheduling. In this paper, train scheduling under uncertainty is addressed. In practical cases, perturbations may result to have infeasible time schedule. In these cases, the dispatchers should decide to have a good re-schedule that almost always leads to non-optimum solutions. Therefore, having a good time schedule that is robust against uncertainty is well appreciated.

1.1 Background

Hansen [1] discussed the recent researches concerning railway network timetabling and traffic management and reviewed the related parameters, such as frequency, regularity, running and recovery times, minimal headway and buffer times, and waiting times. Practically, in a railway timetable, there exist many noises which have impact on the planned train travel and dwell times. A delay not only affects a train, but also might lead to delaying propagations amongst other trains, known as secondary delays. In single-track scheduling problem to absorb the noises that might occur in practical cases and to prevent the occurrence of secondary delays, the time interval amongst the occupation of block sections by trains, called buffer times, is extended. Obviously, the augmentation of buffer times deteriorates the optimum value of objective function. Therefore, in this paper, it is intended to extend those buffer times which, on one hand, have considerable effects on the robustness of timetables and, on the other hand, have the minimum effects on the objective function value. In this paper, the periodic fashion of train-scheduling problem, which is formulated based on the Periodic Event Scheduling Problem (PESP) introduced by Serafini and Ukovich [2], is investigated.

During the past decade or so, train-scheduling problem has become one of the most common research topics. Zhou and Zhong [3] also investigated a modified B&B algorithm containing three methods to reduce the solution space. D’Ariano et al. [4] studied real-time scheduling considering train speed coordination. Castillo et al. [5] proposed a method to find the optimum schedules for mixed double- and single-tracked railway network. Xu et al. [6] proposed an optimization model to obtain optimal balanced schedule with the least delay-ratio which is to find the optimal velocity for each train on the railway line. Li et al. [7] proposed a multi-objective train-scheduling model by minimizing the energy and carbon emission cost as well as the total passenger-time.

Besides exact algorithms, Tornquist [8] proposed heuristic algorithms for train-timetabling problems in railway networks. Caprara et al. [9] exhibited a heuristic algorithm based on the Lagrange relaxation method for a double-track railway line. Cacchiani et al. [10] introduced some exact and heuristic algorithms to solve the train-scheduling problem using the solution of the LP relaxation of an ILP formulation. Luis Espinosa-Aranda and García-Ródenas [11] proposed a heuristic method, based on Avoid Most Delayed Alternative Arc (AMDAA) for train network re-scheduling. de Fabris et al. [12] presented a heuristic timetabling algorithm for large-scale application of railway networks. Ghoseiri and Morshedsolouk [13], Jamili and Kianfar [14], and Tormos et al. [15] applied ant colony, simulated, annealing and genetic meta-heuristic algorithms for scheduling trains in single-track railway lines, respectively. Salido et al. [16] and Shafia and Jamili [17] distinctly proposed two measuring indices for the train timetables robustness. Andersson et al. [18] proposed a new robustness measure that incorporates the concept of critical points to find weaknesses in a timetable for improvements.

The robust optimization approach is a method that could be applied to generate robust train-scheduling problem. Bertsimas and Sim [19] as an example introduced a technique, which defines a protection function based on the fact that in real-world applications, just a few number of possible perturbations would be occurred. Shafia et al. [20] benefited from this approach to reach a robust timetable. This method is based on the assumption that at most a limited number of trains are affected by possible perturbations during passing a block section. According to this method, it is assumed that perturbations belong to some crisp intervals. Another approach is based on considering the stochastic behavior of perturbations, which are also studied in [20]. Shafia et al. [21] proposed a new robust approach based on fuzzy approach for periodic train-scheduling problem. Kroon et al. [22] proposed a stochastic model to find an optimal allocation of the running time supplements of a single train on a number of consecutive trips. The model is then extended to improve a given cyclic timetable for a number of trains. Babar Khan and Zhou [23] proposed a two-stage stochastic recourse model for the double-track train-timetabling problem considering the traveling time perturbations.

In general, the robustness in single-track railway lines is achieved by embedding some buffer times among train departures and arrivals. Besides, in double or more track railway lines, as trains do not meet each other regularly, robustness is obtained by adding time supplements to the traveling times. Jamili and Ghannadpour [24] proposed a new formulation for delay computation in double-track urban railway system considering supplementary times. They also computed the required buffer times for defining the required number of tracks during engineering step of railway construction. Jamili and Pourseyed Aghaee [25] proposed a robust approach for genertaing stop-skipping patterns in urban railway operations under traffic alteration situation.

1.2 Objectives of the Work

This paper deals with a robust periodic train-scheduling problem under perturbation. The objectives of the work are listed as follows:

  1. 1.

    Developing a new robustness index.

  2. 2.

    Proposing a new mathematical model considering practical assumptions, as well as the acceleration and deceleration times along with periodic scheduling.

  3. 3.

    Applying the robustness approach against perturbations.

  4. 4.

    Proposing a new concept in periodic train in case of delay propagation called delay intensification.

  5. 5.

    Developing a hybrid heuristic algorithm.

  6. 6.

    Proposing a new lower bound.

1.3 Outline

In this paper, the author introduces a new robustness index in Sect. 2. In Sect. 3, he provides a brief explanation of the PESP. In Sect. 4, the necessary notations and the new robust mathematical model are proposed. Section 5 deals with explanation of the proposed hybrid heuristic algorithm. In Sect. 6, the validity of the proposed algorithm as well as its effectiveness is demonstrated, and then, a case study about Iranian railway network is reviewed. In the last section, some conclusions are made to summarize the contribution of this paper.

2 Robustness Measure

In this paper, the concept behind the robust solutions and stochastic programming is merged to develop a new approach to generate robust timetables. The objective function is to minimize the total weighted traveling time of the trains and total expected values of delays. Moreover, a threshold is defined as the maximum admissible expected values of train delays in each individual block section.

It is clear that generating robust timetables is accompanied with worsening the optimum value of the objective function that is generally minimizing the total traveling times. As a result, robust timetables with minimum effects on the traveling times of trains are required. It is known that if a train is going to stop at a station, it must decelerate on the block section before the station. It should also accelerate on the block section after the station. An appropriate robust timetable must avoid unnecessary stops due to deceleration and acceleration. In this paper, the author proposes a new robustness index to generate timetables with counted characteristics. The previous works [20] and [23] contain some computational difficulties regarding the stochastic characteristics of perturbations. The new proposed method in this paper simplifies the computation method that is highly invaluable in practical applications. Following notations are used to define the proposed robustness measure:

\(\varepsilon_{ij}\) is the random variable of perturbation occurrence for train i in passing block section j, disregarding the potential remained perturbations effects during passing previous block sections. \(D_{ij}\) is the random variable which denotes the delay in arrival of train i to the end of block section j. \(E(D_{ij} )\) is the expected value of \(D_{ij}\), arr ij is the arrival time of train i to the end of block section j, dep ij is the departure time of train i from the beginning of block section j, B i is the set of block sections met by train i, and Tr is the set of trains.

Remark 1: Each train, e.g., i, in each block section, e.g., j, is not only affected by the possible perturbation which may occur in passing the block section, i.e., \(\varepsilon_{ij}\), but also is affected by the delays propagated through the network originated by any possible trains including itself.

Figure 1 shows how a planned timetable is affected by perturbations. In Fig. 1, the delays of trains in each block section can be obtained as follows:

$$D_{11} = \varepsilon_{11} ,$$
$$D_{12} = \varepsilon_{12} + \,D_{11} ,$$
$$D_{22} = \varepsilon_{22} + D_{12} - ({\text{dep}}_{22} - {\text{arr}}_{12} ),$$
$$D_{31} = \varepsilon_{31} + D_{11} - ({\text{dep}}_{31} - {\text{arr}}_{11} ),$$
$$D_{32} = \varepsilon_{32} + \hbox{max} \left\{ {(D_{31} ),(D_{22} - ({\text{dep}}_{32} - {\text{arr}}_{22} ))} \right\},$$
$$D_{21} = \varepsilon_{21} + \hbox{max} \left\{ \begin{aligned} \left( {D_{22} - \left( {{\text{dep}}_{21} - {\text{arr}}_{22} } \right)} \right), \hfill \\ \left( {D_{31} - \left( {{\text{dep}}_{21} - {\text{arr}}_{31} } \right)} \right) \hfill \\ \end{aligned} \right\}\;{\text{and generally}},{\text{ one can find that}}$$

:

$$D_{ij} = \varepsilon_{ij} + \hbox{max} \{ (D_{{ij^{\prime}}} - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} ))\,,(D_{{i^{\prime}j}} - ({\text{dep}}_{ij} - {\text{arr}}_{{i^{\prime}j}} )),\,0\} ,\forall i \in Tr,\;\forall j \in B_{i} ,$$
(1)

where j′ is the block section, which is met before block section j by train i. i′ is the train which passes block section j just before train i. Equation 1 specifies the delay of train i in block section j. In this equation, the statement \((D_{{ij^{\prime}}} - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} ))\) specifies the effect of remained, i.e., non-absorbed, delay of train i in the previous block section, i.e., j′, while \((D_{{i^{\prime}j}} - ({\text{dep}}_{ij} - {\text{arr}}_{{i^{\prime}j}} ))\) indicates the amount of non-absorbed delay of the last train which has passed block section j just before train i. In this study, these statements are called vertical and horizontal delays, respectively. By the proposed Eq. (1), we have computed the chain effects of all non-absorbed delays of every train in each block section to other ones.

Fig. 1
figure 1

Delay propagation amongst trains

Full size image

To provide the required robustness level of timetables, index 2 is proposed.

$$E(D_{ij} ) < \lambda_{ij} ,\quad \forall \;i \in Tr,\;\forall \;j \in B_{i} ,$$
(2)

where \(\lambda_{ij}\) indicates the maximum allowable expected delay for train i at the end of block section j. In other words, the author intends to find such timetables in which the expected delay of train i, \(\forall \,i \in Tr\), in block section j, \(\forall \,j \in B_{i}\), is less than a pre-determined management threshold, i.e.. \(\lambda_{ij}\).

The colored circle in Fig. 1 shows a special case where train 2 is affected by the delay of train 1. In other words, the delay of train 1 in block Sect. 2 is propagated to the network. The delay of train 2 which is caused by train 1 is called secondary delay.

Proposition 1 Consider \(G = g(x_{1} ,x_{2} )\) , where \(x_{1}\) and \(x_{2}\) are both random variables with joint probability density function \(f(x_{1} ,x_{2} )\) . If \(g(x_{1} ,x_{2} ) = \hbox{max} \{ x_{1} ,x_{2} \}\) , then \(E(G) \ge E(x_{1} )\).

Proof It is easy to find that \(E(G) = \iint {g(x_{1} ,x_{2} ) \times f(x_{1} ,x_{2} ) \times {\text{d}}x_{1} {\text{d}}x_{2} }\), and also, \(E(x_{1} ) = \iint {x_{1} \times f(x_{1} ,x_{2} ) \times {\text{d}}x_{1} {\text{d}}x_{2} }\). The result immediately follows from the observation that \(G = g(x_{1} ,x_{2} ) = \hbox{max} \{ x_{1} ,x_{2} \} \ge x_{1}\).

Proposition 2 Consider Eq. (1), where \(\varepsilon_{ij}\) and \(D_{ij}\) are random variables. Then, the following inequalities hold.

$$E(D_{ij} ) \ge E(\varepsilon_{ij} ) + E(D_{{ij^{\prime}}} ) - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} ),$$
$$E(D_{ij} ) \ge E(\varepsilon_{ij} ) + E(D_{{i^{\prime}j}} ) - ({\text{dep}}_{ij} - {\text{arr}}_{{i^{\prime}j}} ),$$
$$E(D_{ij} ) \ge E(\varepsilon_{ij} ).$$

Proof First, note that, \(E(D_{ij} ) = E\left( {\varepsilon_{ij} + \hbox{max} \left\{ \begin{aligned} (D_{{ij^{\prime}}} - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} )), \hfill \\ (D_{{i^{\prime}j}} - ({\text{dep}}_{ij} - {\text{arr}}_{{i^{\prime}j}} )),\,0 \hfill \\ \end{aligned} \right\}} \right)\)which can be simplified to:\(E(D_{ij} ) = E(\varepsilon_{ij} ) + E\left( {\hbox{max} \left\{ \begin{aligned} (D_{{ij^{\prime}}} - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} )), \hfill \\ (D_{{i^{\prime}j}} - ({\text{dep}}_{ij} - {\text{arr}}_{{i^{\prime}j}} )),\,0 \hfill \\ \end{aligned} \right\}} \right).\)

Based on Proposition 1, it is easy to find that:\(E(\hbox{max} \{ (D_{{ij^{\prime}}} - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} )),\;(D_{{i^{\prime}j}} - ({\text{dep}}_{ij} - {\text{arr}}_{{i^{\prime}j}} )),\,0\} ) \ge E(D_{{ij^{\prime}}} - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} ))\), and therefore, \(E(D_{ij} ) \ge E(\varepsilon_{ij} ) + E(D_{{ij^{\prime}}} ) - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} )\). The other two statements can be proved in a similar way.□

3 Mathematical Model

Consider a railway line consisting of n block sections. There are m trains passing the stations and block sections one after another. The signaling system in single-track ones does not allow more than one train to pass a particular block section at a time. Given the traveling time of trains in block sections, the origin and the destination, the idle time of trains at stations for passenger mounting, and dismounting or freight loading and unloading and the importance weight of trains, it is required to find the arrival and departure times of trains to/from stations. This should be organized in such a way that the objective functions would be optimized and all the operational and safety requirements are satisfied. The arrival and departure times have to be in a recurring mode, so that all events are repeated after a specific time. Lower and upper bounds are assumed for the departure times of trains from their origins. In other words, a fixed time is not allocated for the departures of trains from their origins. Moreover, in practical cases, perturbations are likely to happen. Therefore, in this paper, it is aimed to find such timetables which, on one hand, the total weighted traveling times is minimized, and on the other hand, the desired robustness of timetables against unwilling potential delays is obtained. Another practical issue arises when the deceleration and acceleration times are considered. Stopping at a station, regardless of its reason, is yielding two consequences: First, the train should decrease the speed to stop at the station, and then, it must accelerate to leave the station. In the literature, there are a few researches conducted which have studied the acceleration and deceleration times, e.g., [4]. Among these studies, Zhou and Zhoung [3] have modeled these times by introducing two new binary variables in double-track passenger railways. In this paper, the author formulates the acceleration and deceleration times by introducing just one new binary variable in a single-track railway line.

As specified in the introduction section, the author proposed the application of PESP to the model to generate periodic timetables.

Remark 2 The periodic train-scheduling problem can be redefined as the problem of ordering the occupation times in the circles scaled from 1 to T. Each circle represents a block section. As an example, Fig. 2 shows an infeasible block section occupation.

Fig. 2
figure 2

Infeasible block section occupation

Full size image

In the next section, a new mathematical model, which is able to absorb the perturbations that normally happen in practical cases, is presented. The desired robustness index of the generated timetables should be tuned based on Inequality 2. The proposed formulation of robust periodic train-scheduling (RPTS) problem is presented in the following section.

3.1 Mathematical Model for Robust Periodic Train-Scheduling (RPTS) Problem

To formulate the RPTS problem, the following notations are used in the mathematical model.

B is the set of block sections, t ij is the required time for train i to pass block section j, id ij is the idle time of train i at the end of block section j for mounting and dismounting purposes, w i is the importance weight of train i, o i is the first block section that should be passed by train i, d i is the last block section that should be passed by train i, l i is the lower bound for departure time of train i from o i , u i is the upper bound for departure time of train i from o i , r i is the minimum time interval (headway) between occurrence times of two consecutive events, like arrivals and/or departures, T is the time period, \(\bar{t}_{ij}\) is the added time caused by acceleration of train i at the beginning of block section j, \(\underline{t}_{ij}\) is the added time caused by deceleration of train i at the end of block section j, \(A_{ij}\) is the binary variable which is 1, if train i stops at the end of block section j, and 0 otherwise, \(z_{ikj}\) is an integer variable which is used to model the periodic constrains based on the PESP introduced by Serafini and Ukovich, \(\xi_{ij}\) is a threshold which specifies the maximum allowable non-planned dwell time of train i at the end of block section j, \(\zeta_{i}\) is the threshold which specifies the maximum allowable total dwell times of train i, and M is a big number.

The mathematical model of the RPTS problem is presented as the following.

Model P1:

$$\hbox{min} \sum\limits_{i \in Tr} {w_{i} [{\text{arr}}_{{{\text{id}}_{i} }} - {\text{dep}}_{{io_{i} }} ]} + \sum\limits_{i \in Tr} {\sum\limits_{j \in B} {E(D_{ij} )} } ,$$
(3)

s.t.

$${\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} \ge id_{{ij^{\prime}}} ,\quad \forall \,i \in Tr,\;\forall \,j \in (o_{i} ,d_{i} ],\;\forall \,j^{\prime} \in [o_{i} ,d_{i} ],$$
(4)
$${\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} \le M \times A_{{ij^{\prime}}} ,\quad \forall \,i \in Tr,\;\forall \,j \in (o_{i} ,\,d_{i} ],\;\forall \,j^{\prime} \in [o_{i} ,\,d_{i} ],$$
(5)
$${\text{arr}}_{ij} \ge {\text{dep}}_{ij} + \bar{t}_{ij} A_{{ij^{\prime}}} + \underline{t}_{ij} A_{ij} + t_{ij} ,\quad \forall \,i \in Tr,\;\forall \,j \in (o_{i} ,d_{i} ],\;\forall \,j^{\prime} \in [o_{i} ,d_{i} ],$$
(6)
$$l_{i} \le {\text{dep}}_{{io_{i} }} \le u_{i} ,\quad \forall \,i \in Tr,$$
(7)
$$r_{k} \le {\text{dep}}_{ij} - {\text{arr}}_{kj} - z_{ikj} \times T \le T - t_{kj} - t_{ij} - r_{i} ,\quad \forall \,i,k \in Tr,\;\forall \,j \in B_{i} \cap B_{k} ,$$
(8)
$$E(D_{ij} ) \ge E(\varepsilon_{ij} ) + (E(D_{{ij^{\prime}}} ) - ({\text{dep}}_{ij} - {\text{arr}}_{{ij^{\prime}}} )),\quad \forall \,i \in Tr,\forall \,j,j^{\prime} \in B_{i} ,\;j \ne o_{i} ,$$
(9)
$$E(D_{ij} ) \ge E(\varepsilon_{ij} ) + (E(D_{kj} ) - ({\text{dep}}_{ij} - {\text{arr}}_{kj} - z_{ikj} \times T)),\quad \forall \,i,k \in Tr,\;\forall \,j \in B,$$
(10)
$$E(D_{{io_{i} }} ) \ge E(\varepsilon_{{io_{i} }} ),\quad \forall \,i \in Tr,$$
(11)
$$E(D_{ij} ) \ge E(\varepsilon_{ij} ),\quad \forall \,i \in Tr,\;\forall \,j \in B,$$
(12)
$$E\left( {D_{ij} } \right) < \lambda_{ij} ,\;\forall \,i \in Tr,\;\forall \,j \in B,$$
(13)
$${\text{dep}}_{ij} - ({\text{arr}}_{{ij^{\prime}}} + {\text{id}}_{{ij^{\prime}}} ) \le \xi_{ij} ,\quad \forall i \in Tr,\,\,j \in B_{i} ,$$
(14)
$$arr_{{id_{i} }} - dep_{{io_{i} }} - \sum\limits_{{j \in B_{i} }} {t_{ij} } \le \zeta_{i} ,\;\forall i \in Tr,$$
(15)
$$A_{{{\text{id}}_{i} }} = 1,\quad \forall i \in Tr,$$
(16)
$$M \times A_{ij} \ge id_{ij} ,\quad \forall i \in Tr,\,\,j \in B_{i} ,$$
(17)
$$z_{ikj} \in {\rm Z},\quad \forall \,i,k \in Tr,\;\forall \,j \in B_{i} \cap B_{k} ,$$
$${\text{dep}}_{ij} \ge 0,\quad \forall i \in Tr,\,\,j \in B_{i} ,$$
$${\text{arr}}_{ij} \ge 0,\quad \forall i \in Tr,\,\,j \in B_{i} ,$$
$$A_{ij} \in \{ 0,1\} ,\quad \forall i \in Tr,\,\,j \in B_{i} .$$

The objective function of the model (P1) is to minimize the total weighted traveling time of the trains and total expected values of delays.

Remark 3 The expected value of perturbations,\(E\left( {\varepsilon_{ij} } \right)\), should be determined based on the accumulated statistics dependent on the type of each train and the characteristics of every block section.

Remark 4 The required time to pass a block section by a specific train is not fixed. To clarify the issue, consider Fig. 3 showing four distinct cases that yield different traveling times for train i passing block section j. Note that j′ is the block section that is met by train i before block section j. It can be found that in case 1: \(A_{ij} = A_{{ij^{\prime}}} = 0\), in case 2: \(A_{ij} = 0,\,A_{{ij^{\prime}}} = 1\), in case 3: \(A_{ij} = 1,\,A_{{ij^{\prime}}} = 0\), and in case 4: \(A_{ij} = A_{{ij^{\prime}}} = 1\). Furthermore, it would be concluded that:in case 1: \({\text{arr}}_{ij} - {\text{arr}}_{{ij^{\prime}}} = t_{ij}\), in case 2: \({\text{arr}}_{ij} - {\text{arr}}_{{ij^{\prime}}} \ge t_{ij} + \bar{t}_{ij} + id_{ij}\), in case 3: \({\text{arr}}_{ij} - {\text{arr}}_{{ij^{\prime}}} = t_{ij} + \underline{t}_{ij}\), and in case 4: \({\text{arr}}_{ij} - {\text{arr}}_{{ij^{\prime}}} \ge t_{ij} + \bar{t}_{ij} + \underline{t}_{ij} + {\text{id}}_{ij}\).

Fig. 3
figure 3

Aggregation of acceleration and deceleration times to traveling times

Full size image

Constraint 4 provides the condition in which trains pass block sections one after another. Constraint 5 ensures that if train i stops at the end of a typical block section, e.g., j, the losing times should be considered in the traveling time of train i. Constraint 6 sets the arrival times of trains to the end of block sections considering the possible amount of losing times. Constraint 7 indicates that the departure time of train i from its origin should belong to the interval [l i , u i ]. Constraint 8, which is based on PESP approach, assures that at most only one train can move a particular block section, concurrently. Moreover, this constraint ensures that there is a minimum time interval between two successive events. Constraints 9, 10, 11, 12 are necessary to reformulate Eq. (1) into a linear form. Note that Constraint 13 is the robustness index defined in Sect. 2. Constraint 14 ensures that the non-planned dwell time of a specific train at the end of a block section cannot be more than a threshold. Constraint 15 guarantees that the total dwell times of a specific train cannot be more than a threshold. Constraint 16 is based on the fact that train i stops at the end of its journey, and the required deceleration time must be added to the travel time of train i. Constraint 17 sets the relation between binary variable A ij and parameter \({\text{id}}_{ij}\).

Remark 5 Consider two periods of train timetables. If the second period is not able to absorb the remained delays generated by the first period, a new phenomenon happens which is called “delay intensification”. Once this phenomenon happens, the generated timetable is theoretically infeasible. Namely under the intensification condition, as the number of periods increases, the amount of delays raises from one period to the next. Therefore, if the number of periods converges to infinity the delays of generated timetables converges to infinity as well.

To examine whether a typical timetable is contaminated with the intensification phenomenon, the delays for two consecutive periods must be computed. In the case that the remained delay in the connecting points of periods associated with the second period is bigger than the first period, then it can be concluded that the timetables are infected with the intensification phenomenon.

The discussed mathematical model contains many binary variables involved in a real-world problem formulation. Therefore, one may need to look for a near-optimal solution, as an alternative using a heuristic approach. In the next section, a hybrid meta-heuristic algorithm is presented.

4 Proposed Heuristic Algorithm

Amongst the existing heuristic algorithms, Beam search and meta-heuristic algorithms are the most common approaches in scheduling problems. The beam search algorithm can outperform other substitutes whenever the number of branches in each node is limited. As mentioned before, the departure times from origins are not fixed, and therefore, the number of branches exponentially increases in beam search algorithm as the number of trains and the interval \(\left( {u_{i} - l_{i} } \right),\,\,\forall i \in Tr\) raises. As a result, the meta-heuristic algorithms are more effective to solve the proposed problem. Amongst meta-heuristic algorithms, the convergence speed of evolutionary algorithms, such as genetic algorithm (GA), ant colony algorithm, immune algorithm, particle swarm optimization algorithm, and electromagnetism-like (EM), to the globally (or nearly globally) optimal results is better than that of the traditional techniques. Recently, EM has gained popularity by number of researchers. It is a population-based searching technique, which has high searching efficiency by combining local search. The development of EM is based on analogy with the attraction–repulsion mechanism of the electromagnetism theory to move the sample solutions to optimality based on their associated charges. EM possesses memory, i.e., the characteristics of the good solutions are retained by all particles, whereas in GA, the previous characteristics of the problem are lost once the population alters. Moreover, in EM, all electrical charged particles share their information, and therefore, a constructive cooperation amongst the particles is resulted. From another point of view, EM is often easy to be premature convergence, so that one needs to enrich the exploration for promising solutions within the entire region. On the other hand, simulated annealing (SA) is a stochastic searching algorithm with jumping property (i.e., a worse solution has a probability to be accepted as the new solution). Thus, the author employs the jumping mechanism of SA into EM to achieve the results with enhanced quality.

The rest of this section describes the proposed hybrid algorithm, which consisting of electromagnetism-like (EM) and simulated annealing (SA) algorithms for the RPTS problem. An encoding scheme is presented to generate schedules. SA and EM are then, respectively, reviewed and designed. Finally, the hybridization procedure of these algorithms is explained.

4.1 Encoding Scheme

Using random keys (RKs) as the encoding scheme is well experienced and is easy to adjust to the EM and SA algorithms [26–28]. In this paper, the act of passing a block section by a train is called transit action. Therefore, by assuming that all trains meet every block section, we have \(\left| {Tr} \right| \times \left| B \right|\) transit actions. The priority of trains to pass the block sections is achieved through random keys. Therefore, at the first step, a random number between 0 and 1 is assigned to each transit action, so that all transit actions have a special number. Suppose that these RKs show the relative order of trains passing block sections. Then, the transit actions are sorted considering the assigned RKs.

Once the order of trains passing block sections are calculated, a schedule can be generated based on the given origin departure times, desired robustness index, and the other required parameters defined in Sect. 3.

4.2 Simulated Annealing (SA)

Simulated annealing (SA) is one of the most popular meta-heuristics providing a means to escape local optima by considering moves, which worsen the objective function value. The proposed SA algorithm for the RPTS problem is depicted in Fig. 4.

Fig. 4
figure 4

Proposed SA algorithm

Full size image

Where s is a schedule, s best is the best-found solution, f(s) is the objective function value for schedule s, T k is the temperature in k-th iteration, α is the cooling factor which belongs to the interval (0, 1), and \(P_{\text{accept}} (s,s^{\prime},T_{k} )\) is the probability function to accept non-improving solution s′, Eq. (18):

$$P_{\text{accept}} (s,s^{\prime},T_{k} ) = \left\{ {\begin{array}{*{20}c} 1 & {{\text{if}}\;f(s^{\prime})\, < \,f(s)} \\ {\exp (\frac{{f(s) - f(s^{\prime})}}{{T_{k} }})} & {{\text{otherwise}} .} \\ \end{array} } \right.$$
(18)

Furthermore, MD-1 and MD-2 refer to the Method 1 and Method 2 defined in Sect. 1.3. The procedure named “Timetable generation” is depicted in Fig. 5.

Fig. 5
figure 5

Procedure named “timetable generation”

Full size image

The procedure is divided into three parts, as illustrated in Fig. 5. In Part A, considering the r-th transit action and associated train and block section, e.g., train i, and block section j, an initial value is assigned to train i passing block section j considering the arrival time of train i to the end of the previous block section, i.e., j′. Moreover, the required buffer time which could fulfill the robustness index is also computed and is included into the departure time of train i from the beginning of block section j. The required buffer time is equal to: \(\hbox{max} \{ 0,\;E(D_{ij} ) - \lambda_{ij} \}\). In Part B, the assigned value might be modified, so that it has no conflict with any other scheduled trains. To illustrate the case, consider Fig. 6. Suppose that one intends to schedule train i in the block section j, the dotted line. Part A shows the initial schedule that is modified in Part B as mentioned before. As shown in Fig. 6, the new schedule may affect the possible delay of train l in block section j, see the colored circle in Part B. In Part C, the already scheduled trains are modified using re-schedule algorithm, so that the new schedule covers the desired robustness index. In other words, to reach the desired level of robustness, the scheduled RKs must be reviewed to modify the required buffer times wherever is necessary. This process is performed through re-schedule algorithm. Note that rk lj indicates the RK associated with train l passing block section j.

Fig. 6
figure 6

Illustrative example for timetable generation procedure

Full size image

The procedure named “re-schedule” is depicted in Fig. 7.

Fig. 7
figure 7

Procedure named “Re-schedule”

Full size image

As stated in Part C, if \(E(D_{lj} )\) is altered during scheduling the r-th RK, re-schedule algorithm must be adopted. List (r) is a set which contains the RKs that must be re-scheduled. At the initial iteration, this list only contains the RK related to train l passing block section j, i.e. rk lj.

In Part D, the selected RK is re-scheduled based on the new value of expected delay. Part E and F are to test if the next transit actions must be re-scheduled or not. For example, considering Fig. 6c, the transit action related to the train l passing block section j′ must be investigated in Part E, and in Part F, the transit action associated with train h passing block section j is examined. If in Part E and/or Part F, it is concluded that a new transit action needs to be re-scheduled, then the associated RK is included to the List (r).

4.3 Neighborhood Solution Generation

To generate a neighborhood candidate, two methods are used:

Method 1: This is based on the single-point operator method. In this method, the RK of one randomly selected train from schedule s is regenerated at random.

Method 2: In this method, a train is first selected at random, e.g., train i. Then, the origin departure time of train i, \({\text{dep}}_{{io_{i} }}\), is randomly regenerated, such that the new assigned time is still in the interval [l i , u i ].

The remaining part of this section includes introducing the proposed heuristic algorithm based on the electromagnetism-like mechanism in section D. The proposed method to hybridize this algorithm with SA is explained in section E.

4.4 Electromagnetism-like Mechanism (EM)

EM is a population-based meta-heuristic for solving continuous problems effectively. In general, EM simulates the attraction–repulsion mechanism of electromagnetism theory based on Coulomb’s law. Each particle represents a solution and the charge of each particle relates to its objective function value (OFV). The better OFV of the particle, the higher charge the particle achieves. To compute the force between two points, a charge, such as value q i , is assigned to each point. The charge of the point is computed through the relative efficiency of the OFVs in the current population, as given in the following equation:

$$q_{i} = { \exp }\left( { - n \times \frac{{f(x_{i} ) - f(x_{\text{best}} )}}{{\mathop \sum \nolimits_{j = 1}^{\text{popsize}} (f(x_{j} ) - f(x_{\text{best}} ))}}} \right),\quad \forall i = 1,2, \ldots , {\text{popsize,}}$$
(19)

where q i is the charge of particle i. In addition, f(x i ), f(x best), and f(x j ) denote the objective values of particle i, the best known solution, and the objective value of particle j, respectively. Finally, pop size is the population size. The total force, F i , exerted on candidate solution i is also calculated by Eq. (20). Note that dissimilar to electrical charges, the charge of an individual point in Eq. (19) has no signs. However, the direction of a particular force between two points is computed after comparing their OFVs.

$$F_{i} = \left\{ {\begin{array}{*{20}c} {\sum\limits_{j \ne i}^{\text{popsize}} {(x_{j} - x_{i} )\frac{{q_{j} \times q_{i} }}{{x_{j} - x_{i}^{2} }};} } & {f(x_{j} ) < f(x_{i} )} \\ {\mathop \sum \limits_{j \ne i}^{\text{popsize}} (x_{i} - x_{j} )\frac{{q_{j} \times q_{i} }}{{x_{j} - x_{i}^{2} }};} & {f(x_{j} ) \ge f(x_{i} ).} \\ \end{array} } \right.$$
(20)

The next step is the movement of the candidate solutions based on the total force calculated by Eq. (20). It should be noted that all the candidate solutions are moved except the current best solution. The move for each candidate solution is in the direction of total force exerted on it by a random step length that is generated from uniform distribution between (0, 1), see Eq. (21). It is proved that along this direction by selecting random length, candidate solutions move to the unvisited solution space with a probability more than zero.

$$\left\{ {\begin{array}{*{20}c} {x_{ik} = x_{ik} + {\text{Random}}(0, 1) \times F_{ik} (1 - x_{ik} );} & {F_{ik} > 0} \\ {x_{ik} = x_{ik} + {\text{Random}}(0, 1) \times F_{ik} (x_{ik} );} & {F_{ik} \le 0} \\ \end{array} } \right..$$
(21)

4.5 Hybrid EM–SA Algorithm

The idea of using hybrid algorithms has widely been exploited in the literature, by [26–28]. The evolutionary algorithms have a good convergence speed to the globally (or nearly globally) optimal solutions. EM as a population-based searching technique has recently gained attentions and applications by number of researchers. A weakness of EM is the premature convergence which often results to neglecting some parts of solution space. Therefore, to remove this weak point, the author proposes to employ the jumping mechanism (i.e., a worse solution has a probability to be accepted as the new solution) of SA into EM to achieve the results with higher quality. The EM–SA algorithm includes two phases. In the first phase, the initial solutions are randomly generated. Then, the EM algorithm combined with the SA algorithm is run. The proposed hybrid algorithm is summarized in Fig. 8.

Fig. 8
figure 8

Proposed hybrid algorithm

Full size image

Note that MD-1 and MD-2, the input parameters of SA algorithm, are both considered to be method 2, defined in Sect. 1.3.

4.6 Parameter Tuning

In this section, the parameters of the proposed hybrid algorithm are tuned. These parameters include: pop size, number of SA iteration, the initial temperature, and cooling factor. For this purpose, a full factorial design in the DOE is employed. The levels of the parameters are presented in Table 1.

Table 1 Levels of parameters
Full size table

As shown in Table 1, three parameters must be tuned. Furthermore, for each parameter, two levels are assigned, and therefore, a 23 design is applied. To achieve the interaction plot among hybrid algorithm parameters, 150 numerical experiments are investigated. The result shows that the best pair is 10 for both pop size and SA iteration number, which is accompanied with 0.8 for the cooling factor parameter, where the initial temperature is 150.

The relative deviation index (RDI) is used for the OFV as a performance measure to compare the instances. This index is obtained by the following equation:

$${\text{RDI}}_{k}^{g} = \frac{{{\text{OFV}}_{k}^{g} - {\text{Min}}\{ {\text{OFV}}_{k} \} }}{{{\text{Max}}\{ {\text{OFV}}_{k} \} - {\text{Min}}\{ {\text{OFV}}_{k} \} }},$$
(22)

where \({\text{OFV}}_{k}^{g}\) indicates the objective function value for the k-th instance obtained by the g-th method. \({\text{Min}}\{ {\text{OFV}}_{k} \}\) and \({\text{Max}}\{ {\text{OFV}}_{k} \}\) are the best and worse solutions obtained for k-th instance.

Since the proposed approach is based on heuristic algorithms, there is no guarantee that at the end, an optimal solution is achieved, however, as it is demonstrated in the computational evaluation, Sect. 5, the final schedule will not be far from the optimum solutions. The validation process is performed in two steps. The first step includes the comparison between the outputs of hybrid algorithm and the optimum answers achieved by common software packages based on B&B algorithm using small-size instances. At the second step, the proposed hybrid algorithm is examined and compared by the results of the SA and EM algorithms, as well as an efficient lower bound (LB) using medium- and large-size instances. In this section, an efficient novel LB is presented to find the gap between the best-found solution and the lower bound.

4.7 Lower Bound Generation

Lower bound (LB) can be defined as follows: Let Sc denote the set of all feasible schedules, \(s \in Sc\), of a given train-scheduling problem, P, where the objective function is f(s). Finally LB(P) indicates a lower bound on P where: LB(P) ≤ f(s), \(\forall s \in Sc\). Clearly, it is desired to determine LBs which are as close as possible to the optimum solution.

Singer and Pinedo [29] have introduced an efficient LB for job shop-scheduling problem where the objective is to minimize the total weighted tardiness. This technique is based on relaxing the capacity constraints of all machines except one. The remaining machine is then sequenced optimally by solving a derived single machine-scheduling problem characterized by defining new local release dates and due dates of all operations on the respective machine. In this paper, the LB introduced by Singer and Pinedo is enhanced in a way that instead of relaxing the problem to a single-block section problem, the main problem that consisting of scheduling n trains on m block sections is reduced to the problem of scheduling n trains on 2 contiguous block sections. This alteration aims to find better LBs than the Singer and Pinedo method.

By the above explanation, a combination of \(( {\begin{array}{*{20}c} m \\ 2 \\ \end{array} }) - \frac{(m - 1) + (m - 2)}{2}\) different problems must be solved. To solve the problem of scheduling n trains on block sections k and k + 1, the new origin departure times of trains which travel from station k to k + 1 and vice versa are computed by Eqs. (23) and (24), respectively.

$${\text{nod}}_{i}^{k \to k + 1} = od_{i} + \mathop \sum \limits_{{j = o_{i} }}^{k - 1} t_{ij} ,\quad \forall i \in Tr, {\text{where train}}\; i \;t{\text{ravels from}}\; k {\text{to}}\; k + 1,$$
(23)
$${\text{nod}}_{i}^{k + 1 \to k} = {\text{od}}_{i} + \mathop \sum \limits_{j = k + 2}^{{o_{i} }} t_{ij} ,\quad \forall i \in Tr, {\text{where train}}\; i \;{\text{travels from }}\;k + 1 {\text{to}}\; k.$$
(24)

The lower bound is the minimum achieved objective value among all \(( {\begin{array}{*{20}c} m \\ 2 \\ \end{array} }) - \frac{(m - 1) + (m - 2)}{2}\) combination of solutions.

5 Experimental Results

To illustrate the effectiveness and performance of the proposed hybrid algorithm, it is implemented in VB on a computer with Pentium IV Core 2 Duo 2.53 GHz CPU. According to the earlier explanations, at first, the outputs of hybrid algorithm are compared with optimum solutions achieved by B&B algorithm using small-size instances. Then, the proposed hybrid algorithm is compared individually with the SA and EM algorithms, using medium- and large-size instances. Moreover, the same solution time duration is considered for the algorithms in the second step. Each instance can be characterized by a number of parameters, such as number of trains, number of block sections, origins and destinations of trains, and the tolerance assigned to each origin departure time of trains, traveling times, dwell times for mounting and dismounting of passengers or loading and unloading of goods, the period length and acceleration and deceleration times, as well as expected value of perturbations and robustness index. The generated instances are based on the following assumptions:

  • Trains are divided into two categories: northern and southern trains. All trains meet all block sections, one after another.

  • The origin departure time of each train has a tolerance equal to ±10 min. Moreover, 20-min duration is considered between each consecutive origin departure times of trains.

  • Traveling times are all integer numbers between the interval [10, 20] generated at random.

  • No dwell time is considered for trains at stations.

  • The acceleration and deceleration times are supposed to be equal to 1 and 0 min for all trains, respectively.

  • The expected values of perturbations are all 1 min. The maximum allowable delay for each train in each block section is considered to be 1 min.

The outputs are illustrated in Tables 2 and 3.

Table 2 Comparison results between proposed hybrid algorithm and optimum solution achieved by B&B alg
Full size table
Table 3 Comparison results between hybrid, SA, and EM algorithms in RDI
Full size table

Table 2 shows that the proposed hybrid algorithm is able to find completely near to optimum solutions in a few seconds for small-size instances. The B&B algorithm could not find optimum solutions for larger scale problems within less than 10 min. As the size of the problem expands, the proposed hybrid algorithm reaches better solutions in first minute solving time. In Table 3, the outcomes of proposed hybrid algorithm are compared with those achieved by SA and EM algorithms. The achieved average RDIs for hybrid, SA, and EM algorithms, equal 13.1 %, 69.9 %, and 57.6 %, respectively. The solving times by these three algorithms do not differ meaningfully. The average optimality gap between the achieved lower bound and the best-found solutions by these algorithms equals 30 %. The results demonstrate the effectiveness of the proposed hybrid algorithm in finding near-optimal solutions in a short solving duration.

In this paper, the author also considers a real case study, including the Tehran–Isfahan Railway line, which connects two of the most populated cities of Iran. This route consists of 19 stations. In each period, one freight and three passenger trains travel in north direction and in the same amount in the south direction. The period length equals 360 min. It is also assumed that the traveling times of freight trains are 1.5 times greater than passenger trains. The importance weights of passenger trains are twice than the freight trains. Moreover, the author considered \(\xi_{ij}\), \(\forall i,j\) are equal to 40 min for passenger trains. The acceleration times of passenger and freight trains are considered to be equal to 1 and 2 min, respectively. A time interval equals 90 min are considered amongst the origin departure times of trains. The origin departure times of trains are not fixed and can be altered in a range of ± 40 min.

The desired robustness is adjusted, so that the expected delays of trains in their destinations are less than 3 min, i.e., \(E(D_{{{\text{id}}_{i} }} ) < \lambda_{{{\text{id}}_{i} }} = 3,\quad \forall \,i \in Tr\), where the expected value of perturbations of trains are considered to be equal to 10 % of traveling times. The problem cannot be solved by the exact branch and bound algorithm, and therefore, the author solved the problem by the proposed hybrid algorithm. Based on the previous assumptions, the achieved objective function values of the case study are reported in Table 4 for different amounts of expected value of perturbations all after 15,000 iterations, each of which takes approximately 90 s to be terminated.

Table 4 Objective function values for different amount of \(E(\varepsilon_{ij} )\)
Full size table

6 Conclusion

As it is explained, the train timetable is one of the vital elements of railway planning. To have minimum variations during actual train movements as well as locomotive and crew assignments, the robust timetables play a key role in railway industry. In this paper, a new robust periodic train-scheduling mathematical model is proposed that is capable of handling the perturbations which practically occur during the transit of trains in block sections. The proposed mathematical model could guarantee that a small change in the input parameters does not affect the feasibility and optimality of the produced timetables. As embedding buffer times into timetables may increase unnecessary stops at stations, in this paper, the deceleration and acceleration times are also studied. As a result, in the generated timetables, the buffer times are positioned in a way that they would have minimum effect on the number of train stops. It was shown that in addition to delay propagation amongst trains, there exists a more complicated case in periodic type of scheduling that is the fact of delay propagation from one period to the next, named delay intensification. Besides, a hybrid heuristic algorithm is proposed based on the electromagnetism-like mechanism and simulated annealing. The proposed algorithm is able to solve problems much faster than the exact algorithms. Finally, the implementation of the proposed algorithm is shown as a proof of the effectiveness of the new approach, using some numerical examples and an Iranian case study. For future works, it is suggested to propose some simple rules to embed in the generated time schedule for both single- and double-track railway lines to have a robust timetable.