# Timetable Optimization of Rail Transit Loop Line with Transfer Coordination

Authors: Rui-Jia Shi; Bao-Hua Mao; Yong Ding; Yun Bai; Yao Chen
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

In an urban rail transit system, it is important to coordinate the timetable of a loop line with its connecting lines so as to reduce the waiting time of passengers. This is particularly essential because transfer passengers usually account for the majority of the total passengers in loop lines. In this paper, a timetable optimization model is developed for loop line in order to minimize the average waiting time of access passengers and transfer passengers. This is performed by adjusting the headways and dwell times of trains on the loop line. A genetic algorithm is applied to solve the proposed model, and a numerical example is used to verify its effectiveness. Finally, a case study of a loop line in the Beijing urban rail transit system is conducted. Waiting times of the passengers and the number of waiting passengers are used as performance indicators to verify the optimization results in rush hours and non-rush hours. The results show that the average waiting times for the up-track and down-track are reduced by 3.69% and 2.89% during rush hours and by 11.60% and 11.47% during non-rush hours, respectively.


---

## Body

## 1. Introduction

Loop lines play a vital role in urban rail transit system in several big cities, such as London, Moscow, Tokyo, Beijing, and Shanghai. The loop line connects several radial lines together, thereby enhancing the accessibility of the rail network. It has large passenger volume for providing transfer service for passengers [1]. Thus, the loop line is regarded as a very important aspect of the urban rail transit system, and valuable researches are conducted on loop line planning [2, 3] and design [4].Minimization of waiting time via timetable optimization is an important issue in the operation of urban rail transit. Mohring et al. [5] found that passengers in public transit stations perceive their waiting time to be almost twice that of the actual waiting time. With respect to loop lines, a well-designed timetable with good coordination with the connecting lines can significantly reduce passengers’ waiting time due to the high transfer passenger flow. Therefore, loop line timetable optimization is urgently required to improve service quality by minimizing the waiting time of passengers.Timetable optimization is to determine an optimal timetable that satisfies the operational and safety requirements by determining the departure and arrival times for each train at each station [6]. Mathematical programming was first proposed to solve train scheduling problems for railways by Amit and Goldfarb [7] in 1971. Since then, many mathematical programming models and algorithms are developed by a large number of researches including Zhou and Zhong [8], Castillo et al. [9], and Li et al. [10, 11].Time timetabling can be classified into single-line timetable optimization and network timetable synchronization. The former one always focuses on the waiting time of passengers [12], the number of waiting passengers [13], operational cost [14, 15], travel time [8], vehicle delay [11, 16], and energy consumption [17, 18]. Given that single-line timetable optimization only focuses on a single line without the passenger interchange with other lines in the network, the demand of transfer passengers has not been considered thoroughly.With the expansion of urban rail transit networks, some researchers attempt to optimize timetable for synchronization in a transportation network. Timetable synchronization generally enables the smooth transfer of passengers, and it involves different objectives such as minimizing transfer waiting time [19, 20], minimizing total cost of passengers and operators [21, 22], maximizing synchronization [23], minimizing maximal transfer passenger waiting time [24], minimizing assembling passengers on platforms [25], and maximizing transfer accessibility [26–28]. The studies on timetable synchronization only consider the demand of transfer passengers, and access passenger demand is not sufficiently taken into account.In a loop line, the transfer passenger demand is almost equal to the high access passenger demand. Taking loop line 2 in Beijing, for example, the ratio of the number of transfer passengers to access passengers is 6 : 4. The waiting time of access passengers mainly depends on the headways of trains on loop line and can be reduced by dispatching trains at equal intervals [29]. However, the waiting time of transfer passengers mainly depends on the coordination with connecting lines, and equal intervals of trains do not necessarily lead to minimum waiting times for all passengers. Thus, the waiting time of both access and transfer passengers should be considered in the loop line timetable optimization. However, previous models of timetable optimization only consider either access passengers or transfer passengers, but not both. Hence they are not completely applicable for loop line.In addition, the constraints of turnback connection on loop line are different from that on non-loop lines. The trains on up-track and down-track run independently on loop lines, and there is no turn-round facility. It greatly distinguishes loop lines from non-loop lines. When a train ends up its service at the destination, it moves forward to start a new service. The connections of trains have to be scheduled well to ensure that the headways are in a proper range.In this paper, a more realistic approach of loop line timetable optimization is proposed by coordinating with connecting lines. The objective of the model is to minimize the average waiting time of both access passengers and transfer passengers. Furthermore, train connection constraints are set into the model to ensure the continuity of loop train operation. A genetic algorithm is designed to obtain better timetable of loop line based on the proposed model.The remainder of this paper is organized as follows. Section2 describes passenger flow and route characteristics of loop lines, and a timetable optimization model of loop line is presented. Based on the proposed model, a genetic algorithm is developed in Section 3. In Section 4, a numerical experiment is performed to show the application of the proposed model and algorithm. Then, the suggested model is applied to Line 2 of the Beijing urban rail transit. The final section concludes the paper and discusses future research issues.


## 2. Timetable Optimization Model of Loop Line

### 2.1. Problem Description

This paper focuses on timetable optimization of an urban rail transit loop line. As shown in Figure1, the up-track and down-track trains on the loop line run separately. Each train departs from the depot, runs circle after circle until the service stops, and then returns to the depot. All boarding passengers in the loop line can be divided into two categories, namely, access passengers and transfer passengers. Access passengers are those who board a train of the loop line by swiping cards at the loop line station. Transfer passengers are those who transfer from the connecting lines.Figure 1
The representation of an urban rail transit loop line.The train timetables of loop line and the feeder lines are already known before optimization. The following main assumptions are made throughout the paper.Assumption 1.
All passenger demand is known and steady during the study period. Since the urban rail transit lines have small headways and passengers do not know the exact schedule in advance, it can be assumed that access passenger flow follows a uniform distribution [29].Assumption 2.
Transfer time is known and fixed for all transfer passengers. Transfer time is defined as the time from getting off the feeder train to arriving at the platform waiting area for the connecting train. The transfer times for all interchange stations can be collected by survey and calculated through mathematical statistics.Assumption 3.
In reality, passengers may choose whether to board a train by considering congestion levels. In order to simplify the model, it is assumed that all passengers will board the first arriving train and the capacity of trains is sufficient at any time to receive all the passengers wishing to ride the train.Assumption 4.
All the trains’ total trip time of a cycle is fixed as the original timetable. This preassignment precludes the potential of reducing or increasing the number of trains considered within the study period. The number of operating trains on the loop line is fixed.


### 2.2. Definitions and Notations

The following definitions and notations are used throughout this paper.K: it is the set of lines including loop line and connecting lines, K
=
k
∣
k
=
1
,
2
,
…
,
a, k
∈
K, where a is the total number of lines. The up-track and down-track of a line are considered as two individual lines. Let k
=
1 represent the up-track and let k
=
2 represent the down-track on the loop line.
S: it is the set of stations on the loop line, S
=
s
∣
s
=
1
,
2
,
…
,
b, where b is the total number of stations on the loop line. S
- is the set of transfer stations, and S
-
∈
S.
T: it is the study period.
n
k: it stands for prespecified fleet size during the study period on line k.
n
k
T: it is the number of trains departing from the start terminal on line k over the study period.
h
k
q: it is the departure time of the qth train at the depot on line k.
H
k
q: it is the headway between the qth train and q
-
1
t
h train on line k.
t
k
s
R: it is the run time of the train from station s
-
1 to station s on line k.
t
k
q
s
A: it is the arrival time of the qth train at station s on line k.
t
k
q
s
L: it is the departure time of the qth train at station s on line k.
t
k
q
s
D: it is the dwell time of the qth train at station s on line k.
t
k
s
D: it is the dwell time of the trains at station s on line k in the original timetable.
t
k
s
k
′: it is the transfer time for passengers who transfer from line k
′ to line k at transfer station s.
t
k
R: it is the total trip time taken for a train to run a cycle, consisting of interstation run times and dwell times at stations.
p
k
q
s
k
′
q
′: it is the number of passengers who transfer successfully from the q
′th train on line k
′ to the qth train on line k at transfer station s.
α
k
q
s
k
′
q
′: let α
k
q
s
k
′
q
′
=
1 if the q
′th train on line k
′ arrives at transfer station s sufficiently early such that passengers can transfer to the qth train on line k; otherwise, α
k
q
s
k
′
q
′
=
0.
t
k
q
s
k
′
q
′
W: it is the waiting time for a passenger who transfers successfully from the q
′th train on line k
′ to the qth train on line k at transfer station s.
t
k
q
s
W: it is the total waiting time for access passengers boarding the qth train at station s on line k.
λ
k
s: it is the arrival rate of access passengers at station s on line k.
H
¯
0: it is the maximum service headway on the loop line.
H
_
0: it is the minimum service headway on the loop line.
t
_
k
s
D: it is the minimum dwell time of trains at station s on the loop line.
t
-
k
s
D: it is the maximum dwell time of trains at station s on the loop line.
d
1: it is the allowable maximum range of headways on the loop line.
d
2: it is the allowable maximum range of dwell times on the loop line.
M: it is a large positive number.The decision variables in the model are as follows:H
k
q: the headways on the loop line, k
=
1,2.
t
k
q
s
D: the dwell times of the qth trains at all stations on the loop line, k
=
1,2.


### 2.3. Objective

In order to reduce the waiting time of the total boarding passengers, this paper minimizes the average waiting time of transfer passengers and access passengers.


#### 2.3.1. The Waiting Time of Transfer Passengers

Assumption3 indicates that passengers prefer to ride the first arriving train. Figure 2 illustrates the calculation of t
k
q
s
k
′
q
′
W. The arrow above the timeline represents the arrival times of three trains on line k
′ and the times at which passengers arrive at the platform waiting area of the loop line after transfer time t
k
s
k
′. The arrow below the timeline indicates the departure times of the trains on line k. Obviously, passengers from the (
q
′
-
1
)th, q
′th, and (
q
′
+
1
)th train on line k
′ would transfer to the (
q
-
1
)th, qth, and (
q
+
1
)th train, respectively, on line k.Figure 2
Illustration of transfer waiting time.It is necessary to determine the train, which passengers will transfer into in order to enable correct calculation of transfer waiting time. Thus, formula (1) is derived and this allows the determination of whether passengers from the q
′th train on line k
′ can transfer to the qth train on line k at transfer station s or not:(1)
M
α
k
q
s
k
′
q
′
-
1
≤
t
k
q
s
L
-
t
k
′
q
′
s
A
+
t
k
s
k
′
≤
M
α
k
q
s
k
′
q
′
.Ifα
k
q
s
k
′
q
′
=
1 and α
k
q
-
1
s
k
′
q
′
=
0, passengers from the q
′th train on line k
′ will transfer to the qth train on line k at transfer station s successfully. The transfer waiting time can be calculated by the formula(2)
t
k
q
s
k
′
q
′
W
=
t
k
q
s
L
-
t
k
′
q
s
A
+
t
k
s
k
′
,
α
k
q
s
k
′
q
′
=
1
,
α
k
q
-
1
s
k
′
q
′
=
0
0
,
else.


#### 2.3.2. The Waiting Time of Access Passengers

Based on Assumption1, the average waiting time of access passengers equals half that of the headway. Access passengers waiting time can be calculated by the formula (3)
t
k
q
s
W
=
λ
k
s
t
k
q
s
L
-
t
k
,
q
-
1
,
s
L
2
2
.


#### 2.3.3. Objective Function

The timetables in two directions need to be optimized separately since the up-track and down-track trains operate separately on the loop line. The objective of this paper is to minimize the average waiting time of access passengers and transfer passengers.(4)
min
⁡
Q
=
∑
k
′
=
3
a
∑
s
∈
S
-
∑
q
=
1
n
k
T
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
t
k
q
s
k
′
q
′
W
+
∑
s
∈
S
∑
q
=
1
n
k
T
t
k
q
s
W
∑
k
′
=
3
a
∑
s
∈
S
-
∑
q
=
1
n
k
T
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
+
∑
s
∈
S
λ
k
s
T
.


### 2.4. Constraints

It is necessary to subject timetable optimization problems to the safety, operation, and equipment constraints. Figure3 shows the train connection of the loop line, which is different from non-loop lines. If n
k is fixed, it implies that no further trains can enter or exit the depot after the first cycle within T and that the first train will connect the last train to continue operation. In order to ensure better connections of the trains on loop the line, the following constraints are set.Figure 3
Train connection on loop line.


#### 2.4.1. Total Trip Timet
k
R

According to Assumption4, t
k
R is a fixed value for all trains, and it is the sum of the dwell time at stations and the running time at sections. The sum of dwell times of one train operating one cycle will be a constant value if the running times at sections are not adjusted: (5)
t
k
R
=
∑
i
=
1
b
t
k
i
R
+
∑
i
=
1
b
t
k
q
i
D
.


#### 2.4.2. Departure Timeh
k
q

Since the number of operating trains is fixed on loop line, theqth train would continue the next operation cycle after a cycle. Based on constraint (5), the departure time of each train can be calculated by constraint (6), and the sum of the headways of n
k train equals t
k
R as shown in constraint (7):(6)
h
k
q
=
∑
i
q
H
k
i
,
q
≤
n
k
∑
i
q
-
q
/
n
k
n
k
H
k
i
+
t
k
R
,
n
k
<
q
≤
n
k
T
,
(7)
t
k
R
=
∑
q
q
+
n
k
-
1
H
k
q
,
1
<
q
≤
n
k
.


#### 2.4.3. HeadwaysH
k
q

The model allows the headways for each train in the first cycle to be adjusted individually. The headways are set restricted to a limited range to ensure both operation safety and service quality. Constraint (8) ensures that the variation of headways is within 2
d
1 and has to meet a strict range H
_
0
,
H
¯
0:(8)
0
≤
H
k
q
≤
H
¯
0
,
q
=
1
,
max
⁡
T
n
k
T
-
d
1
,
H
_
0
≤
H
k
q
≤
min
⁡
T
n
k
T
+
d
1
,
H
¯
0
,
1
<
q
≤
n
k
+
1
.


#### 2.4.4. Arrival Timet
k
q
s
A

The arrival time of theqth train at station s on line k is calculated by the constraint (9)
t
k
q
s
A
=
h
k
q
+
∑
i
=
1
s
t
k
i
R
+
∑
i
=
1
s
-
1
t
k
q
i
D
.


#### 2.4.5. Departure Timet
k
q
s
L

The departure time of theqth train at station s on line k is calculated by the constraint (10)
t
k
q
s
L
=
h
k
q
+
∑
i
=
1
s
t
k
i
R
+
∑
i
=
1
s
t
k
q
i
D
.


#### 2.4.6. Dwell Timet
k
q
s
D

Dwell times of trains on the loop line are considered to be decision variables in the model. Similar to the previously mentioned requirements for headways, the variation of dwell times is limited within2
d
2, and the dwell time t
k
q
s
D should not be shorter than t
_
k
s
D and longer than t
-
k
s
D:(11)
max
⁡
t
k
s
D
-
d
2
,
t
_
k
s
D
≤
t
k
q
s
D
≤
min
⁡
t
k
s
D
+
d
2
,
t
-
k
s
D
.


## 2.1. Problem Description

This paper focuses on timetable optimization of an urban rail transit loop line. As shown in Figure1, the up-track and down-track trains on the loop line run separately. Each train departs from the depot, runs circle after circle until the service stops, and then returns to the depot. All boarding passengers in the loop line can be divided into two categories, namely, access passengers and transfer passengers. Access passengers are those who board a train of the loop line by swiping cards at the loop line station. Transfer passengers are those who transfer from the connecting lines.Figure 1
The representation of an urban rail transit loop line.The train timetables of loop line and the feeder lines are already known before optimization. The following main assumptions are made throughout the paper.Assumption 1.
All passenger demand is known and steady during the study period. Since the urban rail transit lines have small headways and passengers do not know the exact schedule in advance, it can be assumed that access passenger flow follows a uniform distribution [29].Assumption 2.
Transfer time is known and fixed for all transfer passengers. Transfer time is defined as the time from getting off the feeder train to arriving at the platform waiting area for the connecting train. The transfer times for all interchange stations can be collected by survey and calculated through mathematical statistics.Assumption 3.
In reality, passengers may choose whether to board a train by considering congestion levels. In order to simplify the model, it is assumed that all passengers will board the first arriving train and the capacity of trains is sufficient at any time to receive all the passengers wishing to ride the train.Assumption 4.
All the trains’ total trip time of a cycle is fixed as the original timetable. This preassignment precludes the potential of reducing or increasing the number of trains considered within the study period. The number of operating trains on the loop line is fixed.


## 2.2. Definitions and Notations

The following definitions and notations are used throughout this paper.K: it is the set of lines including loop line and connecting lines, K
=
k
∣
k
=
1
,
2
,
…
,
a, k
∈
K, where a is the total number of lines. The up-track and down-track of a line are considered as two individual lines. Let k
=
1 represent the up-track and let k
=
2 represent the down-track on the loop line.
S: it is the set of stations on the loop line, S
=
s
∣
s
=
1
,
2
,
…
,
b, where b is the total number of stations on the loop line. S
- is the set of transfer stations, and S
-
∈
S.
T: it is the study period.
n
k: it stands for prespecified fleet size during the study period on line k.
n
k
T: it is the number of trains departing from the start terminal on line k over the study period.
h
k
q: it is the departure time of the qth train at the depot on line k.
H
k
q: it is the headway between the qth train and q
-
1
t
h train on line k.
t
k
s
R: it is the run time of the train from station s
-
1 to station s on line k.
t
k
q
s
A: it is the arrival time of the qth train at station s on line k.
t
k
q
s
L: it is the departure time of the qth train at station s on line k.
t
k
q
s
D: it is the dwell time of the qth train at station s on line k.
t
k
s
D: it is the dwell time of the trains at station s on line k in the original timetable.
t
k
s
k
′: it is the transfer time for passengers who transfer from line k
′ to line k at transfer station s.
t
k
R: it is the total trip time taken for a train to run a cycle, consisting of interstation run times and dwell times at stations.
p
k
q
s
k
′
q
′: it is the number of passengers who transfer successfully from the q
′th train on line k
′ to the qth train on line k at transfer station s.
α
k
q
s
k
′
q
′: let α
k
q
s
k
′
q
′
=
1 if the q
′th train on line k
′ arrives at transfer station s sufficiently early such that passengers can transfer to the qth train on line k; otherwise, α
k
q
s
k
′
q
′
=
0.
t
k
q
s
k
′
q
′
W: it is the waiting time for a passenger who transfers successfully from the q
′th train on line k
′ to the qth train on line k at transfer station s.
t
k
q
s
W: it is the total waiting time for access passengers boarding the qth train at station s on line k.
λ
k
s: it is the arrival rate of access passengers at station s on line k.
H
¯
0: it is the maximum service headway on the loop line.
H
_
0: it is the minimum service headway on the loop line.
t
_
k
s
D: it is the minimum dwell time of trains at station s on the loop line.
t
-
k
s
D: it is the maximum dwell time of trains at station s on the loop line.
d
1: it is the allowable maximum range of headways on the loop line.
d
2: it is the allowable maximum range of dwell times on the loop line.
M: it is a large positive number.The decision variables in the model are as follows:H
k
q: the headways on the loop line, k
=
1,2.
t
k
q
s
D: the dwell times of the qth trains at all stations on the loop line, k
=
1,2.


## 2.3. Objective

In order to reduce the waiting time of the total boarding passengers, this paper minimizes the average waiting time of transfer passengers and access passengers.


### 2.3.1. The Waiting Time of Transfer Passengers

Assumption3 indicates that passengers prefer to ride the first arriving train. Figure 2 illustrates the calculation of t
k
q
s
k
′
q
′
W. The arrow above the timeline represents the arrival times of three trains on line k
′ and the times at which passengers arrive at the platform waiting area of the loop line after transfer time t
k
s
k
′. The arrow below the timeline indicates the departure times of the trains on line k. Obviously, passengers from the (
q
′
-
1
)th, q
′th, and (
q
′
+
1
)th train on line k
′ would transfer to the (
q
-
1
)th, qth, and (
q
+
1
)th train, respectively, on line k.Figure 2
Illustration of transfer waiting time.It is necessary to determine the train, which passengers will transfer into in order to enable correct calculation of transfer waiting time. Thus, formula (1) is derived and this allows the determination of whether passengers from the q
′th train on line k
′ can transfer to the qth train on line k at transfer station s or not:(1)
M
α
k
q
s
k
′
q
′
-
1
≤
t
k
q
s
L
-
t
k
′
q
′
s
A
+
t
k
s
k
′
≤
M
α
k
q
s
k
′
q
′
.Ifα
k
q
s
k
′
q
′
=
1 and α
k
q
-
1
s
k
′
q
′
=
0, passengers from the q
′th train on line k
′ will transfer to the qth train on line k at transfer station s successfully. The transfer waiting time can be calculated by the formula(2)
t
k
q
s
k
′
q
′
W
=
t
k
q
s
L
-
t
k
′
q
s
A
+
t
k
s
k
′
,
α
k
q
s
k
′
q
′
=
1
,
α
k
q
-
1
s
k
′
q
′
=
0
0
,
else.


### 2.3.2. The Waiting Time of Access Passengers

Based on Assumption1, the average waiting time of access passengers equals half that of the headway. Access passengers waiting time can be calculated by the formula (3)
t
k
q
s
W
=
λ
k
s
t
k
q
s
L
-
t
k
,
q
-
1
,
s
L
2
2
.


### 2.3.3. Objective Function

The timetables in two directions need to be optimized separately since the up-track and down-track trains operate separately on the loop line. The objective of this paper is to minimize the average waiting time of access passengers and transfer passengers.(4)
min
⁡
Q
=
∑
k
′
=
3
a
∑
s
∈
S
-
∑
q
=
1
n
k
T
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
t
k
q
s
k
′
q
′
W
+
∑
s
∈
S
∑
q
=
1
n
k
T
t
k
q
s
W
∑
k
′
=
3
a
∑
s
∈
S
-
∑
q
=
1
n
k
T
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
+
∑
s
∈
S
λ
k
s
T
.


## 2.3.1. The Waiting Time of Transfer Passengers

Assumption3 indicates that passengers prefer to ride the first arriving train. Figure 2 illustrates the calculation of t
k
q
s
k
′
q
′
W. The arrow above the timeline represents the arrival times of three trains on line k
′ and the times at which passengers arrive at the platform waiting area of the loop line after transfer time t
k
s
k
′. The arrow below the timeline indicates the departure times of the trains on line k. Obviously, passengers from the (
q
′
-
1
)th, q
′th, and (
q
′
+
1
)th train on line k
′ would transfer to the (
q
-
1
)th, qth, and (
q
+
1
)th train, respectively, on line k.Figure 2
Illustration of transfer waiting time.It is necessary to determine the train, which passengers will transfer into in order to enable correct calculation of transfer waiting time. Thus, formula (1) is derived and this allows the determination of whether passengers from the q
′th train on line k
′ can transfer to the qth train on line k at transfer station s or not:(1)
M
α
k
q
s
k
′
q
′
-
1
≤
t
k
q
s
L
-
t
k
′
q
′
s
A
+
t
k
s
k
′
≤
M
α
k
q
s
k
′
q
′
.Ifα
k
q
s
k
′
q
′
=
1 and α
k
q
-
1
s
k
′
q
′
=
0, passengers from the q
′th train on line k
′ will transfer to the qth train on line k at transfer station s successfully. The transfer waiting time can be calculated by the formula(2)
t
k
q
s
k
′
q
′
W
=
t
k
q
s
L
-
t
k
′
q
s
A
+
t
k
s
k
′
,
α
k
q
s
k
′
q
′
=
1
,
α
k
q
-
1
s
k
′
q
′
=
0
0
,
else.


## 2.3.2. The Waiting Time of Access Passengers

Based on Assumption1, the average waiting time of access passengers equals half that of the headway. Access passengers waiting time can be calculated by the formula (3)
t
k
q
s
W
=
λ
k
s
t
k
q
s
L
-
t
k
,
q
-
1
,
s
L
2
2
.


## 2.3.3. Objective Function

The timetables in two directions need to be optimized separately since the up-track and down-track trains operate separately on the loop line. The objective of this paper is to minimize the average waiting time of access passengers and transfer passengers.(4)
min
⁡
Q
=
∑
k
′
=
3
a
∑
s
∈
S
-
∑
q
=
1
n
k
T
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
t
k
q
s
k
′
q
′
W
+
∑
s
∈
S
∑
q
=
1
n
k
T
t
k
q
s
W
∑
k
′
=
3
a
∑
s
∈
S
-
∑
q
=
1
n
k
T
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
+
∑
s
∈
S
λ
k
s
T
.


## 2.4. Constraints

It is necessary to subject timetable optimization problems to the safety, operation, and equipment constraints. Figure3 shows the train connection of the loop line, which is different from non-loop lines. If n
k is fixed, it implies that no further trains can enter or exit the depot after the first cycle within T and that the first train will connect the last train to continue operation. In order to ensure better connections of the trains on loop the line, the following constraints are set.Figure 3
Train connection on loop line.


### 2.4.1. Total Trip Timet
k
R

According to Assumption4, t
k
R is a fixed value for all trains, and it is the sum of the dwell time at stations and the running time at sections. The sum of dwell times of one train operating one cycle will be a constant value if the running times at sections are not adjusted: (5)
t
k
R
=
∑
i
=
1
b
t
k
i
R
+
∑
i
=
1
b
t
k
q
i
D
.


### 2.4.2. Departure Timeh
k
q

Since the number of operating trains is fixed on loop line, theqth train would continue the next operation cycle after a cycle. Based on constraint (5), the departure time of each train can be calculated by constraint (6), and the sum of the headways of n
k train equals t
k
R as shown in constraint (7):(6)
h
k
q
=
∑
i
q
H
k
i
,
q
≤
n
k
∑
i
q
-
q
/
n
k
n
k
H
k
i
+
t
k
R
,
n
k
<
q
≤
n
k
T
,
(7)
t
k
R
=
∑
q
q
+
n
k
-
1
H
k
q
,
1
<
q
≤
n
k
.


### 2.4.3. HeadwaysH
k
q

The model allows the headways for each train in the first cycle to be adjusted individually. The headways are set restricted to a limited range to ensure both operation safety and service quality. Constraint (8) ensures that the variation of headways is within 2
d
1 and has to meet a strict range H
_
0
,
H
¯
0:(8)
0
≤
H
k
q
≤
H
¯
0
,
q
=
1
,
max
⁡
T
n
k
T
-
d
1
,
H
_
0
≤
H
k
q
≤
min
⁡
T
n
k
T
+
d
1
,
H
¯
0
,
1
<
q
≤
n
k
+
1
.


### 2.4.4. Arrival Timet
k
q
s
A

The arrival time of theqth train at station s on line k is calculated by the constraint (9)
t
k
q
s
A
=
h
k
q
+
∑
i
=
1
s
t
k
i
R
+
∑
i
=
1
s
-
1
t
k
q
i
D
.


### 2.4.5. Departure Timet
k
q
s
L

The departure time of theqth train at station s on line k is calculated by the constraint (10)
t
k
q
s
L
=
h
k
q
+
∑
i
=
1
s
t
k
i
R
+
∑
i
=
1
s
t
k
q
i
D
.


### 2.4.6. Dwell Timet
k
q
s
D

Dwell times of trains on the loop line are considered to be decision variables in the model. Similar to the previously mentioned requirements for headways, the variation of dwell times is limited within2
d
2, and the dwell time t
k
q
s
D should not be shorter than t
_
k
s
D and longer than t
-
k
s
D:(11)
max
⁡
t
k
s
D
-
d
2
,
t
_
k
s
D
≤
t
k
q
s
D
≤
min
⁡
t
k
s
D
+
d
2
,
t
-
k
s
D
.


## 2.4.1. Total Trip Timet
k
R

According to Assumption4, t
k
R is a fixed value for all trains, and it is the sum of the dwell time at stations and the running time at sections. The sum of dwell times of one train operating one cycle will be a constant value if the running times at sections are not adjusted: (5)
t
k
R
=
∑
i
=
1
b
t
k
i
R
+
∑
i
=
1
b
t
k
q
i
D
.


## 2.4.2. Departure Timeh
k
q

Since the number of operating trains is fixed on loop line, theqth train would continue the next operation cycle after a cycle. Based on constraint (5), the departure time of each train can be calculated by constraint (6), and the sum of the headways of n
k train equals t
k
R as shown in constraint (7):(6)
h
k
q
=
∑
i
q
H
k
i
,
q
≤
n
k
∑
i
q
-
q
/
n
k
n
k
H
k
i
+
t
k
R
,
n
k
<
q
≤
n
k
T
,
(7)
t
k
R
=
∑
q
q
+
n
k
-
1
H
k
q
,
1
<
q
≤
n
k
.


## 2.4.3. HeadwaysH
k
q

The model allows the headways for each train in the first cycle to be adjusted individually. The headways are set restricted to a limited range to ensure both operation safety and service quality. Constraint (8) ensures that the variation of headways is within 2
d
1 and has to meet a strict range H
_
0
,
H
¯
0:(8)
0
≤
H
k
q
≤
H
¯
0
,
q
=
1
,
max
⁡
T
n
k
T
-
d
1
,
H
_
0
≤
H
k
q
≤
min
⁡
T
n
k
T
+
d
1
,
H
¯
0
,
1
<
q
≤
n
k
+
1
.


## 2.4.4. Arrival Timet
k
q
s
A

The arrival time of theqth train at station s on line k is calculated by the constraint (9)
t
k
q
s
A
=
h
k
q
+
∑
i
=
1
s
t
k
i
R
+
∑
i
=
1
s
-
1
t
k
q
i
D
.


## 2.4.5. Departure Timet
k
q
s
L

The departure time of theqth train at station s on line k is calculated by the constraint (10)
t
k
q
s
L
=
h
k
q
+
∑
i
=
1
s
t
k
i
R
+
∑
i
=
1
s
t
k
q
i
D
.


## 2.4.6. Dwell Timet
k
q
s
D

Dwell times of trains on the loop line are considered to be decision variables in the model. Similar to the previously mentioned requirements for headways, the variation of dwell times is limited within2
d
2, and the dwell time t
k
q
s
D should not be shorter than t
_
k
s
D and longer than t
-
k
s
D:(11)
max
⁡
t
k
s
D
-
d
2
,
t
_
k
s
D
≤
t
k
q
s
D
≤
min
⁡
t
k
s
D
+
d
2
,
t
-
k
s
D
.


## 3. Solution Algorithm

The proposed model is an integer nonlinear programming problem, which has been proved to be NP-hard [30]. The timetable optimization problem of the loop line is a nonsmooth and nonconvex problem, where the nonconvexity is caused by the minimum function in (8) and (11). Thus, optimal solutions are not easily obtained by adopting traditional optimization approaches.Genetic algorithm (GA) is one of the evolutionary algorithms in artificial intelligence approaches. Different from traditional optimization approaches, GA does not rely on the special characteristics of the problems and thus has no requirement on convexity and smoothness of functions and constraints. It is widely applied in solving timetable optimization problems [31, 32] due to its extensive generality, strong robustness, high efficiency, and practical applicability. The following key steps of GA are designed.(
1) Chromosome Encoding. In this paper, 0-1 binary encoding is used, and the variations of dwelling time and headways are chosen as genes for chromosomes in GA. The expression of chromosome is shown in Figure 4 according to constraints (8) and (11).Figure 4
The expression of chromosomes.(
2) Chromosome Adjustment. The chromosomes of dwelling time and headway are decoded into real solutions. Specifically, H
k
q and t
k
q
s
D assumed the nearest maximum or minimum values if they are beyond constraints (8) and (11). Furthermore, H
k
q and t
k
q
s
D increase or decrease proportionally if chromosome solutions do not meet constraints (5) and (7). This step is repeated until the solution satisfies all constraints, and the real solution is reencoded to 0-1.(
3) Fitness Calculation. It is necessary to transform the objective function (4) into a maximization problem since the GA is designed for solving maximization problem. After calculating the average waiting time Q of the boarding passengers on the loop line, the following equation is used to transform the fitness values:(12)
Q
′
=
1
Q
-
C
k
,where C
k is a constant value and is less than the optimal result. The setting of C
k allows the fitness function to be more sensitive to better solutions, which can increase the probability of selecting better solutions.(
4) Crossover and Mutation Operations. The fitness of the chromosome is sorted, and the largest two chromosomes are recorded before crossover and mutation. Single-point crossover and mutation operations are used in this step. The headways of two parent chromosomes are selected to crossover, which can ensure the chromosomes of the new children to be feasible solutions.Other detailed steps and approaches of GA are similar to the standard GA. The procedure for GA in this problem includes the following steps.Step 1.
Generate initial individuals randomly.Step 2.
Adjust chromosomes to a feasible solution.Step 3.
Calculate fitness of each individual and record the optimal solution.Step 4.
Terminate when the maximum number of generations is reached; otherwise, turn to Step5.Step 5.
Obtain new chromosomes via selection, crossover, and mutation operations; turn to Step2.


## 4. Case Study

In this section, a small test network is used to illustrate the proposed model and algorithm. The model and algorithm are then used in Line 2 in the Beijing urban rail transit to demonstrate the applicability of the model.


### 4.1. Numerical Example

#### 4.1.1. Network and Model Parameters

Figure5 shows a test network for the proposed model. Line 2 is a loop line, which connects two lines in the sample network, namely, Line 1 and Line 3. There are 6 stations on Line 2 including 4 transfer stations. In addition, T3 is the depot at which the train operation starts.Figure 5
A sample transit network.The dwell times of trains at each station and the transfer times of passengers at transfer stations are given in Table1. The run times from terminal station to every station are shown in Table 2. Table 3 depicts the transfer demand and arrival rate of passengers. “U” and “D” indicate “up-track” and “down-track,” respectively. The ratio of the number of transfer passengers and access passenger is 6 : 4. The primary headways of Lines 1–3 are 180 s, 200 s, and 150 s, respectively.Table 1
Dwell time of trains and transfer time of passengers.
S1
S2
S3
S4
S5
S6
Dwell time (s)
Line 1
—
—
30
—
—
30
Line 2
35
20
30
25
35
35
Line 3
30
—
—
—
35
—
Transfer time (s)
90
—
80
—
80
90Table 2
Run time.
Run time (s)
To
S1
S2
S3
S4
S5
S6
From
T1
—
—
1150
—
—
500
T2
—
—
400
—
—
1050
T3-U
250
700
1150
1550
1750
2100
T3-D
2170
1720
1270
870
670
320
T4
450
—
—
—
1050
—
T5
950
—
—
—
350
—Table 3
Passenger demand.
Passenger demand
S1
S2
S3
S4
S5
S6
The number of transfer passengers from a feeder train
1U-2D
—
—
30
—
—
30
1D-2D
—
—
18
—
—
39
3U-2D
30
—
—
—
39
—
3D-2D
27
—
—
—
33
—
Arrival rate of access passengers (person/s)
Line 2
0.2
0.13
0.18
0.1
0.22
0.18In reality, the timetables in rush hours and non-rush hours are different, and the time periods are mostly divided by hours. Therefore, in this paper, 1 hour is set as the study period to test the model.


#### 4.1.2. Result Analysis

(
1)   Optimization Result. The down-track on Line 2 is considered as an example. For simplicity, all the trains are set to the same dwell time at the same station. The program is run by MATLAB (7.8.0). The population size is 100, crossover fraction is 0.9, mutation fraction is 0.3, and generation is 1000. Additionally, d
1 is 30 s, and d
2 is 5 s. The objective function value of each generation is shown in Figure 6. The result shows that the GA has good convergence to solve the proposed model, and the algorithm began to converge in 565 generations.Figure 6
Optimization process of GA.Figure7 shows a comparison of the original timetable and scheduling timetable. The horizontal axis indicates time steps beginning from 0 min, and the vertical axis indicates the stations starting from the depot T3. The departure time of the first train at the depot in the scheduling timetable is 10 s earlier than the original timetable, and the scheduling timetable is not an even timetable after the optimization.Figure 7
Original timetable and scheduling timetable.(
2) Performance Indicators. The results are evaluated from multiple perspectives in terms of Q (average waiting time of boarding passengers), Q
1 (average waiting time of transfer passengers), Q
2 (average waiting time of access passengers), Q
- (average waiting time of passengers transferred from the loop line to connecting lines), and “Just Miss.” Q
- is calculated to show the impact of the optimization results on the other lines. The demand of passengers who transfer into the other lines is considered to be the same as the demand of passengers who transfer from the other lines. Typically, passengers are not happy to find that they just missed the connecting train by a few seconds. Hence, “Just Miss” [19] is calculated, which involves a case when the sum of transfer time and transfer waiting time exceeds the headway of the connecting train. For example, in Figure 2, the transfer in which passengers transfer from the q
′
-
1th train on line k
′ to the q
-
1th train on line k is a “Just Miss” scenario, while the other transfers are not. A comparison of the results of the numerical example is shown in Table 4.Table 4
Result comparison of the numerical example.
Performance indicators
Q
Q
1
Q
2
Q
-
Just Miss
Original timetable
98.0 s
96.7 s
100 s
89.2 s
74
Scheduling timetable
86.2 s
77.3 s
99.4 s
84.6 s
62
Improvement
12.04%
20.06%
0.60%
5.16%
16.22%As shown in Table4, all the performance indicators are improved conspicuously by the suggested model. Specifically, Q
1 improves more than other indicators. In contrast, Q
2 shows only a slight improvement because the average headway in an hour decreases, leading to limited optimization. The optimization effect of Q
2 is not as good as that of Q
1. However, it is necessary to simultaneously optimize the waiting time of access passengers and transfer passengers to avoid worse value of Q
2.The timetable of the loop line affectsQ
- at the same time. In this numerical example, Q
- decreases by 5.11% while Q
1 improves by 20.05%. This indicates that the timetable optimization of loop line can improve the service quality of the entire network. A constraint of Q
- can be set to ensure better impact on the other lines while optimizing the timetable.(
3)   Optimization Results of Transfer Station. The transfer waiting time from all feeder trains at transfer stations is further analyzed due to the great disparity of the headways and transfer passenger demand in the feeder lines. For example, in the case of Station 5 and Station 6, Figure 8(a) displays the transfer waiting times taken by one passenger to transfer from the feeder trains in the down-track of Line 3 to the down-track of Line 2 at Station 5. Figure 8(b) displays the transfer waiting times taken by one passenger to transfer from the feeder trains in the down-track of Line 1 to the down-track of Line 2 at Station 6.Figure 8
Transfer waiting time from all feeder trains at the transfer station.
(a)
(b)Figure8 shows that the transfer waiting time changes periodically before optimization. However, the transfer waiting time does not change periodically in an hour after the optimization affected by the uneven headways. Additionally, a comparison of the transfer waiting times at Station 5 and Station 6 indicates that the transfer waiting time of passengers transferred from Line 1 to Line 2 shows better improvement than that of the passengers transferred from Line 3 to Line 2. This suggested that larger headways of feeder trains may lead to a better optimization effect.


#### 4.1.3. Sensitivity Analysis of the Variation of Headways and Dwell Time

In order to explore the impact on the average waiting time, the allowable maximum range of headway and dwell time on the loop line are adjusted to different degrees. The results are shown in Figure9.Figure 9
Sensitivity analysis of the variation of headways and dwell times.The optimization effect ofQ obtained a phased improvement by simultaneously expanding the allowable maximum range of headway and dwell time. When d
1 is [
0,10
], [
10,20
], and [
20,30
], the increase in the optimization effect of Q indicates three stages. In the case when d
2 is [
0,15
], the optimization effect of Q improves slowly. However, the optimization effect of Q
2 is not stable. With the expansion of d
1 and d
2, the optimization effect of Q
2 showed a slight improvement, which is determined by the mean and variance of the headways on the loop line.The result shows that the expansion of the allowable maximum range of the headway allows better solutions than the same expansion in the allowable maximum range of the dwell time. Therefore,d
1 could be expanded to obtain better optimization results in actual operations.


### 4.2. Line 2 in Beijing Urban Rail Transit

#### 4.2.1. Network Parameters

In order to validate the application of the model in practical cases, the suggested model is applied to Line 2 in the Beijing urban rail transit. The 2014 network structure is shown in Figure10 and includes Line 2 and the feeder lines (except the airport line). Line 2 connects 6 lines and has 18 stations including 10 transfer stations. The scale of the practice case is almost thrice that of the numerical example.Figure 10
Line 2 and the feeder lines in the Beijing urban rail transit.There are significant differences between passenger demand in rush hours and non-rush hours. For the sake of convenience, two typical time intervals are considered in a day, namely, the rush hour period (7:00–9:00) and the non-rush hour period (12:00–14:00). The percentage of transfer passengers accounts for 68% and 56% of the boarding passengers in the rush hours and non-rush hours, respectively. The headways and passenger demand are shown in Tables5 and 6.Table 5
Headways of Line 2 and feeder lines.
Line 1
Line 2
Line 4
Line 5
Line 6
Line 8
Line 13
Rush hour (s)
125
120–150
120
150
240
300
180
Non-rush hour (s)
200
270
240
280
360
460
440–480Table 6
The number of transfer passengers from one feeder train on feeder lines.
To
From
XiZhiMen
CheGongZhuang
FuXingMen
XuanWuMen
DongZhiMen
4U
4D
13U
6U
6D
1U
1D
4U
4D
13D
2U (rush hour)
10
102
223
69
69
94
8
252
35
150
2D (rush hour)
54
148
75
67
34
171
69
185
3
456
2U (non-rush hour)
7
104
116
29
26
63
5
170
63
74
2D (non-rush hour)
47
150
51
26
17
67
58
88
5
211
To
From
ChongWenMen
JianGuoMen
ChaoYangMen
YongHeGong
GuLouDaJie
5U
5D
1U
1D
6U
6D
5U
5D
8U
8D
2U (rush hour)
114
8
68
250
18
157
53
231
106
246
2D (rush hour)
167
53
8
80
21
187
13
154
69
178
2U (non-rush hour)
51
13
59
97
11
47
32
88
57
106
2D (non-rush hour)
70
46
28
59
19
84
10
55
52
63Higher frequency of operations is needed in rush hours due to increased passenger demand. However, the headways cannot infinitely shorten due to the limitation of traffic capacity. Therefore, the allowable maximum range of headways in rush hours is smaller than that in non-rush hours.d
1 is set as 15 s in rush hours and 30 s in non-rush hours. The minimum headway is 120 s. Furthermore, d
2 is set as 5 s in both the periods. The parameters of GA are the same as those in the numerical example.


#### 4.2.2. Result Analysis

In this section, the timetables of up-track and down-track on Line 2 in rush hours and non-rush hours are optimized, respectively. Long passengers waiting time can reduce the service quality and the large number of waiting passengers may cause delays. Therefore,t
_
m
a
x [24] and p
_
m
a
x are proposed to evaluate the equitability of waiting time and the number of waiting passengers. Here, t
_
m
a
x is calculated by m
a
x
p
k
q
s
k
′
q
′
t
k
q
s
k
′
q
′
W, which stands for the maximum time in a transfer direction at transfer stations. p
_
m
a
x is calculated by m
a
x
∑
k
′
=
3
a
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
+
λ
k
s
t
k
q
s
L
-
t
k
,
q
-
1
,
s
L, which stands for the maximum number of passengers waiting to board a train. Table 7 shows a comparison of the original timetable and scheduling timetable.Table 7
Optimization results of Line 2.
Period
Direction
Objective
Improvement
Q
Q
Q
1
Q
2
t
_
m
a
x
p
_
m
a
x
Rush hour
Up-track
58.4 s
3.69%
3.09%
1.92%
−8.31%
3.15%
Down-track
59.4 s
2.89%
2.27%
1.08%
−2.48%
4.75%
Non-rush hour
Up-track
124.7 s
11.60%
6.89%
0.80%
23.53%
−0.44%
Down-track
123.6 s
11.47%
6.19%
−0.25%
0.41%
−0.67%The average waiting times of passengers on the up-track and down-track are improved by 3.69% and 2.89% in rush hours and by 11.6% and 11.47% in non-rush hours. This significantly increases the service quality of Line 2. The optimization effect in non-rush hours is better than that in rush hours. There is only a slight optimization effect on the passenger waiting time in rush hours since the headway in rush hours is quite small and leaves little room for optimization. Access passenger waiting time on down-track of the scheduling timetable is slightly worse than that of the original timetable because of the uneven headways.Additionally,t
_
m
a
x in non-rush hours exhibited a better improvement than that in rush hours, while p
_
m
a
x in rush hours shows a better improvement than that in non-rush hours. Moreover, t
_
m
a
x depends on the increased improvement in the average waiting time in non-rush hours, while p
_
m
a
x depends on the high frequency and good coordination in rush hours. Furthermore, p
_
m
a
x occurs at the XiZhiMen Station during the two periods and is reduced by 18 and 27 passengers on the up-track and down-track, respectively, in rush hours. The corresponding reduction in non-rush hours is 2 and 4 passengers, respectively.Therefore, the suggested model showed encouraging effects on the decrease in the waiting time of passengers in non-rush hours and the number of passengers waiting on platforms in rush hour. The results suggest that headway plays an important role in influencing the passenger waiting time and the number of waiting passengers.


## 4.1. Numerical Example

### 4.1.1. Network and Model Parameters

Figure5 shows a test network for the proposed model. Line 2 is a loop line, which connects two lines in the sample network, namely, Line 1 and Line 3. There are 6 stations on Line 2 including 4 transfer stations. In addition, T3 is the depot at which the train operation starts.Figure 5
A sample transit network.The dwell times of trains at each station and the transfer times of passengers at transfer stations are given in Table1. The run times from terminal station to every station are shown in Table 2. Table 3 depicts the transfer demand and arrival rate of passengers. “U” and “D” indicate “up-track” and “down-track,” respectively. The ratio of the number of transfer passengers and access passenger is 6 : 4. The primary headways of Lines 1–3 are 180 s, 200 s, and 150 s, respectively.Table 1
Dwell time of trains and transfer time of passengers.
S1
S2
S3
S4
S5
S6
Dwell time (s)
Line 1
—
—
30
—
—
30
Line 2
35
20
30
25
35
35
Line 3
30
—
—
—
35
—
Transfer time (s)
90
—
80
—
80
90Table 2
Run time.
Run time (s)
To
S1
S2
S3
S4
S5
S6
From
T1
—
—
1150
—
—
500
T2
—
—
400
—
—
1050
T3-U
250
700
1150
1550
1750
2100
T3-D
2170
1720
1270
870
670
320
T4
450
—
—
—
1050
—
T5
950
—
—
—
350
—Table 3
Passenger demand.
Passenger demand
S1
S2
S3
S4
S5
S6
The number of transfer passengers from a feeder train
1U-2D
—
—
30
—
—
30
1D-2D
—
—
18
—
—
39
3U-2D
30
—
—
—
39
—
3D-2D
27
—
—
—
33
—
Arrival rate of access passengers (person/s)
Line 2
0.2
0.13
0.18
0.1
0.22
0.18In reality, the timetables in rush hours and non-rush hours are different, and the time periods are mostly divided by hours. Therefore, in this paper, 1 hour is set as the study period to test the model.


### 4.1.2. Result Analysis

(
1)   Optimization Result. The down-track on Line 2 is considered as an example. For simplicity, all the trains are set to the same dwell time at the same station. The program is run by MATLAB (7.8.0). The population size is 100, crossover fraction is 0.9, mutation fraction is 0.3, and generation is 1000. Additionally, d
1 is 30 s, and d
2 is 5 s. The objective function value of each generation is shown in Figure 6. The result shows that the GA has good convergence to solve the proposed model, and the algorithm began to converge in 565 generations.Figure 6
Optimization process of GA.Figure7 shows a comparison of the original timetable and scheduling timetable. The horizontal axis indicates time steps beginning from 0 min, and the vertical axis indicates the stations starting from the depot T3. The departure time of the first train at the depot in the scheduling timetable is 10 s earlier than the original timetable, and the scheduling timetable is not an even timetable after the optimization.Figure 7
Original timetable and scheduling timetable.(
2) Performance Indicators. The results are evaluated from multiple perspectives in terms of Q (average waiting time of boarding passengers), Q
1 (average waiting time of transfer passengers), Q
2 (average waiting time of access passengers), Q
- (average waiting time of passengers transferred from the loop line to connecting lines), and “Just Miss.” Q
- is calculated to show the impact of the optimization results on the other lines. The demand of passengers who transfer into the other lines is considered to be the same as the demand of passengers who transfer from the other lines. Typically, passengers are not happy to find that they just missed the connecting train by a few seconds. Hence, “Just Miss” [19] is calculated, which involves a case when the sum of transfer time and transfer waiting time exceeds the headway of the connecting train. For example, in Figure 2, the transfer in which passengers transfer from the q
′
-
1th train on line k
′ to the q
-
1th train on line k is a “Just Miss” scenario, while the other transfers are not. A comparison of the results of the numerical example is shown in Table 4.Table 4
Result comparison of the numerical example.
Performance indicators
Q
Q
1
Q
2
Q
-
Just Miss
Original timetable
98.0 s
96.7 s
100 s
89.2 s
74
Scheduling timetable
86.2 s
77.3 s
99.4 s
84.6 s
62
Improvement
12.04%
20.06%
0.60%
5.16%
16.22%As shown in Table4, all the performance indicators are improved conspicuously by the suggested model. Specifically, Q
1 improves more than other indicators. In contrast, Q
2 shows only a slight improvement because the average headway in an hour decreases, leading to limited optimization. The optimization effect of Q
2 is not as good as that of Q
1. However, it is necessary to simultaneously optimize the waiting time of access passengers and transfer passengers to avoid worse value of Q
2.The timetable of the loop line affectsQ
- at the same time. In this numerical example, Q
- decreases by 5.11% while Q
1 improves by 20.05%. This indicates that the timetable optimization of loop line can improve the service quality of the entire network. A constraint of Q
- can be set to ensure better impact on the other lines while optimizing the timetable.(
3)   Optimization Results of Transfer Station. The transfer waiting time from all feeder trains at transfer stations is further analyzed due to the great disparity of the headways and transfer passenger demand in the feeder lines. For example, in the case of Station 5 and Station 6, Figure 8(a) displays the transfer waiting times taken by one passenger to transfer from the feeder trains in the down-track of Line 3 to the down-track of Line 2 at Station 5. Figure 8(b) displays the transfer waiting times taken by one passenger to transfer from the feeder trains in the down-track of Line 1 to the down-track of Line 2 at Station 6.Figure 8
Transfer waiting time from all feeder trains at the transfer station.
(a)
(b)Figure8 shows that the transfer waiting time changes periodically before optimization. However, the transfer waiting time does not change periodically in an hour after the optimization affected by the uneven headways. Additionally, a comparison of the transfer waiting times at Station 5 and Station 6 indicates that the transfer waiting time of passengers transferred from Line 1 to Line 2 shows better improvement than that of the passengers transferred from Line 3 to Line 2. This suggested that larger headways of feeder trains may lead to a better optimization effect.


### 4.1.3. Sensitivity Analysis of the Variation of Headways and Dwell Time

In order to explore the impact on the average waiting time, the allowable maximum range of headway and dwell time on the loop line are adjusted to different degrees. The results are shown in Figure9.Figure 9
Sensitivity analysis of the variation of headways and dwell times.The optimization effect ofQ obtained a phased improvement by simultaneously expanding the allowable maximum range of headway and dwell time. When d
1 is [
0,10
], [
10,20
], and [
20,30
], the increase in the optimization effect of Q indicates three stages. In the case when d
2 is [
0,15
], the optimization effect of Q improves slowly. However, the optimization effect of Q
2 is not stable. With the expansion of d
1 and d
2, the optimization effect of Q
2 showed a slight improvement, which is determined by the mean and variance of the headways on the loop line.The result shows that the expansion of the allowable maximum range of the headway allows better solutions than the same expansion in the allowable maximum range of the dwell time. Therefore,d
1 could be expanded to obtain better optimization results in actual operations.


## 4.1.1. Network and Model Parameters

Figure5 shows a test network for the proposed model. Line 2 is a loop line, which connects two lines in the sample network, namely, Line 1 and Line 3. There are 6 stations on Line 2 including 4 transfer stations. In addition, T3 is the depot at which the train operation starts.Figure 5
A sample transit network.The dwell times of trains at each station and the transfer times of passengers at transfer stations are given in Table1. The run times from terminal station to every station are shown in Table 2. Table 3 depicts the transfer demand and arrival rate of passengers. “U” and “D” indicate “up-track” and “down-track,” respectively. The ratio of the number of transfer passengers and access passenger is 6 : 4. The primary headways of Lines 1–3 are 180 s, 200 s, and 150 s, respectively.Table 1
Dwell time of trains and transfer time of passengers.
S1
S2
S3
S4
S5
S6
Dwell time (s)
Line 1
—
—
30
—
—
30
Line 2
35
20
30
25
35
35
Line 3
30
—
—
—
35
—
Transfer time (s)
90
—
80
—
80
90Table 2
Run time.
Run time (s)
To
S1
S2
S3
S4
S5
S6
From
T1
—
—
1150
—
—
500
T2
—
—
400
—
—
1050
T3-U
250
700
1150
1550
1750
2100
T3-D
2170
1720
1270
870
670
320
T4
450
—
—
—
1050
—
T5
950
—
—
—
350
—Table 3
Passenger demand.
Passenger demand
S1
S2
S3
S4
S5
S6
The number of transfer passengers from a feeder train
1U-2D
—
—
30
—
—
30
1D-2D
—
—
18
—
—
39
3U-2D
30
—
—
—
39
—
3D-2D
27
—
—
—
33
—
Arrival rate of access passengers (person/s)
Line 2
0.2
0.13
0.18
0.1
0.22
0.18In reality, the timetables in rush hours and non-rush hours are different, and the time periods are mostly divided by hours. Therefore, in this paper, 1 hour is set as the study period to test the model.


## 4.1.2. Result Analysis

(
1)   Optimization Result. The down-track on Line 2 is considered as an example. For simplicity, all the trains are set to the same dwell time at the same station. The program is run by MATLAB (7.8.0). The population size is 100, crossover fraction is 0.9, mutation fraction is 0.3, and generation is 1000. Additionally, d
1 is 30 s, and d
2 is 5 s. The objective function value of each generation is shown in Figure 6. The result shows that the GA has good convergence to solve the proposed model, and the algorithm began to converge in 565 generations.Figure 6
Optimization process of GA.Figure7 shows a comparison of the original timetable and scheduling timetable. The horizontal axis indicates time steps beginning from 0 min, and the vertical axis indicates the stations starting from the depot T3. The departure time of the first train at the depot in the scheduling timetable is 10 s earlier than the original timetable, and the scheduling timetable is not an even timetable after the optimization.Figure 7
Original timetable and scheduling timetable.(
2) Performance Indicators. The results are evaluated from multiple perspectives in terms of Q (average waiting time of boarding passengers), Q
1 (average waiting time of transfer passengers), Q
2 (average waiting time of access passengers), Q
- (average waiting time of passengers transferred from the loop line to connecting lines), and “Just Miss.” Q
- is calculated to show the impact of the optimization results on the other lines. The demand of passengers who transfer into the other lines is considered to be the same as the demand of passengers who transfer from the other lines. Typically, passengers are not happy to find that they just missed the connecting train by a few seconds. Hence, “Just Miss” [19] is calculated, which involves a case when the sum of transfer time and transfer waiting time exceeds the headway of the connecting train. For example, in Figure 2, the transfer in which passengers transfer from the q
′
-
1th train on line k
′ to the q
-
1th train on line k is a “Just Miss” scenario, while the other transfers are not. A comparison of the results of the numerical example is shown in Table 4.Table 4
Result comparison of the numerical example.
Performance indicators
Q
Q
1
Q
2
Q
-
Just Miss
Original timetable
98.0 s
96.7 s
100 s
89.2 s
74
Scheduling timetable
86.2 s
77.3 s
99.4 s
84.6 s
62
Improvement
12.04%
20.06%
0.60%
5.16%
16.22%As shown in Table4, all the performance indicators are improved conspicuously by the suggested model. Specifically, Q
1 improves more than other indicators. In contrast, Q
2 shows only a slight improvement because the average headway in an hour decreases, leading to limited optimization. The optimization effect of Q
2 is not as good as that of Q
1. However, it is necessary to simultaneously optimize the waiting time of access passengers and transfer passengers to avoid worse value of Q
2.The timetable of the loop line affectsQ
- at the same time. In this numerical example, Q
- decreases by 5.11% while Q
1 improves by 20.05%. This indicates that the timetable optimization of loop line can improve the service quality of the entire network. A constraint of Q
- can be set to ensure better impact on the other lines while optimizing the timetable.(
3)   Optimization Results of Transfer Station. The transfer waiting time from all feeder trains at transfer stations is further analyzed due to the great disparity of the headways and transfer passenger demand in the feeder lines. For example, in the case of Station 5 and Station 6, Figure 8(a) displays the transfer waiting times taken by one passenger to transfer from the feeder trains in the down-track of Line 3 to the down-track of Line 2 at Station 5. Figure 8(b) displays the transfer waiting times taken by one passenger to transfer from the feeder trains in the down-track of Line 1 to the down-track of Line 2 at Station 6.Figure 8
Transfer waiting time from all feeder trains at the transfer station.
(a)
(b)Figure8 shows that the transfer waiting time changes periodically before optimization. However, the transfer waiting time does not change periodically in an hour after the optimization affected by the uneven headways. Additionally, a comparison of the transfer waiting times at Station 5 and Station 6 indicates that the transfer waiting time of passengers transferred from Line 1 to Line 2 shows better improvement than that of the passengers transferred from Line 3 to Line 2. This suggested that larger headways of feeder trains may lead to a better optimization effect.


## 4.1.3. Sensitivity Analysis of the Variation of Headways and Dwell Time

In order to explore the impact on the average waiting time, the allowable maximum range of headway and dwell time on the loop line are adjusted to different degrees. The results are shown in Figure9.Figure 9
Sensitivity analysis of the variation of headways and dwell times.The optimization effect ofQ obtained a phased improvement by simultaneously expanding the allowable maximum range of headway and dwell time. When d
1 is [
0,10
], [
10,20
], and [
20,30
], the increase in the optimization effect of Q indicates three stages. In the case when d
2 is [
0,15
], the optimization effect of Q improves slowly. However, the optimization effect of Q
2 is not stable. With the expansion of d
1 and d
2, the optimization effect of Q
2 showed a slight improvement, which is determined by the mean and variance of the headways on the loop line.The result shows that the expansion of the allowable maximum range of the headway allows better solutions than the same expansion in the allowable maximum range of the dwell time. Therefore,d
1 could be expanded to obtain better optimization results in actual operations.


## 4.2. Line 2 in Beijing Urban Rail Transit

### 4.2.1. Network Parameters

In order to validate the application of the model in practical cases, the suggested model is applied to Line 2 in the Beijing urban rail transit. The 2014 network structure is shown in Figure10 and includes Line 2 and the feeder lines (except the airport line). Line 2 connects 6 lines and has 18 stations including 10 transfer stations. The scale of the practice case is almost thrice that of the numerical example.Figure 10
Line 2 and the feeder lines in the Beijing urban rail transit.There are significant differences between passenger demand in rush hours and non-rush hours. For the sake of convenience, two typical time intervals are considered in a day, namely, the rush hour period (7:00–9:00) and the non-rush hour period (12:00–14:00). The percentage of transfer passengers accounts for 68% and 56% of the boarding passengers in the rush hours and non-rush hours, respectively. The headways and passenger demand are shown in Tables5 and 6.Table 5
Headways of Line 2 and feeder lines.
Line 1
Line 2
Line 4
Line 5
Line 6
Line 8
Line 13
Rush hour (s)
125
120–150
120
150
240
300
180
Non-rush hour (s)
200
270
240
280
360
460
440–480Table 6
The number of transfer passengers from one feeder train on feeder lines.
To
From
XiZhiMen
CheGongZhuang
FuXingMen
XuanWuMen
DongZhiMen
4U
4D
13U
6U
6D
1U
1D
4U
4D
13D
2U (rush hour)
10
102
223
69
69
94
8
252
35
150
2D (rush hour)
54
148
75
67
34
171
69
185
3
456
2U (non-rush hour)
7
104
116
29
26
63
5
170
63
74
2D (non-rush hour)
47
150
51
26
17
67
58
88
5
211
To
From
ChongWenMen
JianGuoMen
ChaoYangMen
YongHeGong
GuLouDaJie
5U
5D
1U
1D
6U
6D
5U
5D
8U
8D
2U (rush hour)
114
8
68
250
18
157
53
231
106
246
2D (rush hour)
167
53
8
80
21
187
13
154
69
178
2U (non-rush hour)
51
13
59
97
11
47
32
88
57
106
2D (non-rush hour)
70
46
28
59
19
84
10
55
52
63Higher frequency of operations is needed in rush hours due to increased passenger demand. However, the headways cannot infinitely shorten due to the limitation of traffic capacity. Therefore, the allowable maximum range of headways in rush hours is smaller than that in non-rush hours.d
1 is set as 15 s in rush hours and 30 s in non-rush hours. The minimum headway is 120 s. Furthermore, d
2 is set as 5 s in both the periods. The parameters of GA are the same as those in the numerical example.


### 4.2.2. Result Analysis

In this section, the timetables of up-track and down-track on Line 2 in rush hours and non-rush hours are optimized, respectively. Long passengers waiting time can reduce the service quality and the large number of waiting passengers may cause delays. Therefore,t
_
m
a
x [24] and p
_
m
a
x are proposed to evaluate the equitability of waiting time and the number of waiting passengers. Here, t
_
m
a
x is calculated by m
a
x
p
k
q
s
k
′
q
′
t
k
q
s
k
′
q
′
W, which stands for the maximum time in a transfer direction at transfer stations. p
_
m
a
x is calculated by m
a
x
∑
k
′
=
3
a
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
+
λ
k
s
t
k
q
s
L
-
t
k
,
q
-
1
,
s
L, which stands for the maximum number of passengers waiting to board a train. Table 7 shows a comparison of the original timetable and scheduling timetable.Table 7
Optimization results of Line 2.
Period
Direction
Objective
Improvement
Q
Q
Q
1
Q
2
t
_
m
a
x
p
_
m
a
x
Rush hour
Up-track
58.4 s
3.69%
3.09%
1.92%
−8.31%
3.15%
Down-track
59.4 s
2.89%
2.27%
1.08%
−2.48%
4.75%
Non-rush hour
Up-track
124.7 s
11.60%
6.89%
0.80%
23.53%
−0.44%
Down-track
123.6 s
11.47%
6.19%
−0.25%
0.41%
−0.67%The average waiting times of passengers on the up-track and down-track are improved by 3.69% and 2.89% in rush hours and by 11.6% and 11.47% in non-rush hours. This significantly increases the service quality of Line 2. The optimization effect in non-rush hours is better than that in rush hours. There is only a slight optimization effect on the passenger waiting time in rush hours since the headway in rush hours is quite small and leaves little room for optimization. Access passenger waiting time on down-track of the scheduling timetable is slightly worse than that of the original timetable because of the uneven headways.Additionally,t
_
m
a
x in non-rush hours exhibited a better improvement than that in rush hours, while p
_
m
a
x in rush hours shows a better improvement than that in non-rush hours. Moreover, t
_
m
a
x depends on the increased improvement in the average waiting time in non-rush hours, while p
_
m
a
x depends on the high frequency and good coordination in rush hours. Furthermore, p
_
m
a
x occurs at the XiZhiMen Station during the two periods and is reduced by 18 and 27 passengers on the up-track and down-track, respectively, in rush hours. The corresponding reduction in non-rush hours is 2 and 4 passengers, respectively.Therefore, the suggested model showed encouraging effects on the decrease in the waiting time of passengers in non-rush hours and the number of passengers waiting on platforms in rush hour. The results suggest that headway plays an important role in influencing the passenger waiting time and the number of waiting passengers.


## 4.2.1. Network Parameters

In order to validate the application of the model in practical cases, the suggested model is applied to Line 2 in the Beijing urban rail transit. The 2014 network structure is shown in Figure10 and includes Line 2 and the feeder lines (except the airport line). Line 2 connects 6 lines and has 18 stations including 10 transfer stations. The scale of the practice case is almost thrice that of the numerical example.Figure 10
Line 2 and the feeder lines in the Beijing urban rail transit.There are significant differences between passenger demand in rush hours and non-rush hours. For the sake of convenience, two typical time intervals are considered in a day, namely, the rush hour period (7:00–9:00) and the non-rush hour period (12:00–14:00). The percentage of transfer passengers accounts for 68% and 56% of the boarding passengers in the rush hours and non-rush hours, respectively. The headways and passenger demand are shown in Tables5 and 6.Table 5
Headways of Line 2 and feeder lines.
Line 1
Line 2
Line 4
Line 5
Line 6
Line 8
Line 13
Rush hour (s)
125
120–150
120
150
240
300
180
Non-rush hour (s)
200
270
240
280
360
460
440–480Table 6
The number of transfer passengers from one feeder train on feeder lines.
To
From
XiZhiMen
CheGongZhuang
FuXingMen
XuanWuMen
DongZhiMen
4U
4D
13U
6U
6D
1U
1D
4U
4D
13D
2U (rush hour)
10
102
223
69
69
94
8
252
35
150
2D (rush hour)
54
148
75
67
34
171
69
185
3
456
2U (non-rush hour)
7
104
116
29
26
63
5
170
63
74
2D (non-rush hour)
47
150
51
26
17
67
58
88
5
211
To
From
ChongWenMen
JianGuoMen
ChaoYangMen
YongHeGong
GuLouDaJie
5U
5D
1U
1D
6U
6D
5U
5D
8U
8D
2U (rush hour)
114
8
68
250
18
157
53
231
106
246
2D (rush hour)
167
53
8
80
21
187
13
154
69
178
2U (non-rush hour)
51
13
59
97
11
47
32
88
57
106
2D (non-rush hour)
70
46
28
59
19
84
10
55
52
63Higher frequency of operations is needed in rush hours due to increased passenger demand. However, the headways cannot infinitely shorten due to the limitation of traffic capacity. Therefore, the allowable maximum range of headways in rush hours is smaller than that in non-rush hours.d
1 is set as 15 s in rush hours and 30 s in non-rush hours. The minimum headway is 120 s. Furthermore, d
2 is set as 5 s in both the periods. The parameters of GA are the same as those in the numerical example.


## 4.2.2. Result Analysis

In this section, the timetables of up-track and down-track on Line 2 in rush hours and non-rush hours are optimized, respectively. Long passengers waiting time can reduce the service quality and the large number of waiting passengers may cause delays. Therefore,t
_
m
a
x [24] and p
_
m
a
x are proposed to evaluate the equitability of waiting time and the number of waiting passengers. Here, t
_
m
a
x is calculated by m
a
x
p
k
q
s
k
′
q
′
t
k
q
s
k
′
q
′
W, which stands for the maximum time in a transfer direction at transfer stations. p
_
m
a
x is calculated by m
a
x
∑
k
′
=
3
a
∑
q
′
=
1
n
k
′
T
p
k
q
s
k
′
q
′
+
λ
k
s
t
k
q
s
L
-
t
k
,
q
-
1
,
s
L, which stands for the maximum number of passengers waiting to board a train. Table 7 shows a comparison of the original timetable and scheduling timetable.Table 7
Optimization results of Line 2.
Period
Direction
Objective
Improvement
Q
Q
Q
1
Q
2
t
_
m
a
x
p
_
m
a
x
Rush hour
Up-track
58.4 s
3.69%
3.09%
1.92%
−8.31%
3.15%
Down-track
59.4 s
2.89%
2.27%
1.08%
−2.48%
4.75%
Non-rush hour
Up-track
124.7 s
11.60%
6.89%
0.80%
23.53%
−0.44%
Down-track
123.6 s
11.47%
6.19%
−0.25%
0.41%
−0.67%The average waiting times of passengers on the up-track and down-track are improved by 3.69% and 2.89% in rush hours and by 11.6% and 11.47% in non-rush hours. This significantly increases the service quality of Line 2. The optimization effect in non-rush hours is better than that in rush hours. There is only a slight optimization effect on the passenger waiting time in rush hours since the headway in rush hours is quite small and leaves little room for optimization. Access passenger waiting time on down-track of the scheduling timetable is slightly worse than that of the original timetable because of the uneven headways.Additionally,t
_
m
a
x in non-rush hours exhibited a better improvement than that in rush hours, while p
_
m
a
x in rush hours shows a better improvement than that in non-rush hours. Moreover, t
_
m
a
x depends on the increased improvement in the average waiting time in non-rush hours, while p
_
m
a
x depends on the high frequency and good coordination in rush hours. Furthermore, p
_
m
a
x occurs at the XiZhiMen Station during the two periods and is reduced by 18 and 27 passengers on the up-track and down-track, respectively, in rush hours. The corresponding reduction in non-rush hours is 2 and 4 passengers, respectively.Therefore, the suggested model showed encouraging effects on the decrease in the waiting time of passengers in non-rush hours and the number of passengers waiting on platforms in rush hour. The results suggest that headway plays an important role in influencing the passenger waiting time and the number of waiting passengers.


## 5. Conclusions

In this paper, a timetable optimization model of loop line considering timetable coordination is presented to minimize the average waiting time of access passengers and transfer passengers. Train connection constraints are considered in the model to ensure the continuity of train operation on the loop line. A genetic algorithm is designed and then successfully tested through a numerical example and a real-world case study. The results show that the model presented is effective and efficient for improving the service quality of Line 2 in the Beijing urban rail transit. The results also indicate that the timetable optimization of the loop line is closely related to passenger demand, headways on loop lines, and feeder lines. Timetable optimization helps in reducing the average waiting time for passengers during non-rush hours and maximal number of waiting passengers during rush hours.The arrival characteristic of transfer passengers is assumed to be uniform in the study. However, it is not uniform in real-life scenarios, and this can also affect the results of the model. Hence, future research should attempt to refine the arrival characteristics of transfer passengers in order to make the model more realistic.



---

*Source: 4627094-2016-08-29.xml*