An algorithm for train delay propagation on double-track railway lines under FCFS management

Abstract

This paper proposes an algorithm for train delay propagation on double-track railway lines under First-Come-First-Serve (FCFS) management. The objective is to handle the challenges faced by the dispatchers as they encounter train delays and their effects on the functioning of the railway system. We assume that the location and duration of disruptions are known, which are important inputs to the algorithm. This data enables calculation of delays experienced by each affected train. Our method analyzes factors such as train schedules, track capacities, and operation constraints to assess the manner in which delays would get propagated along railway lines. Key indicators of delay propagation, consisting of the number of delayed trains and stations, disruption settling time, and cumulative delays, are considered. Moreover, a numerical example is given to explain the practical application of this algorithm. Finally, we show that a tool like this would facilitate the dispatchers in managing and rescheduling trains in case of delays and will be improving resilience and efficiency of railway operations.

Graphical abstract

Keywords

train delay propagation / FCFS management / cumulative delays

1 Introduction

Railway system is an important section of the modern transportation that offers reliable and effective service to the passengers. Despite the presence of the excessive railway network, it is more particular vulnerable to the effects of natural disasters and Accidents (Lu et al., 2021; Zhang et al., 2023a; Lian et al., 2024). Generally, train delays occur due to some factors that prevent the smooth operations of train, hence their travel time beyond planned time (Li et al., 2014; Spanninger et al., 2022; Liu et al., 2023a; Tiong et al., 2023). Additionally, heavily trafficked railway lines delay experience can also propagate to other trains of the same route, resulting in cascade delays that transpire across the entire railway network (Li et al., 2021; Khan et al., 2021; Liu et al., 2023b). Cascading delays may disrupt passenger schedules substantially and cause massive disturbance to the transportation system (Wendler 2007; Salido et al., 2008; Zhang et al., 2023b). The consequences of these cascading delays are far reaching, thereby requiring a careful examination of the underpinning mechanisms leading to train delay propagation. In this study delay propagation is investigated as a phenomenon and its implications for railway operations are evaluated.

Research on the study on train delay propagation has been the focus of many researchers in the recent years as the correct understanding of train delay driving mechanism is vital to increase railway services' proper reliability and punctuality (Petersen, 1974; Higgins and Kozan, 1998; Carey and Kwieciński, 1995; Carey, 1999; Meester and Muns, 2007; Sahin, 2017; Hansen et al., 2010; Huang et al., 2022). For example, based on the assumption of independently and uniformly distributed train departure times, Petersen (1974) proposed a stochastic model which permitted the derivation of a formulation that describes delays experienced by affected trains with high accuracy. Higgins and Kozan (1998) and Carey and Kwieciński (1995) derived the knock on delay propagation rule through stochastic approximation based on primary delays and headway buffers. However, Carey (1999) showed that secondary nonnegative delays can be computed with summation and maximization convolution using stochastic delay propagation model. Furthermore, Meester and Muns (2007) developed a phase type distribution for use with delay distributions and developed a train delay propagation model based on a continuous time Markov chain model. Based on this work, Sahin (2017) developed a Markov chain model for train delay and generated a transition matrix on top of which estimates of recovery time in the case of delays were derived. Historical data has also been further examined to understand how delay propagates. Hansen et al. (2010) performed a data mining study to analyze train delay and to provide accurate estimation of the running and dwelling times distributions during emergencies. Overall, Huang et al. (2022) also proposed a context driven hybrid Bayesian network framework combining K-means clustering approach to identifying train delay propagation patterns and Bayesian network model for train delay prediction. Yet, the above mentioned techniques are not properly capturing the complex correlation and mutual influence among stations across the train delay propagation process. Hence, it is crucial to look at the model from a point of view of delay propagation mechanism.

In contrast to statistical methods based on stochastic patterns and historical data, researchers have proposed to quantify delay propagation on the basis of timetable buffers and time supplements for the comparatively inexperienced train operators (Frank, 1966; Goverde, 2007; Goverde, 2010; Jovanović et al., 2017; Harrod et al., 2019; Ye and Zhang, 2020). Through placing redundant, adjunct time at selected points along the route-well-known junctions or congested areas, operators could reduce cascade effects of delays. Frank et al. (1966) proposed a mathematical algorithm for the calculation of train delays and estimation of train density on a bidirectional railway line. Goverde (2007; 2010) used max-plus algebra modeling to represent the railway timetable with a linear system, clarifying propagation mechanisms by incorporating timetable buffers and supplements. Jovanović et al. (2017) offered a buffer time reallocation strategy to enhance timetabling robustness. They employed periodic timetables with compression techniques to determine the overall time reserve, framing this allocation dilemma as a multi-dimensional knapsack problem. Harrod et al. (2019) studied cascading effects of delays at subsequent stations, using the timetable buffers and supplements; they proposed a cumulative delay function on a single track and analyzed the distribution of cumulative delays at different ratios of both timetable buffers and supplements. Ye and Zhang (2020) laid down the foundation for the comprehensive assessment of delay propagation on the railway by accident factors from two perspectives: forward and backward delay propagation. Unfounded assumptions were made concerning knowledge about the occurrence time and duration of incidents, so minimum headway was used for equating train delays; the absence of timetable supplements and buffer time in their analysis led to inaccuracies in evaluating delays taken in earlier affected stations. This cluster of studies seems to be indicative of the necessity of integrating timetable buffers and supplements in understanding and hence controlling train delay propagation. Such metrics would allow the operators to fashion schedules that are more resilient to delay impacts on railway operations.

In the scope of this work, we study in detail the propagation of delays in train operations along railway lines supervised under the First-Come-First-Served (FCFS) principle. Given the broad context of this investigation, we aim to reveal different facets behind such delays where trains are seen basically as a homogenous type of traffic, one that has its basest assumption rooted in the operations of the Chinese high-speed railway system with one-way traffic maintained on each line as well as with trains principally running at the approximate same speed. By comparison with methodologies described in Harrod et al. (2019) and Ye and Zhang (2020), we subjected our worked-out model to various external constraints such as those represented by timetable and station capacity restrictions, allowing for a much better estimate of the delay propagation among trains under FCFS management. Using timetable buffers and auxiliary data, we investigate possible delays accruing to trains from earlier stations, which allows us to evaluate the cumulative delay at each subsequent station after the occurrence of the initial delay. The overall in-depth examination of delay propagation mechanisms gives us not only insight into the cause of propagation but also further directs and enhances our resolution of improving the resilience and efficiency of railway operation. The principal contributions of the work rest in the following merits:

1) Considering the positional and duration characteristics of an emergency, we develop a train delay propagation algorithm under fast, FCFS management, with which one could compute delay distributions of various trains exactly. Efficiency, timetable, safety, and station capacity constraints work, in the main, to contain the algorithm proposed.

2) A necessary and sufficient condition is therewith proposed to determine the occurrence of train delays at stations preceding and following emergencies-very general and lending compactness to the procedure for one to assess train delays at the station.

3) Based on the proposed delay propagation algorithm, this study presents a theoretical analysis of train delay propagation on railway lines. It introduces evaluation indicators such as the boundaries affected by delays for trains and stations, the number of delayed trains, settling time, and cumulative delays.

The structure of this paper is organized as follows: Section 2 presents the problem description and offers the train delay propagation algorithm. Section 3 provides a detailed analysis of the impacts of delay propagation. An illustrative example of our proposed delay propagation algorithm is presented in Section 4. Finally, Section 5 concludes the study.

2 Railway traffic model

This section focuses on the propagation of train delays resulting from interval interruptions on double-track railway lines, as illustrated in Fig.1. The symbols, sets, and parameters used in this analysis are detailed in Tab.1.

2.1 Problem description

This paper examines the propagation of train delays in a scenario involving n trains operating at m stations. The train set \mathit{I} is defined as \mathit{I}=\left\{A_1,A_2,\dots ,A_n\right\}, while the station set \mathit{S} is defined as \mathit{S}=\{S-m_1,S-m_1+1,\dots , S-1,S,S+1,\dots ,S+m_2-1,S+m_2\} , where m=m_2+m_1+1. Fig.1 shows the train operation under interval interruption, where the disruption is depicted by the red line, and the arrow indicates the direction of train movements. In this figure, we can find that the interval interruption happens between stations S and S+1. Additionally, it is assumed that the initial delayed train A_1 will come to a stop at station S at time d_{A_1}(S), and its operation cannot be resumed until time d_{A_1}(S)+P. In real-world scenarios, when a disruption occurs, efforts are commonly made to ensure that subsequent trains stop at the stations. This approach is preferable to allowing trains to continue running as far as possible, potentially halting on the tracks between stations after a disruption. By stopping at stations, passenger anxiety is alleviated, as passengers generally expect that trains will stop at designated stations. Moreover, halting at a station provides greater flexibility for administrative management to implement necessary measures, such as altering the order of train departures, which can only be executed at stations.

Given that the up-link and down-link railways typically demonstrate minimal interference on double-track railway lines, this paper focuses specifically on the propagation of train delays in one direction. Considering that different scheduling strategies result in varying outcomes for delays, this study adopts the more general FCFS scheduling strategy to analyze the propagation of train delays. To enhance the realism of the delay propagation algorithm, several assumptions regarding train operating rules are proposed:

1) The trains that are not delayed will adhere to the scheduled timetable.

2) The duration time of emergencies P is sufficiently long and predetermined.

3) No train is cancelled due to the disruption on railway lines.

Definition 1. (Indicator function) The indicator function F_{\mathcal{D}}(x) of its fraction \mathcal{D} is a function such that

(1)F_{\mathcal{D}}(x)=\{\begin{array}{ll}1,& \text{if}x\in \mathcal{D},\\ 0,& \text{otherwise}.\end{array}

2.2 Train delay propagation model

The concepts of time supplement and buffer time are crucial for analyzing the propagation of train delays. As depicted in Fig.2(a), time supplement refers to the additional duration beyond the minimum operational time of trains, allowing them to maintain punctuality during emergencies within the railway system. Let R_{A_i}(S+k) represent the time supplement of train A_i between stations S+k and S+k+1, then we have

(2)R_{A_i}(S+k)=U_{A_i}(S+k)+W_{A_i}(S+k+1),

where U_{A_i}(S+k) and W_{A_i}(S+k+1) are the running-time supplement and dwelling-time supplement, respectively. The running-time supplement U_{A_i}(S+k) represents the extra time taken by trains to travel between stations S+k and S+k+1 beyond the minimum required running time, while the dwelling-time supplement W_{A_i}(S+k+1) refers to the additional time that trains spend at station S+k+1 beyond the minimum required dwelling time. Both of these supplements can be derived from the scheduled timetable; that is

(3)U_{A_i}(S+k)=a_{A_i}(S+k+1)-d_{A_i}(S+k)-r_{A_i}(S+k),

(4)W_{A_i}(S+k+1)=d_{A_i}(S+k+1)-a_{A_i}(S+k+1)-e_{A_i}(S+k+1).

In contrast to the time supplement, buffer time refers to the extra duration between two consecutive trains that exceeds the minimum headway time. As illustrated in Fig.2(b), buffer time can mitigate interference on subsequent trains in the event of delays experienced by preceding trains. Let B_{A_i}(S+k) represent the buffer time between trains A_i and A_{i+1} at station S+k. Since the headway time between trains A_i and A_{i+1} needs to exceed the minimum headway time h for safety considerations, the definition of buffer time B_{A_i}(S+k) can be given as

(5)B_{A_i}(S+k)=d_{A_{i+1}}(S+k)-d_{A_i}(S+k)-h.

According to the transportation rules, the delay propagation algorithm of trains could be described as follows:

(6){\tau }_{A_i}(S+k)=x_{A_i}(S+k)-d_{A_i}(S+k),

(7)d_{A_i}(S+k+1)-d_{A_i}(S+k)=R_{A_i}(S+k)+e_{A_i}(S+k)+r_{A_i}(S+k),

(8)d_{A_{i+1}}(S+k)-d_{A_i}(S+k)=B_{A_i}(S+k)+h,

where \mathrm{\forall }{A}_i\in \mathit{I} and S+k\in \mathit{S}. The definition of train delays is provided in Eq. (6), representing the discrepancy between the actual departure time and the scheduled departure time. Given the absence of departure time information for trains at the terminal station, we quantify train delays based on their arrival time at the terminal station such that {\tau }_{A_i}\left(S+m_2\right)=y_{A_i}\left(S+m_2\right)-a_{A_i}\left(S+m_2\right) . Eq. (7) shows the time interval between the departure of train A_i from two consecutive stations S+k and S+k+1. This interval comprises the timetable supplement, the minimum dwelling time, and the minimum running time. In Eq. (8), the scheduled headway is shown to consist of the timetable buffer and minimum headway. As illustrated in Fig.2(b), the buffer time serves as an additional temporal allowance, mitigating the impact of delays on subsequent trains. Furthermore, trains on double-track railway lines must satisfy several additional constraints given by

(9)x_{A_i}(S+k)\ge d_{A_i}(S+k),

(10)x_{A_{i+1}}(S+k)\ge h+x_{A_i}(S+k),

where \mathrm{\forall }{A}_i\in \mathit{I} and S+k\in \mathit{S}. The Constraints (9) guarantee that the actual departure time must not precede the scheduled departure time, while Constraints (10) show that trains A_i and A_{i+1} must maintain a minimum headway. Furthermore, trains arriving at or passing through the station will be allocated to specific tracks, with each track accommodating only one train at a time. Therefore, the station capacity constraints are formulated as follows:

(11)\begin{array}{l}{\displaystyle \frac{1}{2}}\sum _{A_i\in I}(\mathrm{s}\mathrm{g}\mathrm{n}(x_{A_q}(S+k)-y_{A_i}(S+k))-\\ \mathrm{s}\mathrm{g}\mathrm{n}(x_{A_q}(S+k)-x_{A_i}(S+k)))\le C(S+k)-1,\end{array}

where \mathrm{\forall }{A}_i\in \mathit{I} and S+k\in \mathit{S}, sgn(·) is the sign function, i.e.,

The left-hand side of Constraints (11) represents the total number of trains that stop at station S+k upon the arrival of train A_q, while the right-hand side indicates the presence of at least one vacant station track for trains to occupy. In general, there are sufficient capacity resources at both the origin and terminal stations. Hence, we suggest that the train capacities C\left(S-m_1\right) and C\left(S+m_2\right) are sufficiently large.

During train operations, overtaking may occur at a station, resulting in a change in the train departure order. To investigate the propagation of delays among trains, the departure order at each station and their adjacency relations are critical. In this context, it is useful to maintain the train sequence \left\{A_1,A_2,\dots ,A_n\right\} at each station because the departure order and their adjacency relations are manifest from this sequence. To specify the delay of a particular train, say, “G123” at each station, we need to be careful. In fact, “G123” has been relabelled as A_{{\sigma }_{S+k}}(G123) at station S+k where {\sigma }_{S+k}(\cdot ) is a pre-determined function to assign a label to each train according to its departure order at station.

2.3 Train delay determination

To evaluate train delays, we employ a series of mathematical expressions derived from an analysis of operational data. The aim is to provide an objective assessment of whether a train arrives at its destination punctually and to quantify any resultant delays. For the sake of writing convenience, we adopt the convention that {\sum }_m^n(\cdot )\equiv 0 when m>n in this paper.

Theorem 1. For -m_1⩽k⩽m_2, k\in \mathbb{Z}, train A_q\in \mathit{I} will experience delays at station S+k in accordance with constraints (9)―(11), if and only if

(12)P-{\sum }_{i=1}^{q-1}{B}_{A_i}(S+k)+{\sum }_{i=k}^{-1}{R}_{A_q}(S+i)+{\mathrm{\Theta }}_{\alpha }>0,

when -m_1⩽k⩽0,

(13)P-{\sum }_{i=1}^{q-1}{B}_{A_i}(S+k)-{\sum }_{i=0}^{k-1}{R}_{A_q}(S+i)+{\mathrm{\Theta }}_{\beta }>0,

when . Here

\begin{array}{rl}{\mathrm{\Theta }}_{\alpha }=& {\displaystyle \sum _{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\displaystyle \sum _{j=i}^{k-1}{u}_{A_q}(S+j)-}}\\ & {\displaystyle \sum _{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\displaystyle \sum _{j=i+1}^{0}C(S+j)h+{\displaystyle \sum _{i=k}^{-1}{u}_{A_q}(S+i),}}}\end{array}

\begin{array}{rl}{\mathrm{\Theta }}_{\beta }=& {\displaystyle \sum _{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\displaystyle \sum _{j=i}^{k-1}{u}_{A_q}(S+j)-}}\\ & {\displaystyle \sum _{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\displaystyle \sum _{j=i+1}^{0}C(S+j)h-{\displaystyle \sum _{i=0}^{k-1}{u}_{A_q}(S+i),}}}\end{array}

u_{A_q}(S+i)=r_{A_q}(S+i)+e_{A_q}(S+i+1), F_{\mathcal{D}}(q,i) is an indicator function such that .

Proof：We first prove the sufficiency of these conditions. When -m_1⩽k⩽0, we have P=x_{A_1}(S)-d_{A_1}(S) and d_{A_1}(S)=d_{A_q}(S+k)-{\sum }_{i=1}^{q-1}(B_{A_i}(S+k)+h)+{\sum }_{i=k}^{-1}(R_{A_q}(S+i)+u_{A_q}(S+i)) according to the definition of time supplement and buffer time, where u_{A_q}(S+i)= r_{A_q}(S+i)+e_{A_q}(S+i+1). Then inequality (12) can be rewritten as x_{A_1}(S)+(q-1-{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i+1}^{0}C(S+j)) h+{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j)-d_{A_q}(S+k)=x_{A_q}(S+k)- d_{A_q}(S+k)={\tau }_{A_q}(S+k)>0. Hence trainA_q scheduled to depart from station S+k will experience a delay.

Similarly, when , we can obtain that P=x_{A_1}(S)-d_{A_1}(S) and d_{A_1}(S)=d_{A_q}(S+k)+{\sum }_{i=1}^{q-1}(B_{A_i} (S+k)+h)+{\sum }_{i=0}^{k-1}(R_{A_q}(S+i)+u_{A_q}(S+i)). According to inequality (13), we have x_{A_1}(S)+(q-1-{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i) {\sum }_{j=i+1}^{0}C(S+j))h+{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j)-d_{A_q}(S+k)= x_{A_q}(S+k)-d_{A_q}(S+k)={\tau }_{A_q}(S+k)>0 Hence train A_q scheduled to depart from station S+k will experience a delay.

Then we prove the necessity of these conditions. According to Eq. (6), it can be observed that {\tau }_{A_q}(S+k)=x_{A_q}(S+k)-d_{A_q}(S+k), where d_{A_q}(S+k) is determined by the scheduled train timetable, and the value of x_{A_q}(S+k) could be obtained in accordance with the FCFS management. For the convenience of discussion, we also distinguish two cases: -m_1⩽k⩽0 and .

In the case of -m_1⩽k⩽0, based on the definitions of time supplement and buffer time, we obtain

(14)\begin{array}{rl}{d}_{A_q}(S+k)=& d_{A_1}(S)+{\sum }_{i=1}^{q-1}(B_{A_i}(S+k)+h)-\\ & {\sum }_{i=k}^{-1}(R_{A_q}(S+i)+u_{A_q}(S+i)).\end{array}

Under FCFS management, we have

(15)\begin{array}{c}{x}_{A_q}(S+k)=d_{A_1}(S)+P+(q-1-{\sum }_{i=-m_1}^0{F}_D(q,i)\\ {\sum }_{j=i+1}^{0}C(S+j))h+{\sum }_{i=-m_1}^0{F}_D(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j),\end{array}

where the first term d_{A_1}(S)+P denotes the moment when trains resume their operations, the second term (q-1-{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i+1}^{0}C(S+j))h guarantees the minimum headway between adjacent trains, and the third term {\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j) denotes the minimum operation time from the initial delayed station of train A_q to station S+k. Since {\tau }_{A_q}(S+k)=x_{A_q}(S+k)- d_{A_q}(S+k)>0, by combining Eqs. (14)―(15), we can obtain x_{A_q}(S+k)-d_{A_q}(S+k)=P-{\sum }_{i=1}^{q-1}{B}_{A_i}(S+k)+{\sum }_{i=k}^{-1} R_{A_q}(S+i)+{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j)-{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i+1}^{0}C(S+j)h+{\sum }_{i=k}^{-1}{u}_{A_q}(S+i)>0. Hence Conditions (12) hold.

Similarly, in the case of , we can obtain

(16)\begin{array}{rl}{d}_{A_q}(S+k)=& d_{A_1}(S)+{\sum }_{i=1}^{q-1}(B_{A_i}(S+k)+h)+\\ & {\sum }_{i=0}^{k-1}(R_{A_q}(S+i)+u_{A_q}(S+i)).\end{array}

Under FCFS management, we have

(17)\begin{array}{c}{x}_{A_q}(S+k)=d_{A_1}(S)+P+(q-1-{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i)\\ {\sum }_{j=i+1}^{0}C(S+j))h+{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j).\end{array}

By combining Eqs. (16)―(17), we can obtain x_{A_q}(S+k)-d_{A_q}(S+k)=P-{\sum }_{i=1}^{q-1}{B}_{A_i}(S+k)-{\sum }_{i=0}^{k-1}{R}_{A_q}(S+i)+ {\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i}^{k-1}{u}_{A_q}(S+j)-{\sum }_{i=-m_1}^0{F}_{\mathcal{D}}(q,i){\sum }_{j=i+1}^{0}C(S+j)h- {\sum }_{i=0}^{k-1}{u}_{A_q}(S+i)>0. Hence Conditions (13) hold. The proof is completed.

illustrates the computational procedure for train delay propagation under FCFS management. Based on Theorem 1, we can forecast the occurrence of train delays at stations during emergencies, as depicted in Fig.1, which could be significantly beneficial for dispatchers in terms of rerouting and rescheduling trains.

3 Analysis of the propagation effects caused by train delays

The objective of this section is to perform a comprehensive analysis of the impact of train delay propagation, including the affected boundaries of trains and stations, the number of delayed trains, settling time, and cumulative delays.

3.1 Boundary values of trains and stations

The boundary values of trains and stations are essential for evaluating the consequences of train delays, providing crucial insights into the overall efficiency and reliability of the transportation system. Initially, let us discuss the boundary value of trains. It is easy to see that the first delayed train is train A_1. According to the train delay propagation model, we can obtain the last delayed train A_1, which is given by

(18)l=sup\{i\mid \sum _{i=-m_1}^{m_2}{\tau }_{A_i}(S+k)>0,1\le i\le n\},

where {\tau }_{A_i}(S+k) can be obtained by Eqs. (6)–(8). For a determined station S+k, its boundary values of trains A_{p(k)} and A_{l(k)} are given as

(19)p(k)=inf\left\{i\mid {\tau }_{A_i}(S+k)>0,1\le i\le n\right\},

(20)l(k)=sup\left\{i\mid {\tau }_{A_i}(S+k)>0,1\le i\le n\right\},

where p(k)\le l(k). The subsequent step involves determining the boundary values of stations S+k_f and S+k_l, where k_f\le 0\le k_l. Then we can calculate these boundary value according to the proposed train delay propagation model, which are given by

(21)k_f=inf\{k\mid \sum _{i=1}^n{\tau }_{A_i}(S+k)>0,-m_1\le k\le m_2\},

(22)k_t=sup\{k\mid \sum _{i=1}^n{\tau }_{A_i}(S+k)>0,-m_1\le k\le m_2\}.

In addition, for a determined train A_q. We can calculate its boundary values of stations S+k_{A_q,f} and S+k_{A_q,l}, which are given by

(23)k_{A_q,f}=inf\{k\mid {\tau }_{A_q}(S+k)>0,-m_1\le k\le m_2\},

(24)k_{A_q,l}=sup\{k\mid {\tau }_{A_q}(S+k)>0,-m_1\le k\le m_2\},

where k_{A_q,f}\le S+k_{A_q,l}. An example of the train delay region is illustrated in Fig.3. In this figure, the red dashed line represents the estimated boundary of train delays, which can be determined by employing Eqs. (18)–(24). Due to the heterogeneous train flow and the necessity of satisfying the constraints (9)–(11) during train operation, it is necessary to calculate p(k), l(k), k_{A_q,f} and k_{A_q,l} separately in order to determine the delay region.

3.2 Number of delayed trains

By understanding the number of delayed trains at each station, transportation authorities can make informed decisions regarding resource allocation, scheduling adjustments, and infrastructure improvements. This information is essential for ensuring efficient operations and minimizing disruptions in train services. According to Eqs. (18)–(24), the number of delayed trains at each station can be given as

(25)N_d=\sum _{k=k_f}^{k_l}\sum _{i=1}^l\mathrm{sign}\left({\tau }_{A_i}(S+k)\right).

In addition, for a determined station S+k, the number of delayed trains can be given as:

(26)N_d(S+k)=\sum _{i=1}^l\mathrm{sign}\left({\tau }_{A_i}(S+k)\right).

3.3 Settling time

The settling time refers to the duration between the moment when the first train halts due to disruptions until all trains return to their scheduled departure times. This metric is vital for evaluating the robustness of the timetable (Salido et al., 2008). For a determined P, the settling time can be given as

(27)\begin{array}{rl}{\mathrm{\Omega }}_p=& \underset{{\tau }_{A_q}(S+k)>0}{max}P+\sum _{i=-m_1}^0{F}_D(q,i)\sum _{j=i}^{k-1}{u}_{A_q}(S+j)+\\ & (q-1-\sum _{i=-m_1}^0{F}_D(q,i)\sum _{j=i+1}^{0}C(S+j))h,\end{array}

where \mathrm{\forall }{A}_q\in I and S+k\in S. The robustness of the train timetable increases when the settling time {\mathrm{\Omega }}_p is decreased while keeping P fixed.

3.4 Cumulative delay

The cumulative delay is a crucial metric for assessing the overall efficiency and reliability of train services. It offers a detailed measure of the total time lost due to delays at each station along the train route. In this paper, the cumulative delay is defined as the sum of individual train delays at all stations, as follows:

(28)\Gamma =\sum _{k=k_f}^{k_l}\sum _{i=1}^l{\tau }_{A_i}(S+k).

In addition, for a determined station S+k, the cumulative delay of trains at the station can be given as

(29)\Gamma (S+k)=\sum _{i=1}^l{\tau }_{A_i}(S+k).

Similarly, we can obtain the cumulative delay of train A_i at all stations if no overtaking occurs such that

(30){\Gamma }_{A_i}=\sum _{k=k_f}^{k_l}{\tau }_{A_i}(S+k).

The flowchart presented in Fig.4 provides a comprehensive overview of the train delay propagation calculation and analysis process.

4 Simulation

In this section, numerical experiments are conducted to validate the effectiveness of the proposed delay propagation algorithm, utilizing both a virtual railway line and a realistic railway line. These experiments offer empirical evidence for the reliability of the delay propagation model across different scenarios.

4.1 Delay propagation of trains on a virtual railway line

The virtual railway line illustrated in Fig.5 consists of a total of 10 stations and 9 segments. The solid red line in the figure indicates the locations of reported emergencies. The scheduled timetable for trains operating from station S-4 to station S+5 is outlined in Tab.2. For the purposes of this analysis, we assume that emergencies occur at 10:08. Consequently, train A_1 is identified as the first train to experience delays and will not be able to resume its operations until 10:08 +P. To effectively assess the propagation of train delays along the railway line, Tab.3 presents the minimum running times required for trains to traverse each segment. Furthermore, Tab.4 details the capacity of each station on the line. We assume a minimum dwelling time of 2 minutes for trains at any given station, along with a minimum headway time of 3 minutes between consecutive trains. Based on the provided information, we can calculate the time supplement and buffer time using Eqs. (2)–(5), which are essential for understanding and managing the dynamics of delay propagation within the railway system.

According to Theorem 1, the determination of train delays at each station is dependent on the duration of emergencies P. Once P is established, we can outline the delay region by calculating the boundary values for trains and stations using Eqs. (18)–(24), as shown in Fig.6. In this figure, the red dashed line represents the boundaries of the delay region. Within this area, the horizontal and vertical coordinates of the nodes indicate the specific instances at which train A_i encounters delays at station S+k. The color coding of each node reflects the severity of the train delay at particular stations. A comparative analysis of Fig.6(a) and 6(b) indicates that the lower left corner of the delay region remains unoccupied. This absence occurs because a train cannot experience a delay at a station it has already passed, regardless of the value of the emergency duration P. Additionally, these figures illustrate that the size of the delay region increases proportionally with the duration of emergencies P, ultimately reaching its maximum area when the duration is P=120 min. This analysis highlights the relationship between emergency duration and the propagation of train delays, providing valuable insights into the operational dynamics of the railway system under emergency conditions.

Using Eqs. (27)–(28), we can identify the variation of cumulative delays and settling time in relation to the duration of emergencies P, as illustrated in Fig.7. This figure demonstrates that cumulative delays increase according to a power-like function as P increases. In contrast, the settling time displays a segmented growth pattern, reflecting limitations imposed by station capacity. Furthermore, it is crucial to emphasize the importance of obtaining the distribution of cumulative delays, as shown in Fig.7.

Utilizing Eqs. (29)–(30), we can derive the distribution of cumulative delays for trains at each station, depicted in Fig.8(a), and for each train across various stations, depicted in Fig.8(b). In Fig.8(a) and Fig.8(b), the color gradient, ranging from blue to yellow, corresponds to the magnitude of delay time, with blue indicating lower delays and yellow indicating higher delays. A general trend emerges, illustrating that cumulative delays increase along with the duration of emergencies.

4.2 Delay propagation of trains on a real high-speed railway line

In this subsection, we examine the Beijing–Shanghai high-speed railway line as a real-world example to demonstrate the effectiveness of the proposed delay propagation algorithm. As illustrated in Fig.9, this railway line comprises a total of 23 stations and 22 segments, accommodating over 100 high-speed trains daily (Li et al., 2014). To narrow our analysis, we focus on trains operating between 8:00 and 10:00, as depicted in Fig.10.

Fig.11 shows the distribution of cumulative delays at different emergency locations. It indicates that cumulative delays increase as the station's proximity to the emergency site decreases. Comparing Fig.11(a)–11(d), train delays are observed to spread more effectively to subsequent stations than to preceding ones. Fig.12 illustrates how cumulative delays vary with parameter changes at different emergency locations. Emergencies in the Dezhoudong–Jinanxi and Ta’an–Qufudong segments have a significantly greater effect on cumulative delays than those in the Tengzhou–Zaozhuang and Bengbunan–Dingyuan segments. This analysis improves our understanding of railway system performance and helps identify train flow bottlenecks, guiding targeted improvements in scheduling and management. By examining delay propagation across segments and stations, more effective strategies can be developed to reduce delays and optimize high-speed railway operations

5 Conclusions

This paper introduces an algorithm created to model the propagation of train delays along double-track railway lines in a FCFS environment. The paper begins by describing the rules of delay propagation and operational restraints on the train schedules. On the basis of these premises, we construct a necessary and sufficient condition to determine when train delays happen among different stations. Also, the paper presents significant measures of delay propagation involving limit values concerning trains and trains at stations, number of delayed trains, settling times, and cumulative delays. An analysis of these measures would give practical insights into how delays spread over the railway line. The paper concludes with numerical experiments that exhibit effectiveness of the algorithm in delay propagation. The findings from the research serve to advance more resilient designs of timetables that can accommodate perturbations resulting from the unforeseen events. The algorithm proposed can later be made extensive in future work in assessing some problems where more than one disruption occurs.

Furthermore, since in reality the railway system constitutes multiple intersecting lines, a feasible way to approach train delay propagation in the railway network would be to extend this paper’s proposed framework. This can be actualized by studying delay propagation along the individual lines while treating the transfer stations as boundaries. Delay propagation along each line in a repeated manner can be computed, and delays can be integrated at the transfer stations, achieving a network-wide prediction in delay propagation.

References

[1] Carey M, (1999). Ex ante heuristic measures of schedule reliability. Transportation Research Part B: Methodological, 33( 7): 473–494

[2] Carey M, Kwieciński A, (1995). Properties of expected costs and performance measures in stochastic models of scheduled transport. European Journal of Operational Research, 83( 1): 182–199

[3] Frank O, (1966). Two-way traffic on a single line of railway. Operations Research, 14( 5): 801–811

[4] Goverde R M P, (2007). Railway timetable stability analysis using max-plus system theory. Transportation Research Part B: Methodological, 41( 2): 179–201

[5] Goverde R M P, (2010). A delay propagation algorithm for large-scale railway traffic networks. Transportation Research Part C: Emerging Technologies, 18( 3): 269–287

[6] HansenI AGoverdeR M Pvan der MeerD J (2010). Online train delay recognition and running time prediction. In: Proceedings of 13th International IEEE Conference on Intelligent Transportation Systems, IEEE, 1783–1788

[7] Harrod S, Cerreto F, Nielsen O A, (2019). A closed form railway line delay propagation model. Transportation Research Part C: Emerging Technologies, 102: 189–209

[8] Higgins A J, Kozan E, (1998). Modeling train delays in urban networks. Transportation Science, 32( 4): 346–357

[9] Huang P, Spanninger T, Corman F, (2022). Enhancing the understanding of train delays with delay evolution pattern discovery: A clustering and bayesian network approach. IEEE Transactions on Intelligent Transportation Systems, 23( 9): 15367–15381

[10] Jovanović P, Kecman P, Bojović N, Mandić D, (2017). Optimal allocation of buffer times to increase train schedule robustness. European Journal of Operational Research, 256( 1): 44–54

[11] Khan A, Ma H, Chung S, Wen X, (2021). Hierarchical integrated machine learning model for predicting flight departure delays and duration in series. Transportation Research Part C: Emerging Technologies, 129: 103225

[12] Li X, Shou B, Ralescu D, (2014). Train rescheduling with stochastic recovery time: A new track-backup approach. IEEE Transactions on Systems, Man, and Cybernetics. Systems, 44( 9): 1216–1233

[13] Li Z, Wen C, Hu R, Xu C, Huang P, Jiang X, (2021). Near-term train delay prediction in the dutch railways network. International Journal of Rail Transportation, 9( 6): 520–539

[14] Lian W, Wu X, Zhou M, Lü J, Dong H, (2024). Bi-directional delay propagation analysis and modeling for high-speed railway networks under disturbance. IEEE Transactions on Computational Social Systems, 11( 3): 3207–3217

[15] Liu Q, Wang S, Li Z, Li L, Zhang J, Wen C, (2023a). Prediction of high-speed train delay propagation based on causal text information. Railway Engineering Science, 31( 1): 89–106

[16] Liu X, Zhou M, Dong H, Wu X, Li Y, Wang F, (2023b). Admm-based joint rescheduling method for high-speed railway timetabling and platforming in case of uncertain perturbation. Transportation Research Part C: Emerging Technologies, 152: 104150

[17] Lu C, Pan Y, Cai C, (2021). Reliability guarantee framework for the Sichuan–Tibet railway. Frontiers of Engineering Management, 8( 4): 480–491

[18] Meester L E, Muns S, (2007). Stochastic delay propagation in railway networks and phase-type distributions. Transportation Research Part B: Methodological, 41( 2): 218–230

[19] Petersen E R, (1974). Over-the-road transit time for a single track railway. Transportation Science, 8( 1): 65–74

[20] Şahin İ, (2017). Markov chain model for delay distribution in train schedules: Assessing the effectiveness of time allowances. Journal of Rail Transport Planning & Management, 7( 3): 101–113

[21] SalidoM ABarberFIngolottiL (2008). Robustness in railway transportation scheduling. In: Proceedings of 7th World Congress on Intelligent Control and Automation, IEEE, 2880–2885

[22] Spanninger T, Trivella A, Büchel B, Corman F, (2022). A review of train delay prediction approaches. Journal of Rail Transport Planning & Management, 22: 100312

[23] Tiong K, Ma Z, Palmqvist C, (2023). A review of data-driven approaches to predict train delays. Transportation Research Part C: Emerging Technologies, 148: 104027

[24] Wendler E, (2007). The scheduled waiting time on railway lines. Transportation Research Part B: Methodological, 41( 2): 148–158

[25] Ye Y, Zhang J, (2020). Accident-oriented delay propagation in high-speed railway network. Journal of Transportation Engineering. Part A: Systems, 146( 4): 04020011

[26] Zhang C, Gao Y, Cacchiani V, Yang L, Gao Z, (2023a). Train rescheduling for large-scale disruptions in a large-scale railway network. Transportation Research Part B: Methodological, 174: 102786

[27] Zhang P, Yang X, Wu J, Sun H, Wei Y, Gao Z, (2023b). Coupling analysis of passenger and train flows for a large-scale urban rail transit system. Frontiers of Engineering Management, 10( 2): 250–261

RIGHTS & PERMISSIONS

Higher Education Press