Research on the Utilization of Metro Regenerative Braking Energy Based on an Improved Differential Evolution Algorithm

Abstract

Urban metro trains have the characteristics of short running distance between stations and frequent starting and braking. A large amount of regenerative braking energy is generated during the braking process. The effective utilization of the regenerative braking energy can substantially reduce the total energy consumption of train operation. In this paper, we establish two integer programming models of train operation that maximize the overlap time between train traction and braking in peak hours and nonpeak hours. On this basis, an improved differential evolution (IDE) algorithm is developed for solving the two integer programming models. The results demonstrate that the overlap time increases by 51.44% after optimization using the IDE algorithm when the headway is set to 154 s in peak hours. The overlap time is further increased by 14.87% by optimizing the headway. In nonpeak hours, the overlap time of traction and braking of the trains in opposite directions at the same station is increased by optimizing the bidirectional departure interval, thereby reducing the total energy consumption of the system.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

Urban metro transportation is safe, comfortable, punctual, and energy-conserving. It is the main public transport mode among various large- and medium-sized cities. As the mileage of metro construction and traffic volume increase, the metro system’s energy consumption increases rapidly. Moreover, the energy consumption of train traction is the main constituent of the total energy consumption. For example, in the Beijing Metro Yi-Zhuang Line, the energy consumption of train traction accounts for approximately 50% of the total energy consumption of the metro system [1]. Therefore, decreasing the energy consumption of train traction is of substantial importance for reducing the energy consumption of the metro system. In various studies, researchers attempted to lower the energy consumption of train operation by optimizing the train velocity curve [2–5] and improving the train operation control strategies [6–8] and realized substantial research achievements. However, it is difficult to reduce the energy consumption of train traction significantly by optimizing the train velocity curve and improving the train operation control strategies if the established train timetable remains unchanged. An urban metro train, as a type of electrified train, has short headway, performs frequent starting and braking, and can produce a substantial amount of regenerative braking energy (regenerative energy) during the braking process. Effective utilization of the regenerative energy can help reduce the total energy consumption of train operation largely. Currently, the regenerative energy is used for resistance energy consumption, is used for energy storage feedback [9], and is adsorbed by an adjacent train [10]. The first two are indirect utilization methods, and the regenerative energy will be consumed in the form of thermal energy, which may not only fail to utilize the regenerative energy effectively but also increase the burden of tunnel ventilation due to the heat dissipation problem. Three main types of storage systems (batteries, supercapacitors, and flywheels) were presented in [9]. Energy storage feedback requires extra equipment and is characterized by complicated maintenance and growing cost. The third type can utilize the energy directly and mainly uses the regenerative energy of the braking train for the traction of other trains that are within the same power supply range by coordinating the running diagrams of the trains. This is currently the most effective means of utilizing the regenerative energy. Therefore, based on the optimization of the single-train operation curve and control strategy, it is necessary to study methods for improving the utilization of regenerative energy by optimizing the train timetable to lower the total energy consumption of train operation. Improving the utilization of regenerative energy has been a hot topic in the literature. Many research efforts aimed at identifying the optimal train timetable for minimizing the energy consumption. Demirci and Celikoglu proposed a timetable optimization model that pairs the accelerating and braking trains to enhance the utilization of the regenerative energy [11]. For enhancing the regenerative energy receptivity in a bidirectional metro transit network, Tang et al. proposed a coordinated train control algorithm that is based on the genetic algorithm [12]. Ramos et al. investigated a timetable optimization model that maximizes the overlap time between traction and braking actions of trains that are in the same substation [13]. Kim et al. considered a mathematical approach that can increase energy savings in timetables and developed a multicriteria mixed-integer programming model. The results demonstrated that the method improved the reusage of regenerative energy by approximately 5% [14]. For using completely the regenerative energy of train braking in stations, an optimized timetable of train movement was proposed in [15], and the genetic algorithm was utilized to optimize the corresponding parameters. Yang et al. formulated an integer optimization model for minimizing the energy consumption, and a genetic algorithm is designed for solving the formulated optimization model to optimize the timetable [1]. The results showed that the proposed scheduling approach can reduce the energy consumption by 6.97% in comparison with the current timetable.

The objective function of the train energy-efficient scheduling problem is nonsmooth and nonlinear. Integer programming deals with optimization problems with integer decision variables, which has been one of the most active research directions in optimization. For example, an integer linear programming formulation is presented for improving the overall cost efficiency in the staff service bus routing problem [16]. In this paper, we formulate the energy-efficient scheduling problem of train operation in the same direction and opposite directions as integer programming models. The traditional optimization methods such as the branch-and-bound method [17] and hybrid methods combined with classical techniques [18] may fail to find a satisfactory solution. Many stochastic approaches are available for solving mixed-integer programming or integer programming problems, such as genetic algorithms [1], simulated annealing algorithms [19], particle swarm optimization [20], and differential evolution (DE) [21]. Among them, the DE algorithm has attracted lots of attention [22–24] since it was first presented by Rainer Storn and Kenneth Price in 1997. DE is considered the most useful recently proposed evolutionary algorithm for solving real-parameter optimization problems because it has fewer parameters and strong robustness. However, in the literature, few attempts have been made to extend the method to discrete space.

Consequently, in this paper, as an extension of the above works, the energy-efficient scheduling problems of the train are solved using an improved differential evolution (IDE) algorithm. The remainder of the paper is organized as follows: Section 2 describes the problem. Section 3 formulates the train operation integer programming model. In Section 4, an IDE algorithm is designed for solving the integer programming model. In Section 5, numerical examples that are based on real-world data from the Nanjing Metro Line 1 are presented. Finally, Section 5 presents the conclusions of this work.

2. Problem Description

Metro train braking is dominated by electric braking and supplemented by air braking. When the train starts braking, it will adopt electric braking initially. If the train is running at a low speed and electric braking does not provide the required braking force, it may adopt the air braking as a supplement. The train will produce a large quantity of regenerative braking energy during the process of electric braking, and the regenerative energy will give priority to the electricity demands of lighting, ventilation, and air-conditioning of the train; however, these demands consume only a small portion of the regenerative energy, thereby leaving a large surplus. In Figure 1, the station distribution of the upward and downward directions and the power flow during the train operation are plotted. Without loss of generality, only the power flow in the upward direction and the power supply zone are plotted; the trend of the power flow in the downward direction and the power supply zone is consistent with that in the upward direction. N stations and M substations are set in the line. The electrical energy is transmitted to the train through the traction substation, supply line, and overhead line system via a 10 kV–35 kV AC bus, while the regenerative current that is generated by the electric braking of the train is transmitted back to the substation through the rail and the return line. The section points in Figure 1 divide the overhead line system into several power supply intervals for convenient repair and to narrow the accident scope. Train i in Figure 1 is in the traction stage, while train i + 1 is in the braking deceleration stage. The regenerative energy that is produced by the braking train can be transmitted back to the substation through the return line and used by other traction trains within the same power supply interval. When the back-fed energy of regenerative braking cannot be completely utilized by trains within the same power supply range, the remaining energy may increase the voltage of the traction network and damage the power supply unit. At this moment, resistance braking shall be launched to ensure that the regenerative energy will not be sent back to the power grid. This amount of energy will be dissipated in the form of thermal energy, which is not effectively utilized. Thus, the effective utilization of the regenerative braking energy is of substantial importance for reducing the train energy consumption.

[figure omitted; refer to PDF]

The number of trains in the line and their headway might impact the utilization of the regenerative braking energy significantly. The higher the rate of traffic flow is, the higher the effective availability of the regenerative braking energy will be. When the headway is longer than 360 s, the coordinated optimization operation of trains might be meaningless. That is because the regenerative energy is utilized in real time and the transmission loss would be huge if the distance is too far. Moreover, if the headway is large, there may not be other trains in the same direction within the same power supply interval. During peak hours, due to the large number of passengers, the small headway, and the huge rate of traffic flow, braking of one train and traction of another train may occur in the same direction and the same power supply interval. During nonpeak hours, due to the few passengers, huge headway, and low rate of traffic flow, it may be difficult to utilize the regenerative energy effectively in the same direction. However, braking of one train and traction of another train in the opposite direction in the same station might occur. In nonpeak hours, the utilization rate of the regenerative braking energy can be improved by using unequal departure intervals; however, unequal departure intervals will affect passenger travel. Studies have shown that equal departure intervals can minimize the average waiting time of passengers [25]. In this paper, we investigate an optimization method for improving the overlap time between the traction and braking actions of adjacent trains in the same direction and in the same substation at peak hours while maximizing the overlap time between the traction and braking actions of trains in opposite directions at the same station during nonpeak hours. The objective of this study is to enhance the availability of regenerative energy via the optimization of the headway, dwell time, and departure interval in opposite directions. Here, four assumptions are made to simplify the problem:

(1)

Due to the short distance between stations, the optimal operation strategy of trains only includes three working actions: traction, coasting, and braking. The velocity curve of train operation between stations is known; namely, the traction, coasting, and braking times of trains are known.

(2)

Trains that are in the same station use the same operation strategy, with the same transfer position and the same traction, coasting, braking, and dwell times.

(3)

The acceleration at the coasting stage is 0, while that at the traction and braking stage is constant.

(4)

The regenerative energy is only used for the train traction within the same power supply interval.

(5)

The train speed is no higher than 80 km/h. The train acceleration is not higher than $1.1\text{m}/{\text{s}}^2$ and not less than $0.9\text{m}/{\text{s}}^2$.

3. Train Operation Optimization Model

3.1. Indices and Parameters

In this paper, all variables and parameters are set as integers numbers to satisfy the engineering requirements. Several principal parameters are introduced as follows:

 

N: number of stations

 

n: station index; $n=\mathrm{1,2},\dots ,N$

 

I: number of up direction trains

 

i: up direction train index, $i=\mathrm{1,2},\dots ,I$

 

J: number of down direction trains

 

$j$: down direction train index, $j=\mathrm{1,2},\dots ,J$

 

$t_a^i\left(n\right)$: time of train i arriving at station n

 

$t_{}^{\mathrm{di}}\left(n\right)$: time of train i departing from station n

 

$t^i\left(n,n+1\right)$: running time of train i between station n and n + 1

 

$t_T^i\left(n,n+1\right)$: traction time of train i between station n and n + 1

 

$t_B^i\left(n,n+1\right)$: braking time of train i between station n and n + 1

 

$t_C^i\left(n,n+1\right)$: coasting time of train i between station n and n + 1

 

$t_n^i$: dwell time at station n

 

$t_h$: headway

 

$t_T$: the whole running time of the train

 

$t_{\mathrm{\Delta }}$: the departure interval of bidirection

There are many control variables in the objective function model. To simplify the problem, it is supposed that the operation strategies of trains that are in the same interval are the same; namely, the traction times, coasting times, and braking times of the trains are known. The dwell time, the headway, and the bidirectional departure interval of trains determine the traction and braking time of adjacent trains in the same direction, as well as the traction and braking time of bidirectional trains in the same station, which play an important role in improving the overlap time. This paper regards the dwell time $t^i\left(n\right)$, the headway $t_h$ , and the bidirectional departure interval $t_{\mathrm{\Delta }}$ as the decision variables of the model.

3.2. Train Regenerative Energy Utilization

According to the overlap time of traction and braking between adjacent trains in the same power supply interval, the utilized regenerative energy can be represented as$$\begin{array}{}\text{(1)}& E_u=\frac{E_r\left(i,i+1\right)\times T\left(i,i+1\right)}{t_b\left(i,i+1\right)},\end{array}$$where $E_u$ denotes the utilized regenerative energy, $E_r$ denotes the regenerative energy that is produced by train i or train i + 1 during the braking process, $T\left(i,i+1\right)$ denotes the overlap time of the traction and braking stage of train i and train i + 1, and $t_b\left(i,i+1\right)$ denotes the braking time of train i or i + 1.

Therefore, according to the overlap time of traction and braking stage of train i and train i + 1 and the braking time of train i or train i + 1, the availability of regenerative energy $\lambda \left(i,i+1\right)$ can be expressed as$$\begin{array}{}\text{(2)}& \lambda \left(i,i+1\right)=\frac{T\left(i,i+1\right)}{t_b\left(i,i+1\right)}.\end{array}$$

According to formula (2), when the braking time is fixed, the longer the overlap time of adjacent trains is, the higher the availability of regenerative energy will be. Therefore, this paper studies an optimization method for enhancing the overlap time between the traction and braking actions of adjacent trains in the same direction and at the same substation at peak hours while maximizing the overlap time between the traction and braking actions of trains in opposite directions at the same station at nonpeak hours.

We establish an objective function for trains that maximizes the overlap time between adjacent trains in the traction and braking stage within the same power supply interval, to increase the utilization of the regenerative energy by optimizing the headway and the dwell time. We also establish an objective function for trains in opposite directions which maximizes the overlap time in the traction and braking stage at the same station, to enhance the availability of regenerative energy by optimizing the departure interval in both directions.

3.3. Objective Function of Train Operation in the Same Direction

Two conditions of train operation in the same direction and with the same power supply interval are considered during peak hours. According to Figure 2(a), train i enters station n + 1 in braking state, and train i + 1 departs from station n − 1 in the traction state simultaneously. If the two trains are in the same power supply interval, then the braking energy of train i can be used for the traction of train i + 1. According to Figure 2(b), train i departs from station n + 1 in the traction state, while train i + 1 will enter station n in the braking state. If the two trains are in the same power supply interval, the braking energy of train i + 1 can be used for the traction of train i.

[figures omitted; refer to PDF]

Therefore, the overlap time of train i and train i + 1 in Figure 2(a) can be expressed as$$\begin{array}{}\text{(3)}& t_1\left(i,n\right)=\left\{\begin{array}{cc}0,\hfill & t_{a1}\ge t_{a4}\text{\hspace{0.17em}or\hspace{0.17em}}{t}_{a2}\le t_{a3},\hfill \\ t_{a2}-t_{a3},\hfill & t_{a3}\le t_{a2}\le t_{a4},\hfill \\ t_{a4}-t_{a1},\hfill & t_{a1}\le t_{a4}\le t_{a2},\hfill \\ t_B^i\left(n,n+1\right),\hfill & t_{a1}\le t_{a3}\text{\hspace{0.17em}and\hspace{0.17em}}{t}_{a2}\ge t_{a4},\hfill \\ t_T^{i+1}\left(n-1,n\right),\hfill & t_{a1}\ge t_{a3}\text{\hspace{0.17em}and\hspace{0.17em}}{t}_{a2}\le t_{a4},\hfill \end{array}\right.\end{array}$$where $t_{a1}=t_d^{i+1}\left(n-1\right)$ and $t_{a2}=t_d^{i+1}\left(n-1\right)+t_T^{i+1}\left(n-1,n\right)$ represent the traction beginning time and ending time, respectively, of train i + 1. $t_{a3}=t_a^i\left(n+1\right)-t_B^i\left(n,n+1\right)$ and $t_{a4}=t_a^i\left(n+1\right)$ represent the braking beginning time and ending time, respectively, of train i.

The overlap time of train i and train i + 1 in Figure 2(b) can be expressed as$$\begin{array}{}\text{(4)}& t_2\left(i,n\right)=\left\{\begin{array}{cc}0,\hfill & t_{b2}\le t_{b3}\text{\hspace{0.17em}or\hspace{0.17em}}{t}_{b1}\ge t_{b4},\hfill \\ t_{b2}-t_{b3},\hfill & t_{b3}\le t_{b2}\le t_{b4},\hfill \\ t_{b4}-t_{b1},\hfill & t_{b1}\le t_{b4}\le t_{b2},\hfill \\ t_T^i\left(n+1,n+2\right),\hfill & t_{b1}\le t_{b3}\text{\hspace{0.17em}and\hspace{0.17em}}{t}_{b2}\ge t_{b4},\hfill \\ t_B^{i+1}\left(n-1,n\right),\hfill & t_{b1}\ge t_{b3}\text{\hspace{0.17em}and\hspace{0.17em}}{t}_{b2}\le t_{b4},\hfill \end{array}\right.\end{array}$$where $t_{b1}=t_a^{i+1}\left(n\right)-t_B^{i+1}\left(n-1,n\right)$ and $t_{b2}=t_a^{i+1}\left(n\right)$ represent the braking beginning time and the ending time, respectively, of train i + 1. $t_{b3}=t_{}^{\mathrm{di}}\left(n+1\right)$ and $t_{b4}=t_{}^{\mathrm{di}}\left(n+1\right)+t_T^i\left(n+1,n+2\right)$ represent the traction beginning time and the ending time, respectively, of train i.

We can obtain the overlap time of all trains in all stations:$$\begin{array}{}\text{(5)}& T_1\left(i,n\right)={\displaystyle \sum _{i=1}^{I-1}{\displaystyle \sum _{n=1}^{N-1}{t}_1\left(i,n\right){\eta }_1\left(n-1,n\right)+t_2\left(i,n\right){\eta }_2\left(n-1,n+1\right)}},\end{array}$$where ${\eta }_1\left(n-1,n\right)=1$ denotes that train i + 1 and train i are in the same electricity supply interval; otherwise, ${\eta }_1\left(n-1,n\right)=0$ in Figure 2(a). ${\eta }_2\left(n-1,n+1\right)=1$ denotes that train i + 1 and train i are in the same electricity supply interval; otherwise, ${\eta }_2\left(n-1,n+1\right)=0$ in Figure 2(b).

Therefore, we formulate the energy-efficient scheduling problem of morning rush hours as an integer programming model:$$\begin{array}{}\text{(6)}& \left\{\begin{array}{cc}\max \hfill & T_1\left(i,n\right)\hfill \\ \text{s.t.}\hfill & t_n^{i,\min }\le t_{}^{\mathrm{di}}\left(n\right)-t_a^i\left(n\right)\le t_n^{i,\max }\hfill \\ \hfill & t_h^{\min }\le t_d^{i+1}\left(n\right)-t_{}^{\mathrm{di}}\left(n\right)\le t_h^{\max }\hfill \\ \hfill & t^i\left(n,n+1\right)=t_a^i\left(n+1\right)-t_{}^{\mathrm{di}}\left(n\right)\hfill \\ \hfill & t_T^{\min }\le t_a^i\left(N\right)-t_a^i\left(1\right)\le t_T^{\max }\hfill \\ \hfill & t_a^i\left(n\right)\in Z,t_{}^{\mathrm{di}}\left(n\right)\in Z,\hfill \end{array}\right.\end{array}$$where the constraint conditions include a dwell time constraint, a headway constraint, an interstation operation time constraint, a total travel time constraint, and a time integer constraint. The model does not consider the bidirectional departure interval.

3.4. Objective Function of Bidirectional Train Operation

Due to the long headway of trains in the same direction during nonpeak hours, the availability of regenerative energy is low. In this case, we consider the bidirectional train operation at the same station.

As illustrated in Figure 3, train i in the upward direction departs from station n in the traction state, while train j in the downward direction will enter station n in the braking deceleration state. If the two stages are in the same time interval, the braking energy of train j can be used for the traction of train i. Therefore, the overlap time of traction and braking of bidirectional trains can be increased by optimizing the overlap time or departure interval of the bidirection trains. The bidirectional departure interval depends on the departure time of train $n$ in the downward direction being earlier or later than that of train $n$ in the upward direction. The setting of a suitable bidirectional departure interval may reduce the voltage fluctuation of the traction network and improve the utilization of the regenerative braking energy.

[figure omitted; refer to PDF]

The overlap time of train i and train j in Figure 3 can be expressed as$$\begin{array}{}\text{(7)}& t_3\left(i,j,n\right)=\left\{\begin{array}{cc}0,\hfill & t_{c1}\ge t_{c4}\text{\hspace{0.17em}or\hspace{0.17em}}{t}_{c2}\le t_{c3},\hfill \\ t_{c2}-t_{c3},\hfill & t_{c3}\le t_{c2}\le t_{c4},\hfill \\ t_{c4}-t_{c1},\hfill & t_{c1}\le t_{c4}\le t_{c2},\hfill \\ t_B^j\left(n+1,n\right),\hfill & t_{c1}\le t_{c3}\text{\hspace{0.17em}and\hspace{0.17em}}{t}_{c2}\ge t_{c4},\hfill \\ t_T^i\left(n,n+1\right),\hfill & t_{c1}\ge t_{c3}\text{\hspace{0.17em}and\hspace{0.17em}}{t}_{c2}\le t_{c4},\hfill \end{array}\right.\end{array}$$where $t_{c1}=t_{}^{\mathrm{di}}\left(n\right)$ and $t_{c2}=t_{}^{\mathrm{di}}\left(n\right)+t_T^i\left(n,n+1\right)$ represent the traction beginning time and the ending time, respectively, of train i. $t_{c3}=t_a^j\left(n\right)-t_B^j\left(n+1,n\right)$ and $t_{c4}=t_a^j\left(n\right)$ represent the braking beginning time and the ending time, respectively, of train j.

The overlap time of all trains in all stations during nonpeak hours of bidirectional operation is$$\begin{array}{}\text{(8)}& T_2\left(i,j,n\right)={\displaystyle \sum _{i=1}^I{\displaystyle \sum _{j=1}^J{\displaystyle \sum _{n=1}^N{t}_3\left(i,j,n\right)}}.}\end{array}$$

Therefore, we formulate the overlap time maximization problem of bidirectional operation as an integer programming model:$$\begin{array}{}\text{(9)}& \left\{\begin{array}{cc}\max \hfill & T_2\left(i,j,n\right)\hfill \\ \text{s.t.}\hfill & t_n^{i,\min }\le t_d^i\left(n\right)-t_a^i\left(n\right)\le t_n^{i,\max }\hfill \\ \hfill & t_h^{\min }\le t_d^{i+1}\left(n\right)-t_d^i\left(n\right)\le t_h^{\max }\hfill \\ \hfill & t^i\left(n,n+1\right)=t_a^i\left(n+1\right)-t_d^i\left(n\right)\hfill \\ \hfill & t_T^{\min }\le t_a^i\left(N\right)-t_a^i\left(1\right)\le t_T^{\max }\hfill \\ \hfill & t_{\Delta }^{\min }\le t_d^i\left(1\right)-t_d^j\left(N\right)\le t_{\Delta }^{\max }\hfill \\ \hfill & t_a^i\left(n\right)\in Z,t_d^i\left(n\right)\in Z,\hfill \end{array}\right.\end{array}$$where the constraints restrict not only the tracking operation of trains in the same direction but also the bidirectional departure interval.

4. Improved Differential Evolution Algorithm

The basic DE algorithm is introduced briefly. The basic DE algorithm includes three main operators: mutation, crossover, and selection. After initialization, the mutation operator chooses individuals from the current population to form a new mutation vector for each target vector. Then, the crossover operator combines the mutation vector and the target vector to generate a trial vector. Finally, the selection vector chooses the more suitable vector from the parent vector and its trial vector to be a new target vector that survives to the next generation.

In this paper, an improved DE (IDE) algorithm is developed for handling integer variables for the nonlinear integer programming model of train tracks. To ensure high convergence speed, the integer variables are only searched in the integer space. We use the rounding operator to deal with the initial population, and the mutation vector and the trial vector are generated via the mutation operation and the crossover operation. Details on the IDE algorithm, including the population initialization, operators, and solution representation, are described in the following.

Assume that the population size is $N_p$ and the problem’s dimension is D. The i-th individual $X_{i,g}$ at the $g$-th generation can be expressed as$$\begin{array}{}\text{(10)}& X_{i,g}=\left(x_{i,g}^1,x_{i,g}^2,\cdots x_{i,g}^D\right),\hspace{1em}i=\mathrm{1,2},\dots ,N_p,\end{array}$$where $x_{i,g}^j$, $j=\mathrm{1,2},\dots ,D$, is randomly generated in terms of a uniform distribution with lower and upper boundaries $\left[X_{\min },X_{\max }\right]$, where $X_{\min }=\left(x_{\min }^1,x_{\min }^2,\dots ,x_{\min }^D\right)$ and $X_{\max }=\left(x_{\max }^1,x_{\max }^2,\dots ,x_{\max }^D\right)$.

4.1. Initialization

The j-th component of the i-th member at $g=0$ is initialized by$$\begin{array}{}\text{(11)}& x_{i,0}^j=x_{\min }^j+\text{INT}\left[\text{rand}\left(\mathrm{0,1}\right)\times \left(x_{\max }^j-x_{\min }^j\right)\right],\hspace{1em}j=\mathrm{1,2},\dots ,D,\end{array}$$where $\text{rand}\left(\mathrm{0,1}\right)$ is a random number that is between 0 and 1 and is drawn from a uniform distribution. The operator $\text{INT}\left(a\right)$ rounds the elements of a to the nearest integers.

4.2. Mutation

The mutation operation that is specified in (12) is referred to as DE/rand/1. For each target vector $X_{i,g}$, $i=\mathrm{1,2},\dots ,N_p$, a mutant vector $V_{i,g}$ is obtained according to$$\begin{array}{}\text{(12)}& V_{i,g}=\text{INT}\left[X_{r_1,g}+F\times \left(X_{r_2,g}-X_{r_3,g}\right)\right],\end{array}$$with random indexes $r_1,r_2,r_3\in \left\{\mathrm{1,2},\dots ,N_p\right\}$. The randomly chosen integers $r_1$, $r_2$, and $r_3$ are selected to be different from each other and different from index i. F is a scaling factor in $\left[\mathrm{0,2}\right]$ for controlling the amplification of the difference vector$\left(X_{r_2,g}-X_{r_3,g}\right)$.

4.3. Crossover

Binomial crossover and exponential crossover are two main crossover types. In binomial crossover, the crossover operator combines the mutation vector and the target vector to generate a new trial vector $U_{i,g}=\left(u_{i,g}^1,u_{i,g}^2,\dots ,u_{i,g}^D\right),i=\mathrm{1,2},\dots ,N_p$, whose j-th variable is expressed as follows:$$\begin{array}{}\text{(13)}& u_{i,g}^j=\left\{\begin{array}{c}{v}_{i,g}^j\text{,}\hspace{1em}{\text{rand}}_j\le CR\text{\hspace{0.17em}or\hspace{0.17em}}j=\text{rand}{n}_i,\\ x_{i,g}^j\text{,}\hspace{1em}{\text{rand}}_j>CR\text{\hspace{0.17em}and\hspace{0.17em}}j\ne \text{rand}{n}_i,\end{array}\right.\end{array}$$where ${\text{rand}}_j$ returns a uniform random number from 0 to 1; $CR\in \left[\mathrm{0,1}\right]$ is the crossover rate; and $\text{rand}{n}_i$ is a randomly chosen index within [1, D], which ensures that $u_{i,g}^j$ obtains at least one element from $v_{i,g}^j$.

According to formula (13), the larger $CR$ is, the larger the contribution of $V_{i,g}$ will be. A larger contribution of $V_{i,g}$ is more favorable for accelerating the search rate. The smaller $CR$ is, the larger the contribution of $X_{i,g}$ will be; a larger contribution of $X_{i,g}$ is more favorable for maintaining the diversity of the population. A value of $CR$ that balances the diversity of the population and the convergence speed must be selected. Therefore, a time-varying crossover probability factor $CR$ is used to improve the performance of the algorithm. In the initial stage, a small $CR$ should be taken to enhance the global searching ability of the algorithm to maintain the diversity of the population. In the later stage, a large $CR$ should be used to improve the local searching ability of the algorithm to enhance the precision of the algorithm. The value of $CR$ increases gradually with the number of iterations. $CR$ is expressed as follows:$$\begin{array}{}\text{(14)}& CR=C{R}^{\min }+\frac{g}{G}\left(C{R}^{\max }-C{R}^{\min }\right),\end{array}$$where $C{R}^{\min },C{R}^{\max }$ represent the minimum value and the maximum value of the crossover operator, respectively. $G$ is the maximum number of evolutions.

4.4. Selection

IDE adopts a greedy selection strategy. The selection operator chooses the more suitable vector from the target vector and the trial vector to be a new target vector. If the trial vector $U_{i,g}$ yields an equally good or better fitness function value than $X_{i,g}$, $U_{i,g}$ replaces $X_{i,g+1}$; otherwise, the vector $X_{i,g}$ is retained. The selection scheme is as follows:$$\begin{array}{}\text{(15)}& X_{i,g+1}=\left\{\begin{array}{cc}{U}_{i,g},& \text{if\hspace{0.17em}}f\left(U_{i,g}\right)\ge f\left(X_{i,g}\right),\\ X_{i,g},& \text{otherwise,}\end{array}\right.\end{array}$$where $X_{i,g+1}$ is the $g$ + 1-th target vector and $f\left(\right)$ is the objective function. Formula (15) is for a maximization problem.

The main steps of the IDE algorithm are as follows:

 

Step 1. Initialization.

 

Step 1.1. Initialize the parameters: the population size $N_p$, the scaling factor F, the lower boundary $C{R}^{\min }$ and the upper boundary $C{R}^{\max }$ of the crossover rate, and the max-generation G.

 

Step 1.2. Set the generation index to $g$ = 0. Generate a random initial population $X_{i,0}$, $i=\mathrm{1,2},\dots ,N_p$.

 

Step 2. Calculate the train performance index via formulas (6) and (9) by target vector $X_{i,g}$.

 

Step 3. If $g$ = max-generation G, return the best searched solution. Otherwise, set $g$ = $g$ + 1 and go to Step 4.

 

Step 4. Generate new vectors.

 

Step 4.1. For each target vector $X_{i,g}$, $i=\mathrm{1,2},\dots ,N_p$, generate a mutant vector $V_{i,g}$ via (12).

 

Step 4.2. Generate a new trial vector $U_{i,g},i=\mathrm{1,2},\dots ,N_p$, via formulas (13) and (14).

 

Step 4.3. Via formula (15), generate the $g+1$-th target vector $X_{i,g+1}$.

 

Step 5. Return to Step 2.

5. Numerical Example

In this section, two numerical examples are presented to demonstrate the availability of the proposed models, and the solution approaches are based on the data of Nanjing Metro Line 1 in China. The simulation is performed on a PC (with a 3.5 GHz processor and 8 GB memory) running the Windows 10 platform with MATLAB R2016a software.

Due to the time dependence of the characteristics of train operation, different decision variables are adopted for the optimization in peak hours and nonpeak hours. The utilization of regeneration energy is enhanced by optimizing the headway and the dwell time in peak hours, whereas the bidirectional departure interval is optimized in nonpeak hours. Nanjing Metro Line 1 has 27 stations and 14 substations in total. The operation times, the interstation distances, and the dwell times of trains in all stations in the simulation are listed in Table 1.

Table 1

Distances, dwell times, and departure times of sections for simulation.

Station	Distance (m)	Dwell time (s)	Departure time (s)
MGQ	0	30	30
HSZ	1148	30	162
NJRS	2273	40	292
XMFR	3981	30	445
XWM	5046	30	557
GL	6305	30	680
ZJR	7170	30	778
XJK	8321	45	908
ZFY	9449	30	1021
SSJ	10359	30	1125
ZHM	12282	35	1294
ADM	14383	35	1473
TLS	15775	30	1612
RJDD	17071	30	1730
HSM	18153	30	1839
NJSRS	20008	40	2001
SLDD	22304	30	2180
HDQ	23655	30	2305
STR	24563	30	2405
BJH	25900	30	2526
XLW	27394	30	2679
ZSR	28533	30	2802
TYDD	30465	30	2956
LMDD	31785	30	3076
NMU	33341	30	3212
NJCI	36077	30	3411
CPU	38051	30	3576

For the convenience of analysis, it is supposed that the operation strategy of a single train is known; namely, the traction, coasting, and braking times of the train are known between stations. According to Table 1, the train operation time in the upward direction is 3576 s, and the total braking time is 437 s.

5.1. Assumptions

The quantitative constraints on the headway and dwell time in peak hours are as follows:

(1)

To guarantee the safety of trains, the headway is longer than 130 s. Meanwhile, to guarantee the operation efficiency in peak hours, the headway is shorter than 300 s.

(2)

According to Table 1, the dwell time ranges from 30 to 45 s, and the dwell time is optimized based on the existing dwell time ($\pm 5$ s).

(3)

To reduce the waiting times of passengers, the train departure time with unequal intervals changes within $\pm 15$ s of the equal interval departure time.

5.2. Case 1

In this case, to enhance the utilization of the regenerative energy, we increase the overlap time of traction and braking of adjacent trains through optimizing the headway and dwell time at each station in peak hours. To clarify the impacts of the headway and dwell time on the overlap time of trains, simulations are conducted under two conditions: optimizing the dwell time while the headway remains unchanged and optimizing the headway while the dwell time remains unchanged.

5.2.1. Optimizing the Dwell Time while the Headway Remains Unchanged

We perform the IDE algorithm procedure with $N_p=100$, $F=0.5$, $C{R}^{\min }=0.4$, $C{R}^{\max }=0.9$, and $G=80$. The number of independent individuals is set to 30. The IDE algorithm can be used to optimize the dwell times of the trains at each station so that the traction and braking times of the trains can be optimized and the overlap times of adjacent trains can be increased. Constant headway means that the headway of each train is the same during the operation period. The overlap time depends on the sum of the total overlap times of traction and braking of all the adjacent trains in the same power supply area in a running period. The first upward direction train takes $t_T$ = 3576 s to complete the journey. This is also the time that is taken by the first train to travel from MGQ station to CPU station. We increase $t_h$ from 150 s to 240 s with a step size of 1 s within the constraints. The dwell time is optimized to obtain the overlap times of adjacent trains with different headways. The simulation results are presented in Table 2 and Figure 4.

Table 2

Train dwell times before and after optimization.

Station	Dwell time before optimize (s)	Optimized dwell time (s)
		$t_h=150$	$t_h=155$	$t_h=160$	$t_h=165$
MGQ	30	30	29	27	27
HSZ	30	27	30	28	28
NJRS	40	41	42	39	42
XMFR	30	32	30	32	31
XWM	30	30	31	33	31
GL	30	27	29	30	29
ZJR	30	32	31	29	29
XJK	45	48	45	44	47
ZFY	30	26	28	28	26
SSJ	30	30	32	32	33
ZHM	35	34	35	34	32
ADM	35	36	34	35	35
TLS	30	31	29	30	27
RJDD	30	32	33	32	30
HSM	30	29	28	27	30
NJSRS	40	42	40	41	43
SLDD	30	27	29	30	29
HDQ	30	29	32	31	31
STR	30	32	30	28	30
BJH	30	30	33	32	32
XLW	30	28	27	27	28
ZSR	30	32	29	30	33
TYDD	30	30	34	32	28
LMDD	30	30	29	28	34
NMU	30	29	30	31	30
NJCI	30	31	32	31	28
CPU	30	30	30	30	30

[figure omitted; refer to PDF]

Table 2 lists the train dwell times before and after optimization for $t_h$ = 150, 155, 160, and 165. According to Table 2, the dwell time after optimization and before optimization differs and the change is within $\pm 5$ s, which satisfies the requirements. Figure 4 shows the total overlap time curves of the traction and braking of adjacent trains in the same power supply area before and after the optimization of the dwell time as $t_h$ increases from 150 s to 240 s with a step size of 1 s. According to Figure 4, the total overlap time is small before the optimization of the dwell time, and the overlap time may be very small at each headway. When $t_h$ = 154 s, the overlap time is only 1390 s before optimization. After the IDE optimization, the overlap time is 2105 s. Compared with the nonoptimization time, the overlap time increases by 51.44%. This is because the dwell time of the train at each station is changed, and the traction and braking times of adjacent trains are changed, which effectively increases the overlap times of adjacent trains in the same power supply area. Moreover, according to Figure 4, the overlap time tends to decrease with the increase of the headway. This is because the number of online trains decreases with the increase of the headway, which reduces the total overlap time. It is concluded from Table 2 and Figure 4 that the total overlap time of trains can be improved by optimizing the dwell time at different headways, which provides an optimized operation scheme for train operation requirements at different headways.

5.2.2. Optimizing the Headway while the Dwell Time Remains Unchanged

According to Figure 4, the maximum overlap time is 2105 s after the optimization of the dwell time at $t_h$ = 154 s. Therefore, this example uses the dwell time data at this time as the simulation data, and the overlap time can be further improved by optimizing the train headway. To ensure that the increase of the overlap time in this example is not caused by the decrease of the headway and the increase of the number of online trains, the headway is set to be greater than or equal to $t_h=154$ s. To reduce the passengers’ waiting times, the train departure time of unequal intervals is set to change within the range of equal interval departure times with $t_h\in \left[\mathrm{154,169}\right]$. We perform the IDE algorithm procedure with $N_p=100$, $F=0.5$, $C{R}^{\min }=0.4$, $C{R}^{\max }=0.9$, and $G=80$. The number of independent individuals is set to 30. The simulation results are presented in Table 3. According to Table 3, in a running cycle, the headways of the trains are not equal. At this time, the overlap time of traction and braking between adjacent trains is 2418 s, which is further increased by 14.87% through optimizing the headway.

Table 3

Train headway.

Train index i	Headway	Train index i	Headway
1	155	12	161
2	154	13	162
3	156	14	155
4	161	15	154
5	158	16	154
6	154	17	156
7	168	18	155
8	154	19	163
9	155	20	154
10	156	21	154
11	154	22	154

5.3. Case 2

In this case, the proposed approach IDE algorithm is applied to solve the integer programming model of bidirection train operation. In nonpeak hours, the headway is long and the regenerative energy utilization of trains in the same direction is low. Therefore, this study does not consider the overlap time of the tracking operation of trains in the same direction during nonpeak hours; it only considers the total overlap time of traction and braking of opposite trains at the same station. To reduce the passengers’ waiting times, only equal headway is considered in nonpeak hours in the upward direction. However, the train headway is long, and the bidirectional departure interval can vary over a wide range; hence, the optimization degree of the dwell time is limited compared with the first two variables. Therefore, in this example, we study the optimization of the bidirectional departure interval under a specified headway in the upward direction when the train dwell time remains unchanged.

In the simulation, we increase the headway $t_h$ of the upward direction from 360 s to 480 s with step size of 10 s and set the train cycle to $t_T$ = 3576 s. Table 4 presents the bidirectional departure intervals after optimization by the IDE algorithm when $t_h$ = 360 s, 370 s, 380 s, and 390 s. In Table 4, a positive number indicates that the departure time of train $n$ in the downward direction is later than that of train $n$ in the upward direction, whereas a negative number indicates that the departure time of train $n$ in the downward direction is earlier than that of train $n$ in the upward direction. In each operating cycle, the number of online trains is 9, and the overlap times of the traction and braking of trains at the same station are 536 s, 528 s, 511 s, and 519 s, respectively. However, if the bidirectional departure interval is 0, the total overlap times of traction and braking at the same station are only 337 s, 357 s, 318 s, and 305 s. The overlap times of the upward and downward trains at the same station were increased by 59.05%, 47.90%, 60.69%, and 70.16% via optimization.

Table 4

Optimized bidirectional train departure intervals.

Train index j	1	2	3	4	5	6	7	8	9
$t_h=360\text{\hspace{0.17em}s}$	23	16	14	−22	−23	20	−18	15	−25
$t_h=370\text{\hspace{0.17em}s}$	32	26	−16	−37	−21	19	−15	−23	35
$t_h=380\text{\hspace{0.17em}s}$	33	35	−18	−39	−32	−11	37	35	−40
$t_h=390\text{\hspace{0.17em}s}$	38	50	−23	−41	−39	15	−27	−17	44

Figure 5 plots the total overlap times of trains at the same station in the bidirectional departure interval when the headway is increased from 360 s to 480 s before and after the optimization. According to Figure 5, the overlap time is substantially improved after the optimization of the bidirectional departure interval under any headway in the upward direction.

[figure omitted; refer to PDF]

Therefore, through the algorithm that is proposed in this paper, a suitable headway in the upward direction and dwell time can be obtained according to the operational demand. After optimizing the bidirectional departure interval, the overlap time can be effectively improved.

6. Conclusion

Aiming at realizing short headway and frequent start and braking in metro trains, this paper studies a kind of train operation schemes that can enhance the utilization of the regenerative braking energy of trains by optimizing the dwell time, the headway, and the bidirectional departure interval. An improved differential evolution algorithm is proposed for solving the integer programming model of the train operation’s overlap time. It solves the integer programming model by rounding the variation vector of the standard DE algorithm, which further improves the search performance of the algorithm by setting a time-varying crossover probability factor. The simulation results illustrate that the overlap time of traction and braking can be effectively improved by optimizing the train’s dwell time and headway during peak hours. In nonpeak hours, the overlap time of traction and braking of bidirectional trains at the same station is improved by optimizing the bidirectional departure interval. Thus, the availability rate of regenerative energy is effectively increased.

Acknowledgments

This work was supported by the National Natural Science Foundation (NNSF) of China under Grant 61503180, Six Talent Peaks Project in Jiangsu Province of China under Grant 2016-JXQC-015, Science Foundation of Higher Education of Jiangsu Province under Grants 15KJA460007 and 18KJB510016, and the Fund of Nanjing Institute of Technology under Grants CKJA201605, CKJB201702, and CKJA201804.

References

[1] X. Yang, A. Chen, X. Li, B. Ning, T. Tang, "An energy-efficient scheduling approach to improve the utilization of regenerative energy for metro systems," Transportation Research Part C: Emerging Technologies, vol. 57, pp. 13-29, DOI: 10.1016/J.TRC.2015.05.002, 2015.

[2] E. Khmelnitsky, "On an optimal control problem of train operation," IEEE Transactions on Automatic Control, vol. 45 no. 7, pp. 1257-1266, DOI: 10.1109/9.867018, 2000.

[3] D. Canca, A. Zarzo, "Design of energy-efficient timetables in two-way railway rapid transit lines," Transportation Research Part B: Methodological, vol. 102, pp. 142-161, DOI: 10.1016/j.trb.2017.05.012, 2017.

[4] G. M. Scheepmaker, R. M. P. Goverde, L. G. Kroon, L. G. Kroon, "Review of energy-efficient train control and timetabling," European Journal of Operational Research, vol. 257 no. 2, pp. 355-376, DOI: 10.1016/j.ejor.2016.09.044, 2017.

[5] N. Zhao, C. Roberts, S. Hillmansen, Z. Tian, "An integrated metro operation optimization to minimize energy consumption," Transportation Research Part C, vol. 75, pp. 168-182, DOI: 10.1016/j.trc.2016.12.013, 2017.

[6] P. Wang, R. M. P. Goverde, P. Goverde, "Multi-train trajectory optimization for energy efficiency and delay recovery on single-track railway lines," Transportation Research Part B: Methodological, vol. 105, pp. 340-361, DOI: 10.1016/j.trb.2017.09.012, 2017.

[7] R. Cheng, D. Chen, B. Cheng, S. Zheng, "Intelligent driving methods based on expert knowledge and online optimization for high-speed trains," Expert Systems with Applications, vol. 87, pp. 228-239, DOI: 10.1016/j.eswa.2017.06.006, 2017.

[8] G. M. Scheepmaker, R. M. P. Goverde, P. Goverde, "The interplay between energy-efficient train control and scheduled running time supplements," Journal of Rail Transport Planning & Management, vol. 5 no. 4, pp. 225-239, DOI: 10.1016/j.jrtpm.2015.10.003, 2015.

[9] N. Ghaviha, J. Campillo, M. Bohlin, E. Dahlquist, "Review of application of energy storage devices in railway transportation," Energy Procedia, vol. 105, pp. 4561-4568, DOI: 10.1016/j.egypro.2017.03.980, 2017.

[10] X. Yang, X. Li, Z. Y. Gao, H. W. Wang, T. Tang, "A cooperative scheduling model for timetable optimization in subway systems," IEEE Transactions on Intelligent Transportations Systems, vol. 14 no. 1, pp. 438-447, DOI: 10.1109/TITS.2012.2219620, 2013.

[11] I. E. Demirci, H. B. Celikoglu, "Timetable optimization for utilization of regenerative braking energy: a single line case over Istanbul metro network," Proceedings of the 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pp. 2309-2314, DOI: 10.1109/ITSC.2018.8569553, .

[12] H. Tang, C. T. Dick, X. Feng, "Improving regenerative energy receptivity in metro transit systems," Transportation Research Record: Journal of the Transportation Research Board, vol. 2534 no. 1, pp. 48-56, DOI: 10.3141/2534-07, 2015.

[13] A. Ramos, M. T. Peria, A. Fernandez, "Mathematical programming approach to underground timetabling problem for maximizing time synchronization," Proceedings of the CIO, pp. 1395-1405, .

[14] K. M. Kim, K. T. Kim, M. S. Han, "A model and approaches for synchronized energy saving in timetabling," Proceedigns of the WCRR, pp. 2309-2314, .

[15] A. Nasri, M. Fekri Moghadam, H. Mokhtari, "Timetable optimization for maximum usage of regenerative energy of braking in electrical railway systems," Proceedings of the SPEEDAM, pp. 1218-1221, DOI: 10.1109/SPEEDAM.2010.5542099, .

[16] S. Hulagu, H. B. Celikoglu, "An integer linear programming formulation for routing problem of University Bus Service," AIRO Springer Series, vol. 1, pp. 303-311, DOI: 10.1007/978-3-030-00473-6_33, 2018.

[17] B. Borchers, J. E. Mitchell, "An improved branch and bound algorithm for mixed integer nonlinear programs," Computers & Operations Research, vol. 21 no. 4, pp. 359-367, DOI: 10.1016/0305-0548(94)90024-8, 1994.

[18] K. Abhishek, S. Leyffer, J. T. Linderoth, "FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs," INFORMS Journal on Computing, vol. 22 no. 4, pp. 555-567, DOI: 10.1287/ijoc.1090.0373, 2010.

[19] S. L. Rosen, C. M. Harmonosky, "An improved simulated annealing simulation optimization method for discrete parameter stochastic systems," Computers & Operations Research, vol. 32 no. 2, pp. 343-358, DOI: 10.1016/S0305-0548(03)00240-5, 2005.

[20] T. Yue, T. Guan-zheng, D. Shu-guang, "Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems," Journal of Central South University, vol. 7, pp. 2731-2742, DOI: 10.1007/s11771-014-2235-6, 2014.

[21] R. Storn, K. Price, "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces," Journal of Global Optimization, vol. 11 no. 4, pp. 341-359, DOI: 10.1023/a:1008202821328, 1997.

[22] S. Zhou, X. Li, N. Du, Y. Pang, H. Chen, "A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost," Computers & Operations Research, vol. 96, pp. 55-68, DOI: 10.1016/j.cor.2018.04.009, 2018.

[23] A. W. Mohamed, "An efficient modified differential evolution algorithm for solving constrained non-linear integer and mixed-integer global optimization problems," International Journal of Machine Learning and Cybernetics, vol. 8 no. 3, pp. 989-1007, DOI: 10.1007/s13042-015-0479-6, 2017.

[24] Y.-C. Lin, K.-S. Huang, F.-S. Wang, "Plant scheduling and planning using mixed-integer hybrid differential evolution with multiplier updating," Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), pp. 593-600, DOI: 10.1109/cec.2000.870351, .

[25] G. Carlos, "Self-organization leads to supraoptimal performance in public transportation systems," PLoS One, vol. 6 no. 6,DOI: 10.1371/journal.pone.0021469, 2011.