A train timetable rescheduling approach based on multi-train tracking optimization of high-speed railways

Abstract

Purpose

This paper aims to propose a train timetable rescheduling (TTR) approach from the perspective of multi-train tracking optimization based on the mutual spatiotemporal information in the high-speed railway signaling system.

Design/methodology/approach

Firstly, a single-train trajectory optimization (STTO) model is constructed based on train dynamics and operating conditions. The train kinematics parameters, including acceleration, speed and time at each position, are calculated to predict the arrival times in the train timetable. A STTO algorithm is developed to optimize a single-train time-efficient driving strategy. Then, a TTR approach based on multi-train tracking optimization (TTR-MTTO) is proposed with mutual information. The constraints of temporary speed restriction (TSR) and end of authority are decoupled to calculate the tracking trajectory of the backward tracking train. The multi-train trajectories at each position are optimized to generate a time-efficient train timetable.

Findings

The numerical experiment is performed on the Beijing-Tianjin high-speed railway line and CR400AF. The STTO algorithm predicts the train’s planned arrival time to calculate the total train delay (TTD). As for the TSR scenario, the proposed TTR-MTTO can reduce TTD by 60.60% compared with the traditional TTR approach with dispatchers’ experience. Moreover, TTR-MTTO can optimize a time-efficient train timetable to help dispatchers reschedule trains more reasonably.

Originality/value

With the cooperative relationship and mutual information between train rescheduling and control, the proposed TTR-MTTO approach can automatically generate a time-efficient train timetable to reduce the total train delay and the work intensity of dispatchers.

Citation

Wang, R., Zhang, T., Yuan, Z., Ding, S. and Zhang, Q. (2023), "A train timetable rescheduling approach based on multi-train tracking optimization of high-speed railways", Railway Sciences, Vol. 2 No. 3, pp. 358-370. https://doi.org/10.1108/RS-05-2023-0022

1. Introduction

High-speed railways are a significant driving force in promoting economic development, cultural exchange and coordinated urban development. Nowadays, China has ranked the highest in the world, including network complexity, traffic flow and passenger transport volume. With the huge passenger flow pressure and changeable emergencies, the high-speed railway network presents unprecedented spatiotemporal complexity. The major challenge of high-speed railway management is to improve safety and efficiency based on train safety tracking.

The high railway signaling system mainly consists of the Chinese train control system (CTCS) and centralized traffic control (CTC). The above two systems cooperate and ensure the safety and efficiency of multi-train tracking optimization (MTTO). However, unpredicted emergencies often occur, leading to disorder in train operations. Dispatchers require to reschedule the train timetable that stimulates the arrival time, the departure time and the departure sequence of trains at each station. This problem can be called train timetable rescheduling (TTR). TTR is mainly addressed by adjusting each train’s arrival/departure time based on dispatchers’ experience. Dispatchers hardly consider the nonlinear variation of the position and speed in the MTTO process. The information interaction between CTCS and CTC is usually neglected. With the increase of train delays caused by emergencies, TTR cannot be resolved by dispatchers in real-time. It is imperative to investigate a novel TTR approach considering the MTTO process and the spatiotemporal information in the high-speed railway signaling system.

Since TTR was proposed in the 1970s (Szpigel, 1973), most researchers usually establish the integer linear programming model based on train operation constraints in block sections and stations. The main optimization approaches of TTR comprise operational research (Zhu & Goverde, 2021; Zhan et al., 2021; Luan & Corman, 2022; Martin-Iradi & Ropke, 2022), evolutionary algorithms (Han et al., 2021; Tang et al., 2021; Pascariu et al., 2022; Wang et al., 2022b) and reinforcement learning (Šemrov, Marsetič, Žura, Todorovski, & Srdic, 2016; Khadilkar, 2018; Wang, Zhou, Li, Zhang, & Dong, 2019). Operational research can obtain an optimal rescheduling solution with branch and bound rules. Nevertheless, the computation time increases exponentially due to the NP characteristic of TTR. Evolutionary algorithms can resolve the TTR problem by utilizing the cross-variation characteristics in the population, but it needs to design efficient encoding/decoding and population initialization methods (Wang et al., 2022b). Reinforcement learning can generate a train timetable in the offline model but has difficulty establishing environment and learning policies (Ning, Li, Zhou, Song, & Dong, 2019). In summary, most TTR approaches focus on analyzing the train operation in block sections and stations to construct the optimization model and objective function.

However, existing TTR approaches mainly calculate the rescheduling solution from the perspective of railway management but scarcely consider the spatiotemporal of MTTO in the level of train operation control. As for the MTTO problem, much research analyses the speed and position changes in the tracking process of the forward and backward trains. Ye and Liu (2016), Wang and Goverde (2017) and Wang and Goverde (2019) constructed a multi-phase optimal control model and used the pseudospectral method to optimize the multi-train energy-saving trajectory. Luan et al. (2018a, b) converted MTTO into a mixed-integer nonlinear programming model and generated the energy-saving train timetable by approximating the nonlinear terms. Rao, Montigel, and Weidmann (2016) adjusted the tracking trajectory of the backward train to realize unnecessary braking or stopping to reduce the train delay and energy consumption. Cai, Sun, and Shangguan (2019), Sheng, Shangguan, Cai, Zhong, and Song (2021), and Song, Shangguan, Sheng, and Zhang (2021) investigated MTTO using the interval elastic adjustment strategy under the moving block system. As for MTTO, Peng, Wang, and Lu (2020) and Lu, Shen, Peng, and Wang (2021) compressed the train arrival interval at most 30 s to optimize the multi-train tracking trajectories of the backward train.

Much research mainly concentrates on multi-train energy-saving trajectory optimization to generate the train timetable but neglects the spatiotemporal information transmitted in the high-speed railway signaling system. Moreover, the time-efficient trajectory of MTTO should be considered first because railway companies concentrate more on reducing the train delay’s impact. Therefore, this paper first extracts, decouples and mines the spatiotemporal information in CTCS and CTC. Then, a TTR approach based on multi-train tracking optimization (TTR-MTTO) is developed by analyzing the nonlinear variation of position and speed and mining the spatiotemporal information in the high-speed railway signaling system. Finally, this proposed TTR approach automatically generates a time-efficient train timetable that can reduce the work intensity of dispatchers and improve operation efficiency and emergency response.

The remainder of our study is organized as follows. In Section 2, we introduce the TTR problem with the tracking process of the forward and backward trains. As for Section 3, we establish a single-train trajectory optimization model and propose the corresponding time-efficient algorithm. Section 4 proposes the TTR-MTTO approach with the train operation constraints, including position, speed and time. Case studies are performed to verify TTR-MTTO’s availability in Section 5. Section 6 concludes the paper and discusses further work.

2. Problem statement

All the parameters in this paper are configured in Table 1. The MTTO problem can be depicted as a three-dimensional diagram of “position-speed-time” in Figure 1. The backward train l+1 tracks the forward train l between the block section (s,s+1). The quasi-moving block in CTCS guarantees the safety of multi-train tracking, i.e. the farthest position of the backward train l+1 cannot cross xl+1,ΓEOA at the next time instant Γ+1, where xl+1,ΓEOA equals the current position xl,Γ for train l at time instant Γ minus the specified protection distance d. If there is temporary speed restriction (TSR) along the railway line, train l+1 adjusts its trajectory by taking xl+1,ΓEOA as the end position of the braking curve.

The train timetable stipulates the arrival/departure times that also indicate the start and end time instant of MTTO’s calculation. Multiple trains optimize their tracking trajectories, determining TTR’s arrival/departure times at the subsequent stations. Consequently, there is a mutual influence and collaboration between the two problems of TTR and MTTO. With the spatiotemporal constraints and mutual information in CTCS and CTC, this paper aims to calculate multi-train tracking trajectories to generate a time-efficient train timetable.

3. Single-train trajectory optimization model and algorithm

Before determining multi-train trajectories of the TTR-MTTO problem, we should calculate the time-efficient single-train trajectory. Firstly, a single-train trajectory optimization model (STTO) is established based on train dynamics and the conversion relationship of train operating conditions. Then, a STTO algorithm is proposed with the TSR constraints.

3.1 STTO model

High-speed trains along the line are mainly subjected to traction F(v), braking force B(v), basic resistance W₀ and additional resistance W₁. We can obtain F(v) at the current speed v in the “speed-traction force” curve. B(v) is calculated similarly to F(v). W₁ will produce when the train enters the ramp, curve and tunnel sections. Moreover, we mainly consider the additional resistance caused by ramps. W₀ is calculated by the empirical formula (Peng & Liu, 2009), i.e.

(1)W0=α1+α2⋅vl,x+α3⋅(vl,x)2

where W₀ is a quadratic function of train speed vl,x.

The train running conditions in different forces are divided into traction, cruising, coast and braking. The resultant force C(v) under different running conditions is calculated as

(2)C(v)={F(v)−W0−W1,traction0,cruising−W0−W1,coast−B(v)−W0−W1,braking

where cruising is the train running condition with partial traction or partial braking to keep the train running at a theoretically uniform speed. Coasting means that the train does not perform traction or braking force but only relies on the basic resistance and additional resistance to accelerate or decelerate. Notably, braking cannot be converted directly to the other three conditions but must be transitioned through the coast condition.

The train kinematics parameters at each position determine the arrival/departure times of the train timetable. We adopt the distance step method to calculate the train kinematics parameters, i.e. assuming that the resultant force on the train equals a constant within the relatively small distance step Δ x. The train kinematics parameters, including acceleration, speed and time are computed as follows.

1. Acceleration

(3){al,x=Cl,x(v)/mal,x≤amaxal,x≤δmax⋅ΔΓl,x−1,x+al,x−1

where the acceleration al,x of train l at position x is constrained by the maximum acceleration amax and maximum impact rate δmax. The variable ΔΓl,x−1,x is the running time of train l within the distance step (x−1,x).

1. Speed

(4){vl,x=(vl,x−1)2+2⋅al,x⋅Δ xvl,x≤v∼l,xk         

for vl,x and vl,x−1 are the speed of train l at position x−1 and x. v∼l,xk is the TSR value when train l runs to position point x due to the influence of the kth TSR section.

1. Passing time

(5)Γl,x=Γl,x−1+ΔΓl,x−1,x=Γl,x−1+vl,x−vl,x−1al,x

where Γl,x approximately equals to the passing time Γl,x−1 of train l at position x−1 plus the running time ΔΓl,x−1,x within the distance step (x−1,x).

3.2 STTO algorithm

Since the objective function of TTR-MTTO is the total train delay, we mainly use the time-efficient driving strategy to generate the single-train trajectory. The time-efficient driving strategy consists of the train operating conditions of “maximum traction – cruising – coast – maximum braking” (Howlett, 1990). Moreover, the energy-efficient driving strategy is also considered as the secondary strategy. Therefore, the train kinematics parameters are calculated by a STTO algorithm based on the time-efficient (primary) and energy-efficient (secondary) driving strategies. Due to the influence of TSR, block section and station, the high-speed railway line is divided into different sections. The steps of the STTO algorithm are illustrated as follows.

1. Denote the left boundary point of each section as the starting point. Then, solve the train’s speed using Formula (4) under the maximum traction-cruising curve.

2. Denote the right boundary point of each section as the starting point. Then, solve the train’s speed using Formula (4) under the maximum braking-cruising curve.

3. The train’s actual speed in STTO is equal to the minimum value under the maximum traction-cruising curve in Step (1) and the maximum braking-cruising curve in Step (2). Then, calculate the other train kinematics parameters using Formulas (3) and (5).

In Step (1) and Step (2), if the train’s speed under maximum traction-cruising or maximum braking-cruising is greater than the speed restriction value of the current section, the train only applies partial traction force or partial braking force to make the train’s actual speed equal the speed restriction value. According to the above steps, the flow chart can be illustrated in Figure 2.

4. TTR-MTTO approach

The high-speed railway network has massive station nodes easily influenced by unexpected emergencies that may cause widespread delays among multiple trains. It is difficult to model and address the TTR-MTTO problem because of strong coupling and nonlinear spatiotemporal constraints. Therefore, a novel TTR-MTTO approach is proposed based on the mutual information in CTCS and CTC.

Unlike the model-based method, we adopt a data-driven approach to optimize the multi-train tracking trajectories with the constraints of TSR and the maximum length of movement authority (MA). The multiple trains in the considered time domain are divided into the first train and other tracking trains. The first train's end of authority (EOA) is always the location of the approach signal at the next stopping station. Therefore, the first train’ s trajectory under the TTR-MTTO method directly reads the corresponding data under the STTO algorithm in Section 3.2. The other trains’ trajectories are calculated with the constraint of TSR and MA according to the real-time position of the forward train. The steps of TTR-MTTO are illustrated as follows.

1. Collect spatiotemporal information in the high-speed railway signaling system.

The necessary spatiotemporal information is the input data of the TTR-MTTO approach. We collect the following spatiotemporal information according to the mutual process between CTCS and CTC.

CTC: the time range and spatial range of the TSR section; the departure sequences and departure times of multi-train at the original station; line parameters including ramps, slopes, neutral zones and TSR.

Radio Block Center (RBC): single-train's position, speed and passing time; MA request.

Computer-based interlocking (CBI): available route information; status of track circuit.

1. Establish the TSR constraints.

Since RBC updates the train position in a time step of 1 minute, let Γ∈{Γstart,Γstart+1 ,⋯,Γend−1,Γend} denote the current time instant. The entire time domain of TTR-MTTO’s calculation is [Γstart,Γend]. The time range and spatial range of the kth TSR section are [Γleftk,Γrightk] and [xleftk,xrightk], respectively.

If there is no TSR along the high-speed railway line, the backward tracking train can directly read the corresponding data under the STTO algorithm in Section 3.2 as its trajectory. Instead, while calculating the multi-train tracking trajectories, the TSR constraint requires to be considered. Firstly, determine whether the backward tracking train l+1 is affected by TSR at the current time instant Γ.

The diagram of TSR influencing the backward tracking train l+1 can be described in Figure 3. The judgment basis can be designed as

(6)xl+1,ΓEOA>xleftk or xl+1,Γ<xrightk,Γ∈[Γleftk,Γrightk]

1. Calculate EOA and its speed of the backward tracking train.

According to the forward train l’s position xl,Γ−1 at the last time instant Γ−1, we calculate the EOA xl+1,ΓEOA and its speed vl+1,ΓEOA of the backward tracking train l+1 in the quasi-moving block system, i.e.

(7){xl+1,ΓEOA=xl,Γ−1−Ltrain−Lblock−Lsafevl+1,ΓEOA=0

where Ltrain is the train length, Lblock is the distance between the backward train and its nearest block section and Lsafe is the protection distance to prevent collision between the forward and backward trains.

1. Optimize the trajectory of the backward train.

According to the train operating condition’s composition of the time-efficient driving strategy, we calculate the multi-train trajectories to satisfy the objective of the TTR-MTTO approach. With the constraints of TSR and EOA, the heuristic method of optimizing the trajectory for the backward tracking train l+1 can be described in Figure 4, i.e.

• (4.1) Perform the maximum traction-cruising condition from xl+1,Γ to xl+1,ΓEOA.

• (4.2) Apply the maximum braking-cruising condition from xl+1,ΓEOA to xl+1,Γ.

• (4.3) The train’s actual speed at each position within [xl+1,Γ,xl+1,ΓEOA] equals the minimum value under the maximum traction-cruising condition in Step (4.1) and the maximum braking-cruising condition in Step (4.2).

  1. Generate the time-efficient train timetable.

The tracking trajectory of each train in the time domain [Γstart,Γend] is calculated by the heuristic method in Step (4). In this way, we can predict all trains’ arrival times, based on which the final time-efficient train timetable is generated.

In summary, the TTR-MTTO approach gives the recommended TTR solution to reduce the total train delay under the tight tracking condition of multiple trains, i.e. to optimize the train trajectory in the next block section with the planned departure time at the current station.

5. Numerical experiment

To validate the effectiveness of the proposed TTR-MTTO approach, we perform the numerical experiment on the actual high-speed railway and Electric Multiple Units (EMU). The planned arrival time of the single-train is calculated in the STTO algorithm without TSR. Then, a typical scenario of TSR is installed to verify that TTR-MTTO can directly generate the time-efficient train timetable. Finally, the superiority of TTR-MTTO is demonstrated in reducing total train delay compared with the traditional TTR approach.

5.1 Scenarios setup

The TTR-MTTO approach is performed on the Beijing-Tianjin high-speed railway, among which the immediate stations are Yizhuang, Yongle, Wuqing and Nancang. Nancang is a station that does not alight and board passengers. The EMU adopted is CR400AF. The parameters of the railway line and CR400AF are configured in Table 2. The time step of RBC updating MA is 1 min. To make a trade-off between the computation efficiency and solution equality of calculating the train trajectory, we refer to Wang, Zhang, and Yan, Ding (2022a) and install the distance step Δ x as 10 m. The numerical experiment runs in C++ programming language with Intel Xeon Gold 5218 CPU@2.30 GHz and 32.0 GB RAM.

As for the TSR scenario, the speed restriction range is 40 km to 60 km of the Beijing-Tianjin high-speed railway. The value of TSR is 200 km/h. Denote the time domain from 6:20 to 6:40. Consider six trains in the time domain from 6:00 to 7:20.

5.2 Result analysis

We use the STTO algorithm to predict the first train’s planned arrival time at each station without TSR, as listed in Table 3. The first train departs from Beijing South at 6:00. Notably, the arrival time (i.e. 6:25:45) of the train at Tianjin minus 6:00:00 equals the planned running time from Beijing South to Tianjin. This time is used to calculate the total train delay in the train timetable under the TSR scenario.

The traditional TTR approach (T-TTR) of dispatchers is used to verify the performance of TTR-MTTO. We adopt the above two approaches to calculate the results and changes of the following evaluation indexes, including the total train delay (TTD), the total energy consumption (TEC) and the computation time (CT), as shown in Table 4.

Since the rescheduling solution in TTR-MTTO is obtained with the tracking relationship and space-time constraints between multiple trains, TEC and CT in the proposed approach are larger than those in T-TTR. However, TTR-MTTO can reduce TTD by 60.60% compared with T-TTR due to the increasing traffic density. More time and spatial are available in TTR-MTTO to help dispatchers reduce the total train delay along the railway line.

Using TTR-MTTO, Figure 5 presents the multi-train tracking trajectories, which can also be used as the overspeed protection curve of the six trains. It can be seen that the six trains depart on schedule at Beijing South and operate closely in the block section from Beijing South to Tianjin. The trajectories can be transmitted from RBC to the trains within the jurisdiction to help safe driving. Notably, the horizontal projection in Figure 5 is also the rescheduling solution, from which the time-efficient train rescheduled timetable in TTR-MTTO is generated, as drawn in Figure 6. The solid and dotted lines represent the train rescheduled timetable in the TTR-MTTO and T-TTR approach, respectively. With the tight tracking mode in TTR-MTTO, the third to fifth trains can effectively use the buffer time in the block section to eliminate some train delays.

We can conclude that TTR-MTTO can assist the dispatcher in adjusting the train timetable and reduce the number of manual operations by dispatchers. Reducing dispatchers' work intensity can further improve the operation efficiency and emergency response capacity of high-speed railways.

6. Conclusion

1. This paper considers the TTR problem from the perspective of multi-train optimization control. Firstly, a single-train trajectory optimization model is established based on train dynamics and operating conditions. The train kinematics parameters are calculated to form the arrival/departure times of the train timetable. A STTO approach with the time-efficient strategy is adopted to optimize the single-train trajectory.

2. With the spatiotemporal constraints and mutual information in CTCS and CTC, the data-driven TTR-MTTO approach is developed to optimize the multi-train tracking trajectories. The constraints of TSR and EOA are decoupled to calculate the trajectory of the backward train. Each train's tracking trajectories in the time domain are integrated to generate the final time-efficient train timetable.

3. The numerical experiment is performed on the Beijing-Tianjin high-speed railway line and EMU. Compared with the traditional TTR approach, the proposed TTR-MTTO approach can effectively reduce the total train delay. The multi-train tracking trajectories in TTR-MTTO can be used as the overspeed protection curve to help safe driving. The time-efficient train timetable is generated automatically to assist dispatchers in adjusting the stage plan.

4. The TTR-MTTO approach can be used as a function module in CTC to improve the efficiency of railway management and emergency response. In our further study, we will consider optimizing multi-train tracking trajectories of the TTR-MTTO approach to reduce the total energy consumption and improve the computation efficiency based on the mode of “virtual coupling”.

Figures

Figure 1

Diagram of TTR-MTTO

Figure 2

Flow chart of the STTO algorithm

Figure 3

Diagram of TSR influencing the backward tracking train

Figure 4

Diagram of optimizing the trajectory for the backward tracking train

Figure 5

Multi-train tracking trajectories in TTR-MTTO

Figure 6

Train rescheduled timetable in TTR-MTTO and T-TTR

Table 1

Parameters of this paper

Notations	Definition
L	total number of trains
S	total number of stations
X	total number of positions
l	train index, l∈{1,2,⋯,L}
s	station index, s∈{1,2,⋯,S}
x	position index, x∈{1,2,⋯,X}
Γ	current time instant
xl+1,ΓEOA	position of end of Authority (EOA) for train l+1 at time instant Γ
vl+1,ΓEOA	speed of EOA for train l+1 at time instant Γ
xl,Γ	current position for train l at time instant Γ
xl+1,Γ	current position for train l+1 at time instant Γ
vl,x	current speed for train l at position x
Lsafe	protection distance
F(v)	maximum traction force
B(v)	maximum braking force
W0	basic resistance
W1	additional resistance
Cl,x(v)	resultant force train l at position x
Δ x	distance step
al,x	acceleration for train l at position x
amax	maximum acceleration
m	train mass
δmax	maximum impact rate
ΔΓl,x−1,x	time interval of train l between distance step (x−1,x)
v∼l,xk	speed restriction value of train l running to position point x due to the influence of the kth TSR section
Γl,x	passing time for train l at position x
Γstart	start time of TTR-MTTO’s calculation
Γend	end time of TTR-MTTO’s calculation
Γleftk	start time of the kth TSR section
Γrightk	end time of the kth TSR section
xleftk	start position of the kth TSR section
xrightk	end position of the kth TSR section
Ltrain	train length
Lblock	distance between the backward train and its nearest block section

Source(s): Authors own work

Table 2

Parameters of the numerical experiment

Type	Parameters	Value	Unit
line	Total line length	117040	m
	Speed restriction in station throat area	80	km/h
	Length of block section	1950	m
	Protection distance	110	m
CR400AF	Mass	501000	kg
	Length	209	m
	Maximum speed	350	km/h
	Maximum acceleration	1	m/s2
	Maximum impact rate	0.5	m/s3

Source(s): Authors own work

Table 3

Planned arrival time of the first train

Station	Position	Planned arrival time
Beijing South	K1 + 105	6:00:00
Yizhuang	K22 + 285	6:07:15
Yongle	K46 + 565	6:10:24
Wuqing	K84 + 454	6:16:54
Nancang	K107 + 969	6:20:57
Tianjin	K118 + 144	6:25:45

Source(s): Authors own work

Table 4

Evaluation indexes in TTR-MTTO and FSFS

Approach	TTD		TEC		CT/s
	Result/s	Change	Result/kW·h	Change	Result	Change
T-TTR	768.64	/	9299.28	/	96.81	/
TTR-MTTO	302.84	↓60.60%	9864.93	↑6.08%	175.97	↑81.77%

Source(s): Authors own work