# Discrete Optimization on Train Rescheduling on Single-Track Railway: Clustering Hierarchy and Heuristic Search

Authors: Zhengkun Zhang; Changfeng Zhu; Wenhu Ma
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

This paper focuses on discrete dynamic optimization on train rescheduling on single-track railway with the consideration of train punctuality and station satisfaction degree. A discrete dynamic system is firstly described to mimic train rescheduling, and a state transition function is specially designed according to the train departure event. The purpose of this function is to improve simulation efficiency by directly confirming the next discrete time. After the construction and analysis of optimization models to discrete dynamic system, a two-stage heuristic search strategy is developed, by using clustering hierarchy theory and stochastic search strategy, to obtain train departure time and arrival time before each state transition of the system. Finally, a numerical experiment is conducted to verify the proposed system, models, and the heuristic search strategy. The result shows that the discrete dynamic system, together with the state transition function and heuristic search strategy, shows better performance in simulation efficiency and solution quality.


---

## Body

## 1. Introduction

Railway transportation plays a significant role in transportation market. Due to the large scale of railway network and the high density of train operation, railway transportation is almost impossible to organize like road transportation [1]. In order to reduce workload and ensure safety, a special organization pattern is generally adopted by railway transportation companies in China; that is, stations and segments in one railway corridor are put under several different dispatching districts, and train dispatchers are appointed to organize train operation in their respective districts. A simplified organization and management of train operation is shown in Figure 1.Figure 1
A simplified organization and management of train operation.In normal case, train operation is well-organized by train dispatcher according to the original train timetable, in which train arrival time and departure time at each station are specially planned [2, 3]. However, original train timetable is usually violated in practice because of some unexpected factors, such as excess dwelling time [4], extended traveling time [5], and infrastructure failure [6]. If the violation is not serious, it can be eliminated without leading to extra disruption by using the buffer time reserved in original timetable. Otherwise, appointed train dispatcher will take some efficient measures to reorder the related trains to follow the original train timetable as far as possible [7]. This is the so-called train rescheduling problem (TREP).TREP is associated with train scheduling, but obviously different. Train scheduling focuses on train preplanning with the purpose to generate an original train timetable, during which some objectives are primarily considered, such as the number of running trains [8], passenger traveling time [9], energy consumption [10], and even the flexibility of train timetable [11, 12]. However, TREP is the train real-time control, during which recovering train order and guaranteeing train punctuality within limited operating time are the primary goals [13, 14]. Essentially speaking, train departure time and train arrival time at each station are the core decision variables to TREP. The selection of reasonable station for train meet and overtake (M&O) or train meet and pass (M&P) are the critical adjustment measures in TREP [15]. For a double-track railway, as some fixed infrastructures, like rail track and signal, are used by inbound train and outbound train, respectively, M&P caused by inbound train and outbound train is unconspicuous. However, inbound train and outbound train on single-track railway share the infrastructures mutually, and only one train can be allowed to occupy one segment at the same time. Therefore, stations for train M&O or M&P on single-track are extremely difficult to confirm in TREP.TREP has been proved to be an NP-hard problem. Tracking back to existing researches, it remains an interesting and changeling topic in operation research [16]. Thereinto, job-shop scheduling theory [17], graph theoretic approach [18], and event-activity network [19] are generally adopted to describe their problems at microscopic level or macroscopic level. The advantage of these researches is that aforementioned theories and approaches have been well-studied in computational sciences, and some existing algorithms can be directly embodied to deal with their models [20]. However, they are difficult to reflect the dynamic process of train operation. Some particular constrains, such as station capacity constrain and segment occupy constrain, have to be simplified. In order to present the problem exhaustively, some other scholars describe their problems from the perspective of time-space network [21]. In their descriptions, two kinds of nodes are used to denote train arrival points and train departure points, and the arcs connecting different nodes will be the potential train trajectories. By this way, majority of constrains can be clearly formulated according to the time that nodes are associated and the numbers that related arcs are connected [22]. However, this method may be unsuitable for TREP on single-track railway in that fixed infrastructures are shared by inbound train and outbound train mutually. Besides, technical operation of dwelling train on single-track railway is various, and they are difficult to depict by using time-space network.System simulation is another efficient method to deal with train scheduling or TREP. For the problem of periodic train scheduling, Goverde et al. [23] construct a linear recursion system by using max-plus linear theory. Thereinto, the state of recursion system is driven by a train arrival event and a train departure event. Similarly, a discrete event dynamic system (DEDS) driven by state transition function is also proposed in [24, 25]. However, the difference is that the designed state transition function is based on a train arrival event in that it is associated with the majority of potential collisions. In the DEDS, the precondition of the motivation of state transition function is that a train arrival event occurs without any potential collision. With this reason, train advance strategy (TAS) is specially provided to repeatedly check the status of all trains and stations before the determination of a departure event. Whereafter, once the arrival event is motivated, the discrete time of next arrival event needs to be confirmed by using the state transition function, during which the state of all trains that are running at a segment needs to be checked secondly (for more details, see [24, 25]). In fact, a train arrival event and train departure event depend on each other, and it is indeed the fact in simulation technic and actual train organization [26]. Therefore, some repeated checks during the period that train is running at segment can be saved if we simultaneously confirm train departure time and next arrival time with no potential collisions. In addition, technical operation at a station requires adequate stopping time for dwelling train, during which the train cannot be departed. Therefore, the checks during this period can also be saved. In short, the fewer the times of the checks are, the higher the simulation efficiency of DEDS will be. Regretfully, it is not sufficiently considered in existing research.TAS is the core check algorithm in DEDS. Just as mentioned, the task of TAS is to confirm a reasonable departure time before each state transition. As the first version of TAS is designed for single-track railway, it is extended by Dorfman and Medanic [25] for collision checking on railway networks. In the subsequent research studies, it is further improved by Xu et al. [27] and Li et al. [28] in terms of collision release and track allocation. Compared with some calculation methods in existing research studies [29–31], TAS has the advantage in solving efficiency and solution adaptation in that it is based on the simulation of train operation in real time. During the simulation, the train with the worst time delay will be selected by TAS to occupy the free segment if there are several potential trains. This mechanism is similar to greedy strategy [32] and neighborhood search strategy [18]. However, it may increase additional burden on related stations, especially the station for M&P or M&O, in that the selected train usually decreases or lengthens train dwelling time and incurs more delayed trains. Hence, how to balance train punctuality and station burden is necessary to TREP. Unfortunately, related research studies seldomly take this problem into consideration. Essentially speaking, TAS is a local optimization strategy or search strategy, and the result obtained by this strategy is factually a local optimum solution. Therefore, designing an efficient search strategy with certain global optimization ability is also important to TREP.Based on the aforementioned analysis, our research focuses on discrete optimization on train rescheduling on sing-track railway. Thereinto, a DEDS, together with a state transition function, is previously designed. Slightly different, DEDS in this paper is presented in the form of mathematical formulation by using cumulative flow variables. By this way, potential collisions and constrains can be conveniently presented. Especially, our state transition function majorly focuses on each train departure event because the particular period that train is running at segment and dwelling at station for necessary technical operation can be saved if train departure time and next arrival time are predetermined without potential collisions. With this reason, simulation efficiency of DEDS may be improved. The purpose of our DEDS is to obtain a new train timetable that can balance train punctuality and station satisfaction degree (namely, the station burden). In order to realize this purpose, a two-stage heuristic search strategy is also provided to simultaneously determine train departure time and arrival time before each state transition of DEDS. Thereinto, the first stage is based on clustering hierarchy, in which all the trains will be divided into several reasonable hierarchies according to train priority. After that, train in different hierarchies will preempt the time windows with different qualities and collisions. The second stage focuses on stochastic search strategy for trains in each hierarchy, during which departure train will be decided among potential trains to occupy segment before state transition of DEDS. Overall speaking, our DEDS is similar to the real-time train adjustment system in [33] and we are also eager that it can be suitable for TREP with different train priorities or multiclasses train rescheduling.The remainders of this paper are organized as follows. Section2 focuses on the description of DEDS. Section 3 and Section 4 are the models and two-stage heuristic search strategy for DEDS, respectively. Section 5 is the analysis based on a numerical experiment, and some conclusions are summarized in Section 6.


## 2. Discrete Event Dynamic System of TREP

### 2.1. Preliminary

Before the description of discrete event dynamic system (DEDS), some necessary assumptions are made as follows.Assumption 1.
Our research only focuses on a dispatching district on single-track railway with semiautomatic block. There are no branch tracks in dispatching district.Assumption 2.
Train running time at segment is uniform but may be different, and it will be assigned according to time delay, collision checks, and departure time.Assumption 3.
The time for signal arrangement and train acceleration or deceleration is integrated as a uniformed and fixed one for all trains and stations.Assumption 4.
All the arrival-departure lines in each station hold ordinary technical operations, such as M&P, M&O, passenger boarding and alighting, and train temporary stopping. For other special operations, each station has an appointed yard to deal with.
Based on the assumptions, letDEDS=S,X,Y,C,Φ be a DEDS to TREP, where S is the discourse domain, X is the collection of events, and Y and C are the collections of states and constraints, respectively. Specially, Φ is the state transition function of DEDS.


### 2.2. Domains, Events, and States of DEDS

#### 2.2.1. Discourse Domain of DEDS

Discourse domain of DEDS includes object, time, and space. The object domain is trainl∈L. Here, we refer to train l running with outbound direction as l=2,4,6,… and refer to train l running with inbound direction as l=1,3,5,… . Time domain is the train rescheduling horizon 0,T with discrete step Δt, and t∈0,Tis the clock of DEDS. Space domain mainly denotes station set Z and segment set Q. The relationship between segments and stations is shown as follows:(1)q=z,z′,∀z,z′∈Z,∀q∈Q,where q is the segment index and z and z′ are the indexes of departure station and arrival station for train l, respectively. They can be expressed as(2)z′=z+2fl−1,∀l∈L,∀z,z′∈Z,where fl is a 0-1 variable to denote the train running direction,that is,fl=1,0,if trainlruns to outbound directionif trainlruns to inbound direction.Formulae (1) and (2) will be always holding in our following research, excepting the special case declared separately.


#### 2.2.2. Event Description of DEDS

Events in DEDS include departure eventXdep and arrival event Xarr. Therein, xl,zdept∈Xdep is a 0-1 decision variable denoting a departure event, that isxl,zdept=1,if stationzcan arrange the departure signal for trainlwhen clock ist0,elseBased on the decision variablexl,zdept, departure time tl,zdep can be confirmed as(3)tl,zdep+xl,zdept⋅M−t−Idep=M,∀l∈L,∀z∈Z,t∈0,T,where M is a bigger integer, which is also the initial value of tl,zdep. Idep is the minimal time for signal arrangement and train departure.Then, arrival timetl,z′arr of train l at station z′ can be formulated as (4)tl,z′arr+xl,zdept⋅M−tl,zdep−tl,qope=M,∀l∈L,∀z,z′∈Z,∀q∈Q,t∈0,T,where tl,qope∈N+ is the decision variable to denote running time of train l at segment q. Specially,(5)tl,qmin≤tl,qope≤tl,qmax,∀l∈L,∀q∈Q,where tl,qmin and tl,qmax are the minimal and maximal running time of train l at segment q, respectively.


#### 2.2.3. State Description of DEDS

The state of DEDS is associated with train departure event and train arrival event. According to departure timet^l,zdep and arrival time t^l,z′arr in original train timetable, DEDS is under the state of time delay if tl,zdep>t^l,zdep or tl,z′arr>t^l,z′arr for ∀l∈L,∀z∈Z.Letyl,zdept be an accumulative 0-1 state variable to record the state that whether train l has been departed at station z when system clock is t, that is, yl,zdept=1,iftl,zdep≤t≤T0,else.Similarly, letyl,zarrt record whether train l has arrived at station z when system clock is tyl,zarrt=1,iftl,zarr≤t≤T0,else.Based on the aforementioned definition, an illustration to accumulative state variables is shown in Figure2.Figure 2
An illustration to accumulative state variables.


### 2.3. Constraint Description in DEDS

#### 2.3.1. Train Departure Constraints

Letk∈0,1,2 denote the types of technical operation. Herein, k=0 denotes train passes through a station or stops at a station for M&P and M&O, k=1 denotes passenger train stops at a station for passenger boarding and alighting, and k=2 denotes train stops at a station for other technical operations. Then, 0-1 variable τl,zk can be defined as τl,zk=1,if operation of trainlat stationzbelongs to typek0,else.There is only one type of technical operation that trainl at station z belongs; hence, (6)∑k∈0,1,2τl,zk=1,∀l∈L,∀z∈Z.To satisfy the necessary dwelling time for different technical operations, the following formula cannot be violated:(7)∑t∈0,Tyl,zarrt−yl,zdept≥τl,zk⋅tl,zmin,∀l∈L,∀z∈Z,k∈1,2,where tl,zmin is the minimal stopping time required by technical operation of train l at station z.Passenger train appointed at stationz for passenger boarding and alighting cannot be dispatched until the clock t meets or overtakes the original departure time. That is, (8)∑t∈0,T1−yl,zdept−τl,zk=1⋅t^l,zdep≥0,∀l∈L,∀z∈Z,where t^l,zdep is the departure time of train l at station z regulated in the original train timetable.


#### 2.3.2. Departure Interval Constraint

Departure interval constraint mainly refers to the minimal time interval required by a departure station for signal arrangement and train departure. We here make an assumption that trainl is under the departure decision at station z and train l′ is the former arrival or departure one at the same station. Then, four scenarios are shown in Figure 3.Figure 3
Four scenarios in departure station constraint: (a) arrival-departure at the different segments; (b) arrival-departure at the same segment; (c) departure-departure at the different segments; (d) departure-departure at the same segment.
(a)(b)(c)(d)According to four scenarios in Figure3, the minimal time interval required by station z can be formulated by the following formulae:(9)∑t∈0,Tyl′,zarrt−yl,zdept≥I,∀l,l′∈L,∀z∈Z,(10)∑t∈0,Tyl′,zdept−yl,zdept≥I,∀l,l′∈L,∀z∈Z,where I is the minimal time required by station for signal arrangement and train departure.


#### 2.3.3. Segment Running Constraint

For a single-track railway with semiautomatic block, M&P and M&O only occur at station. Hence, scenarios in Figure4 will be strictly forbidden.Figure 4
Two trains running at segment under different scenarios: (a) two trains running at segment from opposite direction; (b) two trains running at segment from the same direction.
(a)(b)Based on the scenarios in Figure4, segment running constraint can be denoted as(11)∑l∈Lyl,zdept−yl,z′arrt≤1,∀z,z′∈Z,t∈0,T.


#### 2.3.4. Arrival Station Constraints

In order to avoid collisions and deadlocks in DEDS, arrival station constraints will be predicted and guaranteed by departure station before trainl is departed. With this reason, train departure time tl,zarr and train arrival time tl,z′arr will be determined simultaneously during the simulation:(1)
Arrival interval constraintJust as departure station constrain, the minimal time interval required by the arrival station for signal arrangement and train arrival can be denoted as follows, respectively:(12)∑t∈0,Tyl′,z′dept−yl,z′arrt≥I,∀l,l′∈L,∀z′∈Z,(13)∑t∈0,Tyl′,z′arrt−yl,z′arrt≥I,∀l,l′∈L,∀z′∈Z,whereI is the time interval required by arrival station for signal arrangement and train arrival.(2)
Station space constraintArrival station should at least have one unoccupied arrival-departure track for the approaching train. Hence, station space constraint can be guaranteed by the following formula:(14)∑l∈L∑k∈0,1,2τl,z′kyl,z′arrtl,z′arr−yl,z′deptl,z′arr<Nz′,∀z′∈Z,whereNz′ is the total number of arrival-departure tracks in station z′.


### 2.4. State Transition Function of DEDS

Train departure and train arrival are the two kinds of events that denote the dynamic of DEDS during the simulation of TREP. As having analyzed, train arrival time at the next station will be determined simultaneously with the determination of departure time at one station if we previously make sure there are no potential collisions. With this reason, the state of our DEDS will primarily focus on train departure event. The advantage of this decision is a particular period that train is traveling at segment or dwelling at a station for necessary technical operation that can be saved, just as the analysis in Section1. Based on the aforementioned analysis and accumulative state variable in DEDS, we formulate the state transition function Φ of DEDS as follows:(15)ts+1=mints+Δt,T,(16)s.t.Φl,qts+Δt=1,∀l∈L,∀q∈Q,where Δt∈1,2,3,… is the discrete time step between departure event s and s+1. Φl,q⋅ is the state check function, and it is formulated as follows:(17)Φl,qt=yl,zarrt−tl,zmin−yl,zdept,where tl,zmin is the minimal stopping time required by technical operation of train l at station z, l is the train that will be selected to occupy segment q, and segment q and station z satisfy formula (1).In order to analyze the principle and reasonability of state transition function, an example with three stations and one train is provided as Figure5.Figure 5
An example to explain state transition of DEDS: the state of DEDS (a) before train departure at stationz and (b) after train departure at station z.As shown in Figure5(a), t=3 is a discrete time point for DEDS in that train l is departed at station z″. After that, a satisfactory value of discrete time step Δt can be confirmed as 16 according to formulae (16) and (17), and then, the next potential departure time point, namely, ts+1=19, can be confirmed according to formula (15). In Figure 5(b), train l departs at station z when t=19 and will arrive at station z′ when t=26 because we suppose there are no collisions during this period. If the assumption fails, subsequent potential departure time points ts+1=20,21,… will be successively taken to confirm the corresponding arrival time with no potential collision until the reasonable departure time and arrival time pairs is obtained. This process will be further and illustrated in detail in Section 4. What is noteworthy is that there in only one segment in example. For a dispatching district with several segments, formulae (16) and (17) will be executed for each segment, but the next departure time point is still confirmed by formula (15).


## 2.1. Preliminary

Before the description of discrete event dynamic system (DEDS), some necessary assumptions are made as follows.Assumption 1.
Our research only focuses on a dispatching district on single-track railway with semiautomatic block. There are no branch tracks in dispatching district.Assumption 2.
Train running time at segment is uniform but may be different, and it will be assigned according to time delay, collision checks, and departure time.Assumption 3.
The time for signal arrangement and train acceleration or deceleration is integrated as a uniformed and fixed one for all trains and stations.Assumption 4.
All the arrival-departure lines in each station hold ordinary technical operations, such as M&P, M&O, passenger boarding and alighting, and train temporary stopping. For other special operations, each station has an appointed yard to deal with.
Based on the assumptions, letDEDS=S,X,Y,C,Φ be a DEDS to TREP, where S is the discourse domain, X is the collection of events, and Y and C are the collections of states and constraints, respectively. Specially, Φ is the state transition function of DEDS.


## 2.2. Domains, Events, and States of DEDS

### 2.2.1. Discourse Domain of DEDS

Discourse domain of DEDS includes object, time, and space. The object domain is trainl∈L. Here, we refer to train l running with outbound direction as l=2,4,6,… and refer to train l running with inbound direction as l=1,3,5,… . Time domain is the train rescheduling horizon 0,T with discrete step Δt, and t∈0,Tis the clock of DEDS. Space domain mainly denotes station set Z and segment set Q. The relationship between segments and stations is shown as follows:(1)q=z,z′,∀z,z′∈Z,∀q∈Q,where q is the segment index and z and z′ are the indexes of departure station and arrival station for train l, respectively. They can be expressed as(2)z′=z+2fl−1,∀l∈L,∀z,z′∈Z,where fl is a 0-1 variable to denote the train running direction,that is,fl=1,0,if trainlruns to outbound directionif trainlruns to inbound direction.Formulae (1) and (2) will be always holding in our following research, excepting the special case declared separately.


### 2.2.2. Event Description of DEDS

Events in DEDS include departure eventXdep and arrival event Xarr. Therein, xl,zdept∈Xdep is a 0-1 decision variable denoting a departure event, that isxl,zdept=1,if stationzcan arrange the departure signal for trainlwhen clock ist0,elseBased on the decision variablexl,zdept, departure time tl,zdep can be confirmed as(3)tl,zdep+xl,zdept⋅M−t−Idep=M,∀l∈L,∀z∈Z,t∈0,T,where M is a bigger integer, which is also the initial value of tl,zdep. Idep is the minimal time for signal arrangement and train departure.Then, arrival timetl,z′arr of train l at station z′ can be formulated as (4)tl,z′arr+xl,zdept⋅M−tl,zdep−tl,qope=M,∀l∈L,∀z,z′∈Z,∀q∈Q,t∈0,T,where tl,qope∈N+ is the decision variable to denote running time of train l at segment q. Specially,(5)tl,qmin≤tl,qope≤tl,qmax,∀l∈L,∀q∈Q,where tl,qmin and tl,qmax are the minimal and maximal running time of train l at segment q, respectively.


### 2.2.3. State Description of DEDS

The state of DEDS is associated with train departure event and train arrival event. According to departure timet^l,zdep and arrival time t^l,z′arr in original train timetable, DEDS is under the state of time delay if tl,zdep>t^l,zdep or tl,z′arr>t^l,z′arr for ∀l∈L,∀z∈Z.Letyl,zdept be an accumulative 0-1 state variable to record the state that whether train l has been departed at station z when system clock is t, that is, yl,zdept=1,iftl,zdep≤t≤T0,else.Similarly, letyl,zarrt record whether train l has arrived at station z when system clock is tyl,zarrt=1,iftl,zarr≤t≤T0,else.Based on the aforementioned definition, an illustration to accumulative state variables is shown in Figure2.Figure 2
An illustration to accumulative state variables.


## 2.2.1. Discourse Domain of DEDS

Discourse domain of DEDS includes object, time, and space. The object domain is trainl∈L. Here, we refer to train l running with outbound direction as l=2,4,6,… and refer to train l running with inbound direction as l=1,3,5,… . Time domain is the train rescheduling horizon 0,T with discrete step Δt, and t∈0,Tis the clock of DEDS. Space domain mainly denotes station set Z and segment set Q. The relationship between segments and stations is shown as follows:(1)q=z,z′,∀z,z′∈Z,∀q∈Q,where q is the segment index and z and z′ are the indexes of departure station and arrival station for train l, respectively. They can be expressed as(2)z′=z+2fl−1,∀l∈L,∀z,z′∈Z,where fl is a 0-1 variable to denote the train running direction,that is,fl=1,0,if trainlruns to outbound directionif trainlruns to inbound direction.Formulae (1) and (2) will be always holding in our following research, excepting the special case declared separately.


## 2.2.2. Event Description of DEDS

Events in DEDS include departure eventXdep and arrival event Xarr. Therein, xl,zdept∈Xdep is a 0-1 decision variable denoting a departure event, that isxl,zdept=1,if stationzcan arrange the departure signal for trainlwhen clock ist0,elseBased on the decision variablexl,zdept, departure time tl,zdep can be confirmed as(3)tl,zdep+xl,zdept⋅M−t−Idep=M,∀l∈L,∀z∈Z,t∈0,T,where M is a bigger integer, which is also the initial value of tl,zdep. Idep is the minimal time for signal arrangement and train departure.Then, arrival timetl,z′arr of train l at station z′ can be formulated as (4)tl,z′arr+xl,zdept⋅M−tl,zdep−tl,qope=M,∀l∈L,∀z,z′∈Z,∀q∈Q,t∈0,T,where tl,qope∈N+ is the decision variable to denote running time of train l at segment q. Specially,(5)tl,qmin≤tl,qope≤tl,qmax,∀l∈L,∀q∈Q,where tl,qmin and tl,qmax are the minimal and maximal running time of train l at segment q, respectively.


## 2.2.3. State Description of DEDS

The state of DEDS is associated with train departure event and train arrival event. According to departure timet^l,zdep and arrival time t^l,z′arr in original train timetable, DEDS is under the state of time delay if tl,zdep>t^l,zdep or tl,z′arr>t^l,z′arr for ∀l∈L,∀z∈Z.Letyl,zdept be an accumulative 0-1 state variable to record the state that whether train l has been departed at station z when system clock is t, that is, yl,zdept=1,iftl,zdep≤t≤T0,else.Similarly, letyl,zarrt record whether train l has arrived at station z when system clock is tyl,zarrt=1,iftl,zarr≤t≤T0,else.Based on the aforementioned definition, an illustration to accumulative state variables is shown in Figure2.Figure 2
An illustration to accumulative state variables.


## 2.3. Constraint Description in DEDS

### 2.3.1. Train Departure Constraints

Letk∈0,1,2 denote the types of technical operation. Herein, k=0 denotes train passes through a station or stops at a station for M&P and M&O, k=1 denotes passenger train stops at a station for passenger boarding and alighting, and k=2 denotes train stops at a station for other technical operations. Then, 0-1 variable τl,zk can be defined as τl,zk=1,if operation of trainlat stationzbelongs to typek0,else.There is only one type of technical operation that trainl at station z belongs; hence, (6)∑k∈0,1,2τl,zk=1,∀l∈L,∀z∈Z.To satisfy the necessary dwelling time for different technical operations, the following formula cannot be violated:(7)∑t∈0,Tyl,zarrt−yl,zdept≥τl,zk⋅tl,zmin,∀l∈L,∀z∈Z,k∈1,2,where tl,zmin is the minimal stopping time required by technical operation of train l at station z.Passenger train appointed at stationz for passenger boarding and alighting cannot be dispatched until the clock t meets or overtakes the original departure time. That is, (8)∑t∈0,T1−yl,zdept−τl,zk=1⋅t^l,zdep≥0,∀l∈L,∀z∈Z,where t^l,zdep is the departure time of train l at station z regulated in the original train timetable.


### 2.3.2. Departure Interval Constraint

Departure interval constraint mainly refers to the minimal time interval required by a departure station for signal arrangement and train departure. We here make an assumption that trainl is under the departure decision at station z and train l′ is the former arrival or departure one at the same station. Then, four scenarios are shown in Figure 3.Figure 3
Four scenarios in departure station constraint: (a) arrival-departure at the different segments; (b) arrival-departure at the same segment; (c) departure-departure at the different segments; (d) departure-departure at the same segment.
(a)(b)(c)(d)According to four scenarios in Figure3, the minimal time interval required by station z can be formulated by the following formulae:(9)∑t∈0,Tyl′,zarrt−yl,zdept≥I,∀l,l′∈L,∀z∈Z,(10)∑t∈0,Tyl′,zdept−yl,zdept≥I,∀l,l′∈L,∀z∈Z,where I is the minimal time required by station for signal arrangement and train departure.


### 2.3.3. Segment Running Constraint

For a single-track railway with semiautomatic block, M&P and M&O only occur at station. Hence, scenarios in Figure4 will be strictly forbidden.Figure 4
Two trains running at segment under different scenarios: (a) two trains running at segment from opposite direction; (b) two trains running at segment from the same direction.
(a)(b)Based on the scenarios in Figure4, segment running constraint can be denoted as(11)∑l∈Lyl,zdept−yl,z′arrt≤1,∀z,z′∈Z,t∈0,T.


### 2.3.4. Arrival Station Constraints

In order to avoid collisions and deadlocks in DEDS, arrival station constraints will be predicted and guaranteed by departure station before trainl is departed. With this reason, train departure time tl,zarr and train arrival time tl,z′arr will be determined simultaneously during the simulation:(1)
Arrival interval constraintJust as departure station constrain, the minimal time interval required by the arrival station for signal arrangement and train arrival can be denoted as follows, respectively:(12)∑t∈0,Tyl′,z′dept−yl,z′arrt≥I,∀l,l′∈L,∀z′∈Z,(13)∑t∈0,Tyl′,z′arrt−yl,z′arrt≥I,∀l,l′∈L,∀z′∈Z,whereI is the time interval required by arrival station for signal arrangement and train arrival.(2)
Station space constraintArrival station should at least have one unoccupied arrival-departure track for the approaching train. Hence, station space constraint can be guaranteed by the following formula:(14)∑l∈L∑k∈0,1,2τl,z′kyl,z′arrtl,z′arr−yl,z′deptl,z′arr<Nz′,∀z′∈Z,whereNz′ is the total number of arrival-departure tracks in station z′.


## 2.3.1. Train Departure Constraints

Letk∈0,1,2 denote the types of technical operation. Herein, k=0 denotes train passes through a station or stops at a station for M&P and M&O, k=1 denotes passenger train stops at a station for passenger boarding and alighting, and k=2 denotes train stops at a station for other technical operations. Then, 0-1 variable τl,zk can be defined as τl,zk=1,if operation of trainlat stationzbelongs to typek0,else.There is only one type of technical operation that trainl at station z belongs; hence, (6)∑k∈0,1,2τl,zk=1,∀l∈L,∀z∈Z.To satisfy the necessary dwelling time for different technical operations, the following formula cannot be violated:(7)∑t∈0,Tyl,zarrt−yl,zdept≥τl,zk⋅tl,zmin,∀l∈L,∀z∈Z,k∈1,2,where tl,zmin is the minimal stopping time required by technical operation of train l at station z.Passenger train appointed at stationz for passenger boarding and alighting cannot be dispatched until the clock t meets or overtakes the original departure time. That is, (8)∑t∈0,T1−yl,zdept−τl,zk=1⋅t^l,zdep≥0,∀l∈L,∀z∈Z,where t^l,zdep is the departure time of train l at station z regulated in the original train timetable.


## 2.3.2. Departure Interval Constraint

Departure interval constraint mainly refers to the minimal time interval required by a departure station for signal arrangement and train departure. We here make an assumption that trainl is under the departure decision at station z and train l′ is the former arrival or departure one at the same station. Then, four scenarios are shown in Figure 3.Figure 3
Four scenarios in departure station constraint: (a) arrival-departure at the different segments; (b) arrival-departure at the same segment; (c) departure-departure at the different segments; (d) departure-departure at the same segment.
(a)(b)(c)(d)According to four scenarios in Figure3, the minimal time interval required by station z can be formulated by the following formulae:(9)∑t∈0,Tyl′,zarrt−yl,zdept≥I,∀l,l′∈L,∀z∈Z,(10)∑t∈0,Tyl′,zdept−yl,zdept≥I,∀l,l′∈L,∀z∈Z,where I is the minimal time required by station for signal arrangement and train departure.


## 2.3.3. Segment Running Constraint

For a single-track railway with semiautomatic block, M&P and M&O only occur at station. Hence, scenarios in Figure4 will be strictly forbidden.Figure 4
Two trains running at segment under different scenarios: (a) two trains running at segment from opposite direction; (b) two trains running at segment from the same direction.
(a)(b)Based on the scenarios in Figure4, segment running constraint can be denoted as(11)∑l∈Lyl,zdept−yl,z′arrt≤1,∀z,z′∈Z,t∈0,T.


## 2.3.4. Arrival Station Constraints

In order to avoid collisions and deadlocks in DEDS, arrival station constraints will be predicted and guaranteed by departure station before trainl is departed. With this reason, train departure time tl,zarr and train arrival time tl,z′arr will be determined simultaneously during the simulation:(1)
Arrival interval constraintJust as departure station constrain, the minimal time interval required by the arrival station for signal arrangement and train arrival can be denoted as follows, respectively:(12)∑t∈0,Tyl′,z′dept−yl,z′arrt≥I,∀l,l′∈L,∀z′∈Z,(13)∑t∈0,Tyl′,z′arrt−yl,z′arrt≥I,∀l,l′∈L,∀z′∈Z,whereI is the time interval required by arrival station for signal arrangement and train arrival.(2)
Station space constraintArrival station should at least have one unoccupied arrival-departure track for the approaching train. Hence, station space constraint can be guaranteed by the following formula:(14)∑l∈L∑k∈0,1,2τl,z′kyl,z′arrtl,z′arr−yl,z′deptl,z′arr<Nz′,∀z′∈Z,whereNz′ is the total number of arrival-departure tracks in station z′.


## 2.4. State Transition Function of DEDS

Train departure and train arrival are the two kinds of events that denote the dynamic of DEDS during the simulation of TREP. As having analyzed, train arrival time at the next station will be determined simultaneously with the determination of departure time at one station if we previously make sure there are no potential collisions. With this reason, the state of our DEDS will primarily focus on train departure event. The advantage of this decision is a particular period that train is traveling at segment or dwelling at a station for necessary technical operation that can be saved, just as the analysis in Section1. Based on the aforementioned analysis and accumulative state variable in DEDS, we formulate the state transition function Φ of DEDS as follows:(15)ts+1=mints+Δt,T,(16)s.t.Φl,qts+Δt=1,∀l∈L,∀q∈Q,where Δt∈1,2,3,… is the discrete time step between departure event s and s+1. Φl,q⋅ is the state check function, and it is formulated as follows:(17)Φl,qt=yl,zarrt−tl,zmin−yl,zdept,where tl,zmin is the minimal stopping time required by technical operation of train l at station z, l is the train that will be selected to occupy segment q, and segment q and station z satisfy formula (1).In order to analyze the principle and reasonability of state transition function, an example with three stations and one train is provided as Figure5.Figure 5
An example to explain state transition of DEDS: the state of DEDS (a) before train departure at stationz and (b) after train departure at station z.As shown in Figure5(a), t=3 is a discrete time point for DEDS in that train l is departed at station z″. After that, a satisfactory value of discrete time step Δt can be confirmed as 16 according to formulae (16) and (17), and then, the next potential departure time point, namely, ts+1=19, can be confirmed according to formula (15). In Figure 5(b), train l departs at station z when t=19 and will arrive at station z′ when t=26 because we suppose there are no collisions during this period. If the assumption fails, subsequent potential departure time points ts+1=20,21,… will be successively taken to confirm the corresponding arrival time with no potential collision until the reasonable departure time and arrival time pairs is obtained. This process will be further and illustrated in detail in Section 4. What is noteworthy is that there in only one segment in example. For a dispatching district with several segments, formulae (16) and (17) will be executed for each segment, but the next departure time point is still confirmed by formula (15).


## 3. Optimization Model for TREP-Based DEDS

### 3.1. Objective Function

#### 3.1.1. Objective Function of Train Punctuality

The primary objective of DEDS is to guarantee the punctuality that a train is handed over to the next dispatching district or time horizon; that is,(18)minZ1=∑l∈Lwltl,zlendarr−t^l,zlendarr,where zlend is the last arrival station of train l in dispatching district or time horizon wl is the weight that denotes the priority of train l.With respect to the value of weightwl, some empowerment methods have been developed, such as fuzzy theory [34], group decision-making [35], and rough set theory [36]. In this paper, the entropy weight method is strongly recommended in that this method can effectively avoid decision errors caused by incomplete information [37, 38]. Let A=aijL×n be an attribute matrix; herein, L is the number of rescheduled trains, and n is the number of attributes, such as train type, the importance of train path, and the number of interface stations. If attribute j is positive, aij can be converted as aij′ by formula (19). Otherwise, it can be converted as aij′ by formula (20):(19)aij′=min1≤φ≤Laφj−aij∑1≤θ≤Lmin1≤φ≤Laφj−aθj,j=1,2,…,n,(20)aij′=min1≤φ≤Laφj−aij∑1≤θ≤Lmin1≤φ≤Laφj−aθj,j=1,2,…,n.Then,aij′ can be normalized as pij as follows:(21)pij=aij′∑1≤φ≤naiφ′,i=1,2,…,L,j=1,2,…,n.Based on the normalized indexpij, wl can be obtained according to the following formulae:(22)Ei=−1lnn∑j=1npijlnpij,i=1,2,…,L,(23)wl=wi=Ei−min0≤φ≤LEφmin0≤φ≤LEφ−min0≤φ≤LEφ,l,i=1,2,…,L.


#### 3.1.2. Objective Function of Station Satisfaction Degree

The pivotal task of TREP is to select a reasonable departure train to occupy segment with no collisions. However, it usually decreases or lengthens dwelling time on other trains, which may further lead to additional burdens on related stations. Hence, we employ station satisfaction degree, which can be mapped as a fuzzy value [39], to express the reasonability of rescheduled dwelling time.According to fuzzy theory [31, 40], let μx be a membership function depicting the membership degree of element x from a universal set to interval 0,1. Then, station satisfaction degree can be designed as formula (24) according to the different types of technical operation k∈0,1,2:(24)μtl,zdep−tl,zarr=μ1tl,zdep−tl,zarr,ifτl,zk=0=1,μ2tl,zdep−tl,zarrt^l,zdep−t^l,zarr,ifτl,zk=1=1orτl,zk=2=1,where μ1x and μ2x are membership functions and defined as follows, respectively:(25)μ1x=1,if 0≤x≤x1,x−x2x1−x2,ifx1<x≤x2,0,ifx>x2,(26)μ2x=0,if 0≤x≤x3orx>x6,x−x3x3−x4,ifx3<x≤x4,1,ifx4<x≤x5,x−x6x5−x6,ifx5<x≤x6,where x1,x2,…,x6 are the reference points to argument x.Based on the aforementioned description, the objective function of station satisfaction degree can be formulated as follows:(27)maxZ2=∑l∈L∑z∈Zwzμtl,zdep−tl,zarr,where wz is a weight to characterize station priority.


### 3.2. Optimization Models and Analysis

Holding the purpose to obtain a new timetable with the better punctuality, the optimization model can be constructed asM.1.Objective function: formula (18).Subject to constraints: formulae (1)–(14), (19)–(23).To obtain a new timetable with the higher station satisfaction degree, the optimization model can be constructed asM.2.Objective function: formula (27).Subject to constraints: formulae (1)–(14), (24)–(26).M.1 and M.2 share the decision variable xl,zdept and tl,qope commonly. In detail, xl,zdept and tl,qope are generally accordant and cooperative to M.1. However, they may be more complexity to M.2 because of the cooperativity or anticooperativity caused by recurse property and potential collisions. When train deviation is serious, M.1 will lead to the poorer performance to M.2 by reducing or lengthening dwelling time. In order to obtain a timetable that can balance train punctuality and station satisfaction degree simultaneously, a multiobjective optimization model (M.3) is constructed as follows:Objective function 1: formula (18).Objective function 2: formula (27).Subject to constraints: (1)–(14), (19)–(26).M.1, M.2, and M.3 are integer programming models, and all the objective functions are nonlinear ones. Thereinto, M.1 can be easily solved by commercial software because formula (18) can be linearized. However, M.2 is extremely difficult to be solved in that formula (24) is scarcely linearized. With respect to M.3, the solution procedure will be much more difficult because it requires coordination and equilibrium between M.1 and M.2. Generally speaking, aforementioned models are derived from DEDS. In order to obtain the adequate solution within reasonable computational time, a heuristic search strategy will be designed for our proposed DEDS.


## 3.1. Objective Function

### 3.1.1. Objective Function of Train Punctuality

The primary objective of DEDS is to guarantee the punctuality that a train is handed over to the next dispatching district or time horizon; that is,(18)minZ1=∑l∈Lwltl,zlendarr−t^l,zlendarr,where zlend is the last arrival station of train l in dispatching district or time horizon wl is the weight that denotes the priority of train l.With respect to the value of weightwl, some empowerment methods have been developed, such as fuzzy theory [34], group decision-making [35], and rough set theory [36]. In this paper, the entropy weight method is strongly recommended in that this method can effectively avoid decision errors caused by incomplete information [37, 38]. Let A=aijL×n be an attribute matrix; herein, L is the number of rescheduled trains, and n is the number of attributes, such as train type, the importance of train path, and the number of interface stations. If attribute j is positive, aij can be converted as aij′ by formula (19). Otherwise, it can be converted as aij′ by formula (20):(19)aij′=min1≤φ≤Laφj−aij∑1≤θ≤Lmin1≤φ≤Laφj−aθj,j=1,2,…,n,(20)aij′=min1≤φ≤Laφj−aij∑1≤θ≤Lmin1≤φ≤Laφj−aθj,j=1,2,…,n.Then,aij′ can be normalized as pij as follows:(21)pij=aij′∑1≤φ≤naiφ′,i=1,2,…,L,j=1,2,…,n.Based on the normalized indexpij, wl can be obtained according to the following formulae:(22)Ei=−1lnn∑j=1npijlnpij,i=1,2,…,L,(23)wl=wi=Ei−min0≤φ≤LEφmin0≤φ≤LEφ−min0≤φ≤LEφ,l,i=1,2,…,L.


### 3.1.2. Objective Function of Station Satisfaction Degree

The pivotal task of TREP is to select a reasonable departure train to occupy segment with no collisions. However, it usually decreases or lengthens dwelling time on other trains, which may further lead to additional burdens on related stations. Hence, we employ station satisfaction degree, which can be mapped as a fuzzy value [39], to express the reasonability of rescheduled dwelling time.According to fuzzy theory [31, 40], let μx be a membership function depicting the membership degree of element x from a universal set to interval 0,1. Then, station satisfaction degree can be designed as formula (24) according to the different types of technical operation k∈0,1,2:(24)μtl,zdep−tl,zarr=μ1tl,zdep−tl,zarr,ifτl,zk=0=1,μ2tl,zdep−tl,zarrt^l,zdep−t^l,zarr,ifτl,zk=1=1orτl,zk=2=1,where μ1x and μ2x are membership functions and defined as follows, respectively:(25)μ1x=1,if 0≤x≤x1,x−x2x1−x2,ifx1<x≤x2,0,ifx>x2,(26)μ2x=0,if 0≤x≤x3orx>x6,x−x3x3−x4,ifx3<x≤x4,1,ifx4<x≤x5,x−x6x5−x6,ifx5<x≤x6,where x1,x2,…,x6 are the reference points to argument x.Based on the aforementioned description, the objective function of station satisfaction degree can be formulated as follows:(27)maxZ2=∑l∈L∑z∈Zwzμtl,zdep−tl,zarr,where wz is a weight to characterize station priority.


## 3.1.1. Objective Function of Train Punctuality

The primary objective of DEDS is to guarantee the punctuality that a train is handed over to the next dispatching district or time horizon; that is,(18)minZ1=∑l∈Lwltl,zlendarr−t^l,zlendarr,where zlend is the last arrival station of train l in dispatching district or time horizon wl is the weight that denotes the priority of train l.With respect to the value of weightwl, some empowerment methods have been developed, such as fuzzy theory [34], group decision-making [35], and rough set theory [36]. In this paper, the entropy weight method is strongly recommended in that this method can effectively avoid decision errors caused by incomplete information [37, 38]. Let A=aijL×n be an attribute matrix; herein, L is the number of rescheduled trains, and n is the number of attributes, such as train type, the importance of train path, and the number of interface stations. If attribute j is positive, aij can be converted as aij′ by formula (19). Otherwise, it can be converted as aij′ by formula (20):(19)aij′=min1≤φ≤Laφj−aij∑1≤θ≤Lmin1≤φ≤Laφj−aθj,j=1,2,…,n,(20)aij′=min1≤φ≤Laφj−aij∑1≤θ≤Lmin1≤φ≤Laφj−aθj,j=1,2,…,n.Then,aij′ can be normalized as pij as follows:(21)pij=aij′∑1≤φ≤naiφ′,i=1,2,…,L,j=1,2,…,n.Based on the normalized indexpij, wl can be obtained according to the following formulae:(22)Ei=−1lnn∑j=1npijlnpij,i=1,2,…,L,(23)wl=wi=Ei−min0≤φ≤LEφmin0≤φ≤LEφ−min0≤φ≤LEφ,l,i=1,2,…,L.


## 3.1.2. Objective Function of Station Satisfaction Degree

The pivotal task of TREP is to select a reasonable departure train to occupy segment with no collisions. However, it usually decreases or lengthens dwelling time on other trains, which may further lead to additional burdens on related stations. Hence, we employ station satisfaction degree, which can be mapped as a fuzzy value [39], to express the reasonability of rescheduled dwelling time.According to fuzzy theory [31, 40], let μx be a membership function depicting the membership degree of element x from a universal set to interval 0,1. Then, station satisfaction degree can be designed as formula (24) according to the different types of technical operation k∈0,1,2:(24)μtl,zdep−tl,zarr=μ1tl,zdep−tl,zarr,ifτl,zk=0=1,μ2tl,zdep−tl,zarrt^l,zdep−t^l,zarr,ifτl,zk=1=1orτl,zk=2=1,where μ1x and μ2x are membership functions and defined as follows, respectively:(25)μ1x=1,if 0≤x≤x1,x−x2x1−x2,ifx1<x≤x2,0,ifx>x2,(26)μ2x=0,if 0≤x≤x3orx>x6,x−x3x3−x4,ifx3<x≤x4,1,ifx4<x≤x5,x−x6x5−x6,ifx5<x≤x6,where x1,x2,…,x6 are the reference points to argument x.Based on the aforementioned description, the objective function of station satisfaction degree can be formulated as follows:(27)maxZ2=∑l∈L∑z∈Zwzμtl,zdep−tl,zarr,where wz is a weight to characterize station priority.


## 3.2. Optimization Models and Analysis

Holding the purpose to obtain a new timetable with the better punctuality, the optimization model can be constructed asM.1.Objective function: formula (18).Subject to constraints: formulae (1)–(14), (19)–(23).To obtain a new timetable with the higher station satisfaction degree, the optimization model can be constructed asM.2.Objective function: formula (27).Subject to constraints: formulae (1)–(14), (24)–(26).M.1 and M.2 share the decision variable xl,zdept and tl,qope commonly. In detail, xl,zdept and tl,qope are generally accordant and cooperative to M.1. However, they may be more complexity to M.2 because of the cooperativity or anticooperativity caused by recurse property and potential collisions. When train deviation is serious, M.1 will lead to the poorer performance to M.2 by reducing or lengthening dwelling time. In order to obtain a timetable that can balance train punctuality and station satisfaction degree simultaneously, a multiobjective optimization model (M.3) is constructed as follows:Objective function 1: formula (18).Objective function 2: formula (27).Subject to constraints: (1)–(14), (19)–(26).M.1, M.2, and M.3 are integer programming models, and all the objective functions are nonlinear ones. Thereinto, M.1 can be easily solved by commercial software because formula (18) can be linearized. However, M.2 is extremely difficult to be solved in that formula (24) is scarcely linearized. With respect to M.3, the solution procedure will be much more difficult because it requires coordination and equilibrium between M.1 and M.2. Generally speaking, aforementioned models are derived from DEDS. In order to obtain the adequate solution within reasonable computational time, a heuristic search strategy will be designed for our proposed DEDS.


## 4. Two-Stage Heuristic Search Strategy for DEDS

Heuristic search strategy is designed as two sequential stages in this section. In the first stage, as train punctuality is the primary objective to our problem, and all the trains will be divided into several hierarchies according to train priority. After that, trains in different hierarchies will preempt time windows with different qualities and collisions. Thereinto, the divided hierarchies can be regarded as several subsidiary DEDS. For each DEDS, it has respective system clock and state transition function, but system constrains of each DEDS are shared mutually. The second stage focuses on departure event and constrain inspection at each discrete time in subsidiary DEDS. Herein, the evaluation of each potential departure train will be firstly provided according to different objective functions. Then, a reasonable departure train, together with its departure and next arrival time, will be heuristically determined from potential trains to occupy each free segment. Without doubt, once the departure event is motivated at this discrete time point, the next discrete point will be confirmed according to our designed state transition function.


### 4.1. First-Stage Strategy Based on Clustering Hierarchy

In order to meet an adequate solution as far as possible, an intuitive rescheduling strategy is that trains should be arranged one-by-one according to train priority from high to low, just like the strategy in [41, 42]. However, we concern that it may incur expensive loss in train punctuality and station satisfaction degree because of the interruption for the trains with a lower weight. Therefore, all the trains can be divided into several reasonable hierarchies according to train priority. After that, trains in same hierarchies should be rescheduled simultaneously to preempt time windows with proportionable quality. By this way, the concern may be relieved or even eliminated.In order to obtain a reasonable train hierarchy, clustering analysis theory is particularly introduced in that it has the advantage in maximizing element homogeneity in the same hierarchy and element heterogeneity among different hierarchies [43].According to the train prioritywl, let W=wijL×L be a matrix, where wij is the relative distance between wi and wj, which can be formulated as (28)wij=1−wi−wj2.Obviously,W=wijL×L is a fuzzy similar matrix, and there exists a minimal transfer number π∈N+ for fuzzy similar matrix W to satisfy (29)tW=∪m=1πWm=∪m=1∝Wm=W∗,where tW is the transitive closure for W, W∗is the fuzzy equivalent matrix for W, and ∪m=1πWm=∪m=1π−1Wm∘W⟺wijπ=∨k=1Lwikπ−1∧wkj.According to the fuzzy equivalent matrixW∗, all the trains will be divided into Hλ hierarchies for each given threshold λ. Then, statistical magnitude Rλ2 can be formulated as follows:(30)Rλ2=1−∑iwi−w¯2∑h=1Hλ∑i∈Whwi−w¯h2,where w¯ is the total centroid of  W∗ and w¯h is the centroid of h−th hierarchy.For each thresholdλ, a satisfactory threshold λ∗ can be obtained as(31)λ∗=argλ∈W∗maxRλ2Hλ,where λ∈W∗ denotes λ is an element in matrix W∗.Based on the satisfactory thresholdλ∗, all the trains will be divided into H∗ hierarchies, namely, L=L1∪L2∪⋯∪Lh∪⋯∪LH∗, where 1≤h≤H∗. Then, trains in each hierarchy Lh will be rescheduled simultaneously.


### 4.2. Second-Stage Strategy-Based Stochastic Heuristic Search

The stochastic heuristic search in this stage focuses on train departure and constrain inspection at each discrete time point in each hierarchyLh. The core of the strategy is to decide which train should be selected to occupy segment q if there are several potential trains. Herein, the potential train means its arrival time has been recorded by accumulative variable and will or can be arranged to occupy segment q. For convenience, potential train is denoted as l∈Θhq,t for each segment q. Especially, Θhq,t=∅ means segment q is inefficient. For each potential train l∈Θhq,t, train evaluation can be firstly proposed as follows when the model is M.1:(32)LVl,tl=wltl−t^l,zdep++tl−t^l,zdep−,∀l∈Θhq,t,where tltl≥t is the minimal time at which train l can be departed.If the optimization model isM.2, train evaluation can be proposed as (33)LVl,tl=1wzμtl−tl,zarr+M−1,∀l∈Θhq,t.If the optimization model isM.3, train evaluation can be proposed as(34)LVl,tl=wltl−t^l,zdep++tl−t^l,zdep−wzμtl−tl,zarr+M−1,∀l∈Θhq,t.In formulae (32)–(34), tl=minttestis derived from a time pair ttest,tl,qope, which means that train l can pass through the constraint inspection with departure time ttest and the running time tl,qope. According to this time pair, train departure time and next arrival time pair with no potential collision can also be confirmed. Generally, each departure train will additionally increase the evaluation of other potential trains. However, LVl,tl does not take this influence into consideration. In order to make up this disadvantage, we assume that if train l∈Θhq,t is selected as a departure train, then train l′∈Θhq,t can be dispatched until t=tl′next, where tl′next can be obtained as(35)tl′next=maxtl+Idep+tl,qope,tl′,∀l′∈Θhq,t,l′≠l.Hence, train evaluationLVl,tl can be reconstructed as(36)DVl,tl=LVl,tlmaxl′∈Θhq,tLVl′,tl′next−LVl′,tl′,∀l,l′∈L.If there are several effective segments at current discrete time points, the decision sequence of those segments may lead to different solutions for TREP because of the station space constraint. Hence, segment evaluationQVq,t can be formulated as follows:(37)QVq,t=∑l∈Θhq,tDVl,t.Based on train evaluationDVl,t and segment evaluation QVq,t, a random heuristic search will be adopted to determine segment sequence and departure train. The heuristic strategy is that the segment with higher value of QVq,twill be primely determined with the higher probability, and then, a train will be selected from the potential trains to occupy this segment in the similar heuristic strategy. As segment sequence and departure train may lead secondary collisions, the constraints and collisions must be secondly inspected. If the selected train does not pass though the inspection, it will not be allowed to depart. Otherwise, it be assigned to occupy the corresponding segment by recording train departure time and next arrival time. After that, next discrete point will be confirmed, according to state transition function, to realize state transition of DEDS.


### 4.3. Deadlock Analysis and Strategy Terminal Criterion

In our two-stage heuristic search strategy, deadlock of DEDS is prevented in that train departure time and arrival time are simultaneously determined with no potential collisions. Although our strategy may incur a little waste of effectiveness of arrival-departure line, the potential unsafety that train may be blocked at segment is shunned at least. A unique deadlock may be that all the arrival-departure lines in each station are occupied, which is like the deadlock in a closed system [44]. However, this extreme phenomenon cannot occur in our DEDS in that it is a half-open system at least.In order to obtain adequate train timetable within reasonable computational time, two criteria can be referenced as the terminal to heuristic search strategy. One criterion is the total number of solving cycleEt, which is similar to the maximum cycle in genetic algorithm [45]. Another one is the maximum cycle times Em in that the obtained solution has not been surpassed by subsequent solutions. With these two criterions, the simulation flowchart of train rescheduling based on DEDS is shown as Figure 6.Figure 6
The simulation flowchart of train rescheduling based on DEDS.


## 4.1. First-Stage Strategy Based on Clustering Hierarchy

In order to meet an adequate solution as far as possible, an intuitive rescheduling strategy is that trains should be arranged one-by-one according to train priority from high to low, just like the strategy in [41, 42]. However, we concern that it may incur expensive loss in train punctuality and station satisfaction degree because of the interruption for the trains with a lower weight. Therefore, all the trains can be divided into several reasonable hierarchies according to train priority. After that, trains in same hierarchies should be rescheduled simultaneously to preempt time windows with proportionable quality. By this way, the concern may be relieved or even eliminated.In order to obtain a reasonable train hierarchy, clustering analysis theory is particularly introduced in that it has the advantage in maximizing element homogeneity in the same hierarchy and element heterogeneity among different hierarchies [43].According to the train prioritywl, let W=wijL×L be a matrix, where wij is the relative distance between wi and wj, which can be formulated as (28)wij=1−wi−wj2.Obviously,W=wijL×L is a fuzzy similar matrix, and there exists a minimal transfer number π∈N+ for fuzzy similar matrix W to satisfy (29)tW=∪m=1πWm=∪m=1∝Wm=W∗,where tW is the transitive closure for W, W∗is the fuzzy equivalent matrix for W, and ∪m=1πWm=∪m=1π−1Wm∘W⟺wijπ=∨k=1Lwikπ−1∧wkj.According to the fuzzy equivalent matrixW∗, all the trains will be divided into Hλ hierarchies for each given threshold λ. Then, statistical magnitude Rλ2 can be formulated as follows:(30)Rλ2=1−∑iwi−w¯2∑h=1Hλ∑i∈Whwi−w¯h2,where w¯ is the total centroid of  W∗ and w¯h is the centroid of h−th hierarchy.For each thresholdλ, a satisfactory threshold λ∗ can be obtained as(31)λ∗=argλ∈W∗maxRλ2Hλ,where λ∈W∗ denotes λ is an element in matrix W∗.Based on the satisfactory thresholdλ∗, all the trains will be divided into H∗ hierarchies, namely, L=L1∪L2∪⋯∪Lh∪⋯∪LH∗, where 1≤h≤H∗. Then, trains in each hierarchy Lh will be rescheduled simultaneously.


## 4.2. Second-Stage Strategy-Based Stochastic Heuristic Search

The stochastic heuristic search in this stage focuses on train departure and constrain inspection at each discrete time point in each hierarchyLh. The core of the strategy is to decide which train should be selected to occupy segment q if there are several potential trains. Herein, the potential train means its arrival time has been recorded by accumulative variable and will or can be arranged to occupy segment q. For convenience, potential train is denoted as l∈Θhq,t for each segment q. Especially, Θhq,t=∅ means segment q is inefficient. For each potential train l∈Θhq,t, train evaluation can be firstly proposed as follows when the model is M.1:(32)LVl,tl=wltl−t^l,zdep++tl−t^l,zdep−,∀l∈Θhq,t,where tltl≥t is the minimal time at which train l can be departed.If the optimization model isM.2, train evaluation can be proposed as (33)LVl,tl=1wzμtl−tl,zarr+M−1,∀l∈Θhq,t.If the optimization model isM.3, train evaluation can be proposed as(34)LVl,tl=wltl−t^l,zdep++tl−t^l,zdep−wzμtl−tl,zarr+M−1,∀l∈Θhq,t.In formulae (32)–(34), tl=minttestis derived from a time pair ttest,tl,qope, which means that train l can pass through the constraint inspection with departure time ttest and the running time tl,qope. According to this time pair, train departure time and next arrival time pair with no potential collision can also be confirmed. Generally, each departure train will additionally increase the evaluation of other potential trains. However, LVl,tl does not take this influence into consideration. In order to make up this disadvantage, we assume that if train l∈Θhq,t is selected as a departure train, then train l′∈Θhq,t can be dispatched until t=tl′next, where tl′next can be obtained as(35)tl′next=maxtl+Idep+tl,qope,tl′,∀l′∈Θhq,t,l′≠l.Hence, train evaluationLVl,tl can be reconstructed as(36)DVl,tl=LVl,tlmaxl′∈Θhq,tLVl′,tl′next−LVl′,tl′,∀l,l′∈L.If there are several effective segments at current discrete time points, the decision sequence of those segments may lead to different solutions for TREP because of the station space constraint. Hence, segment evaluationQVq,t can be formulated as follows:(37)QVq,t=∑l∈Θhq,tDVl,t.Based on train evaluationDVl,t and segment evaluation QVq,t, a random heuristic search will be adopted to determine segment sequence and departure train. The heuristic strategy is that the segment with higher value of QVq,twill be primely determined with the higher probability, and then, a train will be selected from the potential trains to occupy this segment in the similar heuristic strategy. As segment sequence and departure train may lead secondary collisions, the constraints and collisions must be secondly inspected. If the selected train does not pass though the inspection, it will not be allowed to depart. Otherwise, it be assigned to occupy the corresponding segment by recording train departure time and next arrival time. After that, next discrete point will be confirmed, according to state transition function, to realize state transition of DEDS.


## 4.3. Deadlock Analysis and Strategy Terminal Criterion

In our two-stage heuristic search strategy, deadlock of DEDS is prevented in that train departure time and arrival time are simultaneously determined with no potential collisions. Although our strategy may incur a little waste of effectiveness of arrival-departure line, the potential unsafety that train may be blocked at segment is shunned at least. A unique deadlock may be that all the arrival-departure lines in each station are occupied, which is like the deadlock in a closed system [44]. However, this extreme phenomenon cannot occur in our DEDS in that it is a half-open system at least.In order to obtain adequate train timetable within reasonable computational time, two criteria can be referenced as the terminal to heuristic search strategy. One criterion is the total number of solving cycleEt, which is similar to the maximum cycle in genetic algorithm [45]. Another one is the maximum cycle times Em in that the obtained solution has not been surpassed by subsequent solutions. With these two criterions, the simulation flowchart of train rescheduling based on DEDS is shown as Figure 6.Figure 6
The simulation flowchart of train rescheduling based on DEDS.


## 5. Numerical Experiment

### 5.1. Experimental Setup

Our experiment is based on a real case with 10 stations in a dispatching district. Within the time horizon 6 hours, 24 trains are involved. Table1 gives the related information about each station. Table 2 is the related information about each train.Table 1
Information about each station.
Station index12345678910Station markSta aSta bSta cSta dSta eSta fSta gSta hSta iSta jNo. of tracks3333563343Mileage (km)091724335564748495Weightwz3.202.161.802.167.007.201.801.802.163.20Note. Track number denotes the number of arrival-departure tracks in each station.Table 2
Information for each train.
Train indexInitial delayValues of different attributesType of technical operationτ^l,zk in original timetableal,1+al,2+al,3+al,4−al,5+Sta aSta bSta cSta dSta eSta fSta gSta hSta iSta j166354222020000003272127200200200005208454200001100007112126300020020209085673000010011111−842574000000000213752583000002000215−72121150002022002178201114000002020219−58238000000000012110104570000000000123794570000000000125−6724710000000001274811400000000001202116322000000004243121142022000000608139110000100008195231032020000020100312103220000020012−6203104200002000014253239422000000001601016222002000001815201212000000000208211112000000000Note. Initial delay means the time delay taken for the train entering dispatching district or time horizon. al,1 is the attribute denoting train type. al,2 is the interface station number. al,3 is the importance of subsequence path. al,4 is the number of M&P or M&O in original timetable. al,5 is the number of stopping station in original timetable. + and − denote the positive attribute and negative attribute, respectively.In order to guarantee security and timeliness,tl,qmin=0.85t^l,qope and tl,qmax=1.15t^l,qope, where t^l,qope is the running time regulated in original timetable. The minimal interval required for signal arrangement is I=2 min. The arrival time and departure time in original timetable are shown as Figure 7.Figure 7
The arrival time and departure time in original timetable.In the objective function of station satisfaction degree, reference points arex1=I, x2=4I, x3=0.75, x4=0.95, x5=1.05, and x6=2.00. The optimal criterial are Et=150 and Em=50.


### 5.2. Results Analysis and Discussion

#### 5.2.1. Adequate Solution Generation and Analysis

According to the train attributes in Table2 and entropy weight method, the weight of each train can be obtained, as shown in Table 3.Table 3
The weight of each train.
Train indexl1357911131517192123Weightwl0.94730.42940.93290.61230.99990.97760.85930.57170.00680.53830.72960.7385Train indexl25272468101214161820Weightwl0.79780.33220.55880.38640.52550.65750.61480.51310.65220.00010.10820.4077According to the weight of each train, fuzzy equivalent matrixW∗ can be obtained when transfer number is π=10. Then, all the trains can be divided into different hierarchies according to corresponding threshold λ. Train hierarchies based on different threshold λ are shown as Figure 8. The statistical magnitude based on different threshold λ is shown as Table 4.Figure 8
Train hierarchies based different thresholdλ.Table 4
The statistical magnitude based on different thresholdλ.
Thresholdλ1.0000.99750.99460.99320.99110.98760.98720.98710.98560.97960.97870.97840.97760.96960.96260.95940.94580.94070.93850.92790.92640.91630.89860.7760Rλ21.00001.00001.0001.00001.00000.99990.99980.99970.99970.99870.99850.99810.99800.99670.99580.98530.98300.98150.97710.91740.74540.55220.54820.0000Hλ242322212019181716151413121110987654321Rλ2/Hλ0.04170.04350.04550.04760.05000.05260.05550.05880.06250.06660.07130.07680.08320.09060.09960.10950.10950.12290.14020.16280.18350.18630.18410.27410.000From Table4, we can obtain the satisfactory threshold λ∗=0.8986 in that the maximum Rλ2/Hλ=0.2741. Then, all the trains are divided into H∗=2 hierarchies, as shown in Figure 8.Based on the aforementioned preparation, our test is realized by Python 3.6.5 on Windows 10 X64 professional platform. The results show that an adequate solution can be found when the iteration is 83, nearly 40 seconds. The convergence graph ofM.3 is shown as Figure 9.Figure 9
The convergence graph ofM.3.In order to illustrate the effectiveness of heuristic search strategy, the results generated by nonrandom search strategy are also presented in Figure9. Obviously, the advantage of our strategy is remarkable both in train punctuality and station satisfaction degree. In addition, the feasible solution can be obtained within 0.4772 seconds, which shows our strategy has the better performance on simulation efficiency than other optimizing strategy, such as TAS in [24] and branch-and-bound strategy in [28]. In order to further analyze the obtained solution, adequate train timetable of M.3 and original train timetable in Figure 7 are contrastively shown in Figure 10.Figure 10
(a) The adequate train timetable ofM.3; (b) the original train timetable in Figure 7.
(a)(b)In adequate train timetable, train 16, train 17, and train 18 are rescheduled under second hierarchy according to train hierarchies in Figure8. With this reason, the delay of train 16 is extended and the departure of train 18 is even failed at station a. Notably, as the adequate timetable has loaded the initial time delay (see Table 2), departure stations and departure time of some trains in adequate timetable are slightly different from those in original timetable, such as train 2, train 3, and train 5. As the reason of initial time delay, some dwelling stations for train M&P or M&O are also changed after train rescheduling, such as train 2 and train 5 at station f for M&P and train 21 and train 23 at station d for M&O. Generally, nearly 70% trains can be handed over to next dispatching district or next time horizon with the less time delay, which is higher than 30% trains before the rescheduling. In order to further analyze the interaction influence of train punctuality and station satisfaction degree, the convergence graph of M.1 and M.2 compared with the M.3 is shown in Figures 11 and 12.Figure 11
The convergence graph ofM.1 compared with process of the M.3.Figure 12
The convergence graph ofM.2 compared with process of the M.3.Figures11 and 12 show that station satisfaction degree is inversely proportional to time delay, but not strictly. For the results of M.1, when optimal time delay meets 160.6451 mins, the station satisfaction degree is 384.8928. However, for the results of M.2, when the optimal satisfaction is 414.6910, total time delay increases as much as 185.8713 min. Compared with M.1 and M.2, time delay of M.3 is 175.4344 mins and station satisfaction degree of M.3 is 409.7517. Hence, M.3 has the better advantage in the balance of train punctuality and station satisfaction degree. In order to further analyze the difference caused by train time delay and station satisfaction degree, the adequate train timetables of M.1 and M.2 are provided in Figure 13.Figure 13
The adequate train timetables of (a)M.1 and (b) M.2.
(a)(b)Compared with (a) and (b) in Figure13, the obvious differences between two train timetables are caused by train 19 for M&P with related trains, such as the oval tags marked S2, S3, and S4. In addition, train 8 for M&P with train 7, train 9, and train 10 is also the important difference, such as the oval tag marked S1. Generally speaking, the results in Figure 13 imply that M.1 requires train to have suitable station for M&P or M&O. However, it may be slightly different in M.2, which requires the reasonable train dwelling time.


#### 5.2.2. Clustering Hierarchy Analysis

Clustering hierarchy in the first stage of our heuristic search strategy has an influence on adequate solution and simulation efficiency. In order to further to analyze,M.1 and M.2 are employed to exhibit the adequate solutions under each clustering hierarchy. The adequate solutions of M.1 and M.2 under each clustering hierarchy are shown as Figures 14 and 15, respectively.Figure 14
The adequate solutions ofM.1 under each clustering hierarchy.Figure 15
The adequate solutions ofM.2 under each clustering hierarchy.From Figures14 and 15, we can find that the adequate solutions of M.1 and M.2 are different under each clustering hierarchy. Specially, train punctuality and station satisfaction degree are too bad to accept when threshold λ≥0.9279. The adequate solutions under each threshold λ≤0.9264 are shown in Table 5.Table 5
The adequate solution under each thresholdλ≤0.9264.
ThresholdλHierarchyHλAdequate solution ofM.1Adequate solution ofM.2Time delay/minSatisfaction degreeTime delay/minSatisfaction degreeλ=0.92644300.4325383.6528375.2197387.5657λ=0.91633165.5400379.6719178.0971413.8428λ=0.89862160.6451384.8928185.8713414.6202λ=0.77601177.8211409.9622187.5274412.5485In Table5, the adequate solutions are generally better when λ≤0.9163. Specially, when λ≤0.9163, the solutions of M.2 are nearly equal. However, the solutions of M.1 are slightly different. Table 5 gives a suggestion that reasonable thresholds are λ=0.9163 and λ=0.8986, that is, H=3 and H=2. In fact, this suggestion is also supported by the following analysis. When λ=0.7760, namely, H=1, adequate solution is not prominent because of the interruption caused by the trains with the lower weight. However, when λ≥0.9385, namely, H≥6, heuristic search strategy becomes less obvious because of the decrease in potential trains in each train hierarchy.As having mentioned,λ=0.9163 and λ=0.8986 are both the reasonable thresholds. Merely, λ=0.8986 is adopted in our study because of the max Rλ2/Hλ (see Table 4). In order to analyze the interaction influence between clustering hierarchy and train multiattributes, the results of clustering hierarchy with different train attributes are shown in Table 6.Table 6
The results of clustering hierarchy with different train attributes.
Train attributesal,1+al,2+al,3+al,4−al,5+al,6+MaxRλ2/Hλ0.24210.40180.38640.28570.29480.3642Rλ∗20.72640.80360.77200.85700.58970.7285λ∗0.92660.83690.80690.89780.87540.8796H∗322322In Table6, trains attributes are corresponding to Table 2. Additionally, train initial delay, namely, al,6+, is also considered as a train attribute. The results in Table 6 show that H∗∈2,3 is always hold although train attributes are taken differently. Hence, clustering hierarchy can be used to confirm train hierarchy. However, how to confirm the optimal train hierarchy in other cases needs to be further explored in that R2 statistical magnitude is just one of the methods in clustering hierarchy theory. In addition, a set of reasonable train attributes are also extremely important to train hierarchy.


#### 5.2.3. Timeliness Analysis of DEDS and Strategy

The simulation time of DEDS depends on the state transition functionΦ and heuristic search strategy. As the purpose of state transition function Φ is to obtain a reasonable discrete time step Δt, computational time with Δt=1 can be provided as a comparison to analyze the timeliness of DEDS. The simulation time of DEDS with different discrete time steps Δt under each train hierarchy is listed in Table 7.Table 7
Simulation time of DEDS with different discrete timeΔt under each train hierarchy.
ThresholdλHierarchyHλComputational time (seconds)Δt=1FunctionΦ1.00002419.151810.77870.99752319.089310.85680.99462219.246710.46630.99322118.587510.76310.99112018.591110.87770.98761918.589310.57560.98721819.175410.93680.98711719.222410.91930.98561618.683111.80970.97961519.310111.71600.97871419.104912.07790.97841318.920611.68480.97761218.714311.74720.96961118.562711.73160.96261018.823712.09090.9594918.917411.90340.9458818.651911.98150.9407719.042412.04710.9385619.071812.43460.9279519.448511.90340.9264418.964310.65600.9163317.80799.66960.8986218.21449.54460.7760118.27699.4821Mean time18.826111.2120Note. The simulation time is based on the terminal criteria Et=Em=20.The results show that clustering hierarchy in heuristic search strategy cannot obviously produce additional simulation time. Compared with simulation time withΔt=1, nearly 40.44 percent of simulation time can be saved by using state transition function Φ. The main reason is that stochastic search strategy in a particular period that train is traveling at segment or dwelling at a station for necessary technical operation is saved by transition function Φ. In order to demonstrate this preconception, the change in time step Δt obtained by transition function Φ is shown as Figure 16. Herein, the results are based on the conditions that λ=0.7760 and Hλ=1.Figure 16
The change in time stepΔt obtained by transition function Φ.As shown in Figure16, the discrete steps are changed obviously, which means that strategy in a particular period is saved by transition function Φ during the simulation. With this reason, the discrete feature of DEDS is more prominent and the efficiency of DEDS is also improved.


## 5.1. Experimental Setup

Our experiment is based on a real case with 10 stations in a dispatching district. Within the time horizon 6 hours, 24 trains are involved. Table1 gives the related information about each station. Table 2 is the related information about each train.Table 1
Information about each station.
Station index12345678910Station markSta aSta bSta cSta dSta eSta fSta gSta hSta iSta jNo. of tracks3333563343Mileage (km)091724335564748495Weightwz3.202.161.802.167.007.201.801.802.163.20Note. Track number denotes the number of arrival-departure tracks in each station.Table 2
Information for each train.
Train indexInitial delayValues of different attributesType of technical operationτ^l,zk in original timetableal,1+al,2+al,3+al,4−al,5+Sta aSta bSta cSta dSta eSta fSta gSta hSta iSta j166354222020000003272127200200200005208454200001100007112126300020020209085673000010011111−842574000000000213752583000002000215−72121150002022002178201114000002020219−58238000000000012110104570000000000123794570000000000125−6724710000000001274811400000000001202116322000000004243121142022000000608139110000100008195231032020000020100312103220000020012−6203104200002000014253239422000000001601016222002000001815201212000000000208211112000000000Note. Initial delay means the time delay taken for the train entering dispatching district or time horizon. al,1 is the attribute denoting train type. al,2 is the interface station number. al,3 is the importance of subsequence path. al,4 is the number of M&P or M&O in original timetable. al,5 is the number of stopping station in original timetable. + and − denote the positive attribute and negative attribute, respectively.In order to guarantee security and timeliness,tl,qmin=0.85t^l,qope and tl,qmax=1.15t^l,qope, where t^l,qope is the running time regulated in original timetable. The minimal interval required for signal arrangement is I=2 min. The arrival time and departure time in original timetable are shown as Figure 7.Figure 7
The arrival time and departure time in original timetable.In the objective function of station satisfaction degree, reference points arex1=I, x2=4I, x3=0.75, x4=0.95, x5=1.05, and x6=2.00. The optimal criterial are Et=150 and Em=50.


## 5.2. Results Analysis and Discussion

### 5.2.1. Adequate Solution Generation and Analysis

According to the train attributes in Table2 and entropy weight method, the weight of each train can be obtained, as shown in Table 3.Table 3
The weight of each train.
Train indexl1357911131517192123Weightwl0.94730.42940.93290.61230.99990.97760.85930.57170.00680.53830.72960.7385Train indexl25272468101214161820Weightwl0.79780.33220.55880.38640.52550.65750.61480.51310.65220.00010.10820.4077According to the weight of each train, fuzzy equivalent matrixW∗ can be obtained when transfer number is π=10. Then, all the trains can be divided into different hierarchies according to corresponding threshold λ. Train hierarchies based on different threshold λ are shown as Figure 8. The statistical magnitude based on different threshold λ is shown as Table 4.Figure 8
Train hierarchies based different thresholdλ.Table 4
The statistical magnitude based on different thresholdλ.
Thresholdλ1.0000.99750.99460.99320.99110.98760.98720.98710.98560.97960.97870.97840.97760.96960.96260.95940.94580.94070.93850.92790.92640.91630.89860.7760Rλ21.00001.00001.0001.00001.00000.99990.99980.99970.99970.99870.99850.99810.99800.99670.99580.98530.98300.98150.97710.91740.74540.55220.54820.0000Hλ242322212019181716151413121110987654321Rλ2/Hλ0.04170.04350.04550.04760.05000.05260.05550.05880.06250.06660.07130.07680.08320.09060.09960.10950.10950.12290.14020.16280.18350.18630.18410.27410.000From Table4, we can obtain the satisfactory threshold λ∗=0.8986 in that the maximum Rλ2/Hλ=0.2741. Then, all the trains are divided into H∗=2 hierarchies, as shown in Figure 8.Based on the aforementioned preparation, our test is realized by Python 3.6.5 on Windows 10 X64 professional platform. The results show that an adequate solution can be found when the iteration is 83, nearly 40 seconds. The convergence graph ofM.3 is shown as Figure 9.Figure 9
The convergence graph ofM.3.In order to illustrate the effectiveness of heuristic search strategy, the results generated by nonrandom search strategy are also presented in Figure9. Obviously, the advantage of our strategy is remarkable both in train punctuality and station satisfaction degree. In addition, the feasible solution can be obtained within 0.4772 seconds, which shows our strategy has the better performance on simulation efficiency than other optimizing strategy, such as TAS in [24] and branch-and-bound strategy in [28]. In order to further analyze the obtained solution, adequate train timetable of M.3 and original train timetable in Figure 7 are contrastively shown in Figure 10.Figure 10
(a) The adequate train timetable ofM.3; (b) the original train timetable in Figure 7.
(a)(b)In adequate train timetable, train 16, train 17, and train 18 are rescheduled under second hierarchy according to train hierarchies in Figure8. With this reason, the delay of train 16 is extended and the departure of train 18 is even failed at station a. Notably, as the adequate timetable has loaded the initial time delay (see Table 2), departure stations and departure time of some trains in adequate timetable are slightly different from those in original timetable, such as train 2, train 3, and train 5. As the reason of initial time delay, some dwelling stations for train M&P or M&O are also changed after train rescheduling, such as train 2 and train 5 at station f for M&P and train 21 and train 23 at station d for M&O. Generally, nearly 70% trains can be handed over to next dispatching district or next time horizon with the less time delay, which is higher than 30% trains before the rescheduling. In order to further analyze the interaction influence of train punctuality and station satisfaction degree, the convergence graph of M.1 and M.2 compared with the M.3 is shown in Figures 11 and 12.Figure 11
The convergence graph ofM.1 compared with process of the M.3.Figure 12
The convergence graph ofM.2 compared with process of the M.3.Figures11 and 12 show that station satisfaction degree is inversely proportional to time delay, but not strictly. For the results of M.1, when optimal time delay meets 160.6451 mins, the station satisfaction degree is 384.8928. However, for the results of M.2, when the optimal satisfaction is 414.6910, total time delay increases as much as 185.8713 min. Compared with M.1 and M.2, time delay of M.3 is 175.4344 mins and station satisfaction degree of M.3 is 409.7517. Hence, M.3 has the better advantage in the balance of train punctuality and station satisfaction degree. In order to further analyze the difference caused by train time delay and station satisfaction degree, the adequate train timetables of M.1 and M.2 are provided in Figure 13.Figure 13
The adequate train timetables of (a)M.1 and (b) M.2.
(a)(b)Compared with (a) and (b) in Figure13, the obvious differences between two train timetables are caused by train 19 for M&P with related trains, such as the oval tags marked S2, S3, and S4. In addition, train 8 for M&P with train 7, train 9, and train 10 is also the important difference, such as the oval tag marked S1. Generally speaking, the results in Figure 13 imply that M.1 requires train to have suitable station for M&P or M&O. However, it may be slightly different in M.2, which requires the reasonable train dwelling time.


### 5.2.2. Clustering Hierarchy Analysis

Clustering hierarchy in the first stage of our heuristic search strategy has an influence on adequate solution and simulation efficiency. In order to further to analyze,M.1 and M.2 are employed to exhibit the adequate solutions under each clustering hierarchy. The adequate solutions of M.1 and M.2 under each clustering hierarchy are shown as Figures 14 and 15, respectively.Figure 14
The adequate solutions ofM.1 under each clustering hierarchy.Figure 15
The adequate solutions ofM.2 under each clustering hierarchy.From Figures14 and 15, we can find that the adequate solutions of M.1 and M.2 are different under each clustering hierarchy. Specially, train punctuality and station satisfaction degree are too bad to accept when threshold λ≥0.9279. The adequate solutions under each threshold λ≤0.9264 are shown in Table 5.Table 5
The adequate solution under each thresholdλ≤0.9264.
ThresholdλHierarchyHλAdequate solution ofM.1Adequate solution ofM.2Time delay/minSatisfaction degreeTime delay/minSatisfaction degreeλ=0.92644300.4325383.6528375.2197387.5657λ=0.91633165.5400379.6719178.0971413.8428λ=0.89862160.6451384.8928185.8713414.6202λ=0.77601177.8211409.9622187.5274412.5485In Table5, the adequate solutions are generally better when λ≤0.9163. Specially, when λ≤0.9163, the solutions of M.2 are nearly equal. However, the solutions of M.1 are slightly different. Table 5 gives a suggestion that reasonable thresholds are λ=0.9163 and λ=0.8986, that is, H=3 and H=2. In fact, this suggestion is also supported by the following analysis. When λ=0.7760, namely, H=1, adequate solution is not prominent because of the interruption caused by the trains with the lower weight. However, when λ≥0.9385, namely, H≥6, heuristic search strategy becomes less obvious because of the decrease in potential trains in each train hierarchy.As having mentioned,λ=0.9163 and λ=0.8986 are both the reasonable thresholds. Merely, λ=0.8986 is adopted in our study because of the max Rλ2/Hλ (see Table 4). In order to analyze the interaction influence between clustering hierarchy and train multiattributes, the results of clustering hierarchy with different train attributes are shown in Table 6.Table 6
The results of clustering hierarchy with different train attributes.
Train attributesal,1+al,2+al,3+al,4−al,5+al,6+MaxRλ2/Hλ0.24210.40180.38640.28570.29480.3642Rλ∗20.72640.80360.77200.85700.58970.7285λ∗0.92660.83690.80690.89780.87540.8796H∗322322In Table6, trains attributes are corresponding to Table 2. Additionally, train initial delay, namely, al,6+, is also considered as a train attribute. The results in Table 6 show that H∗∈2,3 is always hold although train attributes are taken differently. Hence, clustering hierarchy can be used to confirm train hierarchy. However, how to confirm the optimal train hierarchy in other cases needs to be further explored in that R2 statistical magnitude is just one of the methods in clustering hierarchy theory. In addition, a set of reasonable train attributes are also extremely important to train hierarchy.


### 5.2.3. Timeliness Analysis of DEDS and Strategy

The simulation time of DEDS depends on the state transition functionΦ and heuristic search strategy. As the purpose of state transition function Φ is to obtain a reasonable discrete time step Δt, computational time with Δt=1 can be provided as a comparison to analyze the timeliness of DEDS. The simulation time of DEDS with different discrete time steps Δt under each train hierarchy is listed in Table 7.Table 7
Simulation time of DEDS with different discrete timeΔt under each train hierarchy.
ThresholdλHierarchyHλComputational time (seconds)Δt=1FunctionΦ1.00002419.151810.77870.99752319.089310.85680.99462219.246710.46630.99322118.587510.76310.99112018.591110.87770.98761918.589310.57560.98721819.175410.93680.98711719.222410.91930.98561618.683111.80970.97961519.310111.71600.97871419.104912.07790.97841318.920611.68480.97761218.714311.74720.96961118.562711.73160.96261018.823712.09090.9594918.917411.90340.9458818.651911.98150.9407719.042412.04710.9385619.071812.43460.9279519.448511.90340.9264418.964310.65600.9163317.80799.66960.8986218.21449.54460.7760118.27699.4821Mean time18.826111.2120Note. The simulation time is based on the terminal criteria Et=Em=20.The results show that clustering hierarchy in heuristic search strategy cannot obviously produce additional simulation time. Compared with simulation time withΔt=1, nearly 40.44 percent of simulation time can be saved by using state transition function Φ. The main reason is that stochastic search strategy in a particular period that train is traveling at segment or dwelling at a station for necessary technical operation is saved by transition function Φ. In order to demonstrate this preconception, the change in time step Δt obtained by transition function Φ is shown as Figure 16. Herein, the results are based on the conditions that λ=0.7760 and Hλ=1.Figure 16
The change in time stepΔt obtained by transition function Φ.As shown in Figure16, the discrete steps are changed obviously, which means that strategy in a particular period is saved by transition function Φ during the simulation. With this reason, the discrete feature of DEDS is more prominent and the efficiency of DEDS is also improved.


## 5.2.1. Adequate Solution Generation and Analysis

According to the train attributes in Table2 and entropy weight method, the weight of each train can be obtained, as shown in Table 3.Table 3
The weight of each train.
Train indexl1357911131517192123Weightwl0.94730.42940.93290.61230.99990.97760.85930.57170.00680.53830.72960.7385Train indexl25272468101214161820Weightwl0.79780.33220.55880.38640.52550.65750.61480.51310.65220.00010.10820.4077According to the weight of each train, fuzzy equivalent matrixW∗ can be obtained when transfer number is π=10. Then, all the trains can be divided into different hierarchies according to corresponding threshold λ. Train hierarchies based on different threshold λ are shown as Figure 8. The statistical magnitude based on different threshold λ is shown as Table 4.Figure 8
Train hierarchies based different thresholdλ.Table 4
The statistical magnitude based on different thresholdλ.
Thresholdλ1.0000.99750.99460.99320.99110.98760.98720.98710.98560.97960.97870.97840.97760.96960.96260.95940.94580.94070.93850.92790.92640.91630.89860.7760Rλ21.00001.00001.0001.00001.00000.99990.99980.99970.99970.99870.99850.99810.99800.99670.99580.98530.98300.98150.97710.91740.74540.55220.54820.0000Hλ242322212019181716151413121110987654321Rλ2/Hλ0.04170.04350.04550.04760.05000.05260.05550.05880.06250.06660.07130.07680.08320.09060.09960.10950.10950.12290.14020.16280.18350.18630.18410.27410.000From Table4, we can obtain the satisfactory threshold λ∗=0.8986 in that the maximum Rλ2/Hλ=0.2741. Then, all the trains are divided into H∗=2 hierarchies, as shown in Figure 8.Based on the aforementioned preparation, our test is realized by Python 3.6.5 on Windows 10 X64 professional platform. The results show that an adequate solution can be found when the iteration is 83, nearly 40 seconds. The convergence graph ofM.3 is shown as Figure 9.Figure 9
The convergence graph ofM.3.In order to illustrate the effectiveness of heuristic search strategy, the results generated by nonrandom search strategy are also presented in Figure9. Obviously, the advantage of our strategy is remarkable both in train punctuality and station satisfaction degree. In addition, the feasible solution can be obtained within 0.4772 seconds, which shows our strategy has the better performance on simulation efficiency than other optimizing strategy, such as TAS in [24] and branch-and-bound strategy in [28]. In order to further analyze the obtained solution, adequate train timetable of M.3 and original train timetable in Figure 7 are contrastively shown in Figure 10.Figure 10
(a) The adequate train timetable ofM.3; (b) the original train timetable in Figure 7.
(a)(b)In adequate train timetable, train 16, train 17, and train 18 are rescheduled under second hierarchy according to train hierarchies in Figure8. With this reason, the delay of train 16 is extended and the departure of train 18 is even failed at station a. Notably, as the adequate timetable has loaded the initial time delay (see Table 2), departure stations and departure time of some trains in adequate timetable are slightly different from those in original timetable, such as train 2, train 3, and train 5. As the reason of initial time delay, some dwelling stations for train M&P or M&O are also changed after train rescheduling, such as train 2 and train 5 at station f for M&P and train 21 and train 23 at station d for M&O. Generally, nearly 70% trains can be handed over to next dispatching district or next time horizon with the less time delay, which is higher than 30% trains before the rescheduling. In order to further analyze the interaction influence of train punctuality and station satisfaction degree, the convergence graph of M.1 and M.2 compared with the M.3 is shown in Figures 11 and 12.Figure 11
The convergence graph ofM.1 compared with process of the M.3.Figure 12
The convergence graph ofM.2 compared with process of the M.3.Figures11 and 12 show that station satisfaction degree is inversely proportional to time delay, but not strictly. For the results of M.1, when optimal time delay meets 160.6451 mins, the station satisfaction degree is 384.8928. However, for the results of M.2, when the optimal satisfaction is 414.6910, total time delay increases as much as 185.8713 min. Compared with M.1 and M.2, time delay of M.3 is 175.4344 mins and station satisfaction degree of M.3 is 409.7517. Hence, M.3 has the better advantage in the balance of train punctuality and station satisfaction degree. In order to further analyze the difference caused by train time delay and station satisfaction degree, the adequate train timetables of M.1 and M.2 are provided in Figure 13.Figure 13
The adequate train timetables of (a)M.1 and (b) M.2.
(a)(b)Compared with (a) and (b) in Figure13, the obvious differences between two train timetables are caused by train 19 for M&P with related trains, such as the oval tags marked S2, S3, and S4. In addition, train 8 for M&P with train 7, train 9, and train 10 is also the important difference, such as the oval tag marked S1. Generally speaking, the results in Figure 13 imply that M.1 requires train to have suitable station for M&P or M&O. However, it may be slightly different in M.2, which requires the reasonable train dwelling time.


## 5.2.2. Clustering Hierarchy Analysis

Clustering hierarchy in the first stage of our heuristic search strategy has an influence on adequate solution and simulation efficiency. In order to further to analyze,M.1 and M.2 are employed to exhibit the adequate solutions under each clustering hierarchy. The adequate solutions of M.1 and M.2 under each clustering hierarchy are shown as Figures 14 and 15, respectively.Figure 14
The adequate solutions ofM.1 under each clustering hierarchy.Figure 15
The adequate solutions ofM.2 under each clustering hierarchy.From Figures14 and 15, we can find that the adequate solutions of M.1 and M.2 are different under each clustering hierarchy. Specially, train punctuality and station satisfaction degree are too bad to accept when threshold λ≥0.9279. The adequate solutions under each threshold λ≤0.9264 are shown in Table 5.Table 5
The adequate solution under each thresholdλ≤0.9264.
ThresholdλHierarchyHλAdequate solution ofM.1Adequate solution ofM.2Time delay/minSatisfaction degreeTime delay/minSatisfaction degreeλ=0.92644300.4325383.6528375.2197387.5657λ=0.91633165.5400379.6719178.0971413.8428λ=0.89862160.6451384.8928185.8713414.6202λ=0.77601177.8211409.9622187.5274412.5485In Table5, the adequate solutions are generally better when λ≤0.9163. Specially, when λ≤0.9163, the solutions of M.2 are nearly equal. However, the solutions of M.1 are slightly different. Table 5 gives a suggestion that reasonable thresholds are λ=0.9163 and λ=0.8986, that is, H=3 and H=2. In fact, this suggestion is also supported by the following analysis. When λ=0.7760, namely, H=1, adequate solution is not prominent because of the interruption caused by the trains with the lower weight. However, when λ≥0.9385, namely, H≥6, heuristic search strategy becomes less obvious because of the decrease in potential trains in each train hierarchy.As having mentioned,λ=0.9163 and λ=0.8986 are both the reasonable thresholds. Merely, λ=0.8986 is adopted in our study because of the max Rλ2/Hλ (see Table 4). In order to analyze the interaction influence between clustering hierarchy and train multiattributes, the results of clustering hierarchy with different train attributes are shown in Table 6.Table 6
The results of clustering hierarchy with different train attributes.
Train attributesal,1+al,2+al,3+al,4−al,5+al,6+MaxRλ2/Hλ0.24210.40180.38640.28570.29480.3642Rλ∗20.72640.80360.77200.85700.58970.7285λ∗0.92660.83690.80690.89780.87540.8796H∗322322In Table6, trains attributes are corresponding to Table 2. Additionally, train initial delay, namely, al,6+, is also considered as a train attribute. The results in Table 6 show that H∗∈2,3 is always hold although train attributes are taken differently. Hence, clustering hierarchy can be used to confirm train hierarchy. However, how to confirm the optimal train hierarchy in other cases needs to be further explored in that R2 statistical magnitude is just one of the methods in clustering hierarchy theory. In addition, a set of reasonable train attributes are also extremely important to train hierarchy.


## 5.2.3. Timeliness Analysis of DEDS and Strategy

The simulation time of DEDS depends on the state transition functionΦ and heuristic search strategy. As the purpose of state transition function Φ is to obtain a reasonable discrete time step Δt, computational time with Δt=1 can be provided as a comparison to analyze the timeliness of DEDS. The simulation time of DEDS with different discrete time steps Δt under each train hierarchy is listed in Table 7.Table 7
Simulation time of DEDS with different discrete timeΔt under each train hierarchy.
ThresholdλHierarchyHλComputational time (seconds)Δt=1FunctionΦ1.00002419.151810.77870.99752319.089310.85680.99462219.246710.46630.99322118.587510.76310.99112018.591110.87770.98761918.589310.57560.98721819.175410.93680.98711719.222410.91930.98561618.683111.80970.97961519.310111.71600.97871419.104912.07790.97841318.920611.68480.97761218.714311.74720.96961118.562711.73160.96261018.823712.09090.9594918.917411.90340.9458818.651911.98150.9407719.042412.04710.9385619.071812.43460.9279519.448511.90340.9264418.964310.65600.9163317.80799.66960.8986218.21449.54460.7760118.27699.4821Mean time18.826111.2120Note. The simulation time is based on the terminal criteria Et=Em=20.The results show that clustering hierarchy in heuristic search strategy cannot obviously produce additional simulation time. Compared with simulation time withΔt=1, nearly 40.44 percent of simulation time can be saved by using state transition function Φ. The main reason is that stochastic search strategy in a particular period that train is traveling at segment or dwelling at a station for necessary technical operation is saved by transition function Φ. In order to demonstrate this preconception, the change in time step Δt obtained by transition function Φ is shown as Figure 16. Herein, the results are based on the conditions that λ=0.7760 and Hλ=1.Figure 16
The change in time stepΔt obtained by transition function Φ.As shown in Figure16, the discrete steps are changed obviously, which means that strategy in a particular period is saved by transition function Φ during the simulation. With this reason, the discrete feature of DEDS is more prominent and the efficiency of DEDS is also improved.


## 6. Conclusions and Future Research

This paper presents a simulation method for TREP on single-track railway. It can be regarded as an extended version of the research in [24]. In this paper, the proposed DEDS is based on train departure event and arrival event, but the state of DEDS is driven by departure event. With this reason, state transition function can jump over some repeated constrain checks to improve the efficiency of DEDS. Our heuristic search strategy is derived from TAS proposed by Dorfman and Medanic [25]. However, it has certain global search capacity not only in time window preemption of different train hierarchies but also in segment occupation for each potential train. The proposed mathematical optimization models can be referred as further analysis to DEDS and TREP. Herein, the multiobjective optimization framework, namely, M.3, is our primary focus in that it can balance train punctuality and station satisfaction. However, it may be unsuitable for TREP with track allocation because the problem of track allocation for each dwelling train is simplified as Assumption 4 in Section 2.1.Generally speaking, supreme pursue of train punctuality usually leads to additional loss of station satisfaction degree. However, numerical experiment shows that nearly 15.81 percent of train punctuality and 17.47 percent of station satisfactory degree are improved by heuristic search strategy. Besides, state transition function can save the simulation time nearly 40.44 percent. These conclusions present that our DEDS, together with state transition function and heuristic search strategy, has better performance in solution quality and simulation efficiency. The numerical experiment also shows that hierarchical strategy is efficient to quickly obtain adequate solution. Series of simulation with different train attributes imply that reasonable train hierarchies should not be beyond three. However, this conclusion may do not apply to other cases because it is based on only one experiment. As having mentioned, a set of reasonable train attributes are critical to hierarchical strategy; hence, how to confirm the optimal train hierarchy needs further exploration.In future, a more efficient search strategy is worthy developing both in time window preemption based on train hierarchy and segment occupation for potential train, by using some machine learning theories and prediction techniques. Besides, our research just focuses on train rescheduling on dispatching district, and extending our research on railway network is also the future work.



---

*Source: 8892372-2020-11-24.xml*