# Dynamic Schedule-Based Assignment Model for Urban Rail Transit Network with Capacity Constraints

Authors: Baoming Han; Weiteng Zhou; Dewei Li; Haodong Yin
Journal: The Scientific World Journal
 (2015)

---

## Abstract

There is a great need for estimation of passenger flow temporal and spatial distribution in urban rail transit network. The literature review indicates that passenger flow assignment models considering capacity constraints with overload delay factor for in-vehicle crowding are limited in schedule-based network. This paper proposes a stochastic user equilibrium model for solving the assignment problem in a schedule-based rail transit network with considering capacity constraint. As splitting the origin-destination demands into the developed schedule expanded network with time-space paths, the model transformed into a dynamic schedule-based assignment model. The stochastic user equilibrium conditions can be equivalent to the equilibrium passenger overload delay with crowding penalty in the transit network. The proposal model can estimate the path choice probability according to the equilibrium condition when passengers minimize their perceptive cost in a schedule-based network. Numerical example in Beijing urban rail transit (BURT) network is used to demonstrate the performance of the model and estimate the passenger flow temporal and spatial distribution more reasonably and dynamically with train capacity constraints.


---

## Body

## 1. Introduction

As Beijing urban rail transit (BURT) network is growing rapidly, the ridership of the BURT network is about 8,000,000 person-trips, which is still increased quickly successively. For safe and efficient operation requirements, the high risk of passenger flow and multistakeholders status makes it necessary and critical to estimate and evaluate the passenger flow temporal and spatial distribution scientifically and reasonably within the BURT network. With the automatic fare collection (AFC) [1] and passenger information system (PIS), the dynamic transit assignment problem, substantially, is a black-box problem with input of specific original-destination (O-D) information. Transit assignment model is a practical approach for estimating and predicting how passengers utilize transit system and choose paths, which can be definitely divided into two types: “frequency-based” and “schedule-based” [2]. On frequency-based transit network, each transit line is assumed to be run on a constant headway with a static process in the transit assignment [3–5], and the network would be represented in a static manner [6, 7]. For the majority of these models, schedule of transit system is assumed to be sufficiently reliable. Therefore, the headway is calculated by the average frequencies of transit line in frequency-based network. The waiting time and transfer time are implicit estimated based on headway. Since the time dimension is not considered in frequency-based transit model, the assignment results in frequency-based models are the average value in the specified time period (e.g., the rush hour). Unlike frequency-based type model, schedule-based models generally take explicitly timetable or schedule of the transit system into account [8–11], which means that the detailed departure or arrival times of vehicle or train in each transit lines are used in assignment procedures. According to different schedule-based transit assignment models, the time-dependent transit network representations can be classified into four types: (a) diachronic graph [12]; (b) dual graph [13]; (c) forward star network [14]; (d) discrete space-time graph [15] and time-expanded network [16]. Modeling formulations of transit assignment are one of schedule-based problems. Alfa and Chen [17] formulated a transit assignment model to forecast the temporal and spatial demand distribution in transit network. Tong and Wong [14] and Poon et al. [18] put forward a dynamic user equilibrium model, considering the crowded environment in boarding stations. Nielsen [19] proposed a stochastic transit assignment model considering differences properties in passengers’ utility function. As capacity constraints considered in schedule-based network in transit assignment are gradually developed in recent years, Hamdouch and Lawphongpanich [16] developed the model of how passengers are unable to board vehicle due to capacity limited assigned in to waiting arcs of time expanded network. Nuzzolo et al. [20] presented a schedule-based dynamic assignment model with using joint choice model for transit network taking congestion into account through explicit vehicle capacity. Hamdouch et al. [21] and Sumalee et al. [22] considered one of the critical factors of capacity, sitting and standing capacities, and the treatment of seat allocation is considered as a random probability to get a seat or not. Since previous researches in passenger flow assignment models are limited in schedule-based urban rail transit network, especially in considering the particularity of rail transit system described above, and lack of considering train capacity, a new stochastic user equilibrium (SUE) rail transit assignment model is introduced and formulated to estimate the passenger flow temporal and spatial distribution within network during a given time interval.Following the introduction, the remainder of this paper is organized as follows. Section2 focuses on network representation of the presented model. In Section 3, a SUE assignment model of SE network with trains’ capacity constraint and the solution procedure is presented, while Section 4 illustrates the results of an application to the real test experiment. Conclusions of this study are reported in Section 5.


## 2. Network Representation

As the schedule diagrams the departure time from the first station and daily planned arrival or departure time at each station along the transit lines, this paper proposes a new method that represents the static network which incorporates the temporal information of the trains, called schedule-expanded network. Essentially, the SE network is expanded from the two-dimension route networkG
(
N
,
A
) with adding the time dimension. The SE network of BURT network is of the form G
(
N
,
A
,
T
), where N denotes the sets of stations, A denotes the arcs of the sections of lines, and T denotes sets of the scheduled arrival/departure time of trains. The basic elements of the SE network are described as follows.(1) Temporal Nodes. Let r
t
l denote the temporal node, where the trains run through station r of line l at time t. In general, if there are n lines crossing the station and k trains running on each line, the station will be expanded into n
*
k temporal nodes.(2) Temporal Arcs. Let a
(
r
t
1
l
,
s
t
2
l
) denote the temporal section arcs from temporal node r
t
1
l to temporal node s
t
2
lof line l. Similarly an arc a
(
r
,
s
) of route network is expanded into k arcs as the form (
r
t
1
l
,
s
t
2
l
)
k where k equals the number of trains running though the section of the line based on schedule. As defined in the previous section, c
r
s denotes the travel time of arc (
r
,
s
). Let c
t
1
,
t
2
r
s
,
l denote the travel time of temporal section arc a
(
r
t
1
l
,
s
t
2
l
), and let t
1, t
2 be the arrival time at nodes r and s. c
t
1
,
t
2
r
s
,
l can be calculate as follows:(1)
c
t
1
,
t
2
r
s
=
t
2
-
t
1
t
1
,
t
2
∈
T
,
r
,
s
∈
N
,
a
∈
A
.Leta
(
r
t
1
l
1
,
r
t
2
l
2
) denote the temporal transfer arcs of the station r from line l
1 to l
2. As the endpoints of the arcs are the temporal nodes r
t
1
l
1 and r
t
2
l
2, so the travel time c
t
1
′
,
t
2
′
r
,
l
1
l
2 of the transfer arc (
r
t
1
l
1
,
r
t
2
l
2
) is(2)
c
t
1
′
,
t
2
′
r
,
l
1
l
2
=
t
2
′
-
t
1
′
t
1
′
,
t
2
′
∈
T
,
r
,
s
∈
N
,
a
∈
A
.In addition, there are temporal arcs(
r
t
1
,
r
t
2
) that represent passengers having to wait at station r from time t
1 to t
2, defined as a
(
r
t
1
l
,
r
t
2
l
). Let c
t
1
¯
,
t
2
r
,
l denote the passengers waiting time in temporal nodes r
t
1
l at the arrival time t
1
¯ and leave at scheduled departure time t
2:(3)
c
t
1
¯
,
t
2
r
,
l
=
t
2
-
t
1
¯
t
1
¯
,
t
2
∈
T
,
r
,
s
∈
N
,
a
∈
A
.Figure1 shows the SE network based on the route network upside, and the scheduled times of Figure 1 are shown in Table 1. Actually, Figure 1 shows all possible paths from station a
1 to b
3 at 7:30 to 8:10 a.m. For example, the path from a
1
7
:
30
L
1
→
a
2
7
:
33
L
1
→
a
2
7
:
41
L
2
→
b
3
7
:
49
L
2 corresponds to passengers leaving node a
1 at time 7:30 with train 0L11, arriving at a
2 of Line 1 at 7:33, then transferring to a
2 of Line 2 at 7:42, waiting for 0L21 and boarding train 0L21 at 7:47, and finally reaching b
3 at 7:49.Table 1
Partial schedule of the small network.
Train number
Station
Arrival time
Departure time
Line
Direction
0L11
a1
—
7:30
Line 1
Upstream
0L11
a2
7:33
7:34
Line 1
Upstream
0L11
b2
7:40
—
Line 1
Upstream
0L13
a1
—
7:48
Line 1
Upstream
0L13
a2
7:51
7:52
Line 1
Upstream
0L13
b2
7:58
—
Line 1
Upstream
0L21
A2
—
7:41
Line 2
Upstream
0L21
B2
7:46
7:47
Line 2
Upstream
0L21
B3
7:49
—
Line 2
Upstream
0L23
A2
—
7:58
Line 2
Upstream
0L23
B2
8:05
8:06
Line 2
Upstream
0L23
B3
8:08
—
Line 2
UpstreamFigure 1
A SE network based on the route network of one O-D pair in time period.In the SE network, temporal paths of O-D stations are a sequence of temporal arcs. Generally, a temporal path always consists of the 3 kinds of arcs proposed above. Computationally, schedule-expanded nodes and arcs can often be generated using the route network and timetable when solving an optimization problem, for example, to find the most optimal hyperpaths, the least travel time cost, and the most optimal path between O-D pairs. As the possible temporal paths consist of hyperpath with time dimension,k-shortest paths searching algorithm [6, 14] can be used in searching the possible temporal paths, if and only if the condition holds:(4)
t
k
o
i
d
j
≤
min
⁡
t
k
′
o
i
d
j
+
t
tor
,
t
k
′
o
i
d
j
*
1
+
d
1
,
t
k
wat
,
o
i
d
j
≤
min
⁡
t
k
′
wat
,
o
i
d
j
+
t
wat
,
tor
,
t
k
′
wat
,
o
i
d
j
*
1
+
d
2
,
t
k
n
≤
N
,where t
k
o
i
d
j denotes the travel time of kth path l
k in path set L
t
list, t
k
′
o
i
d
j denotes the minimum travel time of the path set L
t
list, t
k
′
wat
,
o
i
d
j denotes the minimum waiting time of the path set, t
tor denotes the maximum tolerance travel time of the path, t
wat
,
tor denotes the maximum tolerance waiting time of the path, t
k
n denotes the number of transfers times, N denotes the maximum tolerance number of transfers times, and d
1 and d
2 denote the maximum magnification of the tolerance time. All these tolerance parameters are user-defined.


## 3. Stochastic Dynamic User Equilibrium Assignment Model

### 3.1. Generalized Travel Time Cost in SE Network

The generalized travel time costg
c
r
s on arc (
r
,
s
) is subjected to a disutility that encompasses four weighted combination components: (i) in-vehicle travel time cost g
c
ivt
r
s; (ii) waiting time cost g
c
WAT
r
,
l; (iii) transfer time cost g
c
trt
r
,
l
1
l
2; (iv) passenger overload cost g
c
~
t
1
,
t
2
r
,
l. Denote β
1, β
2 by the weighting factors for waiting time and transfer time, respectively, and β
3 by the passenger overload delay in weighted time unit parameter. The generalized travel time cost g
c
r
s of the arc a
(
r
,
s
) can be expressed as (5)
g
c
r
s
=
g
c
ivt
r
s
+
g
c
WAT
r
,
l
+
g
c
trt
r
,
l
1
l
2
+
g
c
~
t
1
,
t
2
r
,
l
.Considering the components of the generalized travel time cost function in SE network, the components on the right side of the equation in a time intervalΔ
t may be described as follows.(i) If the number of passengers is large enough to make passengers discomfortable, the cost of the in-vehicle travel time, asT
IVT
r
s, may be amplified. When the number of the passengers is small, for example, less than the number of seats, it is not crowded in the train. Let ω
=
x
t
1
,
t
2
r
s
/
C
l denote trainload. With the trainload increasing, passengers may feel more discomfortable. We defined a piecewise function to describe the discomfort level with the passengers number increasing and the trainload in the temporal section arcs as(6)
f
c
(
x
t
1
,
t
2
r
s
)
=
1
;
x
t
1
,
t
2
r
s
C
l
≤
ω
0
,
1
+
ϕ
1
(
x
t
1
,
t
2
r
s
)
*
x
t
1
,
t
2
r
s
C
l
-
ω
0
,
ω
0
<
x
t
1
,
t
2
r
s
C
l
≤
ω
1
;
1
+
ϕ
1
(
ω
1
*
C
l
)
*
(
ω
1
-
ω
0
)
+
ϕ
1
(
x
t
1
,
t
2
r
s
)
*
(
x
t
1
,
t
2
r
s
C
l
-
ω
1
)
;
ω
1
<
x
t
1
,
t
2
r
s
C
l
;
ω
0
=
Z
l
C
l
,
ϕ
1
x
t
1
,
t
2
r
s
=
α
1
*
ω
γ
,
ω
=
x
t
1
,
t
2
r
s
C
l
,where Z
l denotes the seat number in the train and α
1 and γ are user-defined factors. The in-vehicle travel time cost in SE network is(7)
g
c
ivt
r
s
=
f
c
x
r
s
*
T
IVT
r
s
=
c
t
1
,
t
2
r
s
*
f
c
x
t
1
,
t
2
r
s
.(ii) According to train schedule, it is applicable to calculate the waiting time T
WAT
r
s by the subscripts of the temporal arc:(8)
g
c
WAT
r
,
l
=
β
1
*
T
WAT
r
s
=
β
1
*
c
t
1
,
t
2
r
,
l
.(iii) Transfer time includes two factors: the transfer times and the walking time T
TRT
r
s from one line transfer to the other line at a transfer station. That is because the transfer contains the process of “alighting-walking-boarding.” So the passengers have to change from one vehicle/train to another vehicle/line which will increase the passengers’ extra perceived costs. Letting σ denote the extra perceived cost factor which is affect by the transfer times, transfer time cost can be expressed as(9)
g
c
trt
r
,
l
1
l
2
=
β
2
*
T
TRT
r
s
+
σ
=
β
2
*
c
t
1
,
t
2
r
,
l
1
l
2
+
σ
.(iv) Passenger overload delay is the additional time that passengers spend on waiting for next train of temporal section arc due to the insufficient train capacity when they cannot board the first coming train of the temporal section. Let β
3 denote the passenger overload delay penalty factor and let m
r
s
,
k denote the overload delay of temporal arc (
r
,
s
) in path k:(10)
g
c
~
t
1
,
t
2
r
,
l
=
β
3
*
m
r
s
,
k
.Combined with the generalized travel time costg
c
r
s of the temporal arc a
(
r
,
s
) in temporal arcs list, the generalized travel time cost to reach at destination d
j from original o
i node G
C
k
o
i
d
j can be expressed as(11)
g
c
r
s
x
t
1
,
t
2
r
s
=
g
c
ivt
r
s
+
g
c
wat
r
,
l
+
g
c
trt
r
,
l
1
l
2
+
g
c
~
ody
r
,
l
,
a
r
,
s
∈
a
,
G
C
k
o
i
d
j
=
∑
(
r
,
s
)
∈
a
g
c
t
1
,
t
2
r
s
*
δ
r
s
,
k
o
i
d
j
,
G
C
k
o
i
d
j
=
∞
,
if
t
∉
Δ
t
.


### 3.2. Flow Conservation in SE Network

Passenger flows on temporal arcs which satisfy the following constraints. For each O-D pairo
i
d
j, the trip demand q
o
i
d
j can be split into all effective temporal paths as(12)
q
o
i
d
j
=
∑
l
k
∈
L
t
list
v
k
o
i
d
j
,where v
k
o
i
d
j denotes the passenger flows assign to the path l
k of each o
i
d
j.Each temporal arca
(
r
,
s
) should satisfy the flow conservation of each specific temporal path as (13)
v
r
s
=
∑
a
(
r
,
s
)
∈
a
∑
l
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
,where v
r
s denotes the passenger flows assign to a
(
r
,
s
).Furthermore, temporal arcs flow should satisfy the capacity constraint where would not be an overload in the rail transit train to which the temporal section arcsa
(
r
,
s
) belong:(14)
v
r
s
≤
K
r
s
,
l
,where K
r
s
,
l denotes the capacity a
(
r
,
s
) of in line l.


### 3.3. SUE Assignment Model Formulation

By using the schedule expanded network, the temporal and spatial variation of passengers’ trip would be represented by the temporal path in network. The temporal paths in the network are associated with time and space. Hence, the dynamic rail transit assignment can be transformed into static transit assignment problem.According to the definition, a stochastic user equilibrium (SUE) is achieved in a schedule-based transit network when the allocation of passengers between alternative paths conforms to the following logit model:(15)
In
⁡
f
k
o
i
d
j
f
k
′
o
i
d
j
=
-
θ
G
C
k
o
i
d
j
-
G
C
k
′
o
i
d
j
,where k and k
′ are the alternative temporal paths l
k and l
k
′ associated with the same O-D pair o
i
d
j and θ
>
0 is a given parameter which is used to measure the different degree of passengers’ knowledge about state of the paths in the network. The parameter θ will increase when passengers are more familiar with the schedule and travel time cost of the network. As θ
→
∞, the SUE approximately is equal to that of user equilibrium (UE).Based on (11) and (15), we have(16)
In
⁡
f
k
o
i
d
j
f
k
′
o
i
d
j
=
-
θ
(
g
c
t
1
,
t
2
k
-
g
c
t
1
,
t
2
k
′
)
+
(
g
c
t
1
,
t
2
k
,
l
-
g
c
t
1
,
t
2
k
′
,
l
)
+
g
c
t
1
,
t
2
k
,
l
1
l
2
-
g
c
t
1
,
t
2
k
′
,
l
1
l
2
+
g
c
~
t
1
,
t
2
k
,
l
-
g
c
~
t
1
,
t
2
k
′
,
l
.As the total travel demands increase, the proportionate distribution of passenger flow between the two paths remains the same until one or more temporal arcs on either path are saturated. Ifv
r
s
=
K
r
s
,
l, further increase in total travel demands would cause congestion on paths, leading to the increase overload delay, which will affect the path choice. And the crowding penalty and the overload delay are the equilibrium mechanism of logit-based assignment model in this paper.The SUE assignment problem of the SE network will be formulated as follows:(17)
P
1
:
min
⁡
Z
=
∑
(
r
,
s
)
∈
a
∫
0
v
r
s
g
c
r
s
(
x
)
d
x
+
1
θ
∑
a
r
,
s
∈
k
∑
k
∈
L
list
v
k
o
i
d
j
*
In
⁡
v
k
o
i
d
j
,
(18)
s
.
t
.
q
o
i
d
j
=
∑
k
∈
L
t
list
v
k
o
i
d
j
,
(19)
v
r
s
=
∑
a
r
,
s
∈
a
∑
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
,
(20)
v
r
s
≤
K
r
s
,
l
,
(21)
v
k
o
i
d
j
≥
0
,
(22)
∀
a
r
,
s
∈
a
,
k
∈
L
t
list
.The equivalence and uniqueness of the model have been proved in study (6). By constructing theLagrangian function for problemP1, theKuhn-Tucker conditions ofP1 can be given as follows:(23)
In
⁡
v
k
o
i
d
j
+
θ
*
∑
r
,
s
∈
a
(
g
c
r
s
*
δ
r
s
,
k
o
i
d
j
-
m
r
s
,
k
o
i
d
j
)
-
l
o
i
d
j
=
0
,where m
r
s
,
k
o
i
d
j and l
o
i
d
j are the correspondingLagrangian multiplier to (19) and (20). Equation (17) can be easily transformed into the following logit-based model, which is the kth path probability of path l
k in L
t
list:(24)
p
k
o
i
d
j
=
exp
⁡
(
-
θ
G
C
k
o
i
d
j
+
m
k
o
i
d
j
)
∑
i
∈
L
t
list
exp
⁡
(
-
θ
G
C
i
o
i
d
j
+
m
k
o
i
d
j
)
,where m
k
o
i
d
j denotes the sum ofLagrangian multipliers m
r
s
,
k
o
i
d
j along path l
k in L
t
list.


### 3.4. Solution Procedures

If the capacity constraints are ignored, problemP1 becomes a standard SUE assignment on transit network. This paper developed an advanced method of successive averages (MSA) algorithm to solve problemP1 with capacity constraints.Rewrite (23) as(25)
v
k
o
i
d
j
=
In
⁡
-
θ
g
c
ivt
r
s
+
g
c
wat
r
,
l
+
g
c
trt
r
,
l
1
l
2
∏
a
(
r
,
s
)
∈
k
M
r
s
L
OD
,where L
OD
=
exp
⁡
(
l
o
i
d
j
) and M
r
s
=
exp
⁡
(
m
r
s
,
k
o
i
d
j
). M
r
s is the factor corresponding to overload delay and is to be determined at the arc a
(
r
,
s
)
∈
l
k. With the advanced MSA, a simple solution procedure is put forward to solve the problemP1 with the given O-D demands q
o
i
d
j within time interval Δ
t.Step 1 (network construction).
Calculate the temporal possible paths setL
list in the analytical network with SE network representation method for all O-D pairs o
i
d
j
∈
OD.Step 2 (initialization).
SetL
OD
n
=
1 and M
r
s
n
=
1 for each arc a
(
r
,
s
)
∈
l
k for ∀
o
i
d
j
∈
OD, and set iterations n
=
1.Step 3 (iteration).
Calculate ((26)-(27)) step by step until the convergent conditions are satisfied for each a
(
r
,
s
)
∈
k and o
i
d
j
∈
OD.
For eacha
(
r
,
s
)
∈
k, calculate the following equation:(26)
v
k
o
i
d
j
(
L
→
n
,
M
→
n
)
=
exp
⁡
(
-
θ
(
g
c
ivt
r
s
+
g
c
wat
r
,
l
+
g
c
trt
r
,
l
1
l
2
)
)
∏
a
(
r
,
s
)
∈
k
M
r
s
n
L
o
i
d
j
n
,
η
r
s
n
=
K
t
1
,
t
2
r
s
,
l
∑
o
i
d
j
∈
OD
∑
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
L
→
n
,
M
→
n
,
M
r
s
n
+
1
=
min
⁡
1
,
η
r
s
n
M
r
s
n
.
For eacho
i
d
j
∈
OD, calculate the following equation:(27)
η
o
i
d
j
n
=
q
o
i
d
j
∑
k
∈
L
list
b
o
i
d
j
,
k
v
k
o
i
d
j
L
→
n
,
M
→
n
,
L
o
i
d
j
n
+
1
=
η
o
i
d
j
n
L
o
i
d
j
n
.Then, n
=
n
+
1.
LetL
→
n and M
→
n be the sets of l
o
i
d
j and m
r
s
,
k
o
i
d
j. The superscript n denotes iterations, b
o
i
d
j
,
k denotes arc-demand incidence factor equal 1 if v
k
o
i
d
j
(
L
→
n
,
M
→
n
) loading in path l
k belongs to O-D demands q
o
i
d
j, else b
o
i
d
j
,
k
=
0.Step 4 (convergence and output results).
Calculate the gap function, ifG
(
n
)
=
∑
o
i
d
j
∈
OD
δ
r
s
,
k
o
i
d
j
(
v
k
o
i
d
j
,
n
+
1
-
v
k
o
i
d
j
,
n
)
2
/
∑
o
i
d
j
∈
OD
q
o
i
d
j
<
ε, then stop and ε is the presupposed gap factor. Then, output arcs flow and overload delay value.
For eacha
(
r
,
s
)
∈
k, calculate(28)
v
r
s
=
∑
a
(
r
,
s
)
∈
a
∑
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
,
n
(
L
→
n
,
M
→
n
)
,
m
r
s
,
k
o
i
d
j
=
-
ln
⁡
M
r
s
n
θ
β
3
.Else, back to Step 3.


## 3.1. Generalized Travel Time Cost in SE Network

The generalized travel time costg
c
r
s on arc (
r
,
s
) is subjected to a disutility that encompasses four weighted combination components: (i) in-vehicle travel time cost g
c
ivt
r
s; (ii) waiting time cost g
c
WAT
r
,
l; (iii) transfer time cost g
c
trt
r
,
l
1
l
2; (iv) passenger overload cost g
c
~
t
1
,
t
2
r
,
l. Denote β
1, β
2 by the weighting factors for waiting time and transfer time, respectively, and β
3 by the passenger overload delay in weighted time unit parameter. The generalized travel time cost g
c
r
s of the arc a
(
r
,
s
) can be expressed as (5)
g
c
r
s
=
g
c
ivt
r
s
+
g
c
WAT
r
,
l
+
g
c
trt
r
,
l
1
l
2
+
g
c
~
t
1
,
t
2
r
,
l
.Considering the components of the generalized travel time cost function in SE network, the components on the right side of the equation in a time intervalΔ
t may be described as follows.(i) If the number of passengers is large enough to make passengers discomfortable, the cost of the in-vehicle travel time, asT
IVT
r
s, may be amplified. When the number of the passengers is small, for example, less than the number of seats, it is not crowded in the train. Let ω
=
x
t
1
,
t
2
r
s
/
C
l denote trainload. With the trainload increasing, passengers may feel more discomfortable. We defined a piecewise function to describe the discomfort level with the passengers number increasing and the trainload in the temporal section arcs as(6)
f
c
(
x
t
1
,
t
2
r
s
)
=
1
;
x
t
1
,
t
2
r
s
C
l
≤
ω
0
,
1
+
ϕ
1
(
x
t
1
,
t
2
r
s
)
*
x
t
1
,
t
2
r
s
C
l
-
ω
0
,
ω
0
<
x
t
1
,
t
2
r
s
C
l
≤
ω
1
;
1
+
ϕ
1
(
ω
1
*
C
l
)
*
(
ω
1
-
ω
0
)
+
ϕ
1
(
x
t
1
,
t
2
r
s
)
*
(
x
t
1
,
t
2
r
s
C
l
-
ω
1
)
;
ω
1
<
x
t
1
,
t
2
r
s
C
l
;
ω
0
=
Z
l
C
l
,
ϕ
1
x
t
1
,
t
2
r
s
=
α
1
*
ω
γ
,
ω
=
x
t
1
,
t
2
r
s
C
l
,where Z
l denotes the seat number in the train and α
1 and γ are user-defined factors. The in-vehicle travel time cost in SE network is(7)
g
c
ivt
r
s
=
f
c
x
r
s
*
T
IVT
r
s
=
c
t
1
,
t
2
r
s
*
f
c
x
t
1
,
t
2
r
s
.(ii) According to train schedule, it is applicable to calculate the waiting time T
WAT
r
s by the subscripts of the temporal arc:(8)
g
c
WAT
r
,
l
=
β
1
*
T
WAT
r
s
=
β
1
*
c
t
1
,
t
2
r
,
l
.(iii) Transfer time includes two factors: the transfer times and the walking time T
TRT
r
s from one line transfer to the other line at a transfer station. That is because the transfer contains the process of “alighting-walking-boarding.” So the passengers have to change from one vehicle/train to another vehicle/line which will increase the passengers’ extra perceived costs. Letting σ denote the extra perceived cost factor which is affect by the transfer times, transfer time cost can be expressed as(9)
g
c
trt
r
,
l
1
l
2
=
β
2
*
T
TRT
r
s
+
σ
=
β
2
*
c
t
1
,
t
2
r
,
l
1
l
2
+
σ
.(iv) Passenger overload delay is the additional time that passengers spend on waiting for next train of temporal section arc due to the insufficient train capacity when they cannot board the first coming train of the temporal section. Let β
3 denote the passenger overload delay penalty factor and let m
r
s
,
k denote the overload delay of temporal arc (
r
,
s
) in path k:(10)
g
c
~
t
1
,
t
2
r
,
l
=
β
3
*
m
r
s
,
k
.Combined with the generalized travel time costg
c
r
s of the temporal arc a
(
r
,
s
) in temporal arcs list, the generalized travel time cost to reach at destination d
j from original o
i node G
C
k
o
i
d
j can be expressed as(11)
g
c
r
s
x
t
1
,
t
2
r
s
=
g
c
ivt
r
s
+
g
c
wat
r
,
l
+
g
c
trt
r
,
l
1
l
2
+
g
c
~
ody
r
,
l
,
a
r
,
s
∈
a
,
G
C
k
o
i
d
j
=
∑
(
r
,
s
)
∈
a
g
c
t
1
,
t
2
r
s
*
δ
r
s
,
k
o
i
d
j
,
G
C
k
o
i
d
j
=
∞
,
if
t
∉
Δ
t
.


## 3.2. Flow Conservation in SE Network

Passenger flows on temporal arcs which satisfy the following constraints. For each O-D pairo
i
d
j, the trip demand q
o
i
d
j can be split into all effective temporal paths as(12)
q
o
i
d
j
=
∑
l
k
∈
L
t
list
v
k
o
i
d
j
,where v
k
o
i
d
j denotes the passenger flows assign to the path l
k of each o
i
d
j.Each temporal arca
(
r
,
s
) should satisfy the flow conservation of each specific temporal path as (13)
v
r
s
=
∑
a
(
r
,
s
)
∈
a
∑
l
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
,where v
r
s denotes the passenger flows assign to a
(
r
,
s
).Furthermore, temporal arcs flow should satisfy the capacity constraint where would not be an overload in the rail transit train to which the temporal section arcsa
(
r
,
s
) belong:(14)
v
r
s
≤
K
r
s
,
l
,where K
r
s
,
l denotes the capacity a
(
r
,
s
) of in line l.


## 3.3. SUE Assignment Model Formulation

By using the schedule expanded network, the temporal and spatial variation of passengers’ trip would be represented by the temporal path in network. The temporal paths in the network are associated with time and space. Hence, the dynamic rail transit assignment can be transformed into static transit assignment problem.According to the definition, a stochastic user equilibrium (SUE) is achieved in a schedule-based transit network when the allocation of passengers between alternative paths conforms to the following logit model:(15)
In
⁡
f
k
o
i
d
j
f
k
′
o
i
d
j
=
-
θ
G
C
k
o
i
d
j
-
G
C
k
′
o
i
d
j
,where k and k
′ are the alternative temporal paths l
k and l
k
′ associated with the same O-D pair o
i
d
j and θ
>
0 is a given parameter which is used to measure the different degree of passengers’ knowledge about state of the paths in the network. The parameter θ will increase when passengers are more familiar with the schedule and travel time cost of the network. As θ
→
∞, the SUE approximately is equal to that of user equilibrium (UE).Based on (11) and (15), we have(16)
In
⁡
f
k
o
i
d
j
f
k
′
o
i
d
j
=
-
θ
(
g
c
t
1
,
t
2
k
-
g
c
t
1
,
t
2
k
′
)
+
(
g
c
t
1
,
t
2
k
,
l
-
g
c
t
1
,
t
2
k
′
,
l
)
+
g
c
t
1
,
t
2
k
,
l
1
l
2
-
g
c
t
1
,
t
2
k
′
,
l
1
l
2
+
g
c
~
t
1
,
t
2
k
,
l
-
g
c
~
t
1
,
t
2
k
′
,
l
.As the total travel demands increase, the proportionate distribution of passenger flow between the two paths remains the same until one or more temporal arcs on either path are saturated. Ifv
r
s
=
K
r
s
,
l, further increase in total travel demands would cause congestion on paths, leading to the increase overload delay, which will affect the path choice. And the crowding penalty and the overload delay are the equilibrium mechanism of logit-based assignment model in this paper.The SUE assignment problem of the SE network will be formulated as follows:(17)
P
1
:
min
⁡
Z
=
∑
(
r
,
s
)
∈
a
∫
0
v
r
s
g
c
r
s
(
x
)
d
x
+
1
θ
∑
a
r
,
s
∈
k
∑
k
∈
L
list
v
k
o
i
d
j
*
In
⁡
v
k
o
i
d
j
,
(18)
s
.
t
.
q
o
i
d
j
=
∑
k
∈
L
t
list
v
k
o
i
d
j
,
(19)
v
r
s
=
∑
a
r
,
s
∈
a
∑
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
,
(20)
v
r
s
≤
K
r
s
,
l
,
(21)
v
k
o
i
d
j
≥
0
,
(22)
∀
a
r
,
s
∈
a
,
k
∈
L
t
list
.The equivalence and uniqueness of the model have been proved in study (6). By constructing theLagrangian function for problemP1, theKuhn-Tucker conditions ofP1 can be given as follows:(23)
In
⁡
v
k
o
i
d
j
+
θ
*
∑
r
,
s
∈
a
(
g
c
r
s
*
δ
r
s
,
k
o
i
d
j
-
m
r
s
,
k
o
i
d
j
)
-
l
o
i
d
j
=
0
,where m
r
s
,
k
o
i
d
j and l
o
i
d
j are the correspondingLagrangian multiplier to (19) and (20). Equation (17) can be easily transformed into the following logit-based model, which is the kth path probability of path l
k in L
t
list:(24)
p
k
o
i
d
j
=
exp
⁡
(
-
θ
G
C
k
o
i
d
j
+
m
k
o
i
d
j
)
∑
i
∈
L
t
list
exp
⁡
(
-
θ
G
C
i
o
i
d
j
+
m
k
o
i
d
j
)
,where m
k
o
i
d
j denotes the sum ofLagrangian multipliers m
r
s
,
k
o
i
d
j along path l
k in L
t
list.


## 3.4. Solution Procedures

If the capacity constraints are ignored, problemP1 becomes a standard SUE assignment on transit network. This paper developed an advanced method of successive averages (MSA) algorithm to solve problemP1 with capacity constraints.Rewrite (23) as(25)
v
k
o
i
d
j
=
In
⁡
-
θ
g
c
ivt
r
s
+
g
c
wat
r
,
l
+
g
c
trt
r
,
l
1
l
2
∏
a
(
r
,
s
)
∈
k
M
r
s
L
OD
,where L
OD
=
exp
⁡
(
l
o
i
d
j
) and M
r
s
=
exp
⁡
(
m
r
s
,
k
o
i
d
j
). M
r
s is the factor corresponding to overload delay and is to be determined at the arc a
(
r
,
s
)
∈
l
k. With the advanced MSA, a simple solution procedure is put forward to solve the problemP1 with the given O-D demands q
o
i
d
j within time interval Δ
t.Step 1 (network construction).
Calculate the temporal possible paths setL
list in the analytical network with SE network representation method for all O-D pairs o
i
d
j
∈
OD.Step 2 (initialization).
SetL
OD
n
=
1 and M
r
s
n
=
1 for each arc a
(
r
,
s
)
∈
l
k for ∀
o
i
d
j
∈
OD, and set iterations n
=
1.Step 3 (iteration).
Calculate ((26)-(27)) step by step until the convergent conditions are satisfied for each a
(
r
,
s
)
∈
k and o
i
d
j
∈
OD.
For eacha
(
r
,
s
)
∈
k, calculate the following equation:(26)
v
k
o
i
d
j
(
L
→
n
,
M
→
n
)
=
exp
⁡
(
-
θ
(
g
c
ivt
r
s
+
g
c
wat
r
,
l
+
g
c
trt
r
,
l
1
l
2
)
)
∏
a
(
r
,
s
)
∈
k
M
r
s
n
L
o
i
d
j
n
,
η
r
s
n
=
K
t
1
,
t
2
r
s
,
l
∑
o
i
d
j
∈
OD
∑
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
L
→
n
,
M
→
n
,
M
r
s
n
+
1
=
min
⁡
1
,
η
r
s
n
M
r
s
n
.
For eacho
i
d
j
∈
OD, calculate the following equation:(27)
η
o
i
d
j
n
=
q
o
i
d
j
∑
k
∈
L
list
b
o
i
d
j
,
k
v
k
o
i
d
j
L
→
n
,
M
→
n
,
L
o
i
d
j
n
+
1
=
η
o
i
d
j
n
L
o
i
d
j
n
.Then, n
=
n
+
1.
LetL
→
n and M
→
n be the sets of l
o
i
d
j and m
r
s
,
k
o
i
d
j. The superscript n denotes iterations, b
o
i
d
j
,
k denotes arc-demand incidence factor equal 1 if v
k
o
i
d
j
(
L
→
n
,
M
→
n
) loading in path l
k belongs to O-D demands q
o
i
d
j, else b
o
i
d
j
,
k
=
0.Step 4 (convergence and output results).
Calculate the gap function, ifG
(
n
)
=
∑
o
i
d
j
∈
OD
δ
r
s
,
k
o
i
d
j
(
v
k
o
i
d
j
,
n
+
1
-
v
k
o
i
d
j
,
n
)
2
/
∑
o
i
d
j
∈
OD
q
o
i
d
j
<
ε, then stop and ε is the presupposed gap factor. Then, output arcs flow and overload delay value.
For eacha
(
r
,
s
)
∈
k, calculate(28)
v
r
s
=
∑
a
(
r
,
s
)
∈
a
∑
k
∈
L
t
list
δ
r
s
,
k
o
i
d
j
v
k
o
i
d
j
,
n
(
L
→
n
,
M
→
n
)
,
m
r
s
,
k
o
i
d
j
=
-
ln
⁡
M
r
s
n
θ
β
3
.Else, back to Step 3.


## 4. Numerical Example of Model Application in BURT Network

The proposed models and solution algorithm are used to apply to Beijing urban railway transit network for passenger flow distribution estimation. The network consists of 17 lines and 281 stations including 41 transfer stations, which is shown in Figure2. There are a total of 562 nodes, 624 running sections, and 90 transfer arcs in the topological network.Figure 2
Beijing urban rail transit network (April, 2014).In this study, the input data of the assignment model requires the train running schedules of each transit line, the transfer walking time of each transfer, and the train capacity of each line. Total O-D demands of this time period (7:00~9:00 a.m.) are 1095835 among 54468 O-D pairs. Parts of these data are from the website of Beijing Metro Company, Wikipedia of Beijing Subway, and Beijing Municipal Commission of Transport (BMCT); others are from the corresponding surveys. Parts of the input data are shown in Table2. Since the schedule data is a large table with over 40,000 records in data table, Table 2 only shows partial data.Table 2
Parts of the input data.
(a)
Train running schedule of transit lines (part of the data)
Train number
Station
Arrival time
Departure time
Line
Direction
410000
Fuxingmen
7:03:43
7:04:28
Line 1
Upstream
410002
Fuxingmen
7:05:48
7:06:33
Line 1
Upstream
410001
Fuxingmen
7:01:12
7:01:47
Line 1
Downstream
410003
Fuxingmen
7:03:17
7:04:02
Line 1
Downstream
420000
Xizhimen
7:00:15
7:01:15
Line 2
Upstream
420002
Xizhimen
7:02:15
7:03:15
Line 2
Upstream
420001
Xizhimen
7:01:34
7:02:34
Line 2
Downstream
420003
Xizhimen
7:03:34
7:04:34
Line 2
Downstream
⋮
(b)
Transfer walking time at different transfer station (parts of the data)
Transfer stations
Original line
Terminal line
Transfer walking time (/s)
Transfer stations
Original line
Terminal line
Transfer walking time (/s)
Xizhimen
Line 2
Line 4
164
Fuxingmen
Line 1
Line 2
394
Line 4
Line 2
209
Line 2
Line 1
150
Dongzhimen
Line 2
Line 13
358
Jianguomen
Line 1
Line 2
169
Line 13
Line 2
270
Line 2
Line 1
81
Xidan
Line 1
Line 4
235
Dongdan
Line 1
Line 5
275
Line 4
Line 1
360
Line 5
Line 1
323
Zhichunlu
Line 10
Line 13
241
Dongsi
Line 5
Line 6
357
Line 13
Line 10
225
Line 6
Line 5
339
National Library
Line 4
Line 9
166
Xuanwumen
Line 2
Line 4
166
Line 9
Line 4
45
Line 4
Line 2
619
Beitucheng
Line 8
Line 10
85
Guomao
Line 1
Line 10
309
Line 10
Line 8
90
Line 10
Line 1
322
Huoying
Line 8
Line 13
315
Shaoyaoju
Line 10
Line 13
211
Line 13
Line 8
215
Line 13
Line 10
207
Chongwenmen
Line 2
Line 5
238
Liuliqiao
Line 9
Line 10
80
Line 5
Line 2
392
Line 10
Line 9
103
Hujialou
Line 6
Line 10
142
Lishuiqiao
Line 5
Line 13
217
Line 10
Line 6
127
Line 13
Line 5
231
(c)
Train capacity of each line (persons per vehicle)
Lines
Line 1
Line 2
Line 4
Line 5
Line 6
Line 8
Capacity
1850
1850
1830
1840
2570
1980
Lines
Line 9
Line 10
Line 13
Line 14
Line 15
Capacity
1900
1900
1850
2570
1980
Lines
Changping line
Yizhuang line
Fangshan line
Daxing line
Batong Line
Airport express
Capacity
1900
1900
1900
1830
1900
448In order to verify the results of theP1 above, we select one day in April 2014 of the AFC system to obtain the O-D demands as presented above which is provided from the BMCT.Parameters are calibrated by SPSS statistically with the existing research data, which is shown in Table3. The assignment period is from 7:00 a.m. to 9:00 a.m. The network assignment is running on an AMD Core 16 quad, 8 Gb Ram server. The computing time is about 20 minutes.Table 3
The values of the parameter in the model.
Parameters
β
1
β
2
β
3
ε
α
1
γ
Values
1.5
2
1
0.1%
0.15
4
Parameters
σ
t
tor
t
wat,tor
d
1
d
2
N
Values
3.0
20
15
10%
5%
3Figure3 indicates the iterations of the MSA for θ
=
1. The gap function converges rapidly at the beginning and slowly after 80 iterations (0.637%), suggesting that the advanced MSA has good convergence property in large scale network calculation. In this study, the presupposed gap factor ε
=
0.1
%. The final gap function is 0.1%, which indicates that the assignment results are much close to the equilibrium results. Seeing that the gap function is less than 0.5% after iterating 92 times (0.49%) which is demonstrated in Figure 3, solution results with less than 0.5% gap function are expected to be acceptable in practice, which the iterations and calculating time can be reduced.Figure 3
Convergence characteristics forθ
=
1.The computation results are showed in Figure4 from 7:00 a.m. to 9:00 a.m., and the time interval is 30 minutes. In order to illustrate assignment results of passengers flow distribution in BURT network directly, this paper develops a system which outputs trainload of each section. Besides, this paper defines different color of the transit line sections to indicate the trainload which is shown in Figure 4. The colors are defined to be four degrees of trainload, where green indicates ω
≤
0.8, yellow indicates 0.8
<
ω
≤
1, orange indicates 1
<
ω
≤
1.2, and red indicates ω
>
1.2.Figure 4
Passenger flow distribution in BURT network 7:00–9:00 a.m., each figure displays one time interval of 30 minutes.
(a)
(b)To further analyze the computing results, we compare the computing flows distributing on sections of the lines with the survey data, which includes passenger flows and trainload during the same section in Figure5. It can be obviously seen that the average errors between computing and observed passenger flows are acceptable.Figure 5
Comparison of surveyed flows, computed flows, and capacity in transit sections.In addition, the parameter sensitivity test can be put forward to obtain full understanding of the proposal model. This study changes the parameterθ at a time with all the other parameters being fixed to estimate different assignment results by the assignment method. Figure 6 indicates the path choice probability deviation when taking different values of θ. Some resultant sections over delays are shown in Table 4 of the whole network for θ
=
0.1 to 20, and flows loading on some sections are shown in Figure 7 when θ takes different values.Table 4
Overload delays of transit sections for different values of the parameterθ.
Transit sections
Line
Overload delays of transit sections for different values ofθ (/s)
0.1
0.2
0.5
1
2
5
10
20
FXM-XD
1
74.25
83.55
89.01
106.25
113.83
119.02
137.15
151.38
ZSM-JST
2
15.07
18.92
22.12
24.38
25.72
26.84
28.43
34.53
CSK-XWM
4
22.22
28.21
31.90
34.61
38.12
41.73
43.03
46.84
HB-HN
5
150.61
165.12
172.53
178.7
189.3
197.8
201.3
206.4
HJL-DDQ
6
34.41
45.21
50.31
54.12
58.91
64.5
67.5
72.69
ATZX-BTC
8
36.3
47.21
53.36
57.56
63.35
69.3
71.4
85.4
BJXZ-JSBWG
9
94.95
120.8
136.91
148.85
164.28
180.22
186.21
203.15
BTC-JDM
10
72.79
92.97
104.28
113.29
124.45
136.91
140.84
153.95
GM-JTXZ
10
81.25
102.59
116.62
125.88
138.62
151.56
156.48
172.35
XEQ-SD
13
152.30
208.23
223.16
247.18
262.46
281.34
290.47
348.22Figure 6
Path choice probability deviation with different values ofθ.Figure 7
Impacts ofθ in assignment results of train running sections.(
1
) The vertical axis in Figure 6 represents the normalized value comparison to the path with the least generalized travel time cost. The horizontal axis in Figure 6 represents the choice probability deviation. A large value of θ means that passengers are more sensitive to the difference between the generalized travel costs of their paths. When the value of θ increases, subtle difference in the generalized cost between the alternative paths will lead to a huge probability deviation in the choice probability. Hence, the path choice probability deviation distribution curve is smooth with a small value of θ and steep with a large value of θ.(
2
) It can be seen in Table 4 that the overload delay of the whole network and the partial network would be increased with the increase of parameter θ. With the increase of parameter θ, the passengers would have more knowledge of the network with the paths, congestion status, and schedule or timetable in choosing the departure time and trains of temporal paths. As there is no other path with less generalized travel time cost, passengers would like to board the first coming train until full, which will increase congestion cost because passengers understand clearly that waiting for the next train may not reduce the total cost. And the assignment results have demonstrated the phenomenon that since each passenger has high degree of knowledge for network, they tend to choose the same path as they expected at the same time; however, this increases actual overload delay cost because of the capacity constraint.(
3
) As the parameter θ varies from 0.1 to 20, it can be seen that the assignment results change slightly in Figure 6 during 8:00 to 8:30 a.m. As presented above, a large value of θ means a full knowledge of the network, with a less perception generalized travel time cost function error, and the passengers tend to choose the optimal path with minimum perception cost. A small value of θ indicates that passengers would choose many paths including some high cost paths at the beginning of their travel randomly due to the limited understanding of the network. As the assignment results in different values of the parameter θ comparing with the surveyed flows, the value of θ is better to take the range of [
1,5
] while the average error is 10.1%~12.3% to the surveyed flows.


## 5. Conclusion

A SUE assignment model with capacity constraints has been described in this paper to estimate and predict the passenger flow temporal and spatial distribution in the rail transit network. An advanced MSA algorithm is presented to solute the assignment model which is incorporated with the stochastic effect of passengers’ choice behaviors, the schedule of transit system, capacity constraints of trains, and a large-scale rail transit network. By using schedule expanded network representation, the time-space dynamic assignment problem is formulated as a generalized cost model. Furthermore, this study considers some important factors of passengers, for example, passenger overload delay, which they determine to minimize in their path choice. Passenger overload delay is defined as unknown variables which are determined by the equilibrium mechanism and train capacity constraints with the arcs generalized cost function used in this study. Also this paper analyzes the equilibrium mechanism equivalent to the condition that the mathematical problem will be solved to the equilibrium passenger overload delay when the arcs reach their capacity level.The model provides an important idea to evaluate the performance of the rail transit system subjected to train running sections load. The numerical example in application of BURT network in this study demonstrates that this model can be used on practical large-scale network due to the rapid convergence (within 200 iterations) and reasonable precision (10.1%~12.3%) in practice. With further research of the parameter sensitivity, the results indicate that passengers with better knowledge of the network would result in more overload delay in their trips and cause various assignment results.As BURT network expanded rapidly, it has become a more and more critical task to scientifically estimate the passenger flow distribution in the network. For further research, the proposal model applied to BURT network will be extended with passenger behaviors, such as queuing choice and transfer station choice.



---

*Source: 940815-2015-03-30.xml*