# A Real-Time Train Timetable Rescheduling Method Based on Deep Learning for Metro Systems Energy Optimization under Random Disturbances

Authors: Jinlin Liao; Feng Zhang; Shiwen Zhang; Cheng Gong
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

Considering that uncertain dwell disturbances often occur at metro stations, researchers have proposed many methods for solving the train timetable rescheduling (TTR) problem. This paper proposes a Modified Genetic Algorithm-Gate Recurrent Unit (MGA-GRU) method, which is a real-time TTR method based on deep learning. The proposed method takes the Gate Recurrent Unit (GRU) network as the decision network and uses the results produced by the Modified Genetic Algorithm (MGA) as the training set of the decision network. A well-trained decision network can provide effective solutions in real time after random disturbances occur, in order to optimize the net traction energy consumption of trains in metro systems. Based on the Shanghai Metro Line One (SML1) pilot network, this paper establishes a comprehensive model of the metro system as a training and testing environment to verify the energy-saving effect and real-time performance of the proposed method in solving the TTR problem. The experimental results show that in the two-train metro system, the three-train metro system, and the five-train metro system, the MGA-GRU method can save an average of energy by 4.45%, 6.16%, and 7.19%, while the average decision time is only 0.15 s, 0.27 s, and 0.33 s, respectively.


---

## Body

## 1. Introduction

Compared with ground transportation such as buses and taxis, urban metro systems have achieved rapid development worldwide due to the advantages of no traffic jams, large capacity, and high safety [1]. Although metro systems are energy-efficient compared with other ground vehicles, they still consume a lot of energy [2, 3]. Due to problems such as rising energy prices and environmental pollution, in recent years, reducing the net traction energy consumption of trains in metro systems by studying and optimizing the train timetable has become an important research topic [4, 5].In metro systems, when a train brakes, it can regenerate braking energy to the system [6]. Regenerative braking energy (RBE) can be reused by trains that are simultaneously accelerating and can also be stored in energy storage devices such as batteries [7], supercapacitors [8], and flywheels [9]. Otherwise, RBE must be consumed by resistors as thermal energy to prevent the train voltage from surpassing the safety threshold [10, 11]. The timetable of a metro system can be either predetermined offline or dynamically changed in real time. By designing a suitable timetable, the acceleration trains and the braking trains can be better synchronized to make better use of RBE [12].Although researchers have conducted extensive research on train timetable in the past few decades, trains in metro systems are still often subject to unexpected disturbances, such as a sudden increase in passenger flow, unexpected accidents, and unplanned parking [13, 14]. To solve this kind of problem, researchers have proposed many train timetable rescheduling (TTR) methods [15–19].Previous studies on the TTR problem have focused on reducing the delay time caused by disturbances, which can be divided into two categories: one is to minimize the total delay time of passengers [20]; the other is to minimize the total delay time of all trains [21]. Šemrov et al. [22] introduced a real-time TTR method based on Q-learning. The proposed method has carried out a large number of experiments on the real-world railway network in Slovenia. The experimental results show that the solutions of Q-learning are at least equivalent and generally superior to simple first-in-first-out (FIFO) and random walk methods that do not rely on learning agents.Different from these two types of traditional methods, the TTR method studied in this paper aims to reschedule train timetable after disturbances occur to reduce traction energy consumption. Hou et al. [23] developed a mixed-integer programming (MIP) model to solve a metro train timetable rescheduling problem, which aims to jointly optimize the total train delay, the number of stranded passengers, and the energy consumption of trains. Zhao et al. [24] implemented three search methods, namely, enhanced brute force (EBF), ant colony optimization (ACO), and Genetic Algorithm (GA), to minimize energy consumption and delay after being disturbed. The results show that these three methods can find close to the best or the best train trajectories and driving styles to reduce the energy or improve safety and passenger’s comfort. Gong et al. [25] proposed a Compensational Driving Strategy Algorithm (CDSA) to restore the disturbed train to the original optimal timetable by reducing the travel time of the disturbed train in the next section after a disturbance occurs. The results show that compared with not using CDSA after a disturbance occurs, using CDSA can save 1.86% of energy on average.However, these optimization methods (EBF, ACO, and GA) implemented by Zhao et al. are not suitable for solving the TTR problem in real time due to the long calculation time. And the CDSA proposed by Gong et al. only rearranges the coasting speed of the disturbed trains, which does not adjust other trains’ coasting speeds and all trains’ dwell time. In response to these problems, this paper proposes a TTR method based on deep learning, called Modified Genetic Algorithm-Gate Recurrent Unit (MGA-GRU) by combining the modified Genetic Algorithm (MGA) with the Gate Recurrent Unit (GRU) network.Up to now, many methods based on a general GA have been proposed to solve scheduling and optimization problems [26–29]. Corresponding experimental results show that these methods can find high-quality solutions for large-scale case. And GRU has been applied to solve problems with time-series dimensions [30, 31]. These experimental results show that GRU can extract more rich and complex information from sequences and aspects.Better than EBF, ACO, and GA, MGA-GRU can reschedule the timetable in real time after random disturbances occur. Unlike CDSA which only rearranges the coasting speed of the disturbed train, MGA-GRU rearranges the coasting speed and dwell time of all trains in the metro network in real time after disturbances occur, so as to achieve better energy-saving effect.The remainder of this paper is organized as follows. Section2 builds three models based on Shanghai Metro Line One (SML1). Section 3 introduces the MGA-GRU method to solve the TTR problem in real time after a disturbance occurs. In Section 4, four experiments based on the SML1 pilot network are conducted to verify the energy-saving effect and real-time performance of the proposed method. Section 5 concludes this paper.


## 2. Modeling

In this section, three models are proposed to formulate the metro system: time model, mechanical model, and power model.For a better understanding of this paper, the assumptions, decision variables, and parameters are first introduced.


### 2.1. Assumptions

(1)
The distance between two adjacent stations of SML1 is relatively small. According to the actual operation of trains on the SML1 and the description of Su et al. [32], each train adopts a single-cycle acceleration-coasting-braking strategy instead of repeated acceleration and braking.(2)
Dwell disturbances are small enough so as not to lead to network disruption.(3)
From the first train’s departure to the last train’s arrival, only one dwell disturbance occurs. But the value of the disturbance is random.


### 2.2. Decision Variables

vcm,n : coasting speed of train no. m from station no. n − 1 to station no. ntdwm,n : dwell time of train no. m at station no. n


### 2.3. Parameters

m : index of trainn : index of stationM : total number of trainsN : total number of stationsttrm,i : travel time of train no. m from station no. i − 1 to station no. itdem,n : departure instant of train no. m at station no. ntdwm,n : dwell time of train no. m at station no. nt1 : Headwayε : Duration of a dwell disturbancettotalM,N : total timev : speed of the trainFT : traction forceFB : braking forceFR : running resistanceFG : gravityθ : track slopexm : position of train no. mPTm,n : traction power of train no. m from station no. n − 1 to station no. nPRm,n : regenerative braking power of train no. m from station no. n − 1 to station no. nPFm,n: feedback power of train no. m from station no. n − 1 to station no. nη1 : conversion efficiency of the train traction system (from electrical energy to mechanical energy)η2 : conversion efficiency of the train braking system (from mechanical energy to electrical energy)η3 : braking energy feedback coefficientET : traction energy consumption of acceleration trainsEF : regenerative braking feedback energy used by acceleration trainsE : net energy consumption


### 2.4. Time Model

The time model defines the departure instanttde, travel time ttr, and dwell time tdw of each train at each station [33]. The starting station is defined as station no. 1. The instant when train no. 1 leaves the starting station is defined as time = 0. The interval between each adjacent train leaving the starting station is equal.If a disturbance occurs at station no.n of train no. m, the corresponding dwell time will increase from tdwm,n to tdwm,n+ε. Then the departure instant of train no. m at station no. n is(1)tdem,n=tdem,1+∑i=2nttrm,i+tdwm,i+ε.According to the assumptions above, only one disturbance occurs during each entire test procedure. Therefore, the instantttotalM,N when the last train arrives at the terminal is defined as(2)ttotalM,N=tdeM,1+∑i=2N−1ttrM,i+tdwM,i+ttrM,N+ε.


### 2.5. Mechanics Model

According to the assumption above, each train adopts a single-cycle acceleration-coasting-braking strategy instead of repeatedly acceleration and braking [25]. The unit of FT, FR, FB, etc., is N.In the acceleration phase,FB=0; the relationship between FT and speed v is shown in the following equation:(3)FT=550,0<v≤10m/s,19800v,v>10m/s.When the speed is lower than 10 m/s, the train is in a constant torque traction state, and the acceleration of the train is a fixed value. When the speed increases beyond 10 m/s, the train switches to a constant power traction state. In this state, the traction power is a fixed value, and the traction force is inversely proportional to the speed.In the coasting phase,FB=0, FT=0; the relationship between FR and v conforms to the Davis equation [34]:(4)FR=7.398+0.255v+0.012v2.In the braking phase,FT=0; the relationship between FB and v is shown in the following equation:(5)FB=550,0<v≤18.056m/s,35750v,v>18.056m/s.When the speed is higher than 18.056 m/s, the braking force is inversely proportional to the speed. When the speed decreases within 18.056 m/s, the deceleration is a fixed value.


### 2.6. Power Model

In the metro system, there are three driving states of trains: acceleration, coasting, and braking. Accelerating trains convert electrical energy into mechanical energy, while braking trains can regenerate mechanical energy into electrical energy. The electric energy generated by the braking trains can be supplied to the acceleration trains. This implies that if the trains can be arranged with an appropriate strategy, a lot of energy can be saved by the use of this part of RBE.PB, the regenerative braking power, is defined as(6)PB=η1FBv.PT is the traction power and is defined as(7)PT=FTvη2.If the braking power is less than the traction power, it can be fully used; otherwise, resistors will kick in and consume the overflowing braking power to maintain the train voltage under a safe value. The minimum value of traction power and braking conversion power is defined asPF [33]:(8)PF=minPT,η3PB=minFTvη2,η3η1FBv.


### 2.7. Relationship between Coasting Speed and Travel Time

The area enclosed by the speed curve and the time axis is the distance between two adjacent metro stations. As shown in Figure1, if the acceleration and driving strategy is determined, the coasting speed and the travel time form a one-to-one mapping between two adjacent stations. Higher coasting speed corresponds to a shorter travel time. Therefore, the travel time can be controlled by controlling the coasting speed. And the relation can be defined as ttrm,n=fvcm,n [25].Figure 1
Relationship between coasting speed and travel time.


## 2.1. Assumptions

(1)
The distance between two adjacent stations of SML1 is relatively small. According to the actual operation of trains on the SML1 and the description of Su et al. [32], each train adopts a single-cycle acceleration-coasting-braking strategy instead of repeated acceleration and braking.(2)
Dwell disturbances are small enough so as not to lead to network disruption.(3)
From the first train’s departure to the last train’s arrival, only one dwell disturbance occurs. But the value of the disturbance is random.


## 2.2. Decision Variables

vcm,n : coasting speed of train no. m from station no. n − 1 to station no. ntdwm,n : dwell time of train no. m at station no. n


## 2.3. Parameters

m : index of trainn : index of stationM : total number of trainsN : total number of stationsttrm,i : travel time of train no. m from station no. i − 1 to station no. itdem,n : departure instant of train no. m at station no. ntdwm,n : dwell time of train no. m at station no. nt1 : Headwayε : Duration of a dwell disturbancettotalM,N : total timev : speed of the trainFT : traction forceFB : braking forceFR : running resistanceFG : gravityθ : track slopexm : position of train no. mPTm,n : traction power of train no. m from station no. n − 1 to station no. nPRm,n : regenerative braking power of train no. m from station no. n − 1 to station no. nPFm,n: feedback power of train no. m from station no. n − 1 to station no. nη1 : conversion efficiency of the train traction system (from electrical energy to mechanical energy)η2 : conversion efficiency of the train braking system (from mechanical energy to electrical energy)η3 : braking energy feedback coefficientET : traction energy consumption of acceleration trainsEF : regenerative braking feedback energy used by acceleration trainsE : net energy consumption


## 2.4. Time Model

The time model defines the departure instanttde, travel time ttr, and dwell time tdw of each train at each station [33]. The starting station is defined as station no. 1. The instant when train no. 1 leaves the starting station is defined as time = 0. The interval between each adjacent train leaving the starting station is equal.If a disturbance occurs at station no.n of train no. m, the corresponding dwell time will increase from tdwm,n to tdwm,n+ε. Then the departure instant of train no. m at station no. n is(1)tdem,n=tdem,1+∑i=2nttrm,i+tdwm,i+ε.According to the assumptions above, only one disturbance occurs during each entire test procedure. Therefore, the instantttotalM,N when the last train arrives at the terminal is defined as(2)ttotalM,N=tdeM,1+∑i=2N−1ttrM,i+tdwM,i+ttrM,N+ε.


## 2.5. Mechanics Model

According to the assumption above, each train adopts a single-cycle acceleration-coasting-braking strategy instead of repeatedly acceleration and braking [25]. The unit of FT, FR, FB, etc., is N.In the acceleration phase,FB=0; the relationship between FT and speed v is shown in the following equation:(3)FT=550,0<v≤10m/s,19800v,v>10m/s.When the speed is lower than 10 m/s, the train is in a constant torque traction state, and the acceleration of the train is a fixed value. When the speed increases beyond 10 m/s, the train switches to a constant power traction state. In this state, the traction power is a fixed value, and the traction force is inversely proportional to the speed.In the coasting phase,FB=0, FT=0; the relationship between FR and v conforms to the Davis equation [34]:(4)FR=7.398+0.255v+0.012v2.In the braking phase,FT=0; the relationship between FB and v is shown in the following equation:(5)FB=550,0<v≤18.056m/s,35750v,v>18.056m/s.When the speed is higher than 18.056 m/s, the braking force is inversely proportional to the speed. When the speed decreases within 18.056 m/s, the deceleration is a fixed value.


## 2.6. Power Model

In the metro system, there are three driving states of trains: acceleration, coasting, and braking. Accelerating trains convert electrical energy into mechanical energy, while braking trains can regenerate mechanical energy into electrical energy. The electric energy generated by the braking trains can be supplied to the acceleration trains. This implies that if the trains can be arranged with an appropriate strategy, a lot of energy can be saved by the use of this part of RBE.PB, the regenerative braking power, is defined as(6)PB=η1FBv.PT is the traction power and is defined as(7)PT=FTvη2.If the braking power is less than the traction power, it can be fully used; otherwise, resistors will kick in and consume the overflowing braking power to maintain the train voltage under a safe value. The minimum value of traction power and braking conversion power is defined asPF [33]:(8)PF=minPT,η3PB=minFTvη2,η3η1FBv.


## 2.7. Relationship between Coasting Speed and Travel Time

The area enclosed by the speed curve and the time axis is the distance between two adjacent metro stations. As shown in Figure1, if the acceleration and driving strategy is determined, the coasting speed and the travel time form a one-to-one mapping between two adjacent stations. Higher coasting speed corresponds to a shorter travel time. Therefore, the travel time can be controlled by controlling the coasting speed. And the relation can be defined as ttrm,n=fvcm,n [25].Figure 1
Relationship between coasting speed and travel time.


## 3. Energy Optimization under Disturbances

In order to optimize the net traction energy consumption in real time after a dwell disturbance occurs, this paper proposes an MGA-GRU method based on deep learning. This method combines the modified Genetic Algorithm (MGA) with the Gate Recurrent Unit (GRU) network. The MGA-GRU method consists of four stages. Specifically, in the first stage, the optimal energy timetable without a disturbance is produced by MGA. In the second stage, the dwell time and coasting speed of each train are used as decision variables. And MGA is used to provide effective actions under different disturbances, which are used as the training set. In the third stage, the outcomes of MGA are used to train the GRU network. All the above three stages are offline. In the fourth stage, the well-trained GRU network is used as a decision network. The well-trained decision network can provide effective solutions in real time after a disturbance occurs. This stage is real-time.


### 3.1. Modified Genetic Algorithm

In the first stage, the energy optimization objective function without a disturbance can be expressed as(9)minEt=∑m=1M∑n=2N∫0ttrm,nPTm,nt−PFm,ntdts.t.m∈1,2,⋯,M,n∈2,⋯,N,tdem,n+1=tdem,n+ttrm,n+tdwm,n,ttrm,n=fvcm,n,18m/s≤vcm,n≤22m/s.In the second stage, if a disturbance occurs at station no.n0 of train no. m0, the energy optimization objective function under a disturbance can be expressed as(10)minEt,ε=∑m=1M∑n=2N∫0ttrm,nPTm,nt,ε−PFm,nt,εdts.t.m∈1,2,⋯,M,n∈2,⋯,N,tdem,n+1=tdem,n+ttrm,n+tdwm,n+ε,ifm=m0,n=n0,tdem,n+ttrm,n+tdwm,n,others,ttrm,n=fvcm,n,18m/s≤vcm,n≤22m/s,where ε is a nonzero random variable.Equations (9) and (10) are single-objective optimization problems that can be solved by Genetic Algorithm (GA). However, using general GA to solve such complex optimization problems, the solution is easy to fall into local optimal rather than global optimal. In order to overcome the problem of premature convergence of general GA, this paper introduces a modified Genetic Algorithm (MGA) based on Simulated Annealing (SA) algorithm to avoid falling into local optimum and approach global optimum.Pseudocode for MGA is provided in Algorithm1. GEN is the generation of MGA, and GEN_MAX is the maximum generation of MGA. A is the number of initial individuals, and B is the maximum number of local searches per individual. kc0≤kc≤1 and km0≤km≤1 are random values. FITindα is the fitness of the individual α, and FITneiα is the fitness of the best neighborhood solution of the individual α. Each individual α contains a series of coasting speed (V) and dwell time (T). When adopting V and T, the net energy consumption is equal to FITα. So, if no dwell disturbance occurs, FITα can be calculated based on equation (9), which means that FITα=Et. And if a dwell disturbance occurs, FITα can be calculated based on equation (10), which means that FITα=Et,ε.Algorithm 1: Modified Genetic Algorithm (MGA).
Randomly generate the first generation. The population contains many individuals, and each individual contains a series of decision variables: coasting speed (V), dwell time (T). Ω is used as a series of decision variables, which means Ω=V,T. GEN⟵1.whileGEN∈1,⋯,GEN_MAXdoInitialize the neighborhood structures setΩα,β.α⟵1, β⟵1.whileα∈1,⋯,Adowhileβ∈1,⋯,BdoRandomly generate a series ofV and T within constraints to serve as a set of solutions Ωα,β in the neighborhood of Ωα.β⟵β+1.end whileα⟵α+1, β⟵1.end whileEquations (9) and (10) are used to evaluate the fitness FITα,β of the solution Ωα,β without a disturbance and under a disturbance, respectively.ifFITneiα<FITindαthenFITindα=FITneiα.else ifeFITindα−FITneiα/Temper<Rand0,1thenFITindα=FITneiα.end ifGEN⟵GEN+1.DecreaseTemper.if the probability of crossover Pc≥kcthenCrossover.end ifif the probability of mutation Pm≥kmthenMutation.end ifend whileOutput the global optimum.


### 3.2. Gate Recurrent Unit

The Gate Recurrent Unit (GRU) network belongs to one of the Recurrent Neural Networks (RNN). Like the Long Short-Term Memory (LSTM) network, GRU is also proposed to solve the problems of long-term memory and gradient in backpropagation. Better than LSTM, because GRU has fewer parameters, the training speed is faster, and less data is required to generalize. While using GRU can achieve the same effect as LSTM, the GRU network is easier to be trained and the training efficiency is higher. The GRU network has a strong generalization ability and has been successfully and widely used in voice recognition, computer vision, and other fields. The structure and application of GRU are introduced below.


#### 3.2.1. Input and Output Structure of GRU

The input and output structure of GRU is the same as the Naïve RNN, as shown in Figure2. There is a current input xt and the hidden state ht−1 passed from the previous node. The hidden state ht−1 contains information about the previous node. Combining with xt and ht−1, GRU produces the output yt of the current hidden node and the hidden state ht passed to the next node.Figure 2
Input and output structure of GRU.


#### 3.2.2. Internal Structure of GRU

The states of the two gates (rt and zt) are obtained by the hidden state ht−1 passed from the previous node and the input xt of the current node. As shown in equations (11) and (12), rt is a reset gate that controls reset, and zt is an update gate that controls update. And σ is the sigmoid function. With this function, rt and zt can be transformed into the range 0,1, which can be used as a gating signal. Wxr,Wxz,Wxh and Whr,Whz,Whh denote weight matrices of the reset gate, the update gate, and the hidden layer, respectively. br,bz,bh are the bias matrices.(11)rt=σWxrxt+Whrht−1+br,(12)zt=σWxzxt+Whzht−1+bz.After obtaining the gating signal, the reset gate is the first to be used to produce the reset dataht−1′=ht−1⊙rt. Then ht−1′ is stitched with the input xt. A tanh function is used to shrink the data to the range −1,1, that is, ht′, as shown in equation (13). ht′ mainly contains the current input xt. Adding ht′ to the current hidden state in a targeted manner is equivalent to remembering the current state.(13)ht′=tanhWxhxt+Whhht−1′+bh.In the update memory stage, two steps of forgetting and memorizing are performed at the same time. The expression is as follows:(14)ht=1−zt⊙ht−1+zt⊙ht′,where ⊙ is the Hadamard product, which is to multiply the corresponding elements in the matrix. ⊕ represents the matrix addition operation. The range of the gating signal zt is 0,1. The closer the gating signal is to 1, the more data is remembered; the closer it is to 0, the more is forgotten. 1−zt⊙ht−1 means to selectively forget the previous hidden state, that is, to forget some unimportant information in the dimension of ht−1. zt⊙ht′ indicates selective memory of the current node information ht′. It can be seen from equation (14) that the same update gate zt can be used for forgetting and selectively memorizing, while LSTM needs to use multiple gates. The model parameters including all Wxr,Wxz,Wxh,Whr,Whz,Whh,br,bz,bh are shared by all time steps and learned during model training.In summary, the internal structure of GRU is shown in Figure3.Figure 3
The internal structure of GRU.


#### 3.2.3. Application of GRU

Each decision under different disturbances can be produced by MGA, which includes a series of coasting speeds and dwell time. The outcomes of MGA can be used to train the GRU network, that is, the decision network. A well-trained decision network can provide intelligent decisions in real time after a random disturbance occurs. Figure4 shows the structure of the coasting speed and dwell time decision network. The decision network consists of five parts: input layers, previous hidden layer, current hidden layer, a decision network, and a voter. After a disturbance occurs, at the departure instant, the decision network determines the coasting speed of each departing train and the dwell time at the next station. The speed, position, and driving state of other trains, along with the train number and station number of the departing train, are put into the input layer. The train number and station number of the departing train correspond to one GRU cell. Finally, the voter gives the coasting speed and dwell time of the departing train. Furthermore, for a metro system with M trains, the input layer has 3M − 1 neurons, and the output layer has 2 neurons.Figure 4
Structure of decision network.The dwell disturbance is used in the input layers of the GRU network. After a dwell disturbance occurs at the disturbed trains, the position, speed, and driving state of the disturbed train are delayed as well. Therefore, when a train departs from a station, the position, speed, and driving state of the disturbed train (as one of the other trains) are different from the situation where no dwell disturbance occurs. In a word, the dwell disturbance influences the disturbed train’s the position, speed, and driving state at each departing instant, which are used in the input layers of the GRU network.


## 3.1. Modified Genetic Algorithm

In the first stage, the energy optimization objective function without a disturbance can be expressed as(9)minEt=∑m=1M∑n=2N∫0ttrm,nPTm,nt−PFm,ntdts.t.m∈1,2,⋯,M,n∈2,⋯,N,tdem,n+1=tdem,n+ttrm,n+tdwm,n,ttrm,n=fvcm,n,18m/s≤vcm,n≤22m/s.In the second stage, if a disturbance occurs at station no.n0 of train no. m0, the energy optimization objective function under a disturbance can be expressed as(10)minEt,ε=∑m=1M∑n=2N∫0ttrm,nPTm,nt,ε−PFm,nt,εdts.t.m∈1,2,⋯,M,n∈2,⋯,N,tdem,n+1=tdem,n+ttrm,n+tdwm,n+ε,ifm=m0,n=n0,tdem,n+ttrm,n+tdwm,n,others,ttrm,n=fvcm,n,18m/s≤vcm,n≤22m/s,where ε is a nonzero random variable.Equations (9) and (10) are single-objective optimization problems that can be solved by Genetic Algorithm (GA). However, using general GA to solve such complex optimization problems, the solution is easy to fall into local optimal rather than global optimal. In order to overcome the problem of premature convergence of general GA, this paper introduces a modified Genetic Algorithm (MGA) based on Simulated Annealing (SA) algorithm to avoid falling into local optimum and approach global optimum.Pseudocode for MGA is provided in Algorithm1. GEN is the generation of MGA, and GEN_MAX is the maximum generation of MGA. A is the number of initial individuals, and B is the maximum number of local searches per individual. kc0≤kc≤1 and km0≤km≤1 are random values. FITindα is the fitness of the individual α, and FITneiα is the fitness of the best neighborhood solution of the individual α. Each individual α contains a series of coasting speed (V) and dwell time (T). When adopting V and T, the net energy consumption is equal to FITα. So, if no dwell disturbance occurs, FITα can be calculated based on equation (9), which means that FITα=Et. And if a dwell disturbance occurs, FITα can be calculated based on equation (10), which means that FITα=Et,ε.Algorithm 1: Modified Genetic Algorithm (MGA).
Randomly generate the first generation. The population contains many individuals, and each individual contains a series of decision variables: coasting speed (V), dwell time (T). Ω is used as a series of decision variables, which means Ω=V,T. GEN⟵1.whileGEN∈1,⋯,GEN_MAXdoInitialize the neighborhood structures setΩα,β.α⟵1, β⟵1.whileα∈1,⋯,Adowhileβ∈1,⋯,BdoRandomly generate a series ofV and T within constraints to serve as a set of solutions Ωα,β in the neighborhood of Ωα.β⟵β+1.end whileα⟵α+1, β⟵1.end whileEquations (9) and (10) are used to evaluate the fitness FITα,β of the solution Ωα,β without a disturbance and under a disturbance, respectively.ifFITneiα<FITindαthenFITindα=FITneiα.else ifeFITindα−FITneiα/Temper<Rand0,1thenFITindα=FITneiα.end ifGEN⟵GEN+1.DecreaseTemper.if the probability of crossover Pc≥kcthenCrossover.end ifif the probability of mutation Pm≥kmthenMutation.end ifend whileOutput the global optimum.


## 3.2. Gate Recurrent Unit

The Gate Recurrent Unit (GRU) network belongs to one of the Recurrent Neural Networks (RNN). Like the Long Short-Term Memory (LSTM) network, GRU is also proposed to solve the problems of long-term memory and gradient in backpropagation. Better than LSTM, because GRU has fewer parameters, the training speed is faster, and less data is required to generalize. While using GRU can achieve the same effect as LSTM, the GRU network is easier to be trained and the training efficiency is higher. The GRU network has a strong generalization ability and has been successfully and widely used in voice recognition, computer vision, and other fields. The structure and application of GRU are introduced below.


### 3.2.1. Input and Output Structure of GRU

The input and output structure of GRU is the same as the Naïve RNN, as shown in Figure2. There is a current input xt and the hidden state ht−1 passed from the previous node. The hidden state ht−1 contains information about the previous node. Combining with xt and ht−1, GRU produces the output yt of the current hidden node and the hidden state ht passed to the next node.Figure 2
Input and output structure of GRU.


### 3.2.2. Internal Structure of GRU

The states of the two gates (rt and zt) are obtained by the hidden state ht−1 passed from the previous node and the input xt of the current node. As shown in equations (11) and (12), rt is a reset gate that controls reset, and zt is an update gate that controls update. And σ is the sigmoid function. With this function, rt and zt can be transformed into the range 0,1, which can be used as a gating signal. Wxr,Wxz,Wxh and Whr,Whz,Whh denote weight matrices of the reset gate, the update gate, and the hidden layer, respectively. br,bz,bh are the bias matrices.(11)rt=σWxrxt+Whrht−1+br,(12)zt=σWxzxt+Whzht−1+bz.After obtaining the gating signal, the reset gate is the first to be used to produce the reset dataht−1′=ht−1⊙rt. Then ht−1′ is stitched with the input xt. A tanh function is used to shrink the data to the range −1,1, that is, ht′, as shown in equation (13). ht′ mainly contains the current input xt. Adding ht′ to the current hidden state in a targeted manner is equivalent to remembering the current state.(13)ht′=tanhWxhxt+Whhht−1′+bh.In the update memory stage, two steps of forgetting and memorizing are performed at the same time. The expression is as follows:(14)ht=1−zt⊙ht−1+zt⊙ht′,where ⊙ is the Hadamard product, which is to multiply the corresponding elements in the matrix. ⊕ represents the matrix addition operation. The range of the gating signal zt is 0,1. The closer the gating signal is to 1, the more data is remembered; the closer it is to 0, the more is forgotten. 1−zt⊙ht−1 means to selectively forget the previous hidden state, that is, to forget some unimportant information in the dimension of ht−1. zt⊙ht′ indicates selective memory of the current node information ht′. It can be seen from equation (14) that the same update gate zt can be used for forgetting and selectively memorizing, while LSTM needs to use multiple gates. The model parameters including all Wxr,Wxz,Wxh,Whr,Whz,Whh,br,bz,bh are shared by all time steps and learned during model training.In summary, the internal structure of GRU is shown in Figure3.Figure 3
The internal structure of GRU.


### 3.2.3. Application of GRU

Each decision under different disturbances can be produced by MGA, which includes a series of coasting speeds and dwell time. The outcomes of MGA can be used to train the GRU network, that is, the decision network. A well-trained decision network can provide intelligent decisions in real time after a random disturbance occurs. Figure4 shows the structure of the coasting speed and dwell time decision network. The decision network consists of five parts: input layers, previous hidden layer, current hidden layer, a decision network, and a voter. After a disturbance occurs, at the departure instant, the decision network determines the coasting speed of each departing train and the dwell time at the next station. The speed, position, and driving state of other trains, along with the train number and station number of the departing train, are put into the input layer. The train number and station number of the departing train correspond to one GRU cell. Finally, the voter gives the coasting speed and dwell time of the departing train. Furthermore, for a metro system with M trains, the input layer has 3M − 1 neurons, and the output layer has 2 neurons.Figure 4
Structure of decision network.The dwell disturbance is used in the input layers of the GRU network. After a dwell disturbance occurs at the disturbed trains, the position, speed, and driving state of the disturbed train are delayed as well. Therefore, when a train departs from a station, the position, speed, and driving state of the disturbed train (as one of the other trains) are different from the situation where no dwell disturbance occurs. In a word, the dwell disturbance influences the disturbed train’s the position, speed, and driving state at each departing instant, which are used in the input layers of the GRU network.


## 3.2.1. Input and Output Structure of GRU

The input and output structure of GRU is the same as the Naïve RNN, as shown in Figure2. There is a current input xt and the hidden state ht−1 passed from the previous node. The hidden state ht−1 contains information about the previous node. Combining with xt and ht−1, GRU produces the output yt of the current hidden node and the hidden state ht passed to the next node.Figure 2
Input and output structure of GRU.


## 3.2.2. Internal Structure of GRU

The states of the two gates (rt and zt) are obtained by the hidden state ht−1 passed from the previous node and the input xt of the current node. As shown in equations (11) and (12), rt is a reset gate that controls reset, and zt is an update gate that controls update. And σ is the sigmoid function. With this function, rt and zt can be transformed into the range 0,1, which can be used as a gating signal. Wxr,Wxz,Wxh and Whr,Whz,Whh denote weight matrices of the reset gate, the update gate, and the hidden layer, respectively. br,bz,bh are the bias matrices.(11)rt=σWxrxt+Whrht−1+br,(12)zt=σWxzxt+Whzht−1+bz.After obtaining the gating signal, the reset gate is the first to be used to produce the reset dataht−1′=ht−1⊙rt. Then ht−1′ is stitched with the input xt. A tanh function is used to shrink the data to the range −1,1, that is, ht′, as shown in equation (13). ht′ mainly contains the current input xt. Adding ht′ to the current hidden state in a targeted manner is equivalent to remembering the current state.(13)ht′=tanhWxhxt+Whhht−1′+bh.In the update memory stage, two steps of forgetting and memorizing are performed at the same time. The expression is as follows:(14)ht=1−zt⊙ht−1+zt⊙ht′,where ⊙ is the Hadamard product, which is to multiply the corresponding elements in the matrix. ⊕ represents the matrix addition operation. The range of the gating signal zt is 0,1. The closer the gating signal is to 1, the more data is remembered; the closer it is to 0, the more is forgotten. 1−zt⊙ht−1 means to selectively forget the previous hidden state, that is, to forget some unimportant information in the dimension of ht−1. zt⊙ht′ indicates selective memory of the current node information ht′. It can be seen from equation (14) that the same update gate zt can be used for forgetting and selectively memorizing, while LSTM needs to use multiple gates. The model parameters including all Wxr,Wxz,Wxh,Whr,Whz,Whh,br,bz,bh are shared by all time steps and learned during model training.In summary, the internal structure of GRU is shown in Figure3.Figure 3
The internal structure of GRU.


## 3.2.3. Application of GRU

Each decision under different disturbances can be produced by MGA, which includes a series of coasting speeds and dwell time. The outcomes of MGA can be used to train the GRU network, that is, the decision network. A well-trained decision network can provide intelligent decisions in real time after a random disturbance occurs. Figure4 shows the structure of the coasting speed and dwell time decision network. The decision network consists of five parts: input layers, previous hidden layer, current hidden layer, a decision network, and a voter. After a disturbance occurs, at the departure instant, the decision network determines the coasting speed of each departing train and the dwell time at the next station. The speed, position, and driving state of other trains, along with the train number and station number of the departing train, are put into the input layer. The train number and station number of the departing train correspond to one GRU cell. Finally, the voter gives the coasting speed and dwell time of the departing train. Furthermore, for a metro system with M trains, the input layer has 3M − 1 neurons, and the output layer has 2 neurons.Figure 4
Structure of decision network.The dwell disturbance is used in the input layers of the GRU network. After a dwell disturbance occurs at the disturbed trains, the position, speed, and driving state of the disturbed train are delayed as well. Therefore, when a train departs from a station, the position, speed, and driving state of the disturbed train (as one of the other trains) are different from the situation where no dwell disturbance occurs. In a word, the dwell disturbance influences the disturbed train’s the position, speed, and driving state at each departing instant, which are used in the input layers of the GRU network.


## 4. Experimental Verification

In order to verify the energy-saving effect and real-time performance of the proposed MGA-GRU method for solving the TTR problem, four numerical experiments are conducted in this section. In experiment 1, MGA is used to produce the optimal timetable without a disturbance in the two-train metro system. In experiment 2, the timetable is rescheduled after a disturbance occurs, by using the MGA-GRU method. In experiment 3, the MGA-GRU method is applied for solving the TTR problem in a three-train metro system. In experiment 4, the MGA-GRU method is applied in a bidirectional metro system with five trains on two tracks.The information of the pilot metro system is shown in Figure5. The configuration of the numerical experiment is shown in Table 1.Figure 5
Information of the pilot metro system.Table 1
Configuration of numerical experiment.
ItemsConfiguration informationOperating systemWindows 10CPUIntel® Xeon® CPU E5-2620 v4 @ 2.10 GHzRAM32 GBSimulation environmentTensorFlowLocalesPythonSome settings for the four experiments are listed in Table2. Based on the above settings, there are no traffic jam conflicts between trains. In experiments 2 and 3, the dwell disturbance occurs at train no. 1 at Changshu Road Station, while in experiment 4, the dwell disturbance can occur at train no. 1 at Hengshan Road Station or at Changshu Road Station or at South Shaanxi Road Station.Table 2
Settings for the four experiments.
ItemsRangeThe headway120 sDwell time30,35sDwell disturbance−5,15sCoasting speed18,22m/sη10.8η20.7η30.7


### 4.1. Experiment 1

The goal of experiment 1 is to validate MGA for solving the energy optimization problem and produce the optimal timetable without a disturbance. MGA is used to solve the energy optimization problem based on equation (7) and the optimal timetable as is shown in Table 3.Table 3
The optimal timetable of the two-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:3029.621.828:02:008:03:4220.118Hengshan Road ⟶ Changshu Road1125.718:01:598:03:2128.41828:04:028:05:2227.218.32Changshu Road ⟶ South Shaanxi Road979.218:03:498:04:5622.021.0828:05:498:07:0123.418.4South Shaanxi Road ⟶ South Huangpi Road1377.418:05:188:06:4523.121.4428:07:258:09:012018South Huangpi Road ⟶ People’s Square1526.818:07:088:08:542018.0428:09:218:11:0626.518.32People’s Square ⟶ Xinzha Road961.218:09:148:10:25—18.0428:11:328:12:44—18.04Figure6 shows the distribution of individuals of the 1st, 10th, and 15th generations produced by MGA. As shown in Figure 6, the distribution of individuals in the 1st generation is discrete. After 10 generations, the individuals’ distribution gradually concentrates. Finally, after 15 generations, the individuals converge with a fitness value of 256.02 kWh, which is the optimal energy consumption without a disturbance.Figure 6
Individuals’ distribution of the 1st, 10th, and 15th generations produced by MGA.In order to prove the effectiveness of MGA, a general GA is also applied to produce the offline timetable without a disturbance under the same condition. Figure7 shows the distribution of individuals of the 1st, 10th, and 15th generations produced by a general GA. After 15 generations, the individuals converge with a fitness value of 276.59 kWh. It can be seen from Figure 7 that the individuals of a general GA concentrate more quickly than those of MGA. What is more, the fitness of a general GA (276.59 kWh) is bigger than that of MGA (256.02 kWh). Therefore, compared with a general GA, the proposed MGA can avoid falling into local optimum prematurely and provide a better solution.Figure 7
Individuals’ distribution of the 1st, 10th, and 15th generations produced by a general GA.


### 4.2. Experiment 2

This experiment is to use the MGA-GUR method to solve the TTR problem under random disturbances in the two-train metro system. The energy-saving effect of the MGA-GRU method is reflected by the saved energy during test compared with the no-action strategy. The real-time performance of the MGA-GRU method is reflected by the time it takes to provide a pair of strategies during testing.


#### 4.2.1. Dataset

The outputs of MGA based on equation (8) under the disturbance from 10s,10.2s,10.4s,…,14.8s,15.0s are selected as the dataset to train the MGA-GRU network.


#### 4.2.2. Baselines

The proposed MGA-GRU method is compared against two baselines: (i)no action, where each train does not take any measures after disturbances occur and (ii) MGA, where MGA is used to give an offline strategy to deal with the dwell disturbances. The two baselines are representative of the worst and best possible strategies. It is expected that MGA-GRU falls in between these two extreme cases. It should be emphasized that MGA-GRU can reschedule the timetable in real time.The changes of the net energy consumption with these three strategies are compared during testing. The dwell disturbance which occurs at train no. 1 at Changshu Road Station is 13.45 s. Figure8 shows the net energy consumption curve of the whole journey using the three methods. It can be seen from Figure 8 that from the moment when the disturbance occurs, the net energy consumption of no action has always remained the highest. Although MGA can achieve good results in saving energy, it takes a lot of time to provide a decision, which does not meet the real-time requirements for solving the TTR problem. Compared with the above two methods, MGA-GRU can reschedule the timetable in real time and achieve saving energy.Figure 8
Changes in net energy consumption with different strategies under a 13.45 s dwell disturbance.The rescheduled timetable with the MGA-GRU method under a 13.45 s dwell disturbance in the two-train metro system is shown in Table4.Table 4
The rescheduled timetable with the MGA-GRU method in the two-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:3029.621.828:02:008:03:3521.218.04Hengshan Road ⟶ Changshu Road1125.718:01:598:02:2141.91828:03:568:05:122218Changshu Road ⟶ South Shaanxi Road979.218:04:038:05:1129.618.2828:05:348:06:432018.2South Shaanxi Road ⟶ South Huangpi Road1377.418:05:418:07:1129.81828:07:038:08:332018.08South Huangpi Road ⟶ People’s Square1526.818:07:418:09:13201828:08:538:10:2621.818.04People’s Square ⟶ Xinzha Road961.218:09:338:10:39—18.5628:10:488:11:55—18Table5 shows the average calculation time and average total energy consumption of the three strategies in 10 tests. The MGA-GRU strategy is energy efficient compared with the no-action strategy and its average calculation time is only 0.15 s which meets the requirements of real-time effect. Therefore, MGA-GRU can reschedule the timetable in real time and achieve saving energy after a dwell disturbance occurs. It should be noted that although the total energy consumption of the MGA strategy is less than the MGA-GRU strategy, it requires a greatly long calculation time (8694.08 s in total) to reschedule the timetable, which absolutely does not meet the real-time requirements of the TTR problem. In terms of calculation time, MGA-GRU has an absolute superiority.Table 5
Performances with three strategies in the two-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no action strategy (%)No action0293.95—MGA8694.08274.586.59MGA-GRU0.15280.884.45


### 4.3. Experiment 3

In the real case of SML1, there are at most three trains between two substations. Therefore, it is essential to apply the MGA-GRU method to a three-train metro system. What is more, according to the real case of SML1 [35], the train departs early frequently, which means that the value of a disturbance can be negative. This situation is also taken into consideration in experiment 3.First, MGA produces the optimal timetable without a disturbance based on equation (7), as shown in Table 6.Table 6
The optimal timetable of the three-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:412018.1228:02:008:03:292021.9638:04:008:05:4225.318Hengshan Road ⟶ Changshu Road1125.718:02:018:03:182019.8828:03:498:05:0520.220.5238:06:078:07:2529.519.16Changshu Road ⟶ South Shaanxi Road979.218:03:388:04:5126.31828:05:258:06:3227.521.3238:07:558:09:0726.818South Shaanxi Road ⟶ South Huangpi Road1377.418:05:178:06:54201828:07:008:08:2620.121.5238:09:348:11:002021.84South Huangpi Road ⟶ People’s Square1526.818:07:148:09:002018.0428:08:468:10:202021.438:11:208:13:062018.04People’s Square ⟶ Xinzha Road961.218:09:208:10:25—21.628:10:408:11:47—21.1238:13:268:14:33—20.08


#### 4.3.1. Dataset

The outputs of MGA under the disturbance from10s,10.2s,10.4s,…,14.8s,15.0s and −5.0s,−4.8s,…,−0.4s,−0.2s,0.0s are selected as the dataset to train the MGA-GRU network.


#### 4.3.2. Baselines

Same as experiment 2, in the three-train metro system, MGA-GRU is also compared against two baselines: no action and MGA.Figure9 gives the net energy consumption curve of the whole journey under a −2.37 s dwell disturbance (departing early) in the three-train metro system. As can be seen from Figure 9, the MGA method has the best energy-saving effect. However, it also requires a long calculation time.Figure 9
Changes in net energy consumption with different strategies under the −2.37 s dwell disturbance.The rescheduled timetable with the MGA-GRU method under a −2.37 s dwell disturbance in the three-train metro system is shown in Table7.Table 7
The rescheduled timetable with the MGA-GRU method of the three-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:412018.1228:02:008:03:2929.919.8838:04:008:05:3526.818Hengshan Road ⟶ Changshu Road1125.718:02:018:03:1817.621.828:03:598:05:132020.9238:06:018:07:1520.121.84Changshu Road ⟶ South Shaanxi Road979.218:03:358:04:4227.320.6828:05:338:06:3928.120.7638:07:358:08:412018.76South Shaanxi Road ⟶ South Huangpi Road1377.418:05:098:06:352418.7628:07:078:08:3221.519.9238:09:018:10:2620.121.76South Huangpi Road ⟶ People’s Square1526.818:06:598:08:3121.719.5228:08:548:10:2725.81938:10:478:12:1922.819.08People’s Square ⟶ Xinzha Road961.218:08:538:09:59—18.228:10:528:11:58—20.5638:12:428:13:47—18Table8 shows the average calculation time and average total energy consumption of the three strategies in 10 tests. The average calculation time of MGA-GRU to provide the coasting speed and dwell time of each group is only 0.27 s, which meets the real-time requirements of the TTR problem. Besides, the MGA-GRU strategy is energy efficient compared with the no-action strategy. Therefore, MGA-GRU can reschedule the timetable in real time and achieve energy saving after a random dwell disturbance occurs.Table 8
Performances with three strategies in the three-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no-action strategy (%)No action0412.23—MGA13768.68380.827.62MGA-GRU0.27386.846.16


### 4.4. Experiment 4

According to the real case of SML1, there exist at most 3 trains on one track between 2 substations. The goal of experiment 4 is to apply MGA-GRU to a real metro system, which is a bidirectional metro line with five trains on two tracks. Different from experiments 2 and 3, in experiment 4, the disturbances’ range is−5,15s, and each dwell disturbance can occur at Hengshan Road Station or at Changshu Road Station or at South Shaanxi Road Station.The bidirectional metro line with five trains on two tracks is shown in Figure10. The fourteen stations are numbered in sequence from 1 to 14. There are three trains departing from station no.1 and travels in sequence to station no.7, which is called up direction. Then, there is a turning of 60 s in duration from station no.7 to station no.8. After that, each train drives from station no.8 to station no.14, which is called down direction. After that, there is also a turning of 60 s in duration from station no.14 back to station no.1. And there are other two trains departing from station no.8 to station no.7 and then back to station no.8. The departure instant of train no.1 at station no.1 and train no.4 at station no.8 is the same. Besides, the headway time of every two train is also 120 s.Figure 10
Bidirectional metro line with five trains on two tracks.First, MGA is also used to produce the optimal timetable under no disturbance.


#### 4.4.1. Dataset

The outputs of MGA under the disturbance from−5.0s,−4.8s,−4.6s,…,14.6s,14.8s,15.0s are selected as the dataset to train the MGA-GRU network.


#### 4.4.2. Baselines

In the five-train metro system, the proposed MGA-GRU method is compared against three baselines: (i)no action, where each train does not take any measures after disturbances occur; (ii) general GA, where a general GA is used to give an offline strategy to deal with the dwell disturbances; and (iii) MGA, where MGA is used to give an offline strategy to deal with the dwell disturbances. It is expected that MGA-GRU can achieve better energy saving effect than a general GA, which can prove the effectiveness of MGA.Table9 shows the average calculation time and average total energy consumption of the four strategies in 20 tests. The average calculation time of MGA-GRU to provide the coasting speed and dwell time of each group is only 0.33 s, which meets the real-time requirements of the TTR problem as well. And compared with no-action strategy, the MGA-GRU strategy is energy efficient compared with the no-action strategy and can save an average of 7.19% energy. Therefore, MGA-GRU can reschedule the timetable in real time and achieve energy saving after a random dwell disturbance occurs. What is more, MGA (8.73%) achieves better energy saving effect than a general GA (6.15%), which also proves the effectiveness of MGA.Table 9
Performances with three strategies in the five-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no-action strategy (%)No action0741.85—General GA17941.36696.226.15MGA21074.15677.098.73MGA-GRU0.33688.517.19The decision time of MGA-GRU with the onboard computer’s configuration is also discussed. And the configuration of the train’s onboard computer is shown in Table10.Table 10
Configuration of the train’s onboard computer.
ItemsConfiguration informationCPUIntel Celeron G3900RAM4 GB DDR4 2133 MHzROM120G SSDThe configuration on the PC is restricted to the same as the train’s onboard computer, and then experiment 4 is performed again. The experimental results show that the average calculation time is 0.35 s, which reflects that the proposed MGA-GRU method can be applied to the onboard computer.


## 4.1. Experiment 1

The goal of experiment 1 is to validate MGA for solving the energy optimization problem and produce the optimal timetable without a disturbance. MGA is used to solve the energy optimization problem based on equation (7) and the optimal timetable as is shown in Table 3.Table 3
The optimal timetable of the two-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:3029.621.828:02:008:03:4220.118Hengshan Road ⟶ Changshu Road1125.718:01:598:03:2128.41828:04:028:05:2227.218.32Changshu Road ⟶ South Shaanxi Road979.218:03:498:04:5622.021.0828:05:498:07:0123.418.4South Shaanxi Road ⟶ South Huangpi Road1377.418:05:188:06:4523.121.4428:07:258:09:012018South Huangpi Road ⟶ People’s Square1526.818:07:088:08:542018.0428:09:218:11:0626.518.32People’s Square ⟶ Xinzha Road961.218:09:148:10:25—18.0428:11:328:12:44—18.04Figure6 shows the distribution of individuals of the 1st, 10th, and 15th generations produced by MGA. As shown in Figure 6, the distribution of individuals in the 1st generation is discrete. After 10 generations, the individuals’ distribution gradually concentrates. Finally, after 15 generations, the individuals converge with a fitness value of 256.02 kWh, which is the optimal energy consumption without a disturbance.Figure 6
Individuals’ distribution of the 1st, 10th, and 15th generations produced by MGA.In order to prove the effectiveness of MGA, a general GA is also applied to produce the offline timetable without a disturbance under the same condition. Figure7 shows the distribution of individuals of the 1st, 10th, and 15th generations produced by a general GA. After 15 generations, the individuals converge with a fitness value of 276.59 kWh. It can be seen from Figure 7 that the individuals of a general GA concentrate more quickly than those of MGA. What is more, the fitness of a general GA (276.59 kWh) is bigger than that of MGA (256.02 kWh). Therefore, compared with a general GA, the proposed MGA can avoid falling into local optimum prematurely and provide a better solution.Figure 7
Individuals’ distribution of the 1st, 10th, and 15th generations produced by a general GA.


## 4.2. Experiment 2

This experiment is to use the MGA-GUR method to solve the TTR problem under random disturbances in the two-train metro system. The energy-saving effect of the MGA-GRU method is reflected by the saved energy during test compared with the no-action strategy. The real-time performance of the MGA-GRU method is reflected by the time it takes to provide a pair of strategies during testing.


### 4.2.1. Dataset

The outputs of MGA based on equation (8) under the disturbance from 10s,10.2s,10.4s,…,14.8s,15.0s are selected as the dataset to train the MGA-GRU network.


### 4.2.2. Baselines

The proposed MGA-GRU method is compared against two baselines: (i)no action, where each train does not take any measures after disturbances occur and (ii) MGA, where MGA is used to give an offline strategy to deal with the dwell disturbances. The two baselines are representative of the worst and best possible strategies. It is expected that MGA-GRU falls in between these two extreme cases. It should be emphasized that MGA-GRU can reschedule the timetable in real time.The changes of the net energy consumption with these three strategies are compared during testing. The dwell disturbance which occurs at train no. 1 at Changshu Road Station is 13.45 s. Figure8 shows the net energy consumption curve of the whole journey using the three methods. It can be seen from Figure 8 that from the moment when the disturbance occurs, the net energy consumption of no action has always remained the highest. Although MGA can achieve good results in saving energy, it takes a lot of time to provide a decision, which does not meet the real-time requirements for solving the TTR problem. Compared with the above two methods, MGA-GRU can reschedule the timetable in real time and achieve saving energy.Figure 8
Changes in net energy consumption with different strategies under a 13.45 s dwell disturbance.The rescheduled timetable with the MGA-GRU method under a 13.45 s dwell disturbance in the two-train metro system is shown in Table4.Table 4
The rescheduled timetable with the MGA-GRU method in the two-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:3029.621.828:02:008:03:3521.218.04Hengshan Road ⟶ Changshu Road1125.718:01:598:02:2141.91828:03:568:05:122218Changshu Road ⟶ South Shaanxi Road979.218:04:038:05:1129.618.2828:05:348:06:432018.2South Shaanxi Road ⟶ South Huangpi Road1377.418:05:418:07:1129.81828:07:038:08:332018.08South Huangpi Road ⟶ People’s Square1526.818:07:418:09:13201828:08:538:10:2621.818.04People’s Square ⟶ Xinzha Road961.218:09:338:10:39—18.5628:10:488:11:55—18Table5 shows the average calculation time and average total energy consumption of the three strategies in 10 tests. The MGA-GRU strategy is energy efficient compared with the no-action strategy and its average calculation time is only 0.15 s which meets the requirements of real-time effect. Therefore, MGA-GRU can reschedule the timetable in real time and achieve saving energy after a dwell disturbance occurs. It should be noted that although the total energy consumption of the MGA strategy is less than the MGA-GRU strategy, it requires a greatly long calculation time (8694.08 s in total) to reschedule the timetable, which absolutely does not meet the real-time requirements of the TTR problem. In terms of calculation time, MGA-GRU has an absolute superiority.Table 5
Performances with three strategies in the two-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no action strategy (%)No action0293.95—MGA8694.08274.586.59MGA-GRU0.15280.884.45


## 4.2.1. Dataset

The outputs of MGA based on equation (8) under the disturbance from 10s,10.2s,10.4s,…,14.8s,15.0s are selected as the dataset to train the MGA-GRU network.


## 4.2.2. Baselines

The proposed MGA-GRU method is compared against two baselines: (i)no action, where each train does not take any measures after disturbances occur and (ii) MGA, where MGA is used to give an offline strategy to deal with the dwell disturbances. The two baselines are representative of the worst and best possible strategies. It is expected that MGA-GRU falls in between these two extreme cases. It should be emphasized that MGA-GRU can reschedule the timetable in real time.The changes of the net energy consumption with these three strategies are compared during testing. The dwell disturbance which occurs at train no. 1 at Changshu Road Station is 13.45 s. Figure8 shows the net energy consumption curve of the whole journey using the three methods. It can be seen from Figure 8 that from the moment when the disturbance occurs, the net energy consumption of no action has always remained the highest. Although MGA can achieve good results in saving energy, it takes a lot of time to provide a decision, which does not meet the real-time requirements for solving the TTR problem. Compared with the above two methods, MGA-GRU can reschedule the timetable in real time and achieve saving energy.Figure 8
Changes in net energy consumption with different strategies under a 13.45 s dwell disturbance.The rescheduled timetable with the MGA-GRU method under a 13.45 s dwell disturbance in the two-train metro system is shown in Table4.Table 4
The rescheduled timetable with the MGA-GRU method in the two-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:3029.621.828:02:008:03:3521.218.04Hengshan Road ⟶ Changshu Road1125.718:01:598:02:2141.91828:03:568:05:122218Changshu Road ⟶ South Shaanxi Road979.218:04:038:05:1129.618.2828:05:348:06:432018.2South Shaanxi Road ⟶ South Huangpi Road1377.418:05:418:07:1129.81828:07:038:08:332018.08South Huangpi Road ⟶ People’s Square1526.818:07:418:09:13201828:08:538:10:2621.818.04People’s Square ⟶ Xinzha Road961.218:09:338:10:39—18.5628:10:488:11:55—18Table5 shows the average calculation time and average total energy consumption of the three strategies in 10 tests. The MGA-GRU strategy is energy efficient compared with the no-action strategy and its average calculation time is only 0.15 s which meets the requirements of real-time effect. Therefore, MGA-GRU can reschedule the timetable in real time and achieve saving energy after a dwell disturbance occurs. It should be noted that although the total energy consumption of the MGA strategy is less than the MGA-GRU strategy, it requires a greatly long calculation time (8694.08 s in total) to reschedule the timetable, which absolutely does not meet the real-time requirements of the TTR problem. In terms of calculation time, MGA-GRU has an absolute superiority.Table 5
Performances with three strategies in the two-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no action strategy (%)No action0293.95—MGA8694.08274.586.59MGA-GRU0.15280.884.45


## 4.3. Experiment 3

In the real case of SML1, there are at most three trains between two substations. Therefore, it is essential to apply the MGA-GRU method to a three-train metro system. What is more, according to the real case of SML1 [35], the train departs early frequently, which means that the value of a disturbance can be negative. This situation is also taken into consideration in experiment 3.First, MGA produces the optimal timetable without a disturbance based on equation (7), as shown in Table 6.Table 6
The optimal timetable of the three-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:412018.1228:02:008:03:292021.9638:04:008:05:4225.318Hengshan Road ⟶ Changshu Road1125.718:02:018:03:182019.8828:03:498:05:0520.220.5238:06:078:07:2529.519.16Changshu Road ⟶ South Shaanxi Road979.218:03:388:04:5126.31828:05:258:06:3227.521.3238:07:558:09:0726.818South Shaanxi Road ⟶ South Huangpi Road1377.418:05:178:06:54201828:07:008:08:2620.121.5238:09:348:11:002021.84South Huangpi Road ⟶ People’s Square1526.818:07:148:09:002018.0428:08:468:10:202021.438:11:208:13:062018.04People’s Square ⟶ Xinzha Road961.218:09:208:10:25—21.628:10:408:11:47—21.1238:13:268:14:33—20.08


### 4.3.1. Dataset

The outputs of MGA under the disturbance from10s,10.2s,10.4s,…,14.8s,15.0s and −5.0s,−4.8s,…,−0.4s,−0.2s,0.0s are selected as the dataset to train the MGA-GRU network.


### 4.3.2. Baselines

Same as experiment 2, in the three-train metro system, MGA-GRU is also compared against two baselines: no action and MGA.Figure9 gives the net energy consumption curve of the whole journey under a −2.37 s dwell disturbance (departing early) in the three-train metro system. As can be seen from Figure 9, the MGA method has the best energy-saving effect. However, it also requires a long calculation time.Figure 9
Changes in net energy consumption with different strategies under the −2.37 s dwell disturbance.The rescheduled timetable with the MGA-GRU method under a −2.37 s dwell disturbance in the three-train metro system is shown in Table7.Table 7
The rescheduled timetable with the MGA-GRU method of the three-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:412018.1228:02:008:03:2929.919.8838:04:008:05:3526.818Hengshan Road ⟶ Changshu Road1125.718:02:018:03:1817.621.828:03:598:05:132020.9238:06:018:07:1520.121.84Changshu Road ⟶ South Shaanxi Road979.218:03:358:04:4227.320.6828:05:338:06:3928.120.7638:07:358:08:412018.76South Shaanxi Road ⟶ South Huangpi Road1377.418:05:098:06:352418.7628:07:078:08:3221.519.9238:09:018:10:2620.121.76South Huangpi Road ⟶ People’s Square1526.818:06:598:08:3121.719.5228:08:548:10:2725.81938:10:478:12:1922.819.08People’s Square ⟶ Xinzha Road961.218:08:538:09:59—18.228:10:528:11:58—20.5638:12:428:13:47—18Table8 shows the average calculation time and average total energy consumption of the three strategies in 10 tests. The average calculation time of MGA-GRU to provide the coasting speed and dwell time of each group is only 0.27 s, which meets the real-time requirements of the TTR problem. Besides, the MGA-GRU strategy is energy efficient compared with the no-action strategy. Therefore, MGA-GRU can reschedule the timetable in real time and achieve energy saving after a random dwell disturbance occurs.Table 8
Performances with three strategies in the three-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no-action strategy (%)No action0412.23—MGA13768.68380.827.62MGA-GRU0.27386.846.16


## 4.3.1. Dataset

The outputs of MGA under the disturbance from10s,10.2s,10.4s,…,14.8s,15.0s and −5.0s,−4.8s,…,−0.4s,−0.2s,0.0s are selected as the dataset to train the MGA-GRU network.


## 4.3.2. Baselines

Same as experiment 2, in the three-train metro system, MGA-GRU is also compared against two baselines: no action and MGA.Figure9 gives the net energy consumption curve of the whole journey under a −2.37 s dwell disturbance (departing early) in the three-train metro system. As can be seen from Figure 9, the MGA method has the best energy-saving effect. However, it also requires a long calculation time.Figure 9
Changes in net energy consumption with different strategies under the −2.37 s dwell disturbance.The rescheduled timetable with the MGA-GRU method under a −2.37 s dwell disturbance in the three-train metro system is shown in Table7.Table 7
The rescheduled timetable with the MGA-GRU method of the three-train system.
SectionSpacing (m)Train no.Departure instantArrival instantDwell time (s)Coasting speed (m/s)Xujiahui ⟶ Hengshan Road1458.518:00:008:01:412018.1228:02:008:03:2929.919.8838:04:008:05:3526.818Hengshan Road ⟶ Changshu Road1125.718:02:018:03:1817.621.828:03:598:05:132020.9238:06:018:07:1520.121.84Changshu Road ⟶ South Shaanxi Road979.218:03:358:04:4227.320.6828:05:338:06:3928.120.7638:07:358:08:412018.76South Shaanxi Road ⟶ South Huangpi Road1377.418:05:098:06:352418.7628:07:078:08:3221.519.9238:09:018:10:2620.121.76South Huangpi Road ⟶ People’s Square1526.818:06:598:08:3121.719.5228:08:548:10:2725.81938:10:478:12:1922.819.08People’s Square ⟶ Xinzha Road961.218:08:538:09:59—18.228:10:528:11:58—20.5638:12:428:13:47—18Table8 shows the average calculation time and average total energy consumption of the three strategies in 10 tests. The average calculation time of MGA-GRU to provide the coasting speed and dwell time of each group is only 0.27 s, which meets the real-time requirements of the TTR problem. Besides, the MGA-GRU strategy is energy efficient compared with the no-action strategy. Therefore, MGA-GRU can reschedule the timetable in real time and achieve energy saving after a random dwell disturbance occurs.Table 8
Performances with three strategies in the three-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no-action strategy (%)No action0412.23—MGA13768.68380.827.62MGA-GRU0.27386.846.16


## 4.4. Experiment 4

According to the real case of SML1, there exist at most 3 trains on one track between 2 substations. The goal of experiment 4 is to apply MGA-GRU to a real metro system, which is a bidirectional metro line with five trains on two tracks. Different from experiments 2 and 3, in experiment 4, the disturbances’ range is−5,15s, and each dwell disturbance can occur at Hengshan Road Station or at Changshu Road Station or at South Shaanxi Road Station.The bidirectional metro line with five trains on two tracks is shown in Figure10. The fourteen stations are numbered in sequence from 1 to 14. There are three trains departing from station no.1 and travels in sequence to station no.7, which is called up direction. Then, there is a turning of 60 s in duration from station no.7 to station no.8. After that, each train drives from station no.8 to station no.14, which is called down direction. After that, there is also a turning of 60 s in duration from station no.14 back to station no.1. And there are other two trains departing from station no.8 to station no.7 and then back to station no.8. The departure instant of train no.1 at station no.1 and train no.4 at station no.8 is the same. Besides, the headway time of every two train is also 120 s.Figure 10
Bidirectional metro line with five trains on two tracks.First, MGA is also used to produce the optimal timetable under no disturbance.


### 4.4.1. Dataset

The outputs of MGA under the disturbance from−5.0s,−4.8s,−4.6s,…,14.6s,14.8s,15.0s are selected as the dataset to train the MGA-GRU network.


### 4.4.2. Baselines

In the five-train metro system, the proposed MGA-GRU method is compared against three baselines: (i)no action, where each train does not take any measures after disturbances occur; (ii) general GA, where a general GA is used to give an offline strategy to deal with the dwell disturbances; and (iii) MGA, where MGA is used to give an offline strategy to deal with the dwell disturbances. It is expected that MGA-GRU can achieve better energy saving effect than a general GA, which can prove the effectiveness of MGA.Table9 shows the average calculation time and average total energy consumption of the four strategies in 20 tests. The average calculation time of MGA-GRU to provide the coasting speed and dwell time of each group is only 0.33 s, which meets the real-time requirements of the TTR problem as well. And compared with no-action strategy, the MGA-GRU strategy is energy efficient compared with the no-action strategy and can save an average of 7.19% energy. Therefore, MGA-GRU can reschedule the timetable in real time and achieve energy saving after a random dwell disturbance occurs. What is more, MGA (8.73%) achieves better energy saving effect than a general GA (6.15%), which also proves the effectiveness of MGA.Table 9
Performances with three strategies in the five-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no-action strategy (%)No action0741.85—General GA17941.36696.226.15MGA21074.15677.098.73MGA-GRU0.33688.517.19The decision time of MGA-GRU with the onboard computer’s configuration is also discussed. And the configuration of the train’s onboard computer is shown in Table10.Table 10
Configuration of the train’s onboard computer.
ItemsConfiguration informationCPUIntel Celeron G3900RAM4 GB DDR4 2133 MHzROM120G SSDThe configuration on the PC is restricted to the same as the train’s onboard computer, and then experiment 4 is performed again. The experimental results show that the average calculation time is 0.35 s, which reflects that the proposed MGA-GRU method can be applied to the onboard computer.


## 4.4.1. Dataset

The outputs of MGA under the disturbance from−5.0s,−4.8s,−4.6s,…,14.6s,14.8s,15.0s are selected as the dataset to train the MGA-GRU network.


## 4.4.2. Baselines

In the five-train metro system, the proposed MGA-GRU method is compared against three baselines: (i)no action, where each train does not take any measures after disturbances occur; (ii) general GA, where a general GA is used to give an offline strategy to deal with the dwell disturbances; and (iii) MGA, where MGA is used to give an offline strategy to deal with the dwell disturbances. It is expected that MGA-GRU can achieve better energy saving effect than a general GA, which can prove the effectiveness of MGA.Table9 shows the average calculation time and average total energy consumption of the four strategies in 20 tests. The average calculation time of MGA-GRU to provide the coasting speed and dwell time of each group is only 0.33 s, which meets the real-time requirements of the TTR problem as well. And compared with no-action strategy, the MGA-GRU strategy is energy efficient compared with the no-action strategy and can save an average of 7.19% energy. Therefore, MGA-GRU can reschedule the timetable in real time and achieve energy saving after a random dwell disturbance occurs. What is more, MGA (8.73%) achieves better energy saving effect than a general GA (6.15%), which also proves the effectiveness of MGA.Table 9
Performances with three strategies in the five-train metro system.
StrategyCalculation time (s)Net traction energy consumption (kWh)Energy-saving percentage compared with no-action strategy (%)No action0741.85—General GA17941.36696.226.15MGA21074.15677.098.73MGA-GRU0.33688.517.19The decision time of MGA-GRU with the onboard computer’s configuration is also discussed. And the configuration of the train’s onboard computer is shown in Table10.Table 10
Configuration of the train’s onboard computer.
ItemsConfiguration informationCPUIntel Celeron G3900RAM4 GB DDR4 2133 MHzROM120G SSDThe configuration on the PC is restricted to the same as the train’s onboard computer, and then experiment 4 is performed again. The experimental results show that the average calculation time is 0.35 s, which reflects that the proposed MGA-GRU method can be applied to the onboard computer.


## 5. Conclusion

In this paper, a Modified Genetic Algorithm-Gate Recurrent Unit (MGA-GRU) method is proposed to solve the train timetable rescheduling (TTR) problem. The proposed MGA-GRU method can reschedule timetable to optimize the net traction energy consumption of the metro system under a random dwell disturbance in real time. Specifically, the outcomes of modified Genetic Algorithm (MGA) under different dwell disturbances are used as the training set to train the Gate Recurrent Unit (GRU) network (the decision network). After a disturbance occurs, the well-trained decision network can provide appropriate coasting speed and dwell time in real time.Better than traditional optimization methods, such as enhanced brute force (EBF), ant colony optimization (ACO), and Genetic Algorithm (GA), MGA-GRU can achieve real-time train timetable rescheduling. Superior to CDSA, MGA-GRU can rearrange the coasting speed and dwell time of all trains in real time after disturbances occur, so as to achieve better energy-saving effect.Four experiments are conducted on the Shanghai Metro Line One (SML1) pilot network to verify the energy-saving effect and real-time performance of the proposed method. The experimental results show that in the two-train metro system, the three-train metro system, and the five-train metro system (a bidirectional metro line on two tracks) after a disturbance occurs, the MGA-GRU strategy can save an average of 4.45%, 6.16%, and 7.19% of energy compared with the no-action strategy, while the average calculation time for each group of coasting speed and dwell time is only 0.15 s, 0.27 s, and 0.33 s, respectively. In all the two-train metro system, the three-train metro system, and the five-train metro system, the proposed MGA-GRU method can solve the TTR problem under random disturbances in real time.In the future work, according to Taguchi’s experimental design method [36] and other intelligent optimization methods [37], the impact of user-defined parameters on the performance of the proposed algorithm should be analyzed, other parameters should be compared, and the best settings should be decided.



---

*Source: 8882554-2020-12-12.xml*