《1. Introduction》

1. Introduction

Trains are likely to deviate from train operation plans during their operation and produce headway and route conflicts as a result of the influences of factors such as the weather, geological conditions, and driver and train performance. Therefore, dispatchers often need to make some adjustment to conflicts, on the premise of keeping subsequent operation plans unchanged, and without considering disturbances. Obviously, these assumptions do not align well with the real world. Previous studies on the train delay propagation law [1-3], the dynamic properties of train delays [4,5], and the operation adjustment decision making have proposed adjusting the buffer time as the major way to eliminate headway conflicts or having simulated subsequent train operations by introducing stochastic disturbances [6-10]. Considering that the train timetable is operated periodically and that daily delay information including where, when, and how long can be recorded, we can sum up the delay distribution law and obscure the time interval in a train timetable in order to simulate the subsequent train operation status based on these historical time data. This approach is much more realistic and valuable than stochastic disturbances.

Murata [11] and Zhou et al. [12] discussed temporal uncertainty and fuzzy timing in a high-level Petri net model with four fuzzy time functions and algorithms for performing the reasoning. This method was applied to check the consistency of temporal knowledge during operation planning by Ye et al. [13] and Liu et al. [14]. Wen et al. [15,16] proposed a method for distinguishing and predicting train operation conflicts based on triangular fuzzy number workflow nets. These studies provide insight into how actual operational data can be used to improve the reliability of conflict prediction results. The aim of this paper is to discuss the following research questions:

•How can the time interval in a train timetable be obscured based on the historical time data?

•What are the decision conditions to headway conflict, and how can the conflict prediction results be presented?

•What is the advantage of the fuzzy temporal knowledge reasoning method in practical application, compared with the current method?

The remainder of this paper is organized as follows: Section 2 models a train timetable based on a timed place Petri net and explains how to obscure the time interval based on historical time data. Section 3 proposes the judging conditions for two different types of conflicts and the evaluation indexes for conflict prediction results presentation. Section 4 takes the Beijing South-Jinan West railway line as an example. Conflict predictions with or without additional perturbations are simulated and the amount of available information in two different reasoning methods is compared, proving the feasibility and effectiveness of the fuzzy temporal knowledge reasoning method.

《2. Modeling and pre-processing a high-speed railway timetable》

2. Modeling and pre-processing a high-speed railway timetable

《2.1. Modeling a train timetable based on a timed place Petri net (TPPN)》

2.1. Modeling a train timetable based on a timed place Petri net (TPPN)

Train timetables have been modeled using different simulation tools and mathematical methods in previous studies. Petri net theory is one of the theories used for timetable modeling, and has been previously applied to train timetable modeling and analysis [2,17,18]. The timed Petri net (TPN) theory is one of the important branches of Petri net theory, and can be divided into the timed transition Petri net (TTPN), timed place Petri net (TPPN), and timed arc Petri net (TAPN) theories, according to the different temporal factor distributions involved [2]. Considering that only the time delay in TTPN is satisfied, and that the state marking of the subsequent places can be changed, the state marking can be easily misunderstood. Therefore, we adopted TPPN as the modeling tool to ensure that the state marking at any time in the model can be explained in an unambiguous way. A high-speed railway train timetable can be modeled based on TPPN as follows:

where,

• N is the TPPN model of a high-speed railway train timetable;

• P  = { p₁, p₂,…, p_m}, the finite place set, representing the temporal constraints between adjacent train actions and satisfying the conditions that P∪T=∅∧P∩T=∅;

• T  = { t₁, t₂,…, t_n}, the finite transition set, representing the train operations at station and satisfying the conditions that P∪T=∅∧P∩T=∅;

• Pre: P  ×  T  → {0, 1}, the preceding related functions;

• Post: T  ×  P  → {0, 1}, the posterior related functions;

• TD: P  →  time, the mapping function from the place of the time interval; and

• K, W, and M₀ are the place capacity function, directed arc weight function, and initial identification, respectively. In this model, K  =  W  = 1, which means that a train only has one accurate statement at any time.

Fig. 1 is an example of a high-speed railway train timetable for three trains ( Tr₁, Tr₂, Tr₃) and four stations ( S₁, S₂, S₃, S₄). We build the TPPN model shown in Fig. 2 for this timetable. In this figure, the subscripts using Arabic numerals represent trains or stations and the subscripts using Roman numerals represent sections.

《Fig. 1》

Fig.1 A sample of high-speed railway train timetable.

《Fig. 2》

Fig.2 Model of train timetable sample.

As seen in this example, any train operation plan is a sequence of operational stations and time intervals between adjacent operations. Given these characteristics of a train timetable, its TPPN model has the following features. First, there are three types of transitions, representing train departures, train arrivals, and trains passing through. Two place types exist: the state of a train being at a station, where the delay time is the time interval between adjacent train operations; and the state of a train being in the section between stations, where the delay time is the running time at that interval. Second, a preceding train operation (the preceding transition) imposes restrictions on a train’s succeeding operation (the succeeding transition) or on that of an adjacent train. In the meantime, the succeeding transition is restricted only by the preceding transition at the station and the schedule time of the train operation. Based on these characteristics, the transformation from a train graph to a TPPN model is simple and direct and lays the foundation for simulating the fuzzy temporal knowledge reasoning process.

《2.2. Trapezoidal fuzzy number and fuzzy processing》

2.2. Trapezoidal fuzzy number and fuzzy processing

In real-world systems, the total duration of any event can be a certain value or a time interval that encompasses the earliest finish time and the latest finish time. Obviously, the time interval expresses more information than a certain value. Furthermore, fuzzy processing of a planning time interval is the objective reflection of uncertainty in a system’s actual operation, which can improve system compatibility and better reflect system performance. The fuzzy trapezoidal time function, which is transformed from a time interval, can be defined as follows:

where, h is the maximum possibility of T; c is the latest finish time; b is the earliest finish time, and section ( a, b), ( c, d) is the time interval range. Fig. 3 is a graphical representation of a trapezoidal fuzzy number.

《Fig. 3》

Fig.3 Fuzzy trapezoidal time function.

Considering that the trapezoidal time function can express more information and provide a sound basis for the fuzzy temporal knowledge reasoning method, how the time interval can be transformed to a trapezoidal time function should be studied.

2.2.1. Transformation from a certain value to a time interval

As modeled in Section 2.1, the time interval between adjacent train operations in a train timetable is a certain value and is assigned to the corresponding place. Considering the preset buffer time, which is the difference between two adjacent trains’ departure time at a station, should be added into a timetable.

2.2.2. Transformation from a time interval to a trapezoidal time function

As the train timetable is operated periodically, the related operating units can collect a large quantity of operational data from the actual use of the train timetable. Every train’s arrival and departure time at each station can be recorded for the experimental period, such as one month or two months. In particular, it should be explained that the train timetable should remain constant in the experimental period, in which the daily operation can be repeated and no special status occurs. When all the historical time data are prepared, the statistical analysis can be done. Taking one time interval Δ tas an example, it is observed and recorded n times in the experimental period. After subtracting the planned time interval from the observed one n times, the values are recorded and their mean value µ and normalized variance σ can be calculated. Assuming that the values are normally distributed, the confidence interval at a confidence level α can be predicted by the following formula:

where, z_α/2 can be achieved by querying the standard normal distribution chart based on the confidence level α. Then the trapezoidal time function of this time interval is (Δt−r+μ−z_α/2× , Δt−r, Δt, Δt+μ−z_α/2× ),  where r is the preset buffer time in this time interval.

《3. Conflict prediction》

3. Conflict prediction

《3.1. Conflict types and judgment condition》

3.1. Conflict types and judgment condition

In China, the minimum interval between adjacent train operations in high-speed railway train timetables, I_min, is typically 5 min [19]. As defined in the literature [16], a train operation conflict occurs when two trains need to use the same technical equipment or train path at the same time. Based on this definition and considering the temporal constraints in a high-speed railway train timetable, a conflict is taken in this paper to be a situation in which a train cannot satisfy the minimum time interval requirement. Depending on whether a conflict occurs, the conflicts in a train timetable can be divided into two types, as described below.

3.1.1. Potential conflict

A potential conflict (PC) is the state in which the preset buffer time is sufficient to dissipate the influence of the train’s delay so that the minimum interval is still satisfied. The hidden trouble is still present and may evolve into a certain conflict after delay propagation.

Fig. 4(a) illustrates an example in which the occurrence time of transition t₁ is later than the planned time stamp, which leads to the actual train path deviating from the planned one. Assuming that the fuzzy occurrence times of transition t₁ and transition t₂ are o( t₁) = ( A, B, C, D) and o( t₂) = ( E, F, G, H), respectively, the requested minimum interval is I_min, and the actual interval is I. A diagram of transition t₁, transition t₂, and the actual interval I is shown in Fig. 4(b). If and only if the condition I  ≥  I_minis satisfied, the conflict is temporarily avoided. However, as the delay of transition t₁ still exists, it cannot be taken as certain that the delay propagation will not result in any other conflicts.

《Fig. 4》

Fig.4 Conflict type judgment. (a) Potential conflict (PC); (b) actual interval, I; (c) certain conflict (CC).

3.1.2. Certain conflict

A certain conflict (CC) is the state in which all of the measures that can reduce a train’s delay have been perfectly used, yet the actual interval still cannot meet the minimum interval requirement. As a result, a conflict will occur. As shown in Fig. 4(c), there is a conflict between transition t₁ and transition t₂, even though the delay in the arrival of transition t₂ weakens the influence of transition t₁. It can be concluded that a CC can occur when the constraint I  <  I_min is satisfied.

《3.2. Conflict measurement index》

3.2. Conflict measurement index

When a train is delayed because of some internal or external disturbance, the succeeding trains will be influenced due to delay propagation, and the scope of influence will gradually expand. Conflicts may occur to different degrees during this process. Conflict possibility measurement can be performed in two ways, as described below.

3.2.1. Deviation of a single train

For any single train, the planned operation time in a high-speed railway train timetable is expressed by the time stamp π( τ). When any delay occurs, the degree of deviation from the planned train path can be seen as the consequence of the initial delay and the primary cause of the succeeding conflicts. We assume that the planned train operation time stamp and the actual time stamp of train i for operation j are (τ)=(A,B,C,D) and (τ)=(E,F,G,H), respectively. When the condition (τ)=(τ) is satisfied, we can conclude that train i at operation j has deviated from the plan, as shown in Fig. 5. In this case, the degree of deviation of train i at operation j can be calculated according to the following formula:

《Fig. 5》

Fig.5 Deviation of a single train.

where, S( ABCD) is the area of trapezoid ABCD; S( ABCD∩ EFGH) is the overlapping part of the areas of trapezoids ABCD and EFGH. The average degree of deviation of train i can be calculated as follows:

where, Δis the sum of train i’s operations. Apparently, the greater the degree of deviation is, the higher the conflict possibility can be.

3.2.2. Conflict possibility between adjacent train operations

In this case, the train operation conflict occurs between adjacent transitions. According to the judging rules, when the condition I  <  I_min is satisfied, a headway conflict may occur. Therefore, the first task is to identify the conflict type when a train delay occurs. If the conflict is a PC, it can be avoided, and possibility conflict measurement is unnecessary. Otherwise, possibility measurement is performed in the following way.

Fig. 6(a) shows an example of a temporal constraint between transition t₁ and transition t₂. We assume that the fuzzy occurrence time of transition t₁ and the fuzzy enabling time of transition t₂ are o( t₁) = ( A, B, C, D) and o( t₂) = ( E, F, G, H), respectively, and that the condition I  <  I_min is satisfied. In this case, the minimum buffer time requested to resolve the conflict can be computed as R  =  I_min  -  I. The available buffer times of transition t₁ and transition t₂ are =C−B and =G−F, respectively. The fuzzy time functions of transition t₁ and transition t₂ should be updated as described below.

《Fig. 6》

Fig.6 Conflict possibilities between adjacent trains. (a) Before conflict reduction; (b) after conflict reduction.

According to the rules of buffer time usage for train operation adjustment, the previous buffer time takes priority and is used first. The surplus buffer time of transition t₁ is =max{−R,0}. If −R≥0, the conflict has been resolved, and the buffer time  remains unchanged. Otherwise, the surplus redundancy time of transition t₂ is =max{+−R,0}. After the maximum possible conflict is resolved, the updated time interval between the two transitions is I′=+−R−I_min, and the updated fuzzy time functions of the two transitions are o(t₁)=(A,B,B+,B++D−C) and o(t₂)=(E+−r′,F+−,G,H), respectively, as shown in Fig. 6(b). The change in the shaded area reflects the conflict resolution results. By this time, the conflict possibility between transition t₁ and transition t₂ is as follows:

The higher the conflict possibility is, the greater the likelihood is that the succeeding train will suffer from delay propagation.

3.3. Conflict prediction algorithm

In this study, conflict prediction for a high-speed railway train timetable was conducted using a Structured Query Language (SQL) server and the C# simulation platform. The SQL server was used to store the initial train timetable, actual operational data, and the fuzzy delay times of the time intervals after fuzzy processing, based on the actual operational data. The C# simulation platform was used to import the original data from the SQL server, transform the original data into incidence relations between transitions and places in the TPPN model, assign the fuzzy delay times to places, predict conflicts based on fuzzy temporal knowledge reasoning, record the simulation data, calculate the values of the evaluation indexes, and output the results. Conflict prediction is performed according to the following steps:

Step 1: The original data is collected and pre-processed, including the train timetable and its actual operational data. Before proceeding to the next step, the time intervals in the train timetable should be obscured based on the actual operational data and distributed to the corresponding places as fuzzy delay times.

Step 2: Conflict prediction is performed, based on fuzzy temporal knowledge reasoning, from left to right and from top to bottom. If there is a temporal constraint between two adjacent transitions, a conflict judgment should be performed. If the conflict is a CC, the fuzzy time function of the two related transitions should be updated, and the conflict possibility δ should be calculated and recorded. After this updating, the conflict prediction continues until all of the transitions are checked. As an example, we take the conflict prediction between transition t₁₁ and in Fig. 7; namely, the conflict check between the arrival of train Tr₁ and the passing through of train Tr₂ on S₂. For this case, the occurrence time of transition t₁₁, o( t₁₁) = (0, 0, 0, 0), and the fuzzy delay times of the related places are shown in Table 1, and the reasoning process is shown in Fig. 7.

《Fig. 7》

Fig.7 Fuzzy temporal knowledge reasoning process.

《Table 1》

Table 1

Fuzzy delay times of related places.

Step 3: Statistical analysis of the simulation results is performed. Based on the output results, the values of the evaluation indexes—that is, the average deviation degree η_i and the conflict possibility δ—are calculated and analyzed. The usage of the preset buffer time can be recorded as well and can provide helpful information for use in further train timetable adjustment decision making.

《4. Simulation examples》

4. Simulation examples

《4.1. Simulation experiment design》

4.1. Simulation experiment design

It is difficult to collect the actual operational data of an active high-speed railway train timetable in China. Therefore, we generated a high-speed railway train timetable including 6 stations and 15 trains based on the track data of the Beijing South-Jinan West railway line, as shown in Fig. 8 and Fig. 9. For the historical time data of the virtual train timetable, we simulated the time interval range by random number: The value range of the left-side time interval is 1-2 min and that of the right-side time interval is 1-3 min. Even though we replaced the fuzzy processing of the time interval with random numbers in this example, the pre-processing method proposed in Section 2.2 is still effective when it is applied to the actual train timetable if we can get the historical operation time data. Besides, the virtual train timetable and random trapezoidal fuzzy numbers do not affect the presentation of the fuzzy temporal knowledge reasoning process.

《Fig. 8》

Fig.8 Schematic diagram of the Beijing South-Jinan West railway line.

《Fig. 9》

Fig.9 An example of train timetable.

Based on these early initial data, a fuzzy train timetable where the time interval is presented as a trapezoidal fuzzy number can be modeled as a TPPN system and the fuzzy time interval is distributed to the corresponding place as a fuzzy delay time function. The simulation experiment consists of two scenarios. In Scenario 1, the conflict prediction is done in the fuzzy train timetable without any additional disturbances. As the time interval is fuzzy processed, headway conflict may occur and the conflict prediction results can reflect the train timetable quality and performances. In Scenario 2, additional disturbances are assigned to train G203, which departs from Beijing South Station 10 min later than planned. Even though the presentation of the conflict prediction results in two scenarios that are almost the same, simulating under two scenarios permits the train timetable to be evaluated and also allows the flexibility of the fuzzy train timetable to be highlighted by comparing the results of the two scenarios, while eliminating the influence of the train timetable itself.

《4.2. Analysis of simulation》

4.2. Analysis of simulation

The analysis of the two simulation results is divided into three parts. In Part 1, the conflict prediction result is presented in diagrams, which can be executed and updated once when the operational circumstance changes, such as when a new delay occurs or the dispatcher tries to do some operational adjustment. The updated conflict results will assist the dispatchers by warning of current and follow-up PCs including information about where the conflict may occur and how great the conflict possibility is. As for the operational adjustment, the two successive conflict results will evaluate its effect in advance. Part 2 compares the conflict prediction results of the fuzzy temporal knowledge reasoning method and the in-use method. As mentioned earlier, in the current method, the subsequent operation plan is assumed to be constant and only the current conflict shows in the operating screen when the dispatcher is trying to resolve a current conflict. The difference in the amount of available information in the two different methods is discussed in this part. In Part 3, the comparison between the two scenarios is done.

Part 1: Conflict prediction result presentation. The conflict prediction result is expressed based on the two evaluation indexes proposed in Section 3.2. When the conflict prediction is executed once, the deviation degree of a single train and the conflict possibility of adjacent train operations are calculated and displayed in the diagram. As shown in Fig. 10, the deviation degree of every train in the timetable is displayed, and every time interval of a train oper-ation plan can be illustrated in detail if needed. Take train G203 as an example: Fig. 10(b) shows the deviation degree of every time interval, which will help the dispatcher understand the reasons for the whole deviation. Regarding the conflict, one PC consists of four factors: Where the conflict occurs, how great the conflict possibility is, how much allowance time is needed to resolve the conflict completely, and how much of the buffer time is used here to eliminate the conflict. Overall, the dispatcher also needs to know the number of PCs. As shown in Fig. 11(a), all the PCs are displayed, and every conflict can be refined, as shown in Fig. 11(b), including the four factors of concern.

《Fig. 10》

Fig.10 Index of deviation degree. (a) Overall deviation degree of all trains; (b) deviation degree distribution of Train G203.

《Fig. 11》

Fig.11 Index of conflict possibility. (a) Conflict possibility distribution; (b) conflict content of transition pair (DT008, DT0024).

Part 2: Comparison of the two different methods. As discussed earlier, the conflict prediction result is informative and includes operational detail according to the requirement. This is important for dispatchers, in that dealing with too much information at the same time can be stressful, although dispatchers sometimes require more details in order to make decisions. In the real world, when the dispatcher needs to do some operational adjustment, the operational system will warn the dispatcher of the current conflict resolution progress by assuming that the subsequent operational train plan will be executed as a plan, and no additional perturbations will be considered. Therefore, the information about operational conflict that the in-use method provides only focuses on the current operational environment and on the result of the conflict; not on the reason for the conflict. The amount of available information these two different methods provide is compared in Table 2.

《Table 2》

Table 2

Comparison of the amount of available information.

We can conclude that the fuzzy temporal knowledge reasoning method used in this paper is much more informative and beneficial to the dispatchers, as it permits them to know what is happening in the present time and how to keep the train timetable flexible and robust.

Part 3: Comparison between two different scenarios. As shown in Fig. 10 and Fig. 11, the fuzzy train timetable without any additional perturbations still has PCs, even though the planned train timetable has no conflicts at all. The reason for this is that fuzzy processing of the time interval broadens the planned operation time interval, causing the time interval between adjacent train operations to be less than the minimum headway. This phenomenon leads to a new problem: How can dispatchers distinguish whether the PCs provided by fuzzy temporal knowledge reasoning are caused by the train timetable itself, by the new additional perturbations, or by both? Therefore, a comparison between these two different scenarios is necessary. Fig. 12 displays the conflict possibility distribution calculated by the two scenarios in a scatter diagram.

《Fig. 12》

Fig.12 Conflict possibility distribution comparisons.

It is interesting to note that the conflict possibility in Scenario 2 may descend or even descend to zero compared to Scenario 1. This means that additional disturbances in the fuzzy train timetable can contribute to eliminating or resolving the headway conflict. For example, transition pairs (DT008, DT0024) and (DT0022, DT0028) represent two adjacent train operations that need inspection of the conflict possibility. Transition pair DT008 and DT0024 means that train G201 arrives at Dezhou East Railway Station while G205 passes through Dezhou East Railway Station. Transition pair DT0022 and DT0028 means that trains G205 and G207 pass through Tianjin Railway Station. As shown in Fig. 13, the conflict of transition pair (DT008, DT0024) is resolved completely in Scenario 2, and the conflict possibility of transition pair (DT0022, DT0028) is down sharply in Scenario 2. This performance provides the insight that additional delay is not always a bad thing; a certain amount of habitual delay can somehow be incorporated into the preset buffer time in order to avoid or resolve headway conflicts. It must be said, however, that the additional delay increases the PC possibility and complicates the train operation environment.

《Fig. 13》

Fig.13 Conflict possibility comparisons. (a) transition pair (DT008, DT0024); (b) transition pair (DT0022, DT0028).

《5. Conclusions and future work》

5. Conclusions and future work

Compared to random disturbances, the fuzzy processing of time intervals in a train timetable based on historical time statistics is closer to the actual conditions. This is the foundation for obscuring the train timetable and predicting PCs based on the fuzzy temporal knowledge reasoning method. The simulation experiment was designed under two different scenarios and, according to the result comparison and analysis, we can draw the following conclusions.

(1) A fuzzy train timetable may have PCs, and the indexes proposed by this paper will help traffic management units to know the quality of the planned train timetable and what the causes of conflict are. This knowledge will assist in timetabling, especially in the preset buffer time distribution.

(2) Conflict prediction based on fuzzy temporal knowledge reasoning provides more available information for the dispatchers, compared to the in-use method, which deviates from the actual state by assuming that the subsequent train plan will not be disturbed at all. The conflict prediction simulated by this new method will help the dispatcher to master the comprehensive influence of the new operational circumstance and to evaluate the adjustment effect by traversing the prediction algorithm.

(3) An interesting finding during the simulation result analysis was that additional delay may eliminate a PC; this finding goes against the common-sense assumption that a delay is always a bad thing and the chief culprit in reducing the flexibility and robustness of a train timetable. This finding provides us with the insight that a certain amount of habitual delay can somehow be incorporated into the preset buffer time in order to avoid or resolve headway conflicts.

Future research is recommended in the following directions: First, an impact analysis should be performed on the size and network distribution of the time allowance and the time intervals on train delay propagation; and second, an examination should be done on how to use fuzzy temporal knowledge reasoning results to effectively support train rescheduling in real time.

《Acknowledgements》

Acknowledgements

This work was supported by the National Nature Science Foundation of China (U1234206 and 61503311). We acknowledge support under the Railways Technology Development Plan of China Railway Corporation (2016X008-J) and the Fundamental Research Funds for the Central Universities (2682015CX039). Parts of this work were supported by the National United Engineering Laboratory of Integrated and Intelligent Transportation. We are grateful for useful contributions made by our project partners.

He Zhuang, Liping Feng, Chao Wen, Qiyuan Peng, and Qizhi Tang declare that they have no conflict of interest or financial conflicts to disclose.