# An Optimization Method for Operation Adjustment of High-Speed Delayed Trains

Authors: Xiaojuan Li; Yueying Huo; Zhenying Yan; Baoming Han
Journal: Discrete Dynamics in Nature and Society
 (2019)

---

## Abstract

Train delays have a great impact on the schedule of high-speed railways including overall efficiency and the quality of the travel service of the passengers. Therefore, the development of an approach to recover a schedule via timely and rapid operation adjustments must be investigated. In this paper, a complete final real-time adjustment scheme is proposed for the train dispatcher of a railway enterprise for delayed trains. A train operation process model based on the Max-Plus algebra method is proposed. Six operation adjustment strategies are analyzed including section acceleration, operation based on the original timetable, dwell time reduction, increase in overtaking, reduction in overtaking, and train postponement. An approximate model is then built based on the minimum number of delayed trains considering the constraints of the adjustment strategies and the feasible adjusted schemes can be quickly obtained without any record specific time data and constraints. The set of feasible solutions of the approximate model is then regarded as the importation of the second model. In addition, the second model is an optimization model for operation adjustment with the least average delay time of each train at each station by updating the state matrixes of the train operation process model. The algorithms are designed for these models, and this approach can reduce the computation time. Finally, the timetable of the Beijing-Shanghai high-speed railway is considered as the actual case for analysis. Thus, the method was proven feasible for operation adjustment of delayed trains.


---

## Body

## 1. Introduction

A high-speed railway is characterized by several parameters such as large density and high speed. Moreover, the operation of high-speed trains is sensitive to traffic delay. As such, efficient and on-time operation of high-speed trains is very important given the emphasis of passengers on on-time service. Therefore, real-time operation adjustment for delayed trains should be investigated. Theoretical results can thus be provided for studies on train schedules, timetable evaluation, and passenger service level.The train delay propagation methods have been studied for a long time. The simulation model and the analysis model of train delay were initially proposed by Pertersen [1] and Greenberg [2]. Then, many subsequent studies applied the Max-Plus algebra method to railway systems. An evaluation method of timetable stability based on this approach was proposed by Goverde [3, 4]. The train delay propagation model and algorithm of the periodic timetable based on the Max-Plus algebra method was studied also by Goverde [5, 6]. The author investigated the train delay propagation process using a time-event timetable and analyzed the delay propagation behavior of the trains based on the reliability and stability of the timetable. In addition, different types of train delays were discussed including primary and secondary delay, structural delay, periodic delay, and delay explosion. Combined with the Max-Plus algebraic method and the model prediction control method, the dynamic control of the railway operation system was studied by Schutter et al. [7, 8]. Subsequently, the Max-Plus algebra method was extended to a new form by Hiroyukl et al. [9] in which the model can consider the capacity constraints and change of the train sequence. This method was determined to be more suitable for scheduling problems. An activity diagram was used to express train delay propagation, and the mathematical process of graph traversal was established by Büker et al. [10]. Based on these studies, a train operation process model using the Max-Plus algebra theory to record the train operation status of different delay adjustment schemes was built by the authors.The operation adjustment method for delayed trains has been investigated in numerous studies. The method for operation adjustment of delayed trains is usually studied using an optimization, simulation, or intelligent algorithm method. It is necessary to obtain the optimal adjustment scheme based on a specific target for a new timetable. For this reason, two main aspects of these studies have been addressed: (1) adjustment strategies are proposed and (2) the optimal targets of the adjustment method are different.Regarding the first aspect, Qian et al. [11] established an approximate set model for train operation adjustment and a simple algorithm based on adjustment rules was proposed for the model. Li et al. [12] studied the train operation adjustment method using the Switching-Max-Plus algebra and order optimization theory. Three basic adjustment strategies: increasing overtaking, increasing the stop and overtaking, and train postponing by minimum headway, were proposed. In addition, an optimization model for the delayed train operation adjustment by minimizing the total train delay time was established. Zhan et al. [13] proposed a train operation adjustment method using the strategy of delayed waiting of trains in the station until the end of the delay interruption. Zhou et al. [14] proposed an algorithm for timetable adjustment that combined moving operation times, exchanging operation order, and changing stop plan, based on the choice strategies of the conflicts. Ghaemi et al. [15] investigated the impact of the disruption length estimates on the rescheduling strategy and the resulting passenger delays, and this research presented a framework consisting of three models: a disruption length model, short-turning model, and passenger assignment model.For the second aspect, the three main optimal targets in these studies are as follows.(1)Minimum Delay Time of Passengers. Espinosa-Aranda et al. [16] proposed a new weighted train delay adjustment method based on demand using the alternative graph. The method considered the satisfaction of passenger services and was expressed by minimizing the average delay time of all passengers at the destination station. Corman et al. [17] considered the efficiency of train operation adjustment and the service quality of passengers comprehensively. An optimization model that minimized the total time of all passengers in the travel system was established and the model was solved using a fast heuristic algorithm.(2)Minimum Delay Trains or Delay Time of the Trains. Zhan et al. [13] established a mixed integer programming model for minimizing the total weighted train delay and the number of canceled trains. It was necessary for this model to satisfy the constraints such as the headway time and station capacity. In the study by Gavone et al., 2015, a train operation adjustment model based on a hybrid integer linear programming method was established. The target of this model was the comprehensive optimization of the minimum delay time and maximum robustness of the timetable. Heuristic algorithms used to identify and resolve operational conflicts were studied to solve the model. Luca Oneto et al. [18] purposed a data-driven Train Delay Prediction System (TDPS) for large-scale railway networks that exploited the most recent big data technologies including learning algorithms and statistical tools. In particular, they proposed a fast learning algorithm for Shallow and Deep Extreme Learning Machines that fully exploited the recent in-memory large-scale data processing technologies for predicting train delays. Zhou et al. [14] proposed an optimization model of train timetabling for high-speed rail networks, with the aim of minimizing the total travel time of trains considering the time interval constraints of trains operating on both same and various rail lines. In addition, a linear programming model was constructed to optimize train arrival and departure times with a fixed order based on the extension of a digraph of the train timetable from the rail line to the rail network.(3) Some relative contents of the train delay such as the railway capacity and the buffer time of the timetable were studied. In [19], the timetable was adjusted in real time. It was determined that the possibility of delay in the timetable, the sensitivity of the delay, and the capability of delay recovery should be analyzed before evaluation of the timetable stability. In [20], using the method of microscopic network simulation, a method which could improve capacity, reduce delay, and increase the stability of the timetable was proposed. A method for improving train punctuality rate was investigated by Andrea et al. [21]. This method could flexibly adjust the timetable without reducing the railway capacity. The improvement in the punctuality rate can also indirectly improve the railway capacity. It is necessary to increase the buffer time of the trains to increase their punctuality rate; however, this results in capacity reduction. Therefore, a model and algorithm were proposed to solve the train operation conflict using flexible adjustment of the train operation without reducing the capacity. Because of delay adjustment, the buffer time has an effect on the railway capacity. The effect of the buffer time of the timetable on the operation adjustment of delayed trains was consequently analyzed in the investigation.When the trains are delayed for a long time, different trains are adjusted at different stations, which cause a continuous change of the timetable. A large-scale solving scheme for the adjustment will therefore be produced. The algorithm is complex and has a low efficiency, which cannot meet the needs of real-time adjustment. In this investigation, the method of ordinal optimization for the operation adjustment of the delayed train is used. Xie et al. [22] explained order optimization theory, which has two critical ideas: target softening and order comparison. Target softening involves relaxing the goal of the optimal solution to obtain an appropriate solution with high probability. Order comparison entails determining the order relationship of the solution other than calculating the actual value. On the basis of building the train operation adjustment model of complex railway networks and taking the shortest train travel time as the objective function for optimization, a fast preliminary evaluation calculation is performed and the theory and method of ordinal optimization were applied to solve train operation adjustment as a new method [23]. Li et al. [12] also studied the train operation adjustment method for delayed trains using the order optimization theory by building two-stage models.Apparently, “order” is much easier to be compared than “value.” A simple rough model is not sufficient to accurately determine the difference in performance among different solutions, but it can clearly show the difference between the solutions. An approximate model is usually sufficient because it has a significant advantage in terms of computation time compared to the exact model. In addition, the set of solutions of the approximate model is the input parameters of the exact model.This report analyzes the delay time of each train at each station to decrease the impact on delays, and it is structured as follows. Section2 presents the methodology used in the investigation and outlines the specific details of the approach. Section 3 presents the operation process model based on the Max-Plus algebra method. The delay adjustment strategies and the adjustment model and algorithm are considered in Section 4. Section 5 outlines the case study, along with the analysis of the effect of the buffer time for operation adjustment. Section 6 summarizes the main conclusions.


## 2. Materials and Method

As shown in Figure1, our approach uses a timetable as the basic input data. The arrival time of each train and the sequence of the trains at each station are represented by the train operation process model based on the Max-Plus algebra method in Section 3. The train operation process model can present two sets of important information. One is the arrival time of each train at each station and the other is the operation sequence of the trains at each station. The model can record different train operation status.Figure 1
The methodology structure of the paper.After adding the train delays, the first station affected by the delay is selected. Then the delayed trains are selected in order and adjusted using the alternative adjustment strategies. Six alternative adjustment strategies are utilized including the acceleration in section, operation based on the timetable, dwell time reduction, increase in overtaking, and reduction in overtaking, including train postponement with the minimum headway in Section4.1. For each delayed train, one or more adjustment strategies can be selected under the condition that the constraints of these strategies are satisfied. A new adjustment scheme can be obtained for any adjustment strategy of each delayed train at each station. Then the next delayed train is selected for adjustment based on the current adjustment scheme until the next train has no delay. Accordingly, a large number of schemes can be obtained.Based on the method of ordinal optimization, an optimal method is proposed in Sections4.2 and 4.3. Two models are built. One of them is the approximate model, which has simple target values and constraints. Good-enough solutions based on the approximate model can be quickly obtained.The good-enough solutions are the feasible adjustment schemes based on the target value (the minimal number of delayed trains) and the constraints of the adjustment strategies. The solution of the approximate model is not just one solution scheme, but a set of adjustment schemes. These good-enough solutions are calculated using the second model. The second model is the accurate model that has the comprehensive constraints and target values of the total minimum delayed time for all trains. In the second model, only the delayed time of the trains needs to be calculated. It is not necessary to choose the adjustment strategy again.An optimal solution based on the accurate model is the final operation adjustment scheme of the delayed trains.The main parameters are defined as shown in Table1, and the operation time is defined as the sum of the total running time, the dwell time, and the additional time of the trains for a section or a station.Table 1
Variables.
Variables Corresponding meaning S = s i ∣ i = 1,2 , … , m The station set,m is the number of the stations.  L = l j ∣ j = 1,2 , … , n The train set,n is the number of the trains.  t x , s i a , l j The arrival time of trainlj at station si after adjustment.  t u , s i a , l j The arrival time of trainlj at station si before delay.  t x , s i d , l j The departure time of trainlj at station si after adjustment.  t u , s i d , l j The departure time of trainlj at station si before delay.  t s i , s i + 1 m i n , l j The minimum operation time of trainlj between stations si and si+1.  t s i , s i + 1 d e l a y , l j The delay time of trainlj between stations si and si+1 before adjustment.  τ s i a The minimum arrival headway at stationsi.  τ s i d The minimum departure headway at stationsi.  t s i m i n , l j The minimum stop time of trainlj at station si.  t s i m a x , l j The maximum stop time of trainlj at station si.  t s i , s i + 1 a c c , l j The maximum acceleration time of trainlj between station si and station si+1.  t s i , s i + 1 λ , l j The adjustment time of trainlj between station si and station si+1.  t s i λ , l j The adjustment time of trainlj at station si.  A q × ( m × n q ) = a i j The state matrix records the operation time of the trains with different adjustment schemes.  B q × ( m × n q ) = b q i j The state matrix records the departure sequence of the trains at each station.  q The number of sections.  n q The number of sections.  n q , l The number of trains in the sectionq.  y j → The Max-Plus algebra model of trainlj operation process.  η l h s i Binary variable,ηlhsi=1 if train lj is overtaken by train lh at the station si; otherwise, the value is zero.  Θ = θ The set of good-enough solutions that represent the input parameter for Model II.  ξ l j θ Binary variable.ξljθ=1 means that train lj in Scheme #θ had been delayed for at least one station. Otherwise, ξljθ=0 means that train lj in Scheme #θ had no delay at any station.  J The minimum average delay time of each trainlj at each station si.  t q b,tqe The beginning time and the ending time of the effective time period in sectionq of the operation adjustment.


## 3. Train Operation Process Model Based on Max-Plus Algebra Method

The Max-Plus algebra method (Max-Plus) can be defined as follows, assumingε=-∞, where R is the set of whole real numbers. Setting Rmax=R∪ε and for any two numbers a,b∈Rmax, we have a⊕b=max⁡a,b, a⊗b=a+b, D=Rmax,⊕,⊗. Therefore,D is the maximum algebra in which ⊕ and ⊗ are the addition and multiplication on the maximum algebra, respectively, and ε and 0 are the units of addition and multiplication, respectively.Based on the Max-Plus algebra method, the train operation process model of a high-speed railway can be built based on Eq. (1). (1)tx,sia,lj=tx,si-1a,lj⊗tu,sid,lj-tu,si-1a,lj+tsi-1,siλ,lj⊗tu,si-1d,lj-tu,si-1a,lj+tsi-1λ,lj⊕tx,sia,lj-1⊗τsia⊕tu,sia,ljThe elements in matrixesA and B can be described as Eqs. (2)~(5). When the number of trains changes, the state matrices also change. The state matrix A can express the arrival time of the trains based on the adjustment time for different adjustment strategies. When different adjustment strategies are selected, the elements of the state matrixA are also changed. When the arrival sequence of the trains at each station changes, the elements of the state matrixB change. Based on the state matrixesA andB, a new timetable can be calculated.(2)Aq×m×nq=aij∣1≤q≤nq,1≤i≤m,1≤j≤nq,l(3)aij=tu,sid,lj-tu,si-1a,lj+tsi-1,siλ,lj+tu,si-1d,lj-tu,si-1a,lj+tsi-1λ,lj(4)Bq×m×nq=bqij∣1≤q≤nq,1≤i≤m,1≤j≤nq,l(5)bqij∈Z+,1≤bqij≤nq,lThe Max-Plus algebra modelyj→ of train lj operation process can be described by Eqs. (6)~(7). The model yj→ records the arrival time at each station of train lj.(6)tx,sia,ljq=aq,i,bqij⊗tx,si-1a,lbqijq⊕τsid⊗tx,sia,lbqij-1q⊕uqij(7)yj→=yij∣yij=tx,sia,ljq,∀q,iWhen a train is delayed, the timetable changes and the matrices in the model are updated. The state matrices afterθ updated are defined as Aθ and Bθ. Then, the operation process model of train lj can be described as Eq. (8):(8)yj→θ=yijθ∣yijθ=tx,sia,ljqθ,∀θ,q,i


## 4. Operation Adjustment Method of High-Speed Delayed Trains

### 4.1. Alternative Adjustment Strategies

Six adjustment strategies are designed for the adjustment method of high-speed delayed trains. For each delayed train at each station, at least one adjustment strategy can be selected. The constraints of these adjustment strategies are analyzed as follows.(1) Section Acceleration. The buffer time of trains is reserved in the timetable. Therefore, after a delay, section acceleration strategy is the most direct, convenient, and effective adjustment method. For operational security, this strategy should ensure that the train speed does not exceed the maximum speed and the operational time of the adjusted train in the section does not exceed the minimum operation time for the same speed and stops. Therefore, the section acceleration strategy can be selected depending on Eqs. (9)~(11). Eq. (9) indicates that the adjusted arrival time of train lj at station si should not be less than the arrival time on the original timetable. Eq. (10) indicates that the operation time in section (si-1, si) of train lj after adjustment should not be less than the minimum operation time of the section. Eq. (11) indicates that the arrival headway between the adjusted train lj and the front train lj-1 should not be less than the minimum arrival headway at the station si. (9)tx,sia,lj≥tu,sia,lj(10)tx,sia,lj-tx,si-1a,lj≥tsi-1,simin,lj(11)tx,sia,lj-tx,sia,lj-1≥τsiaIn addition, the time can be reduced for trainlj in the section (si-1, si) as calculated using Eq. (12). The time is the minimum value among the minimum arrival headway of the station si, the difference between the actual operation time in section (si-1, si) and the minimum operation time in the section, and the difference between the adjusted arrival time and the original arrival time at the station si.(12)tsi-1,siacc,lj=min⁡τsia,tu,sia,lj-tu,si-1a,lj-tsi-1,simin,lj,tx,sia,lj-tu,sia,lj(2) Operation Based on the Original Timetable. When train lj has a large delay time, the sequence of this train and train lj+1 can be changed. Otherwise, station si is the original departure station of train lj+1 and is the middle stop station of train lj. Therefore, train lj+1 can operate based on the time of the original timetable without waiting for train lj as shown in Figure 2. The red line is the operation line after the delay of train lj.Figure 2
The condition of the strategy (2).The constraint on this strategy is that the departure time of trainlj+1 should not be less than the sum of the adjusted departure times of train lj and the minimum departure headway of the station si which can be expressed by Eq. (13). (13)tx,sid,lj≥tu,sid,lj+1+τsid(3) Dwell Time Reduction. High-speed trains usually stop for a short time at the station. When trains stop for a long time or there is a reduction in overtaking, the train delay can be reduced by reducing the dwell time. Therefore, there is one constraint for this strategy: the dwell time of the train after adjustment should not be less than the minimum dwell time at the station. In addition, the constraint can be expressed as Eq. (14). (14)tx,sid,lj-tx,sia,lj≥tsimin,lj(4) Overtaking Reduction. As shown in Figure 3, when train lj+1 has a large delay time and it overtakes train lj at station si, the overtaking reduction strategy can be selected to reduce the delay time of train lj. In addition, the departure sequence of train lj and train lj+1 at the station si also changes.Figure 3
The condition of the strategy (4).This adjustment strategy is constrained by Eq. (15). The constraint indicates that the departure time after the delay of train lj is not less than the sum of the arrival time of train lj+1, the minimum dwell time of train lj+1 and the minimum departure headway at station si. Therefore, this adjustment strategy is usually used with the strategy of dwell time reduction for train lj+1. (15)tx,sid,lj≥tx,sia,lj+1+tsimin,lj+1+τsid(5) Increase in Overtaking. As shown in Figure 4, when train lj has a large delay at station si, which is satisfied by Eq. (16), train lj can be overtaken by train lj+1 to decrease the delay time of the latter.(16)tx,sid,lj+1≤tx,sid,ljFigure 4
The condition of the strategy (5).The constraint conditions of this strategy include the following: (a) the stationsj can handle the overtaking and (b) at the station si, overtaking between the two trains should satisfy the constraint given by Eq. (17). The number of the overtaking trains is determined by the maximum dwell time of the overtaken train.(17)τsia+∑h=j+1nηlhsitx,sid,lh-tx,sid,lh-1+tsimin,lh+τsid≤tsimax,lj(6) Train Postponement. If the constraints of the adjustment strategies (1)~(5) cannot be satisfied, then the train postponement base on the minimum headway can be selected. The delayed trains can be postponed in order as scheduled by the timetable as the minimum headway and this strategy is constrained by Eq. (18). (18)tx,sia,lj+1=tx,sia,lj+τsiaortx,sid,lj+1=tx,sid,lj+τsidBased on different adjustment strategy, the adjustment time of trains at each station and in each section is different and these values can be calculated using Eqs. (19)~(20) where tsi-1,siλ,lj and tsiλ,lj may be positive or negative numbers. Moreover, bij of the state matrix B should be updated if strategies (2)∖(4)∖(5) are used.(19)tsiλ,lj=tu,sid,lj-tu,sia,lj-tx,sid,lj-tx,sia,lj(20)tsi-1,siλ,lj=tsi-1,sidelay,lj-tsi-1,siacc,lj-tsi-1λ,lj


### 4.2. The Model for Operation Adjustment

Model I: The Approximate Model. The intent of the approximate model is to quickly collect good-enough solutions of the operation adjustment for delayed trains. Therefore, the target function and the constraints should be simple for the purpose of calculation. During the operation adjustment process, the shorter the train delay, the smaller the impact on the operation of the other trains and the transportation organization is induced.Therefore, the target function of the approximate model is the minimum number of delayed trains after adjustment as described by Eq. (21). Moreover, the constraints of the adjustment strategies as expressed in Section 4.1 need to be satisfied. Using the approximate model, the adjustment schemes have the same number of delayed trains. This is because there would be several adjustment schemes with the same minimum number of delayed trains after adjustment. If the solution satisfies the minimum number of delayed trains and the constraints of the adjustment strategies, this scheme is one of the acceptable adjustment schemes for the second model. Therefore, an adjustment scheme set Θ can be obtained using the approximate model and the elements of the set are the good-enough solutions. (21)Θ=minθ∑j=1nξljθ(22)ξljθ=1tx,sia,ljθ>tu,sia,lj∣tx,sid,ljθ>tu,sid,lj,∀i0tx,sia,ljθ=tu,sia,lj&tx,sid,ljθ=tu,sid,lj,∀iModel II: The Accurate Model. Based on the set Θ, an accurate model for operation adjustment of the delayed trains is constructed. The target function of the accurate model of the train operation adjustment can be described by Eq. (23) and the model needs to satisfy the constraints expressed by Eqs. (24)~(28). Eq. (24) and Eq. (25) are the constraints of the effective time period whereby the trains can be adjusted. Eq. (26) is the constraint that the arrival time of the adjusted train should not be less than the arrival time in the original timetable whereas Eq. (27) is the constraint of the minimum headway. Eq. (28) is the constraint of the minimum operation time between two neighboring stations. (23)J=minθ∈Θ∑i=1m∑j=1nyijθ-tu,sia,lj(24)y11≥tqb,∀θ,q(25)ymn≤tqe,∀θ,q(26)yijθ-tu,sia,lj>0,∀θ,i,j(27)yijθ-yij-1θ>τsia,∀θ,i,1<j≤n(28)yijθ-yi-1jθ>tsi-1,simin,lj+tsi-1min,lj,∀θ,j,1<i≤m


### 4.3. The Algorithms for Operation Adjustment

Based on the parameters of the original timetable and Max-Plus algebra method, the algorithm of the train operation process is as shown in Algorithm1.Algorithm 1
Input : original timetable, adjustment time in each section and at each station. Output : the arrival time of each train after adjustment. (1)  Build the structure A,B,Yθ (2)  For  q=1 to nq (3)    Initial the state matrixes Aq and Bq (4)    For  i=1 to m (5)     For  j=1 to n (6)      If train lj is adjusted at station si (7)       Update the state matrix θ.A by calculating aij based on tsi-1,siλ,lj,tsiλ,lj and Eq.(3) (8)      End If (9)      If the sequence of train lj is changed (10)      Update the state matrix θ.Bby calculating bij (11)     End If (12)     Calculate the value xij by Eq.(6) (13)    End For (14)   End For (15)   Update θ.(yj→) by Eq.(8) (16)  End ForBased on the original delay, the algorithm for the rough model is as shown in Algorithm2.Algorithm 2
Input : original timetable, original delay. Output : The set Θ. (1)  Initial the minimum number of delayed train Nmax and number set of delayed trains Nd=zeros(n), the solution setΘ=zeros(Nmax), for which Nmax is a sufficiently large number. (2)  For  i=1 to m (3)    For  j=1 to n (4)     If train lj is delayed at station si (5)       For  u=1 to 63   %the possible combinations of the six strategies (6)         If the constraints of the strategies are all satisfied (7)           The strategies are used for train lj at each station si (8)         End If (9)       End For (10)      If only one strategy can be chosen (11)         Update Scheme θ (12)      Else (13)         Create the new Schemes θ (14)      End If (15)         Update the number of delayed train of Schemes θ,Nd(n) (16)      If  θ.Count.Nd(n)> Nmax (17)        Delete the Scheme θ (18)        Break (19)      Else (20)    End If (21)   End For (22)   θ→Θ (23)   Nmax=θ. Count.Nd(n) (24)  End ForBased on the setΘ, the algorithm for the accurate model is as shown in Algorithm 3.Algorithm 3
Input : The set Θ . Output : The optimal adjustment scheme. (1)  Initial the average delay time J=Nmax, (2)  While(θ∈Θ) (3)    Jθ=0  %initial the delay time of the scheme#θ (4)    For  i=1 to m (5)      For  j=1 to n (6)        If for yij, the constraints Eqs.(24)~(28) of the accurate model are all satisfied (7)          The adjustment time tsi-1,siλ,lj, tsiλ,ljare calculated by Eq.(19)~(20) (8)          Algorithm1  (tsi-1,siλ,lj,tsiλ,lj) (9)          Jθ=Jθ+yij-tu,sia,lj (10)       End If (11)     End For (12)   End For (13)   If  Jθ<J (14)    J=Jθ (15)    The optimal adjustment scheme is scheme #θ and the timetable of the scheme #θ is recorded (16)   End If (17) End While


## 4.1. Alternative Adjustment Strategies

Six adjustment strategies are designed for the adjustment method of high-speed delayed trains. For each delayed train at each station, at least one adjustment strategy can be selected. The constraints of these adjustment strategies are analyzed as follows.(1) Section Acceleration. The buffer time of trains is reserved in the timetable. Therefore, after a delay, section acceleration strategy is the most direct, convenient, and effective adjustment method. For operational security, this strategy should ensure that the train speed does not exceed the maximum speed and the operational time of the adjusted train in the section does not exceed the minimum operation time for the same speed and stops. Therefore, the section acceleration strategy can be selected depending on Eqs. (9)~(11). Eq. (9) indicates that the adjusted arrival time of train lj at station si should not be less than the arrival time on the original timetable. Eq. (10) indicates that the operation time in section (si-1, si) of train lj after adjustment should not be less than the minimum operation time of the section. Eq. (11) indicates that the arrival headway between the adjusted train lj and the front train lj-1 should not be less than the minimum arrival headway at the station si. (9)tx,sia,lj≥tu,sia,lj(10)tx,sia,lj-tx,si-1a,lj≥tsi-1,simin,lj(11)tx,sia,lj-tx,sia,lj-1≥τsiaIn addition, the time can be reduced for trainlj in the section (si-1, si) as calculated using Eq. (12). The time is the minimum value among the minimum arrival headway of the station si, the difference between the actual operation time in section (si-1, si) and the minimum operation time in the section, and the difference between the adjusted arrival time and the original arrival time at the station si.(12)tsi-1,siacc,lj=min⁡τsia,tu,sia,lj-tu,si-1a,lj-tsi-1,simin,lj,tx,sia,lj-tu,sia,lj(2) Operation Based on the Original Timetable. When train lj has a large delay time, the sequence of this train and train lj+1 can be changed. Otherwise, station si is the original departure station of train lj+1 and is the middle stop station of train lj. Therefore, train lj+1 can operate based on the time of the original timetable without waiting for train lj as shown in Figure 2. The red line is the operation line after the delay of train lj.Figure 2
The condition of the strategy (2).The constraint on this strategy is that the departure time of trainlj+1 should not be less than the sum of the adjusted departure times of train lj and the minimum departure headway of the station si which can be expressed by Eq. (13). (13)tx,sid,lj≥tu,sid,lj+1+τsid(3) Dwell Time Reduction. High-speed trains usually stop for a short time at the station. When trains stop for a long time or there is a reduction in overtaking, the train delay can be reduced by reducing the dwell time. Therefore, there is one constraint for this strategy: the dwell time of the train after adjustment should not be less than the minimum dwell time at the station. In addition, the constraint can be expressed as Eq. (14). (14)tx,sid,lj-tx,sia,lj≥tsimin,lj(4) Overtaking Reduction. As shown in Figure 3, when train lj+1 has a large delay time and it overtakes train lj at station si, the overtaking reduction strategy can be selected to reduce the delay time of train lj. In addition, the departure sequence of train lj and train lj+1 at the station si also changes.Figure 3
The condition of the strategy (4).This adjustment strategy is constrained by Eq. (15). The constraint indicates that the departure time after the delay of train lj is not less than the sum of the arrival time of train lj+1, the minimum dwell time of train lj+1 and the minimum departure headway at station si. Therefore, this adjustment strategy is usually used with the strategy of dwell time reduction for train lj+1. (15)tx,sid,lj≥tx,sia,lj+1+tsimin,lj+1+τsid(5) Increase in Overtaking. As shown in Figure 4, when train lj has a large delay at station si, which is satisfied by Eq. (16), train lj can be overtaken by train lj+1 to decrease the delay time of the latter.(16)tx,sid,lj+1≤tx,sid,ljFigure 4
The condition of the strategy (5).The constraint conditions of this strategy include the following: (a) the stationsj can handle the overtaking and (b) at the station si, overtaking between the two trains should satisfy the constraint given by Eq. (17). The number of the overtaking trains is determined by the maximum dwell time of the overtaken train.(17)τsia+∑h=j+1nηlhsitx,sid,lh-tx,sid,lh-1+tsimin,lh+τsid≤tsimax,lj(6) Train Postponement. If the constraints of the adjustment strategies (1)~(5) cannot be satisfied, then the train postponement base on the minimum headway can be selected. The delayed trains can be postponed in order as scheduled by the timetable as the minimum headway and this strategy is constrained by Eq. (18). (18)tx,sia,lj+1=tx,sia,lj+τsiaortx,sid,lj+1=tx,sid,lj+τsidBased on different adjustment strategy, the adjustment time of trains at each station and in each section is different and these values can be calculated using Eqs. (19)~(20) where tsi-1,siλ,lj and tsiλ,lj may be positive or negative numbers. Moreover, bij of the state matrix B should be updated if strategies (2)∖(4)∖(5) are used.(19)tsiλ,lj=tu,sid,lj-tu,sia,lj-tx,sid,lj-tx,sia,lj(20)tsi-1,siλ,lj=tsi-1,sidelay,lj-tsi-1,siacc,lj-tsi-1λ,lj


## 4.2. The Model for Operation Adjustment

Model I: The Approximate Model. The intent of the approximate model is to quickly collect good-enough solutions of the operation adjustment for delayed trains. Therefore, the target function and the constraints should be simple for the purpose of calculation. During the operation adjustment process, the shorter the train delay, the smaller the impact on the operation of the other trains and the transportation organization is induced.Therefore, the target function of the approximate model is the minimum number of delayed trains after adjustment as described by Eq. (21). Moreover, the constraints of the adjustment strategies as expressed in Section 4.1 need to be satisfied. Using the approximate model, the adjustment schemes have the same number of delayed trains. This is because there would be several adjustment schemes with the same minimum number of delayed trains after adjustment. If the solution satisfies the minimum number of delayed trains and the constraints of the adjustment strategies, this scheme is one of the acceptable adjustment schemes for the second model. Therefore, an adjustment scheme set Θ can be obtained using the approximate model and the elements of the set are the good-enough solutions. (21)Θ=minθ∑j=1nξljθ(22)ξljθ=1tx,sia,ljθ>tu,sia,lj∣tx,sid,ljθ>tu,sid,lj,∀i0tx,sia,ljθ=tu,sia,lj&tx,sid,ljθ=tu,sid,lj,∀iModel II: The Accurate Model. Based on the set Θ, an accurate model for operation adjustment of the delayed trains is constructed. The target function of the accurate model of the train operation adjustment can be described by Eq. (23) and the model needs to satisfy the constraints expressed by Eqs. (24)~(28). Eq. (24) and Eq. (25) are the constraints of the effective time period whereby the trains can be adjusted. Eq. (26) is the constraint that the arrival time of the adjusted train should not be less than the arrival time in the original timetable whereas Eq. (27) is the constraint of the minimum headway. Eq. (28) is the constraint of the minimum operation time between two neighboring stations. (23)J=minθ∈Θ∑i=1m∑j=1nyijθ-tu,sia,lj(24)y11≥tqb,∀θ,q(25)ymn≤tqe,∀θ,q(26)yijθ-tu,sia,lj>0,∀θ,i,j(27)yijθ-yij-1θ>τsia,∀θ,i,1<j≤n(28)yijθ-yi-1jθ>tsi-1,simin,lj+tsi-1min,lj,∀θ,j,1<i≤m


## 4.3. The Algorithms for Operation Adjustment

Based on the parameters of the original timetable and Max-Plus algebra method, the algorithm of the train operation process is as shown in Algorithm1.Algorithm 1
Input : original timetable, adjustment time in each section and at each station. Output : the arrival time of each train after adjustment. (1)  Build the structure A,B,Yθ (2)  For  q=1 to nq (3)    Initial the state matrixes Aq and Bq (4)    For  i=1 to m (5)     For  j=1 to n (6)      If train lj is adjusted at station si (7)       Update the state matrix θ.A by calculating aij based on tsi-1,siλ,lj,tsiλ,lj and Eq.(3) (8)      End If (9)      If the sequence of train lj is changed (10)      Update the state matrix θ.Bby calculating bij (11)     End If (12)     Calculate the value xij by Eq.(6) (13)    End For (14)   End For (15)   Update θ.(yj→) by Eq.(8) (16)  End ForBased on the original delay, the algorithm for the rough model is as shown in Algorithm2.Algorithm 2
Input : original timetable, original delay. Output : The set Θ. (1)  Initial the minimum number of delayed train Nmax and number set of delayed trains Nd=zeros(n), the solution setΘ=zeros(Nmax), for which Nmax is a sufficiently large number. (2)  For  i=1 to m (3)    For  j=1 to n (4)     If train lj is delayed at station si (5)       For  u=1 to 63   %the possible combinations of the six strategies (6)         If the constraints of the strategies are all satisfied (7)           The strategies are used for train lj at each station si (8)         End If (9)       End For (10)      If only one strategy can be chosen (11)         Update Scheme θ (12)      Else (13)         Create the new Schemes θ (14)      End If (15)         Update the number of delayed train of Schemes θ,Nd(n) (16)      If  θ.Count.Nd(n)> Nmax (17)        Delete the Scheme θ (18)        Break (19)      Else (20)    End If (21)   End For (22)   θ→Θ (23)   Nmax=θ. Count.Nd(n) (24)  End ForBased on the setΘ, the algorithm for the accurate model is as shown in Algorithm 3.Algorithm 3
Input : The set Θ . Output : The optimal adjustment scheme. (1)  Initial the average delay time J=Nmax, (2)  While(θ∈Θ) (3)    Jθ=0  %initial the delay time of the scheme#θ (4)    For  i=1 to m (5)      For  j=1 to n (6)        If for yij, the constraints Eqs.(24)~(28) of the accurate model are all satisfied (7)          The adjustment time tsi-1,siλ,lj, tsiλ,ljare calculated by Eq.(19)~(20) (8)          Algorithm1  (tsi-1,siλ,lj,tsiλ,lj) (9)          Jθ=Jθ+yij-tu,sia,lj (10)       End If (11)     End For (12)   End For (13)   If  Jθ<J (14)    J=Jθ (15)    The optimal adjustment scheme is scheme #θ and the timetable of the scheme #θ is recorded (16)   End If (17) End While


## 5. Case Study

In this case, the timetable of the Beijing-Shanghai High-Speed railway in May 2017 is analyzed. The operation parameters are described as follows:The speed of the trains is 300 km/h; the additional time of departure is 2 min and additional time of arrival is 3 min; the minimum departure headway of the original station is 5 min; the minimum arrival headway and departure headway at other stations are 4 min; the minimum stop time at the station is 2 min and the minimum operation time of each section is 12 min, 12 min, 18 min, 21 min, 12 min, 12 min, 14 min, 11 min, 7 min, and 13 min.The original timetable is shown as in Figure5. The horizontal axis represents the time and the vertical axis represents the station. We select a part of trains in timetable between 7:00 am and 8:00 am and between Beijing South Station and Xuzhou East Station. There are 9 trains during this time period, in which seven trains originate from the Beijing South Station and two trains originate from Jinan West Station. The number of section nq=2; one is from Beijing South Station to Jinan West Station and the other is from Jinan West Station to Xuzhou East Station.Figure 5
Original timetable.


### 5.1. Result Analysis

A 20-min delay time is added to train G103 including 10 min from the Langfang Station to Tianjin South Station and 10 min from Tianjin South Station to Cangzhou West Station. The conflicts caused by the delay of train G103 and the other trains are shown as in Figure6.Figure 6
Timetable after delay.The optimal adjustment scheme is shown in Figure7. In this figure, the red lines are the original delayed train, the yellow lines are the trains affected by the delay, and the black lines are the trains not affected by the delay. The original timetable and the adjusted timetable are shown in Table 2.Table 2
The original timetable and adjusted timetable.
Train number Train station original arrival time original departure time Delayed arrival time Delayed departure time Adjustment scheme Delay Time(min) G103 Beijing South 0 7:05 0 7:05  0 G103 Langfang 7:23 7:23 7:23 7:23  0 G103 Tianjin South 7:36 7:36 7:46 7:46  10 G103 Cangzhou West 7:56 7:58 8:16 8:18  20 G103 Dezhou East 8:23 8:23 8:41 8:41 section acceleration 2min 18 G103 Jinan West 8:44 8:46 8:56 8:58 section acceleration 6min 12 G103 Taian 9:03 9:04 9:15 9:16 train postponement 12 G103 Qufu East 9:21 9:21 9:33 9:33 train postponement 12 G103 Tengzhou East 9:35 9:37 9:47 9:49 train postponement 12 G103 Zaozhuang 9:46 9:46 9:58 9:58 overtaking increasing 12 G103 Xuzhou East 10:02 0 10:14 0 train postponement 12 G11 Beijing South 0 8:00 0 8:00  0 G11 Langfang 8:18 8:18 8:18 8:18  0 G11 Tianjin South 8:28 8:28 8:28 8:28  0 G11 Cangzhou West 8:48 8:48 8:48 8:48  0 G11 Dezhou East 9:10 9:10 9:10 9:10  0 G11 Jinan West 9:32 9:34 9:32 9:34  0 G11 Taian 9:48 9:48 9:48 9:48  0 G11 Qufu East 10:06 10:08 10:06 10:08 section acceleration 1min 0 G11 Tengzhou East 10:21 10:21 10:21 10:21  0 G11 Zaozhuang 10:28 10:28 10:28 10:28  0 G11 Xuzhou East 10:41 0 10:44 0 train postponement 3 G133 Jinan West 0 8:54 0 8:54 Operation based on the original timetable 0 G133 Taian 9:08 9:08 9:08 9:08  0 G133 Qufu East 9:29 9:30 9:29 9:30  0 G133 Tengzhou East 9:43 9:43 9:43 9:43  0 G133 Zaozhuang 9:54 9:59 9:54 10:00  0 G133 Xuzhou East 10:18 0 10:18 0 section acceleration 1min 0 G177 Beijing South 0 7:25 0 7:25  0 G177 Langfang 7:43 7:43 7:43 7:43  0 G177 Tianjin South 7:59 8:03 8:02 8:06 train postponement 3 G177 Cangzhou West 8:21 8:21 8:32 8:32 train postponement 11 G177 Dezhou East 8:50 8:52 8:59 9:01 section acceleration 2min 9 G177 Jinan West 9:16 9:16 9:20 9:20 section acceleration 5min 4 G177 Taian 9:32 9:32 9:34 9:34 section acceleration 2min 2 G177 Qufu East 9:46 9:46 9:48 9:48 train postponement 2 G177 Tengzhou East 10:00 10:06 10:06 10:08 reducing the dwell time 4min 6 G177 Zaozhuang 10:18 10:20 10:20 10:22  2 G177 Xuzhou East 10:38 0 10:40 0  2 G234 Jinan West 0 9:25 0 9:25  0 G234 Taian 9:43 9:43 9:43 9:43  0 G234 Qufu East 9:59 10:01 9:59 10:01  0 G234 Tengzhou East 10:14 10:14 10:14 10:14  0 G234 Zaozhuang 10:25 10:34 10:25 10:34  0 G234 Xuzhou East 10:52 0 10:52 0  0 G261 Beijing South 0 7:15 0 7:15  0 G261 Langfang 7:33 7:33 7:33 7:33  0 G261 Tianjin South 7:49 7:51 7:54 7:56 train postponement 5 G261 Cangzhou West 8:10 8:10 8:24 8:24 train postponement 14 G261 Dezhou East 8:35 8:37 8:49 8:51 train postponement 14 G261 Jinan West 9:01 9:03 9:10 9:12 train postponement 9 G261 Taian 9:21 9:21 9:26 9:26 section acceleration 4min 5 G261 Qufu East 9:38 9:38 9:40 9:40 section acceleration 3min 2 G261 Tengzhou East 9:49 9:49 9:54 9:54  5 G261 Zaozhuang 9:56 9:56 10:05 10:05 overtaking reduction 9 G261 Xuzhou East 10:11 0 10:21 0  10 G265 Beijing South 0 7:48 0 7:48  0 G265 Langfang 8:05 8:05 8:05 8:05  0 G265 Tianjin South 8:22 8:24 8:22 8:24  0 G265 Cangzhou West 8:43 8:43 8:43 8:43  0 G265 Dezhou East 9:05 9:05 9:05 9:05  0 G265 Jinan West 9:27 9:39 9:27 9:39  0 G265 Taian 9:55 9:57 9:55 9:57  0 G265 Qufu East 10:14 10:14 10:14 10:14  0 G265 Tengzhou East 10:25 10:25 10:25 10:25  0 G265 Zaozhuang 10:32 10:32 10:32 10:32  0 G265 Xuzhou East 10:48 0 10:48 0  0 G471 Beijing South 0 7:10 0 7:10  0 G471 Langfang 7:28 7:28 7:28 7:28  0 G471 Tianjin South 7:44 7:45 7:50 7:51 train postponement 6 G471 Cangzhou West 8:05 8:05 8:20 8:20 train postponement 15 G471 Dezhou East 8:30 8:32 8:47 8:49 train postponement 17 G471 Jinan West 8:56 0 9:06 0 section acceleration 7min 12 G57 Beijing South 0 7:20 0 7:20  0 G57 Langfang 7:38 7:38 7:38 7:38  0 G57 Tianjin South 7:54 7:58 7:58 8:02 train postponement 4 G57 Cangzhou West 8:18 8:18 8:28 8:28 train postponement 10 G57 Dezhou East 8:45 8:48 8:55 8:57 reducing the dwell time 1min 10 G57 Jinan West 9:11 9:11 9:16 9:16 section acceleration 4min 5 G57 Taian 9:26 9:26 9:30 9:30 section acceleration 1min 4 G57 Qufu East 9:42 9:42 9:44 9:44 section acceleration 2min 2 G57 Tengzhou East 9:53 9:53 9:58 9:58 train postponement 5 G57 Zaozhuang 10:03 10:04 10:09 10:10 train postponement 6 G57 Xuzhou East 10:22 0 10:28 0  6Figure 7
The timetable after adjustment.For the optimal adjustment scheme, there are five trains affected by the original delayed train G103. Train G133 operates according to original timetable because of strategy (2) and trains G234 and G265 are also not affected by the delay. The average delay time of each train at each station is 355 min. Using a standard PC with an Intel (R) Core (TM) i5-6500 3.2 GHz and 4 Gb of RAM, the calculation time is within 20 s using MATLAB 2016a and has good solution efficiency.The average delay time of the trains is shown in Figure8. Train G103 is the initially delayed train and the delay time is larger than the delay time of the other trains. Train G133 has no delay because of strategy (2). Train G471 operates from the Beijing South Station to Jinan West Station, and the number of stop stations is less than that of the entire line of trains such as train G103. Therefore, the average delay time of train G471 is less than the trend value as indicated by the blue line in Figure 8. The trend of the delay time of trains G103, G261, G57, G177, and G11 gradually decreases in Figure 8. The delay time of each train at each station is shown in Figure 9. The delay time at the Cangzhou West Station and Dezhou East Station is larger than the other stations. The delay time was absorbed during the train operation by the adjustment method.Figure 8
The delay time of each train.Figure 9
The delay time of each train at each station.


### 5.2. Buffer Time Analysis

In this case, the delay time can be absorbed within the time period of five trains by optimal adjustment. The buffer time includes two parts; one is the headway buffer time between the two adjacent trains (the difference of the actual headway and the minimum headway between two adjacent trains) and the other is the operation buffer time of the train (the difference between the actual operation time and the minimum operation time in the same section). In this case, most delay of the trains can be reduced by the strategies of the section acceleration and train postponement. This indicates that the original timetable has a certain buffer time.The buffer time of each train operation in each section of the original timetable and the adjusted timetable is shown in Figures10(a) and 10(b), which represent the operation buffer time. The texts of the “Trains” axis are trains G103, G471, G261, G57, G177, G265, G11, G133, and G234 in order. The texts of the “Sections” axis are Langfang-Tianjin South, Tianjin South-Cangzhou West, Cangzhou West-Dezhou East, Dezhou East-Jinan West, Jinan West-Taian, Taian-Qufu East, Qufu East-Tengzhou East, Tengzhou East-Zaozhuang, and Zaozhuang-Xuzhou East in order. Based on Figure 10, the interval time of trains G103 and G471 in the sections from the Langfang Station to Cangzhou West Station increased because of the primary delay. Then, the delay time of the trains including G103, G471, G261, G57, and G177 in the sections from Jinan West Station to Qufu East Station decreased with a reduction of their operation time in these sections. The section acceleration strategy is used frequently. The buffer time of each train operation at each station of the original timetable and the adjusted timetable is shown in Figures 11(a) and 11(b). This buffer time is the headway buffer time. After adjustment, most headway buffer times decrease in the range 0-5 min as shown in Figure 12, and a small part of the headway buffer time is increased by the delay.Figure 10
The operation buffer time of each train in each section.
(a)
Original timetable (b)
Adjusted timetableFigure 11
The buffer time of each train at each station by arrival headway.
(a)
Original timetable (b)
Adjusted timetableFigure 12
The difference of the buffer time between the original timetable and adjusted timetable.As shown in Figures10 and 11, the delay time can be reasonably decreased by the buffer time and is effectively based on the operation adjustment method of delayed trains in this paper. Under the same conditions of timetable and delay, the capacity utilization is larger, the surplus usable capacity is smaller, and the loss of capacity is greater. When the utilization rate reaches 100%, any delay will have a great impact on the train operation according to the original timetable.


### 5.3. Delay Distribution Analysis

Three schemes with different delay distributions are studied.Scheme #1 is the scheme in Section5.1.Scheme #2: 10 min delay time is added to trains G103 and G471, respectively, from Langfang Station to Tianjin South Station.Scheme #3: 10 min delay time is added to trains G103 and G261, respectively, from Langfang Station to Tianjin South Station.For Scheme #2, the adjusted timetable of the optimal adjustment scheme is shown in Figure13. There are six delayed trains. The average delay time is 232 minutes, of which trains G103, G471, G261, G57, G177, G265, G11, G133, and G234 are delayed by 98 min, 33 min, 42 min, 31 min, 26 min, 0 min, 0 min, 2 min, and 0 min, respectively. For Scheme #3, the optimal adjustment scheme is the same as the optimal adjustment scheme of Scheme #2. The difference is that train G261 is delayed 1 min more than in Scheme #2 at the Tianjin South Station, Changzhou West Station, and Dezhou East Station, respectively. In addition, trains G56 and G177 are delayed 1 min more than in Scheme #2 at the Cangzhou West Station, Dezhou East Station, and Jinan West Station, respectively, and the average delay time is 9 min more than in Scheme #2. After the adjustment, there are also six delayed trains. The average delay time is 241 minutes of which trains G103, G471, G261, G57, G177, G265, G11, G133, and G234 are delayed by 98 min, 33 min, 45 min, 34 min, 29 min, 0 min, 0 min, 2 min, and 0 min, respectively.Figure 13
The optimal adjustment solution of the delay scheme #2.Figure14 expresses the relationship of the delay time of each train for the three different schemes. The average delay time after adjustment using Scheme #2 is less than that using Scheme #1 with the same total original delay time. This is mainly because train G471 was affected by the delay of G103. When the delay time is added for train G471, a part of the original delay time is overlapped. Compared with Scheme #2, the average delay time for Scheme #3 exhibits a small increase. Therefore, when the original delay is added to the different trains with the same total original delay time, the interval time of the originally delayed trains is larger; the average delay time is more after adjustment. However, in this case, the operation buffer time of train G261 is large and the recovery capability of train G261 itself is strong. Therefore, it is not much different from Scheme #2. If delays of different trains do not overlap, the delay time after adjustment will be even larger.Figure 14
The delay time of each train in different delay schemes.


## 5.1. Result Analysis

A 20-min delay time is added to train G103 including 10 min from the Langfang Station to Tianjin South Station and 10 min from Tianjin South Station to Cangzhou West Station. The conflicts caused by the delay of train G103 and the other trains are shown as in Figure6.Figure 6
Timetable after delay.The optimal adjustment scheme is shown in Figure7. In this figure, the red lines are the original delayed train, the yellow lines are the trains affected by the delay, and the black lines are the trains not affected by the delay. The original timetable and the adjusted timetable are shown in Table 2.Table 2
The original timetable and adjusted timetable.
Train number Train station original arrival time original departure time Delayed arrival time Delayed departure time Adjustment scheme Delay Time(min) G103 Beijing South 0 7:05 0 7:05  0 G103 Langfang 7:23 7:23 7:23 7:23  0 G103 Tianjin South 7:36 7:36 7:46 7:46  10 G103 Cangzhou West 7:56 7:58 8:16 8:18  20 G103 Dezhou East 8:23 8:23 8:41 8:41 section acceleration 2min 18 G103 Jinan West 8:44 8:46 8:56 8:58 section acceleration 6min 12 G103 Taian 9:03 9:04 9:15 9:16 train postponement 12 G103 Qufu East 9:21 9:21 9:33 9:33 train postponement 12 G103 Tengzhou East 9:35 9:37 9:47 9:49 train postponement 12 G103 Zaozhuang 9:46 9:46 9:58 9:58 overtaking increasing 12 G103 Xuzhou East 10:02 0 10:14 0 train postponement 12 G11 Beijing South 0 8:00 0 8:00  0 G11 Langfang 8:18 8:18 8:18 8:18  0 G11 Tianjin South 8:28 8:28 8:28 8:28  0 G11 Cangzhou West 8:48 8:48 8:48 8:48  0 G11 Dezhou East 9:10 9:10 9:10 9:10  0 G11 Jinan West 9:32 9:34 9:32 9:34  0 G11 Taian 9:48 9:48 9:48 9:48  0 G11 Qufu East 10:06 10:08 10:06 10:08 section acceleration 1min 0 G11 Tengzhou East 10:21 10:21 10:21 10:21  0 G11 Zaozhuang 10:28 10:28 10:28 10:28  0 G11 Xuzhou East 10:41 0 10:44 0 train postponement 3 G133 Jinan West 0 8:54 0 8:54 Operation based on the original timetable 0 G133 Taian 9:08 9:08 9:08 9:08  0 G133 Qufu East 9:29 9:30 9:29 9:30  0 G133 Tengzhou East 9:43 9:43 9:43 9:43  0 G133 Zaozhuang 9:54 9:59 9:54 10:00  0 G133 Xuzhou East 10:18 0 10:18 0 section acceleration 1min 0 G177 Beijing South 0 7:25 0 7:25  0 G177 Langfang 7:43 7:43 7:43 7:43  0 G177 Tianjin South 7:59 8:03 8:02 8:06 train postponement 3 G177 Cangzhou West 8:21 8:21 8:32 8:32 train postponement 11 G177 Dezhou East 8:50 8:52 8:59 9:01 section acceleration 2min 9 G177 Jinan West 9:16 9:16 9:20 9:20 section acceleration 5min 4 G177 Taian 9:32 9:32 9:34 9:34 section acceleration 2min 2 G177 Qufu East 9:46 9:46 9:48 9:48 train postponement 2 G177 Tengzhou East 10:00 10:06 10:06 10:08 reducing the dwell time 4min 6 G177 Zaozhuang 10:18 10:20 10:20 10:22  2 G177 Xuzhou East 10:38 0 10:40 0  2 G234 Jinan West 0 9:25 0 9:25  0 G234 Taian 9:43 9:43 9:43 9:43  0 G234 Qufu East 9:59 10:01 9:59 10:01  0 G234 Tengzhou East 10:14 10:14 10:14 10:14  0 G234 Zaozhuang 10:25 10:34 10:25 10:34  0 G234 Xuzhou East 10:52 0 10:52 0  0 G261 Beijing South 0 7:15 0 7:15  0 G261 Langfang 7:33 7:33 7:33 7:33  0 G261 Tianjin South 7:49 7:51 7:54 7:56 train postponement 5 G261 Cangzhou West 8:10 8:10 8:24 8:24 train postponement 14 G261 Dezhou East 8:35 8:37 8:49 8:51 train postponement 14 G261 Jinan West 9:01 9:03 9:10 9:12 train postponement 9 G261 Taian 9:21 9:21 9:26 9:26 section acceleration 4min 5 G261 Qufu East 9:38 9:38 9:40 9:40 section acceleration 3min 2 G261 Tengzhou East 9:49 9:49 9:54 9:54  5 G261 Zaozhuang 9:56 9:56 10:05 10:05 overtaking reduction 9 G261 Xuzhou East 10:11 0 10:21 0  10 G265 Beijing South 0 7:48 0 7:48  0 G265 Langfang 8:05 8:05 8:05 8:05  0 G265 Tianjin South 8:22 8:24 8:22 8:24  0 G265 Cangzhou West 8:43 8:43 8:43 8:43  0 G265 Dezhou East 9:05 9:05 9:05 9:05  0 G265 Jinan West 9:27 9:39 9:27 9:39  0 G265 Taian 9:55 9:57 9:55 9:57  0 G265 Qufu East 10:14 10:14 10:14 10:14  0 G265 Tengzhou East 10:25 10:25 10:25 10:25  0 G265 Zaozhuang 10:32 10:32 10:32 10:32  0 G265 Xuzhou East 10:48 0 10:48 0  0 G471 Beijing South 0 7:10 0 7:10  0 G471 Langfang 7:28 7:28 7:28 7:28  0 G471 Tianjin South 7:44 7:45 7:50 7:51 train postponement 6 G471 Cangzhou West 8:05 8:05 8:20 8:20 train postponement 15 G471 Dezhou East 8:30 8:32 8:47 8:49 train postponement 17 G471 Jinan West 8:56 0 9:06 0 section acceleration 7min 12 G57 Beijing South 0 7:20 0 7:20  0 G57 Langfang 7:38 7:38 7:38 7:38  0 G57 Tianjin South 7:54 7:58 7:58 8:02 train postponement 4 G57 Cangzhou West 8:18 8:18 8:28 8:28 train postponement 10 G57 Dezhou East 8:45 8:48 8:55 8:57 reducing the dwell time 1min 10 G57 Jinan West 9:11 9:11 9:16 9:16 section acceleration 4min 5 G57 Taian 9:26 9:26 9:30 9:30 section acceleration 1min 4 G57 Qufu East 9:42 9:42 9:44 9:44 section acceleration 2min 2 G57 Tengzhou East 9:53 9:53 9:58 9:58 train postponement 5 G57 Zaozhuang 10:03 10:04 10:09 10:10 train postponement 6 G57 Xuzhou East 10:22 0 10:28 0  6Figure 7
The timetable after adjustment.For the optimal adjustment scheme, there are five trains affected by the original delayed train G103. Train G133 operates according to original timetable because of strategy (2) and trains G234 and G265 are also not affected by the delay. The average delay time of each train at each station is 355 min. Using a standard PC with an Intel (R) Core (TM) i5-6500 3.2 GHz and 4 Gb of RAM, the calculation time is within 20 s using MATLAB 2016a and has good solution efficiency.The average delay time of the trains is shown in Figure8. Train G103 is the initially delayed train and the delay time is larger than the delay time of the other trains. Train G133 has no delay because of strategy (2). Train G471 operates from the Beijing South Station to Jinan West Station, and the number of stop stations is less than that of the entire line of trains such as train G103. Therefore, the average delay time of train G471 is less than the trend value as indicated by the blue line in Figure 8. The trend of the delay time of trains G103, G261, G57, G177, and G11 gradually decreases in Figure 8. The delay time of each train at each station is shown in Figure 9. The delay time at the Cangzhou West Station and Dezhou East Station is larger than the other stations. The delay time was absorbed during the train operation by the adjustment method.Figure 8
The delay time of each train.Figure 9
The delay time of each train at each station.


## 5.2. Buffer Time Analysis

In this case, the delay time can be absorbed within the time period of five trains by optimal adjustment. The buffer time includes two parts; one is the headway buffer time between the two adjacent trains (the difference of the actual headway and the minimum headway between two adjacent trains) and the other is the operation buffer time of the train (the difference between the actual operation time and the minimum operation time in the same section). In this case, most delay of the trains can be reduced by the strategies of the section acceleration and train postponement. This indicates that the original timetable has a certain buffer time.The buffer time of each train operation in each section of the original timetable and the adjusted timetable is shown in Figures10(a) and 10(b), which represent the operation buffer time. The texts of the “Trains” axis are trains G103, G471, G261, G57, G177, G265, G11, G133, and G234 in order. The texts of the “Sections” axis are Langfang-Tianjin South, Tianjin South-Cangzhou West, Cangzhou West-Dezhou East, Dezhou East-Jinan West, Jinan West-Taian, Taian-Qufu East, Qufu East-Tengzhou East, Tengzhou East-Zaozhuang, and Zaozhuang-Xuzhou East in order. Based on Figure 10, the interval time of trains G103 and G471 in the sections from the Langfang Station to Cangzhou West Station increased because of the primary delay. Then, the delay time of the trains including G103, G471, G261, G57, and G177 in the sections from Jinan West Station to Qufu East Station decreased with a reduction of their operation time in these sections. The section acceleration strategy is used frequently. The buffer time of each train operation at each station of the original timetable and the adjusted timetable is shown in Figures 11(a) and 11(b). This buffer time is the headway buffer time. After adjustment, most headway buffer times decrease in the range 0-5 min as shown in Figure 12, and a small part of the headway buffer time is increased by the delay.Figure 10
The operation buffer time of each train in each section.
(a)
Original timetable (b)
Adjusted timetableFigure 11
The buffer time of each train at each station by arrival headway.
(a)
Original timetable (b)
Adjusted timetableFigure 12
The difference of the buffer time between the original timetable and adjusted timetable.As shown in Figures10 and 11, the delay time can be reasonably decreased by the buffer time and is effectively based on the operation adjustment method of delayed trains in this paper. Under the same conditions of timetable and delay, the capacity utilization is larger, the surplus usable capacity is smaller, and the loss of capacity is greater. When the utilization rate reaches 100%, any delay will have a great impact on the train operation according to the original timetable.


## 5.3. Delay Distribution Analysis

Three schemes with different delay distributions are studied.Scheme #1 is the scheme in Section5.1.Scheme #2: 10 min delay time is added to trains G103 and G471, respectively, from Langfang Station to Tianjin South Station.Scheme #3: 10 min delay time is added to trains G103 and G261, respectively, from Langfang Station to Tianjin South Station.For Scheme #2, the adjusted timetable of the optimal adjustment scheme is shown in Figure13. There are six delayed trains. The average delay time is 232 minutes, of which trains G103, G471, G261, G57, G177, G265, G11, G133, and G234 are delayed by 98 min, 33 min, 42 min, 31 min, 26 min, 0 min, 0 min, 2 min, and 0 min, respectively. For Scheme #3, the optimal adjustment scheme is the same as the optimal adjustment scheme of Scheme #2. The difference is that train G261 is delayed 1 min more than in Scheme #2 at the Tianjin South Station, Changzhou West Station, and Dezhou East Station, respectively. In addition, trains G56 and G177 are delayed 1 min more than in Scheme #2 at the Cangzhou West Station, Dezhou East Station, and Jinan West Station, respectively, and the average delay time is 9 min more than in Scheme #2. After the adjustment, there are also six delayed trains. The average delay time is 241 minutes of which trains G103, G471, G261, G57, G177, G265, G11, G133, and G234 are delayed by 98 min, 33 min, 45 min, 34 min, 29 min, 0 min, 0 min, 2 min, and 0 min, respectively.Figure 13
The optimal adjustment solution of the delay scheme #2.Figure14 expresses the relationship of the delay time of each train for the three different schemes. The average delay time after adjustment using Scheme #2 is less than that using Scheme #1 with the same total original delay time. This is mainly because train G471 was affected by the delay of G103. When the delay time is added for train G471, a part of the original delay time is overlapped. Compared with Scheme #2, the average delay time for Scheme #3 exhibits a small increase. Therefore, when the original delay is added to the different trains with the same total original delay time, the interval time of the originally delayed trains is larger; the average delay time is more after adjustment. However, in this case, the operation buffer time of train G261 is large and the recovery capability of train G261 itself is strong. Therefore, it is not much different from Scheme #2. If delays of different trains do not overlap, the delay time after adjustment will be even larger.Figure 14
The delay time of each train in different delay schemes.


## 6. Conclusions

In this report, a train operation process model is established for high-speed railway based on the Max-Plus algebra method. For operation adjustment of the delayed trains, six alternative adjustment strategies are proposed including the section acceleration, operation in advance, stop time reduction, increase of overtaking, reduction of overtaking, and train postponement. The constraints are analyzed for each adjustment strategy. Then, the train operation adjustment method is established with the two models and three algorithms. Finally, the portion of the delayed timetable of the Beijing-Shanghai High-Speed Railway is analyzed. The conclusions can be summarized as follows. (1) After the high-speed trains are delayed, the optimal adjustment scheme can be obtained by the operation adjustment method proposed in this report. The optimal adjustment scheme is a new timetable with the minimum number of delayed trains and the minimum average delay time of each train at each station. The adjusted new timetable can be directly applied in the real-time scheduling for the delay condition of the high-speed railway. (2) The buffer time, which includes the headway buffer time and the operation buffer time, can effectively absorb train delays and rapidly recover the schedule. However, the buffer time will simultaneously reduce the carrying capacity of the railway line. (3) This method can be applied in real-time railway rescheduling and it proves that the proposed method is valid and feasible for the operation adjustment of delay.



---

*Source: 9846970-2019-05-02.xml*