# A Short Turning Strategy for Train Scheduling Optimization in an Urban Rail Transit Line: The Case of Beijing Subway Line 4

Authors: Miao Zhang; Yihui Wang; Shuai Su; Tao Tang; Bin Ning
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

In urban rail transit systems, train scheduling plays an important role in improving the transport capacity to alleviate the urban traffic pressure of huge passenger demand and reducing the operation costs for operators. This paper considers the train scheduling with short turning strategy for an urban rail transit line with multiple depots. In addition, the utilization of trains is also taken into consideration. First, we develop a mixed integer nonlinear programming (MINLP) model for the train scheduling, where short turning train services and full-length train services are optimized based on the predefined headway obtained by the passenger demand analysis. The MINLP model is then transformed into a mixed integer linear programming (MILP) model according to several transformation properties. The resulting MILP problem can be solved efficiently by existing solvers, e.g., CPLEX. Two case studies with different scales are constructed to assess the performance of train schedules with the short turning strategy based on the data of Beijing Subway line 4. The simulation results show that the reduction of the utilization of trains is about 20.69%.


---

## Body

## 1. Introduction

With the rapid development of the urban rail transit systems, more and more researches pay attention to train scheduling. Researchers have devoted themselves to optimize the train schedule to assist help dispatchers make better decisions meeting passengers and operators expectations. The objective functions are most concentrated on enhancing passengers satisfaction in terms of degree of crowdedness [1–3], passengers waiting time [2, 4, 5] and passengers travel time [6, 7] or reducing operation costs in terms of energy consumption [6, 8–10], trains [11, 12], train travel time [13], etc. Not only does the urban rail transit systems expand fast, but also the passenger demand rises significantly. In the 15 urban rail lines operated by Beijing Mass Transit Railway Operation Corporation Limited, the numbers of sections (i.e., the trip between two consecutive stations) where load factors are over 100% and 120% are up to 38 and 9, respectively. Note that the load factor is a parameter to assess the performance of a transport system. It is defined as the dimensionless ratio of passenger-kilometers traveled to seat-kilometers available. In 2016, China’s volume of passenger traffic reaches 16.09 billion per year except for five regional express rail lines and eight modern trams, which shows an increase by 16.6% compared to last year. Figure 1 shows a comparison between the passenger flow of a quantity of Chinese cities in 2015, 2016, and 2017 [14]. Under such huge pressure of large passenger demand, several strategies are adopted for operators to tackle it. For example, reducing the headway of departure times to increase the number of train services, which is limited by the capacity of urban rail transit line and minimum turnaround time required by trains, adopting the capacity restriction method like closing several stations that have large passenger flow, offering plenty of discounts during low peak period, and so forth. However, drawbacks remain in these strategies such as the shortage of trains and the dissatisfaction of passenger for inconvenience caused by using other means of transportation. In particular, the passenger demand of an urban rail transit line is not evenly distributed at all stations but shows a tendency such as a convex curve that increases gradually and then drops from the maximal volume point to the end of the line or a curve like a ladder [15]. Due to the unbalanced circumstance, train operation pattern with short turning strategy is better to satisfy the unevenly distributed passenger demand [16].Figure 1
Comparison of passenger flows in 2015, 2016, and 2017 for the metro systems in the cities of China.In past decades, plenty of models and algorithms have been proposed to solve the train scheduling problem with short turning strategy (Table1). Furth [17] proposed schedule coordination mode to denote the ratio between the number of short turning train services and full-length train services. They illustrated that the operation pattern with 1:1 schedule coordination mode can provide a better performance than train schedules with full-length train services for an OD matrix obtained from a survey, which means that a short turning service appears between two full-length services can meet passenger demand better. Tirachini et al. [18] developed a short turning model to optimize the frequencies, vehicle sizes, and turnaround stations for the short turning and full-length train services on a bus corridor. Only a single operation period is taken into consideration in this work, while Site and Filippi [19] focused on service patterns over different operation periods for a bus corridor to minimize the cost for users and operators by taking short turning strategy and variable vehicle sizes into consideration. Leffler et al. [20] dealt with the problem to determine where the turnaround station for a short turning service is and when a bus is a short turning service on a single bidirectional bus line in real-time. Canca et al. [21] considered inserting short turning services to deal with a disruption situation such as infrastructure incidences for rapid transit systems with the objective of diminishing the passenger waiting time. Ghaemi et al. [22] also considered a situation with a complete blockage and presented a mixed integer linear programming model to compute the train schedule by adopting short turning strategy. As for the optimization problem of train scheduling with short turning strategy in urban rail transit systems, Wang and Ni [23] set a nonlinear mixed integer programming model with the objective of minimizing the passengers' travel costs, and the operating costs. Bai et al. [24] established a model aiming at minimizing the trains according to the spatial distribution of passengers to optimize and balance train operation scheme. According to the prediction of passenger flow and the amount of trains, Li et al. [25] discussed the different operation patterns with different schedule coordination mode and the choice of the turnaround station based on the Line 1 in Shanghai, which is the first urban rail transit line with short turning strategy. Wang [26] took the passenger flow and trains into consideration with short turning strategy based on a single line in urban rail transit network and establish a multiobjective model to optimize the train schedule by minimizing the number of trains and the variance of the actual passenger capacity and the expected passenger capacity. Hu [27] analyzed the cause of disequilibrium passenger flow and the feasibility of operation pattern with short turning strategy and evaluates the train schedule by trains and the factor of loading.Table 1
Summary of the relevant studies with short turning train scheduling.
Publication Objective Decision variables Solution approach Wang [26] minimize the number of trains short turning service headway and cycles fuzzy optimization Wang and Ni [23] minimize the passenger travel cost and enterprise operation cost short turning offsets, turn back station ideal point method Canca et al. [21] reduce the passenger waiting time turn back points location, departure and arrival times, short turning offsets MILP Bai et al. [24] minimize the number of trains turn back point location, headway, turning times enumeration method Ghaemi et al. [22] minimize the delays and canceled services after blockage short turning stations routes and platform tracks MILPTrain circulation plan is also important for the train scheduling because the number of the trains is limited. Chang et al. [28] proposed an integrated optimization model for train scheduling and utilization planning problems. Peeters and Kroon [29] developed an integer programming model to find an efficient railway train circulation on a set of interacting train lines by a branch-and-price algorithm. Abbink et al. [30] proposed a model to obtain an optimal allocation of railway train with the objective to minimize the shortages of capacity during the rush hours, where the optimal solution is more effective than the manually planned one. Lai et al. [31] developed a model which covered a lot of characteristics, such as train, inspection, utilization path, and operation. Corts et al. [32] took deadheading into consideration and proposed a model to set the optimal value of frequencies and capacity of vehicles, combining deadheading and short turning into an integrated fleet management strategy.The contribution of this paper is a train scheduling model adopting short turning strategy to satisfy the passenger demand for an urban rail transit line with multiple depots. We integrate headway deviation and train circulation plan for all train services to establish a mixed integer linear programming model. We also take departure times, dwell times, and train orders into consideration.The remainder of the paper is structured as follows. Section2 introduces train operation and presents the assumptions and notations for the train scheduling model. Section 3 formulates the optimal model with decision variables, objective function, and constraints for the optimization problem. In Section 4, the optimization problem is transformed into an MILP problem through three transformation properties. In Section 5, a case study is implemented based on the data of Beijing Subway line 4. Finally, the conclusion and future work are presented in Section 6.


## 2. Problem Description

This section illustrates the concepts that are relevant to train operation and the train scheduling with a short turning strategy in an urban rail transit line. The assumptions and notations used for the train scheduling model with short turning strategy are also described.


### 2.1. Train Operation

The urban rail transit line in this paper is defined as a double-track rail line as shown in Figure2 and the operation of trains in one direction is not influenced by the other. Train services in different directions are indexed differently. Three depots A, B, and C are connected with station 1, station J, and station P, respectively. The direction from station 1 to station P is referred to as the up direction, and the direction from station P to station 1 is referred to as the down direction. Block sections are divided into two areas, where area 1 includes the block section from station J+1 to station P and area 2 denotes the block section from station 1 to station J. Both short turning train services and full-length train services can run through area 2, but for area 1, only can full-length train services operate in it. In particular, the short turning train services are defined as train services only run in area 2. We divide the operation time of the urban rail transit line into several time intervals according to the passenger traffic flow, which is indexed by k. We introduce i and l to index a train service in the up and down direction with i∈Sserviceup={1,2,…,Itotalup} and l∈Sservicedn={1,2,…,Itotaldn}, where Itotalup and Itotaldn denote the total number of train services for both directions.(1)Itotalup=∑k=1KIup,k,(2)Itotaldn=∑k=1KIdn,k,where K is the number of time intervals and Iup,k and Idn,k denote the number of train services during the kth time interval in the up and down direction, respectively.Figure 2
The layout of an urban rail transit line.There are several situations for train operations on the urban rail transit line. Figure3(a) is to demonstrate the possible operations for a short turning train service in the up direction that comes out from Depot A. Situation 1 depicts a short turning train service that goes back to Depot B, and in Situation 2, a short turning train service turnaround at the destination station and then the connection train service goes back to Depot A. As for Situation 3, not only does the short turning train service turnaround at the station J, but also the connection train service in the down direction turnaround at its destination station, that is station 1. For full-length train services operating in the urban rail transit line, Figure 3(b) also shows several situations that are similar to Figure 3(a). Accordingly, there are also 6 situations for operation of train services in the down direction.Figure 3
Possible situations for operations of train services in the up direction.
(a) (b)


### 2.2. Optimal Train Scheduling Problem

As stated by Meng and Zhou [33], to improve the competitive advantages of rail operators, providing punctual and reliable train services is a fundamental goal. A train schedule typically contains detailed departure times, arrival times, train orders, and train circulation plan for each train service in the urban rail transit line. We aim to minimize the total headway deviation between the actual headway and the predefined headway of departure and arrival times. Meanwhile, the trains utilization can also be optimized to reduce the size of trains and provide more train services.The main decision variables of the train scheduling optimization problem are(1)
departure times and arrival times of train services at the origin and destination station for both directions;(2)
types of train services, which means that a train service is a short turning one or a full-length one;(3)
connection relationship between train services in the up direction and down direction.As for constraints, departure and arrival times of each train services, train orders of train services, headways, including headways for train services in area 1 and area 2, and train circulation plan should be included.Note that we only consider the headways at the origin station and the destination station, because the running times and dwell times are constants that the headway at the interstation should be equal to the headway at the origin station.It is assumed that 5 train services should be served and there are different passenger demands during area 1 and area 2, where the values are 360s and 180s, respectively. Passengers in area 2 hope to get on train with the headway equaling to 180s, while passengers in area 1 only need a headway about 360s. For train operation pattern without short turning strategy, two patterns can be constructed with a single frequency. Pattern 1 is to satisfy the passenger demand in area 1, that the headway of departure time is 360s as shown in Figure4. It can cause 180s×5 increasing in headway, which is obtained by the sum of headway difference in area 2. Pattern 2 focuses on the passenger demand in area 2 and the headway of departure time is 180s as shown in Figure 5. It also has the same influence with Pattern 1. However, when the short turning train services depart between two consecutive full-length train services like Figure 6, the passenger demand for both areas can be satisfied well.Figure 4
Only passenger demand in area 1 can be satisfied.Figure 5
Only passenger demands in area 2 can be satisfied.Figure 6
Both passenger demands in areas 1 and 2 can be satisfied.


### 2.3. Assumptions about the Train Operation

The train scheduling model with short turning strategy mainly consider the departure times of train services for both directions, headways, turnaround operations and train circulation plans. In this paper, we make the following assumptions to simplify the optimal problem.(i)
A1: the station capacity per direction is equal to 1, which means that there is no overtaking at any point in the urban rail transit line.(ii)
A2: there are two short turning train services at most between two full-length train services.(iii)
A3: the running times and dwell times between stations are constants.(iv)
A4: there are enough trains to serve the train services for three depots.Assumption A1 guarantees the first-in first-out order for train services, which is valid for most urban rail transit lines. Assumption A2 is introduced to reduce the waiting time of passengers whose destinations are not in the short turning area. The fixed running times and dwell times in assumption A3 ensure that departure times of train services can obtain when the headway and the departure time of the first train service are predefined. Assumption A4 means that the depot capacity is not included in this paper.


### 2.4. Notations

As mentioned in assumption A3, the following parameters should be given: the running times and dwell times for short turning train services and full-length train services in both directions. To describe the detailed modeling methods, subscripts and parameters are shown in Table2 and decision variables are shown in Table 3.Table 2
Subscripts and parameters.
symbol description i , i ′ index for train services in the up direction l , l ′ index for train services in the down direction o origin d destination A,B,C depots J total number of stations for short-turning P total number of stations for whole line K total number of time intervals up up operation direction dn down operation direction I t o t a l u p total number of train services in the up direction I t o t a l d n total number of train services in the down direction S s e r v i c e u p set of train services in the up direction{1,2,...,Itotalup} S s e r v i c e d n set of train services in the down direction{1,2,...,Itotaldn} r s u p running time for short turning trains in the up direction r f u p running time for full-length trains in the up direction r s d n running time for short turning trains in the down direction r f d n running time for full-length trains in the down direction τ s u p dwell time for short turning trains in the up direction τ f u p dwell time for full-length trains in the up direction τ s d n dwell time for short turning trains in the down direction τ f d n dwell time for full-length trains in the down direction I u p , k the number of train services in thekth time interval for up direction I d n , k the number of train services in thekth time interval for down direction d o , 1 p r e predetermined departure time for the first train service at the origin station d o , t o t a l p r e predetermined departure time for the last train service at the origin station h m i n minimal headway h m a x maximal headway H 2 , k u p expected headway of train services in area 2 during thekth time interval in the up direction H 1 , k u p expected headway of train services in area 1 during thekth time interval in the up direction H 2 , k d n expected headway of train services in area 2 during thekth time interval in the down direction H 1 , k d n expected headway of train services in area 1 during thekth time interval in the down direction r m i n t u r n minimal turnaround time r m a x t u r n maximal turnaround time M a sufficiently large positive numberTable 3
Decision variables.
symbol description d o , i u p departure time of train servicei in the up direction at the origin d d , i u p departure time of train servicei in the up direction at the destination d o , l d n departure time of train servicei in the down direction at the origin d d , l d n departure time of train servicei in the down direction at the destination δ i 0-1 binary variables, ifδi=1, then train service i is a short turning train service γ l 0-1 binary variables, ifγl=1, then train service l is a short turning train service ε ( i , l ) 0-1 binary variables, ifε(i,l)=1, then train service l is the connection train of train service i at the destination station η ( l , i ) 0-1 binary variables, ifη(l,i)=1, then train service i is the connection train of train service l at the destination station α i u p 0-1 binary variables, if traini in the up direction comes out from the depot, αiup=0, otherwise, αiup=1 α l d n 0-1 binary variables, if trainl in the down direction comes out from the depot, αldn=0, otherwise, αldn=1 β i u p 0-1 binary variables, if traini in the up direction goes back to the depot, βiup=0, otherwise, βiup=1 β l d n 0-1 binary variables, if trainl in the down direction goes back to the depot, βldn=0, otherwise, βldn=1


## 2.1. Train Operation

The urban rail transit line in this paper is defined as a double-track rail line as shown in Figure2 and the operation of trains in one direction is not influenced by the other. Train services in different directions are indexed differently. Three depots A, B, and C are connected with station 1, station J, and station P, respectively. The direction from station 1 to station P is referred to as the up direction, and the direction from station P to station 1 is referred to as the down direction. Block sections are divided into two areas, where area 1 includes the block section from station J+1 to station P and area 2 denotes the block section from station 1 to station J. Both short turning train services and full-length train services can run through area 2, but for area 1, only can full-length train services operate in it. In particular, the short turning train services are defined as train services only run in area 2. We divide the operation time of the urban rail transit line into several time intervals according to the passenger traffic flow, which is indexed by k. We introduce i and l to index a train service in the up and down direction with i∈Sserviceup={1,2,…,Itotalup} and l∈Sservicedn={1,2,…,Itotaldn}, where Itotalup and Itotaldn denote the total number of train services for both directions.(1)Itotalup=∑k=1KIup,k,(2)Itotaldn=∑k=1KIdn,k,where K is the number of time intervals and Iup,k and Idn,k denote the number of train services during the kth time interval in the up and down direction, respectively.Figure 2
The layout of an urban rail transit line.There are several situations for train operations on the urban rail transit line. Figure3(a) is to demonstrate the possible operations for a short turning train service in the up direction that comes out from Depot A. Situation 1 depicts a short turning train service that goes back to Depot B, and in Situation 2, a short turning train service turnaround at the destination station and then the connection train service goes back to Depot A. As for Situation 3, not only does the short turning train service turnaround at the station J, but also the connection train service in the down direction turnaround at its destination station, that is station 1. For full-length train services operating in the urban rail transit line, Figure 3(b) also shows several situations that are similar to Figure 3(a). Accordingly, there are also 6 situations for operation of train services in the down direction.Figure 3
Possible situations for operations of train services in the up direction.
(a) (b)


## 2.2. Optimal Train Scheduling Problem

As stated by Meng and Zhou [33], to improve the competitive advantages of rail operators, providing punctual and reliable train services is a fundamental goal. A train schedule typically contains detailed departure times, arrival times, train orders, and train circulation plan for each train service in the urban rail transit line. We aim to minimize the total headway deviation between the actual headway and the predefined headway of departure and arrival times. Meanwhile, the trains utilization can also be optimized to reduce the size of trains and provide more train services.The main decision variables of the train scheduling optimization problem are(1)
departure times and arrival times of train services at the origin and destination station for both directions;(2)
types of train services, which means that a train service is a short turning one or a full-length one;(3)
connection relationship between train services in the up direction and down direction.As for constraints, departure and arrival times of each train services, train orders of train services, headways, including headways for train services in area 1 and area 2, and train circulation plan should be included.Note that we only consider the headways at the origin station and the destination station, because the running times and dwell times are constants that the headway at the interstation should be equal to the headway at the origin station.It is assumed that 5 train services should be served and there are different passenger demands during area 1 and area 2, where the values are 360s and 180s, respectively. Passengers in area 2 hope to get on train with the headway equaling to 180s, while passengers in area 1 only need a headway about 360s. For train operation pattern without short turning strategy, two patterns can be constructed with a single frequency. Pattern 1 is to satisfy the passenger demand in area 1, that the headway of departure time is 360s as shown in Figure4. It can cause 180s×5 increasing in headway, which is obtained by the sum of headway difference in area 2. Pattern 2 focuses on the passenger demand in area 2 and the headway of departure time is 180s as shown in Figure 5. It also has the same influence with Pattern 1. However, when the short turning train services depart between two consecutive full-length train services like Figure 6, the passenger demand for both areas can be satisfied well.Figure 4
Only passenger demand in area 1 can be satisfied.Figure 5
Only passenger demands in area 2 can be satisfied.Figure 6
Both passenger demands in areas 1 and 2 can be satisfied.


## 2.3. Assumptions about the Train Operation

The train scheduling model with short turning strategy mainly consider the departure times of train services for both directions, headways, turnaround operations and train circulation plans. In this paper, we make the following assumptions to simplify the optimal problem.(i)
A1: the station capacity per direction is equal to 1, which means that there is no overtaking at any point in the urban rail transit line.(ii)
A2: there are two short turning train services at most between two full-length train services.(iii)
A3: the running times and dwell times between stations are constants.(iv)
A4: there are enough trains to serve the train services for three depots.Assumption A1 guarantees the first-in first-out order for train services, which is valid for most urban rail transit lines. Assumption A2 is introduced to reduce the waiting time of passengers whose destinations are not in the short turning area. The fixed running times and dwell times in assumption A3 ensure that departure times of train services can obtain when the headway and the departure time of the first train service are predefined. Assumption A4 means that the depot capacity is not included in this paper.


## 2.4. Notations

As mentioned in assumption A3, the following parameters should be given: the running times and dwell times for short turning train services and full-length train services in both directions. To describe the detailed modeling methods, subscripts and parameters are shown in Table2 and decision variables are shown in Table 3.Table 2
Subscripts and parameters.
symbol description i , i ′ index for train services in the up direction l , l ′ index for train services in the down direction o origin d destination A,B,C depots J total number of stations for short-turning P total number of stations for whole line K total number of time intervals up up operation direction dn down operation direction I t o t a l u p total number of train services in the up direction I t o t a l d n total number of train services in the down direction S s e r v i c e u p set of train services in the up direction{1,2,...,Itotalup} S s e r v i c e d n set of train services in the down direction{1,2,...,Itotaldn} r s u p running time for short turning trains in the up direction r f u p running time for full-length trains in the up direction r s d n running time for short turning trains in the down direction r f d n running time for full-length trains in the down direction τ s u p dwell time for short turning trains in the up direction τ f u p dwell time for full-length trains in the up direction τ s d n dwell time for short turning trains in the down direction τ f d n dwell time for full-length trains in the down direction I u p , k the number of train services in thekth time interval for up direction I d n , k the number of train services in thekth time interval for down direction d o , 1 p r e predetermined departure time for the first train service at the origin station d o , t o t a l p r e predetermined departure time for the last train service at the origin station h m i n minimal headway h m a x maximal headway H 2 , k u p expected headway of train services in area 2 during thekth time interval in the up direction H 1 , k u p expected headway of train services in area 1 during thekth time interval in the up direction H 2 , k d n expected headway of train services in area 2 during thekth time interval in the down direction H 1 , k d n expected headway of train services in area 1 during thekth time interval in the down direction r m i n t u r n minimal turnaround time r m a x t u r n maximal turnaround time M a sufficiently large positive numberTable 3
Decision variables.
symbol description d o , i u p departure time of train servicei in the up direction at the origin d d , i u p departure time of train servicei in the up direction at the destination d o , l d n departure time of train servicei in the down direction at the origin d d , l d n departure time of train servicei in the down direction at the destination δ i 0-1 binary variables, ifδi=1, then train service i is a short turning train service γ l 0-1 binary variables, ifγl=1, then train service l is a short turning train service ε ( i , l ) 0-1 binary variables, ifε(i,l)=1, then train service l is the connection train of train service i at the destination station η ( l , i ) 0-1 binary variables, ifη(l,i)=1, then train service i is the connection train of train service l at the destination station α i u p 0-1 binary variables, if traini in the up direction comes out from the depot, αiup=0, otherwise, αiup=1 α l d n 0-1 binary variables, if trainl in the down direction comes out from the depot, αldn=0, otherwise, αldn=1 β i u p 0-1 binary variables, if traini in the up direction goes back to the depot, βiup=0, otherwise, βiup=1 β l d n 0-1 binary variables, if trainl in the down direction goes back to the depot, βldn=0, otherwise, βldn=1


## 3. Modeling Formulation

To describe the detailed mathematical formulation, the decision variables are introduced as given in Table2.The variablesdo,iup and do,ldn are used to directly describe the time-stamps when train service i and l departs from the origin station. dd,iup and dd,ldn denote the time-stamps when train service i and l departs from the destination station, respectively. Actually, in this paper, arrival times are calculated by departure times plus the dwell times instead of introducing other variables to denote the arrival times. The departure time at the destination station equals the departure time at the origin station plus the running time and the dwell time at the intermediate stations.The objective is to minimize the headway deviation and the number of trains as mentioned in Section2.2. The headway deviation can be divided into two parts; one is the headway deviation for train services in area 1, which is represented by hi,1up and hl,1dn. The other is the headway deviation for train services in area 2 and it is denoted by hi,2up and hl,2dn. The key problem is to define whether a train service is a short turning one or a full-length one for both directions, which is solved by introducing these two binary variables δi and γl as shown in the following expressions:(3)δi=1,trainserviceiisashortturningtrainservice,0,train  serviceiis  a  full-length  train  service,and(4)γl=1,trainservicelisashortturningtrainservice,0,train  servicelis  a  full-length  train  service.Actually, the key point to calculatehi,1up and hl,1dn is to find the departure times of two consecutive full-length train services. Based on Assumption A2, there are three circumstances C1, C2, and C3 as shown in Figure 7. Assume that a train service i is a full-length train service, which means that δi=0. When there is no short turning train service between two full-length train services as C1, then train service i+1 must be a full-length one with δi+1=0 and hi,1up must be equal to do,i+1up-do,iup. If there is only one short turning train service between two full-length train service, which means δi+1=1, δi+2=0, then hi,1up should be calculated by do,i+2up-do,iup. As for C3, it is obvious that hi,1up should be calculated by do,i+3up-do,iup with δi+1=1, δi+2=1, and δi+3=0. The circumstances are the same for train services in the down direction.Figure 7
Possible combinations of short turning and full-length train services in the up direction.Based on the above circumstances,hi,1up and hl,1dn can be calculated as follows:(5)hi,1up=1-δi1-δi+1do,i+1up-do,iup+1-δiδi+11-δi+2do,i+2up-do,iup+1-δiδi+1δi+21-δi+3do,i+3up-do,iup=do,i+1up-do,iup-δido,i+1up-do,iup-δi+1do,i+1up-do,iup+δiδi+1do,i+1up-do,iup+δi+1do,i+2up-do,iup-δiδi+1do,i+2up-do,iup-δi+1δi+2do,i+2up-do,iup+δiδi+1δi+2do,i+2up-do,iup+δi+1δi+2do,i+3up-do,iup-δiδi+1δi+2do,i+3up-do,iup-δi+1δi+2δi+3do,i+3up-do,iup+δiδi+1δi+2δi+3do,i+3up-do,iup,and(6)
h
l
,
1
d
n
=
1
-
γ
l
1
-
γ
l
+
1
d
o
,
l
+
1
d
n
-
d
o
,
l
d
n
+
1
-
γ
l
γ
l
+
1
1
-
γ
l
+
2
d
o
,
l
+
2
d
n
-
d
o
,
l
d
n
+
1
-
γ
l
γ
l
+
1
γ
l
+
2
1
-
γ
l
+
3
d
o
,
l
+
3
d
n
-
d
o
,
l
d
n
=
d
o
,
l
+
1
d
n
-
d
o
,
l
d
n
-
γ
l
d
o
,
l
+
1
d
n
-
d
o
,
l
d
n
-
γ
l
+
1
d
o
,
l
+
1
d
n
-
d
o
,
l
d
n
+
γ
l
γ
l
+
1
d
o
,
l
+
1
d
n
-
d
o
,
l
d
n
+
γ
l
+
1
d
o
,
l
+
2
d
n
-
d
o
,
l
d
n
-
γ
l
γ
l
+
1
d
o
,
l
+
2
d
n
-
d
o
,
l
d
n
-
γ
l
+
1
γ
l
+
2
d
o
,
l
+
2
d
n
-
d
o
,
l
d
n
+
γ
l
γ
l
+
1
γ
l
+
2
d
o
,
l
+
2
d
n
-
d
o
,
l
d
n
+
γ
l
+
1
γ
l
+
2
d
o
,
l
+
3
d
n
-
d
o
,
l
d
n
-
γ
l
γ
l
+
1
γ
l
+
2
d
o
,
l
+
3
d
n
-
d
o
,
l
d
n
-
γ
l
+
1
γ
l
+
2
γ
l
+
3
d
o
,
l
+
3
d
n
-
d
o
,
l
d
n
+
γ
l
γ
l
+
1
γ
l
+
2
γ
l
+
3
d
o
,
l
+
3
d
n
-
d
o
,
l
d
n
.Accordingly, hi,2up is the headway between departure times of all consecutive train services, which can be calculated as follows:(7)hi,2up=do,i+1up-do,iup.As short turning train services and full-length train services in the down direction do not have fixed origins, hl,2dn should be calculated by the following equation:(8)hl,2dn=dd,l+1dn-dd,ldn.As for minimizing the number of trains, it is equivalent to maximize the number of train services that are served by the same train. We introduce two binary variablesεi,l and ηl,i to express whether a train service i and a train service l are served by the same train or not for both directions.(9)εi,l=1,trainservicelistheconnectiontrainserviceoftrainservicei,0,trainservicelisnottheconnectiontrainserviceoftrainservicei.and(10)ηl,i=1,trainserviceiistheconnectiontrainserviceoftrainservicel,0,trainserviceiisnottheconnectiontrainserviceoftrainservicel.Based on above descriptions, the optimal problem is now formulated as the following problem:(11)Z=min⁡w1·f1F1+w2·f2F2where(12)F1=min⁡f1=min⁡∑k=1K∑i=∑m=0k-1Iup,m+1∑m=1kIup,mhi,2up-H1,kup+hi,1up-1-δiH2,kup+∑k=1K∑l=∑n=0k-1Idn,n+1∑n=1kIdn,nhl,2dn-H1,kdn+hl,1dn-1-γlH2,kdn,(13)F2=min⁡f2=-min⁡∑i=1Itotalup∑l=1Itotaldnεi,l+ηl,i,and(14)w1+w2=1.The formula above should be subject to the following groups constraints:Group 1 (departure time constraints). To describe the relationship between the departure times of train services at the origin and the destination in different directions, the following two constraints should be satisfied:(15)dd,iup=do,iup+δi×rsup+τsup+1-δi×rfup+τfup,(16)dd,ldn=do,ldn+γl×rsdn+τsdn+1-γl×rfdn+τfdn.Group 2(train order constraints). As shown in Figure 8, the train order of train services in the same direction is fixed in this paper, which means that train service i must depart before train service i+1 and train service l must arrive before train service l+1.Figure 8
The order of train services in the up and down directions.Group 3 (headway constraints). The headway for departure times of two consecutive train services must be larger than the minimal headway and smaller than the maximal headway.Headway of train services in area 1 is(17)hmin-M×1-δi≤hi,1up≤hmax+M×1-δi,and(18)hmin-M×1-γl≤hl,1dn≤hmax-M×1-γl,where M is a sufficiently large positive number. If train service i or l is a full-length one, that is δi=0 or γl=0, then the headway of train services in area 1 is larger than the minimum headway and smaller than the maximum headway. If i or l is a short turning train service, then (17) and (18) can be satisfied automatically.Headway of train services in area 2 is(19)hmin≤hi,2up≤hmax,and(20)hmin≤hl,2dn≤hmax.Group 4 (train circulation plan constraints). According to the layout of the urban rail transit line, a train service may come out from the depot or be served by a train that just finishes a previous train service. After arriving at the destination station, a train service could go back to the depot or just turnaround and the same train serves another train service. αiup, αldn, βiup, and βldn are introduced to describe the above operation of train services for both directions.(21)αiup=1,trainserviceidoesnotcomeoutfromthedepot,0,trainserviceicomesoutfromthedepot.(22)αldn=1,trainserviceldoesnotcomeoutfromthedepot,0,trainservicelcomesoutfromthedepot.(23)βiup=1,trainserviceidoesnotgobacktothedepot,0,trainserviceigoesbacktothedepot.(24)βldn=1,trainserviceldoesnotgobacktothedepot,0,trainservicelgoesbacktothedepot.Based on the above definition of operation for train services, the following constraints should be satisfied:(25)αiup=∑l∈Sservicednηl,i,(26)αldn=∑i∈Sserviceupεi,l,(27)βiup=∑l∈Sservicednεi,l,(28)βldn=∑i∈Sserviceupηl,i,where (25) means that if a train service i in the up direction does not come out from the depot, that is αiup=1, then there must be a train service l in the down direction that turnarounds at its destination station and train service i is served by the same train, which means that ηl,i=1 and βldn=1. Accordingly, (26) denotes that if a train service l does not come out from the depot with αldn=1, then there must be train service i turnarounds and the train which serves the train service i will serve the train service l; that is, εi,l=1 and βiup=1. As for (27), when a train service i does not go back to the depot, which means that βiup=1, then the train must turnaround and serve another train service l with εi,l=1 and αldn=1. Similarly, if a train service l does not go back to the depot with βldn=1, then a train service i must be served by the same train with train service l; that is, ηl,i=1 and αiup=1.In addition, the following constraint must be involved to ensure that a short turning train service in the up direction will not connect with a full-length train service in the down direction or a full-length train service in the up direction will not connect with a short turning train service in the down direction:(29)εi,l≤1+2δiγl-δi-γlFurthermore, if a train service turnarounds at the destination station, then the actual turnaround time must be larger than the minimal turnaround time and smaller than the maximal turnaround time, which can be formulated as follows:(30)rminturn-M×1-εi,l⩽do,ldn-dd,iup⩽rmaxturn+M×1-εi,l,(31)rminturn-M×1-ηl,i⩽do,iup-dd,ldn⩽rmaxturn+M×1-ηl,i.Note that M is a big value in this paper.


## 4. Solution Approach: MILP Approach

The mixed integer nonlinear model can be transformed into a mixed integer linear programming MILP problem based on several transformation properties. We introduce three properties to linearize the nonlinear section in the model proposed above according to [34].(i)
PropertyI is described as follows: a new auxiliary real-valued variable z is introduced to replace δ×f~, where δ is a logical variable and f~ is a real-value variable. When δ=0⇒z=0, and δ=1⇒z=f~, then z=δ×f~ is equivalent to(32)z≤f~max×δ,z≥f~min×δ,z≤f~-f~min×1-δ,z≥f~-f~max×1-δ,wheref~max is the maximal value of f~ and f~min is the minimal value of f~.(ii)
PropertyII: there are two logical variables multiplied, i.e., δ1×δ2. It can be replaced by an auxiliary logical variable δ3, which is equivalent to(33)-δ1+δ3≤0,-δ2+δ3≤0,δ1+δ2-δ3≤1,whereδ1=0,δ2=0⇒δ3=0; δ1=0,δ2=1 or δ1=1,δ2=0⇒δ3=0; and δ1=1,δ2=1⇒δ3=1.(iii)
PropertyIII: for an optimal problem with the objective to minimize fobj, where fobj=f~, we introduce a new auxiliary real-valued variable w~ to replace fobj and transform f~ as follows:(34)w~≥f~w~≥-f~.Taking nonlinear terms in constraints that related to train services in the up direction for example, the following terms in (5) should be transformed according to property I:We introducez1,i=δido,i+1up-do,iup, z2,i=δi+1do,i+1up-do,iup, z3,i=δiδi+1do,i+1up-do,iup, z4,i=δi+1do,i+2up-do,iup, z5,i=δiδi+1do,i+2up-do,iup, z6,i=δi+1δi+2do,i+2up-do,iup, z7,i=δiδi+1δi+2do,i+2up-do,iup, z8,i=δi+1δi+2do,i+3up-do,iup, z9,i=δiδi+1δi+2do,i+3up-do,iup, z10,i=δi+1δi+2δi+3do,i+3up-do,iup and z11,i=δiδi+1δi+2δi+3do,i+3up-do,iup(35)z1,i≤hmax·δi,z1,i≥hmin·δi,z1,i≤do,i+1up-do,iup-hmin·1-δi,z1,i≥do,i+1up-do,iup-hmax·1-δi.(36)z2,i≤hmax·δi+1,z2,i≥hmin·δi+1,z2,i≤do,i+1up-do,iup-hmin·1-δi+1,z2,i≥do,i+1up-do,iup-hmax·1-δi+1.(37)z3,i≤hmax·δiδi+1,z3,i≥hmin·δiδi+1,z3,i≤do,i+1up-do,iup-hmin·1-δiδi+1,z3,i≥do,i+1up-do,iup-hmax·1-δiδi+1.(38)z4,i≤hmax·δi+1,z4,i≥hmin·δi+1,z4,i≤do,i+2up-do,iup-hmin·1-δi+1,z4,i≥do,i+2up-do,iup-hmax·1-δi+1.(39)z5,i≤hmax·δiδi+1,z5,i≥hmin·δiδi+1,z5,i≤do,i+2up-do,iup-hmin·1-δiδi+1,z5,i≥do,i+2up-do,iup-hmax·1-δiδi+1.(40)z6,i≤hmax·δi+1δi+2,z6,i≥hmin·δi+1δi+2,z6,i≤do,i+2up-do,iup-hmin·1-δi+1δi+2,z6,i≥do,i+2up-do,iup-hmax·1-δi+1δi+2.(41)z7,i≤hmax·δiδi+1δi+2,z7,i≥hmin·δiδi+1δi+2,z7,i≤do,i+2up-do,iup-hmin·1-δiδi+1δi+2,z7,i≥do,i+2up-do,iup-hmax·1-δiδi+1δi+2.(42)z8,i≤hmax·δi+1δi+2,z8,i≥hmin·δi+1δi+2,z8,i≤do,i+3up-do,iup-hmin·1-δi+1δi+2,z8,i≥do,i+3up-do,iup-hmax·1-δi+1δi+2.(43)z9,i≤hmax·δiδi+1δi+2,z9,i≥hmin·δiδi+1δi+2,z9,i≤do,i+3up-do,iup-hmin·1-δiδi+1δi+2,z9,i≥do,i+3up-do,iup-hmax·1-δiδi+1δi+2.(44)z10,i≤hmax·δi+1δi+2δi+3,z10,i≥hmin·δi+1δi+2δi+3,z10,i≤do,i+3up-do,iup-hmin·1-δi+1δi+2δi+3,z10,i≥do,i+3up-do,iup-hmax·1-δi+1δi+2δi+3.(45)z11,i≤hmax·δiδi+1δi+2δi+3,z11,i≥hmin·δiδi+1δi+2δi+3,z11,i≤do,i+3up-do,iup-hmin·1-δiδi+1δi+2δi+3,z11,i≥do,i+3up-do,iup-hmax·1-δiδi+1δi+2δi+3.Note that some terms in (35)-(45) also should be linearized according to property II. δi·δi+1, δi·δi+1·δi+2, δi·δi+1·δi+2·δi+3 can be translated into the following constraints:(46)-δi+W1,i≤0,-δi+1+W1,i≤0,δi+δi+1-W1,i≤1.(47)-W1,i+W2,i≤0,-δi+2+W2,i≤0,W1,i+δi+2-W2,i≤1.(48)-W1,i+W3,i≤0,-W1,i+1+W3,i≤0,W1,i+W1,i+1-W3,i≤1,where W1,i=δi·δi+1, W2,i=W1,i·δi+2, and W3,i=F1,i·W1,i+1. All these terms should be replaced according to the previous two properties. As for the absolute value terms in the objective function, they are equivalent to the following constraints:(49)xi,k≥h2,iup-H2,kup,xi,k≥-h2,iup-H2,kup.(50)yl,k≥h2,ldn-H2,kdn,yl,k≥-h2,ldn-H2,kdn.(51)ui,k≥hi,1up-1-δiH1,kup,ui,k≥-hi,1up-1-δiH1,kup.(52)vl,k≥hl,1dn-1-γlH1,kdn,vl,k≥-hl,1dn-1-γlH1,kdn.where xi,k=h2,iup-H2,kup, yl,k=h2,ldn-H2,kdn, ui,k=hi,1up-1-δiH1,kup, and vl,k=hl,1dn-1-γlH1,kdn. The corresponding term f1 in the objective function will be reformulated as the following equation:(53)f1=∑k=1K∑i=∑m=0k-1Iup,m+1∑m=1kIup,mxi,k+ui,k+∑k=1K∑l=∑n=0k-1Idn,n+1∑n=1kIdn,nyl,k+vl,k.The MILP problem can be solved by several existing commercial and free solvers, such as CPLEX, Xpress-MP, and GLPK.


## 5. Case Study

In order to assess the performance of the proposed MILP approach, we use two case studies to compare two operation patterns with or without short turning strategy based on the data of Beijing Subway line 4, where the layout is shown in Figure9. Three depots connect with Anheqiao North Station, Xingong Station, and Tiantongyuan Station, respectively. Area 1 includes the section between Xingong Station and Tiantongyuan Station. Section from Xingong Station to Anheqiao North Station is depicted as area 2. In addition, the parameters of train operation in line 4 also are given in Table 4. The MILP problem is solved by the commercial solver CPLEX with version 12.6 on a 64-bit windows 10 platform.Table 4
Operation information of line 4 in Beijing.
up direction down direction Station Running time[s] Dwell time[s] Station Running time[s] Dwell time[s] AnheqiaoNorth 3750 30 Tiangongyuan 2405 35 Xingong 2430 30 Xingong 3762 35 Tiangongyuan - 30 AnheqiaoNorth - 30Figure 9
The layout of the Beijing Subway line 4.Note that the value of dwell times at stations inside short turning circle in the up direction is 875s and outside short turning circle in the up direction is 1175s. For train services in the down direction, the dwell time at stations in area 1 and area 2 are 1190s and 900s, respectively.


### 5.1. Case Study-A

In case study-A, the input parameters are given in Table5. The total number of train services for both directions is 37, respectively. In particular, the maximal and minimal turnaround times are 720s and 120s. As for the headway of departure times must larger than 120s and smaller than 660s. Note that the departure time of the first train service in both directions is 5:00, and the departure time of the last train service for both directions is 9:00.Table 5
Input parameters for case study-A.
Time interval I u p I d n H2,kup[s] H1,kup[s] H2,kdn[s] H1,kdn[s] 5:00-7:00 13 13 600 600 600 600 7:00-9:00 24 24 600 300 600 300In this case study, a small scale of simulation is conducted. We assume the operation time of the urban rail transit line is 5:00 to 9:00 and the time period is divided into 2 time intervals as shown in Table5. The urban rail transit line serves different operation pattern during two time intervals. During 5:00 to 7:00, the ratio of headway in area 2 and headway in area 1 is 1, which means that there would be only full-length train services operated. From 7:00 to 9:00, headway in area 2 is twice headway in area 1; then there would be a short turning train service served between two full-length train services.Firstly, we calculate the value ofF1 and F2 by (12) and (13), which also should meet all constraints. We obtain the values of F1 and F2 which are 894 and -46, respectively. There are 15377 constrains and 4757 variables. Then the comparison of optimization results is shown in Table 6, where we set several different values for weight coefficients w1 and w2. Computing times, objective function values, and gap are considered in this result. The result of computing time shows a decreasing tendency where the value of w1 increases and w2 decreases at the same time. Also the objective function value is on the rise during this process. The gap can reach the maximum value among these results when the weight of headway deviation equals the weight of train circulation plan. All the gaps are not too large because there only are 74 train services in total that should be served. Furthermore, the trains used in both directions are 16 and 14, which is smaller than trains used without short turning strategy. The optimal train schedule obtained when w1=0.1 and w2=0.9 is shown as Figure 10, where the lines with same color mean that the train services are served by the same train.Table 6
Comparison with different value of weight coefficients for case study-A.
w1 w 2 Computing time[s] Objective function value Gap 0.1 0.9 1.76 -0.657 0 0.3 0.7 1.55 -0.059 0.58% 0.5 0.5 1.31 0.536 2.03% 0.7 0.3 1.29 1.124 0.41% 0.9 0.1 1.25 1.713 0Figure 10
Optimal train schedule with short turning strategy for case study-A.


### 5.2. Case Study- B

In case study-B, the input parameters are given in Table7. The total number of train services for both directions is 145, respectively. The optimal train schedule with short turning strategy obtained by CPLEX solver is demonstrated in Figure 11; the line with same color means that these train services are served by the same train. The schedule coordination mode during each time interval is 1:0, 1:2, 1:1, and 1:0, where the former value is frequency for full-length train services and the latter one is frequency for short turning train services. The calculation results of values of F1 and F2 are 1680 and -223, respectively. In this case study, we set the value of w1 and w2 equal to 0.9 and 0.1 to use less computing time. The numbers of constraints and variables are 171269 and 50117. During the whole operation period, 43 trains come out from Depot A to serve the train services for the service pattern with short turning strategy, and 26 trains come out from Depot B or Depot C to serve the train service in the down direction.Table 7
Input parameters for case study-B.
Time interval I u p I d n H2,kup[s] H1,kup[s] H2,kdn[s] H1,kdn[s] 5:00-7:00 13 13 600 600 600 600 7:00-9:00 60 60 360 120 360 120 9:00-13:00 60 60 480 240 480 240 13:00-15:00 12 12 600 600 600 600Figure 11
Optimal train schedule with short turning strategy for case study-B.To make a comparison, optimal train schedule without short turning strategy also is presented as shown in Figure12. Under this situation, the same passenger demand should be satisfied, which means that values of the predefined headway are identical to the corresponding values for operation pattern with short turning strategy. To serve 145 train services in the up direction, 44 trains come out from Depot A. Meanwhile, 43 trains come out from Depot B or Depot C to serve the 145 train services in the down direction. According to the results, optimal train schedule with short turning strategy could provide a better train circulation plan with 20.69% reduction of trains in use. In particular, the number of trains in theory can be calculated by the following equation:(54)Ntrain=tcyclehwhere Ntrain is the number of trains that can be computed theoretically, tcycle is the cycling time of the train service, and h is the headway [15]. Based on (54), the number of trains to satisfy the passenger demand is 122.7 in single direction, which means the optimal train schedule can reduce about [(122.7-43-26)+122.7-44-43)]/122.7×2=36.43% of trains.Figure 12
Optimal train schedule without short turning strategy for case study-B.Furthermore, the objective value obtained by optimal train schedule with short turning strategy is(2.634-0.801)/2.634∗100% = 69.59% better than the train schedule without short turning strategy. Because the number of train services that should be served is calculated by dividing the length of the time interval by predefined headway in area 2, which means that satisfying the passenger demand inside short turning circle is the basis goal. To finish the whole operation period, train schedule without short turning train services can only meet the passenger demand in area 2 well, while load factor in area 1 is insufficient. For instance, during the second time interval, the predefined headways in area 1 and area 2 are 360s and 120s, respectively. The actual headway of two consecutive train services is close to 120s, which cannot make full use of the trains as passenger demand in area 1 does not match the transport capacity. As a result, there is a huge increase in headway deviation.Figures13 and 14 demonstrate the load factor of a train service at two certain stations in the up direction. Note that Qingyuan Road Station is a station in area 1, and East gate of Peking University Station is a station in area 2, which means that Qingyuan Road Station is not included in the short turning circle, while East gate of Peking University Station is. As shown in Figure 13, the values for train operation pattern with short turning strategy are larger than the ones without short turning strategy at Qingyuan Road Station. That is caused by the different passenger demand in area 1 and area 2, which is related to the predefined headway. Actually, the number of train services that should be served is calculated by the following equation [35]:(55)Hk=tk+1-tkIkwhere Hk is the predefined headway for the kth time interval, tk and tk are the starting time and ending time of the kth time interval, and Ik is the number of train services that should be operated during the kth time interval. When trains are running without short turning strategy and the same number of train services that should be operated, the predefined headway is the same as the predefined headway inside short turning circle. That means the actual headway between two consecutive train services is closed to the headway in area 2. This leads to an excess of train services running in area 1 and making the load factor of stations in area 1 small. In addition, the value of the load factor is less than 0.3, which resulted from the small quantity of passenger flow at this station. The passenger demand is so small that there is no need to establish the station. As for load factor at East gate of Peking University Station in Figure 14, if service pattern is operated with short turning strategy, the load factor is smaller but closer to 1 compared with the load factor of a train service without short turning strategy at East gate of Peking University Station during the early peak hour period. It indicates that the short turning strategy can reduce the crowdedness at stations in area 2. The load factor between 8:00 and 9:00 is near to 1.4, an overcrowd circumstance that is abnormal. The reason for the phenomenon is that the passenger flow for line 4 is so large that only adopting the short turning strategy cannot satisfy the huge passenger demand. Other measures can be taken into consideration in future.Figure 13
Load factor of a train service at Qingyuan Road Station.Figure 14
Load factor of a train service at east gate of Peking University Station.


## 5.1. Case Study-A

In case study-A, the input parameters are given in Table5. The total number of train services for both directions is 37, respectively. In particular, the maximal and minimal turnaround times are 720s and 120s. As for the headway of departure times must larger than 120s and smaller than 660s. Note that the departure time of the first train service in both directions is 5:00, and the departure time of the last train service for both directions is 9:00.Table 5
Input parameters for case study-A.
Time interval I u p I d n H2,kup[s] H1,kup[s] H2,kdn[s] H1,kdn[s] 5:00-7:00 13 13 600 600 600 600 7:00-9:00 24 24 600 300 600 300In this case study, a small scale of simulation is conducted. We assume the operation time of the urban rail transit line is 5:00 to 9:00 and the time period is divided into 2 time intervals as shown in Table5. The urban rail transit line serves different operation pattern during two time intervals. During 5:00 to 7:00, the ratio of headway in area 2 and headway in area 1 is 1, which means that there would be only full-length train services operated. From 7:00 to 9:00, headway in area 2 is twice headway in area 1; then there would be a short turning train service served between two full-length train services.Firstly, we calculate the value ofF1 and F2 by (12) and (13), which also should meet all constraints. We obtain the values of F1 and F2 which are 894 and -46, respectively. There are 15377 constrains and 4757 variables. Then the comparison of optimization results is shown in Table 6, where we set several different values for weight coefficients w1 and w2. Computing times, objective function values, and gap are considered in this result. The result of computing time shows a decreasing tendency where the value of w1 increases and w2 decreases at the same time. Also the objective function value is on the rise during this process. The gap can reach the maximum value among these results when the weight of headway deviation equals the weight of train circulation plan. All the gaps are not too large because there only are 74 train services in total that should be served. Furthermore, the trains used in both directions are 16 and 14, which is smaller than trains used without short turning strategy. The optimal train schedule obtained when w1=0.1 and w2=0.9 is shown as Figure 10, where the lines with same color mean that the train services are served by the same train.Table 6
Comparison with different value of weight coefficients for case study-A.
w1 w 2 Computing time[s] Objective function value Gap 0.1 0.9 1.76 -0.657 0 0.3 0.7 1.55 -0.059 0.58% 0.5 0.5 1.31 0.536 2.03% 0.7 0.3 1.29 1.124 0.41% 0.9 0.1 1.25 1.713 0Figure 10
Optimal train schedule with short turning strategy for case study-A.


## 5.2. Case Study- B

In case study-B, the input parameters are given in Table7. The total number of train services for both directions is 145, respectively. The optimal train schedule with short turning strategy obtained by CPLEX solver is demonstrated in Figure 11; the line with same color means that these train services are served by the same train. The schedule coordination mode during each time interval is 1:0, 1:2, 1:1, and 1:0, where the former value is frequency for full-length train services and the latter one is frequency for short turning train services. The calculation results of values of F1 and F2 are 1680 and -223, respectively. In this case study, we set the value of w1 and w2 equal to 0.9 and 0.1 to use less computing time. The numbers of constraints and variables are 171269 and 50117. During the whole operation period, 43 trains come out from Depot A to serve the train services for the service pattern with short turning strategy, and 26 trains come out from Depot B or Depot C to serve the train service in the down direction.Table 7
Input parameters for case study-B.
Time interval I u p I d n H2,kup[s] H1,kup[s] H2,kdn[s] H1,kdn[s] 5:00-7:00 13 13 600 600 600 600 7:00-9:00 60 60 360 120 360 120 9:00-13:00 60 60 480 240 480 240 13:00-15:00 12 12 600 600 600 600Figure 11
Optimal train schedule with short turning strategy for case study-B.To make a comparison, optimal train schedule without short turning strategy also is presented as shown in Figure12. Under this situation, the same passenger demand should be satisfied, which means that values of the predefined headway are identical to the corresponding values for operation pattern with short turning strategy. To serve 145 train services in the up direction, 44 trains come out from Depot A. Meanwhile, 43 trains come out from Depot B or Depot C to serve the 145 train services in the down direction. According to the results, optimal train schedule with short turning strategy could provide a better train circulation plan with 20.69% reduction of trains in use. In particular, the number of trains in theory can be calculated by the following equation:(54)Ntrain=tcyclehwhere Ntrain is the number of trains that can be computed theoretically, tcycle is the cycling time of the train service, and h is the headway [15]. Based on (54), the number of trains to satisfy the passenger demand is 122.7 in single direction, which means the optimal train schedule can reduce about [(122.7-43-26)+122.7-44-43)]/122.7×2=36.43% of trains.Figure 12
Optimal train schedule without short turning strategy for case study-B.Furthermore, the objective value obtained by optimal train schedule with short turning strategy is(2.634-0.801)/2.634∗100% = 69.59% better than the train schedule without short turning strategy. Because the number of train services that should be served is calculated by dividing the length of the time interval by predefined headway in area 2, which means that satisfying the passenger demand inside short turning circle is the basis goal. To finish the whole operation period, train schedule without short turning train services can only meet the passenger demand in area 2 well, while load factor in area 1 is insufficient. For instance, during the second time interval, the predefined headways in area 1 and area 2 are 360s and 120s, respectively. The actual headway of two consecutive train services is close to 120s, which cannot make full use of the trains as passenger demand in area 1 does not match the transport capacity. As a result, there is a huge increase in headway deviation.Figures13 and 14 demonstrate the load factor of a train service at two certain stations in the up direction. Note that Qingyuan Road Station is a station in area 1, and East gate of Peking University Station is a station in area 2, which means that Qingyuan Road Station is not included in the short turning circle, while East gate of Peking University Station is. As shown in Figure 13, the values for train operation pattern with short turning strategy are larger than the ones without short turning strategy at Qingyuan Road Station. That is caused by the different passenger demand in area 1 and area 2, which is related to the predefined headway. Actually, the number of train services that should be served is calculated by the following equation [35]:(55)Hk=tk+1-tkIkwhere Hk is the predefined headway for the kth time interval, tk and tk are the starting time and ending time of the kth time interval, and Ik is the number of train services that should be operated during the kth time interval. When trains are running without short turning strategy and the same number of train services that should be operated, the predefined headway is the same as the predefined headway inside short turning circle. That means the actual headway between two consecutive train services is closed to the headway in area 2. This leads to an excess of train services running in area 1 and making the load factor of stations in area 1 small. In addition, the value of the load factor is less than 0.3, which resulted from the small quantity of passenger flow at this station. The passenger demand is so small that there is no need to establish the station. As for load factor at East gate of Peking University Station in Figure 14, if service pattern is operated with short turning strategy, the load factor is smaller but closer to 1 compared with the load factor of a train service without short turning strategy at East gate of Peking University Station during the early peak hour period. It indicates that the short turning strategy can reduce the crowdedness at stations in area 2. The load factor between 8:00 and 9:00 is near to 1.4, an overcrowd circumstance that is abnormal. The reason for the phenomenon is that the passenger flow for line 4 is so large that only adopting the short turning strategy cannot satisfy the huge passenger demand. Other measures can be taken into consideration in future.Figure 13
Load factor of a train service at Qingyuan Road Station.Figure 14
Load factor of a train service at east gate of Peking University Station.


## 6. Conclusions and Future Work

In this paper, we have developed a new model for train scheduling optimization problem for an urban rail transit line with multiple depots. In this model, short turning strategy is introduced to satisfy the unbalanced passenger demand. Groups of practical and typical constraints such as departure times, dwell times, headways, train orders, and train circulation plan are taken into consideration. Several transformation properties are involved to transform the model into a mixed integer linear programming one, which can be solved by existing solvers.Simulation experiment is carried out based on the data of Beijing Subway line 4 to evaluate the performance of the proposed model and approach. Our results show that operation pattern with short turning strategy can acquire a better train schedule and train circulation plan.For the future research steps, we will extend it by taking more realistic constraints into consideration, such as depot equilibrium and stochastic passenger flow. In particular, the large scale of train services such as train schedule in one day could be implemented for extended problem. Furthermore, other types layout of urban rail transit lines could be considered.



---

*Source: 5367295-2018-08-02.xml*