# Stochastic User Equilibrium Assignment in Schedule-Based Transit Networks with Capacity Constraints

Authors: Wangtu Xu; Lixin Miao; Wei-Hua Lin
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

This paper proposes a stochastic user equilibrium (SUE) assignment model for a schedule-based transit network with  capacity constraint. We consider a situation in which passengers do not have the full knowledge about the condition of the network and select paths that minimize a generalized cost function encompassing five components: (1) ride time, which is composed of in-vehicle and waiting times, (2) overload delay, (3) fare, (4) transfer constraints, and (5) departure time difference. We split passenger demands among connections which are the space-time paths between OD pairs of the network. All transit vehicles have a fixed capacity and operate according to some preset timetables. When the capacity constraint of the transit line segment is reached, we show that the Lagrange multipliers of the mathematical programming problem are equivalent to the equilibrium passenger overload delay in the congested transit network. The proposed model can simultaneously predict how passengers choose their transit vehicles to minimize their travel costs and estimate the associated costs in a schedule-based congested transit network. A numerical example is used to illustrate the performance of the proposed model.


---

## Body

## 1. Introduction

Transit assignment is an approach used for predicting the way in which passengers choose routes traveling from origins to destinations. Much progress has been made in the past three decades [1], and the assignment model can be broadly divided into three types: transport system-based, frequency-based, and schedule-based.In a transport system-based network, the all-or-nothing assignment method in which passengers choose the quickest route without considering headways of line routes as well as timetables is adopted. The result provides an overview of the structure of travel demand for long-distance planning purposes. Generally, the transport system-based assignment procedure does not require any line frequencies or timetables as input data. The early transit assignment approaches such as Dial’s algorithm [2, 3] and the method by Fearnside and Draper [4] are also based on the transport system in a way similar to road traffic assignment.In a frequency-based network, each transit line is assumed to operate on a constant headway. The assignment procedure encompasses three steps: route search, route choice, and demand split. The first step searches for possible paths between all origin-destination (OD) pairs. The second step compares the individual routes and eliminates the unreasonable routes. Then the final step evaluates the remaining routes and assigns the trips of an OD matrix to these routes.During the route choice step, for at least some OD pairs, there are sections in a path with more than one parallel service offered and passengers can choose the one they perceive as the best, which leads to the common lines problem [5], often regarded as the most complex problem for transit assignment. De Cea et al. [6] proposed an alternative method of generating minimum cost routes, as well as the partial paths from different lines using a common route section with a nonlinear programming method. Following the ideas of Chriqui and Robillard [5], Spiess [7], Spiess and Florian [8] introduced a strategy for choosing an attractive route set of lines at boarding stop points. This idea was further extended by Wu et al. [9] who proposed the strategy-based asymmetric transit link cost function and the hyperpath concept. These models assumed no capacity limit for links of a network. Gendreau [10] was the first to formulate a general transit assignment with the capacity constraint, and following by Lam et al. [11], Cominetti and Correa [12] and Kurauchi et al. [13]. Lam et al. advanced a stochastic user equilibrium assignment model for congested transit networks with a solution algorithm that can simultaneously predict how passengers choose their optimal routes and estimate the total passenger travel cost [11]. Cominetti and Correa proposed a model based on the common lines paradigm, which was applied to general networks using a dynamic programming approach, and congestion was treated by means of a simplified bulk queue model [12]. Kurauchi et al. proposed a model in which passengers unable to board due to the capacity constraint were then routed through spill-links [13]. These algorithms considered the congestion situation by introducing a volume-dependent link cost function with the capacity constraint. Consequently the resulting equilibrium models could be solved by standard algorithms for convex minimization. Another important topic on frequency-based transit assignment is the common line problem based on the hyperpath approach. Nguyen et al. [14] investigated the application of a nested logit model to trip assignment on urban transit networks where every set of competitive transit lines is described by a hyperpath. Schmöcker [15] also employed the hyperpath concept to the transit assignment problem with the capacity constraint.In general, the frequency-based transit assignment algorithm assumes that the passenger demand is constant within the specified time period of interest. The transfer time is not explicitly calculated but to be estimated based on the headway of the transit vehicle. This means that the impact of timetable is not considered, and the waiting time is usually assumed to be equal to the half of the headway.On a schedule-based transit network, the assignment considers the exact timetable and therefore the procedure needs to model the spatial and temporal structure of travel demand. The resulting assignment would show explicitly the exact number of passengers apportioned to each scheduled vehicle. Recently, this method becomes more and more popular, Florian [16] firstly proposed a deterministic schedule-based transit assignment method and applied it to the EMME/2 software package, in which the weight factors and non-time-based cost elements in determining the optimal path were used to evaluate the feasibility of a path and its attractiveness, and the shortest path algorithm was employed to assign trips. Tong and Wong [17, 18] formulated a dynamic transit assignment model. In their model, passengers were assumed to travel on a path with minimum generalized costs. These algorithms could be applied over a period in which both passenger demands and vehicle headways are varying. Friedrich and Wekeck [19] constructed a transit path choice method using the branch and bound technique, which reduced further the computation time. Friedrich [20] made an extension of their algorithm from a single-day to a multiday situation, which allowed considering changes in supply and demand within the course of a multiday time period. Nielsen [21] developed a stochastic schedule-based transit assignment model considering the utility of different passengers and optimized the stochastic assignment model based on the method of successive averages (MSA) [22]. Nuzzolo also developed algorithms for the transit assignment problem [23, 24]. Xu et al. proposed the K-shortest path searching algorithm in a schedule-based transit network [25]. This algorithm could be used in the flow assignment when the time-space path is taking part in the flow split between the OD pair.  In all those algorithms developed, the attractive connection in a schedule-based network is not considered. Besides, the stochastic path choice behavior in the congested situation has not been studied.Previous studies involved in flow assignment methods in the schedule-based transit network are extremely limited, let alone the consideration of capacity constraint in a stochastic user equilibrium (SUE) transit assignment model.  In this paper, a schedule-based SUE transit assignment algorithm for a similar common line problem is presented. We consider the schedule-based transit network described in Friedrich and Wekeck [19]. In our work, however, we assume that passengers do not necessarily have full knowledge of the schedule of transit service.  A stochastic user equilibrium assignment method with the congested situation is proposed, which is an extension of the work by Lam et al. [11]. The latter considers the problem in the context of a frequency-based transit network. The purpose of this paper is to formulate a model to determine exactly the load of vehicle on a transit line at a given time period. Moreover, we examine whether the passenger volume on a transit line exceeds the designed capacity.This paper is organized as follows. In the next section, some useful concepts for a transit network are briefly reviewed. Notations and basic assumptions of the mathematical model are given. In Section3, the attractive connection set is defined. In Section 4, a generalized travel cost function is formulated to choose the best routes between OD pairs on the schedule-based transit network firstly. Then a SUE assignment model is proposed, as well as its solution algorithm. The numerical example of this model is presented in Section 5 to illustrate the validity of the algorithm. Conclusions are given in Section 6 as well as the direction for future research.


## 2. Concepts, Notations, and Basic Assumptions

### 2.1. Concepts

We provide here an overview of terms used in this paper such as line, line section, and line route before embarking on a discussion of the common lines problem and SUE transit assignment. We adopt the definitions of these terms from the previous work: definitions of the transit line, transit arc, and line segment from Lam et al. [11], definitions of route segment, connection and connection segment from Friedrich and Wekeck [19].A connection is a line that a passenger chooses to travel from his/her origin node to the destination node. In the schedule-based transit network, each connection is composed of origin node, destination node, walking link, transfer nodes, departure time, arrival time, in-vehicle time, transfer time, number of transfers, and the total travel time.A connection segment is a portion of a connection which describes a part of a journey and is also endowed with a departure and arrival time, and which is the building block of a connection. In this paper, the connection segments using access and egress walk links would not be considered.The example network (shown in Figure1) used by Friedrich and Wekeck [19] is adopted here to explain the definition of line (segment), line route (segment) and connection (segment). In this example, the given network consists of a bus line and a train line, passengers traveling from origin A-Village to destination X-City may choose between direct bus connections and faster bus-train connections.Figure 1
An example schedule-based transit network (Friedrich and Wekeck [19]).Since a transit line is characterized by an initial stop node, a terminal stop node, length and running time, the connection segments can be calculated from a set of line sections. For the example network given in Figure1, bus line 1 from node A-Village to station has three connection segments, that is, boarding and departing at node A-Village at 6:10, arriving at station at 6:22; or departing at 6:55, arriving at 7:07; or departing at 7:25 and arriving at 7:37. A given transit line with n stations would include n(n-1)/2 line sections and consequently include a total of k×n(n-1)/2 connection segments (where k is the total number of vehicle runs). The connections of the example transit network of Figure 1 are shown in Table 1.Table 1
Connections of example schedule-based transit network.
Connection ID
Passing stations
Departure time
Arrival time
In-vehicle  time
Transfer time
Total travel time
Number of transfers
c
1
A-S-B-X
6:10
6:55
45 min
0 min
45 min
0
c
2
A-S-B-X
6:55
7:40
45 min
0 min
45 min
0
c
3
A-S-B-X
7:25
8:10
45 min
0 min
45 min
0
c
4
A-S-X
6:10
6:41
28 min
3 min
31 min
1
c
5
A-S-X
7:25
8:01
28 min
8 min
36 min
1From the above example, we can conclude that in a schedule-based transit network a connection is a route path plus a series of time strategies, including the departure time, arrival time and transfer time. When an incoming bus is operating at its capacity level, passengers may choose not to board but opt to wait for the next one with successor connections. In this situation, we can call this attractive connection problem for a schedule-based transit network with capacity constraints. Namely, passengers choose their journey strategy at a station from an attractive connection set.


### 2.2. Notations

W:
Set of OD pairs
w:
An element of setW
g
w:
Passenger demand between OD pairw
C
w:
Set of attractive connections associated with OD pairw
c:
Index of connection
S:
Set of connection segments of the attractive connections
s:
Index of connection segment
v
c:
Passenger flow on connectionc
v
s:
Passenger flow on connection segments
d
c:
Passenger overload delay, that is, the time that passengers spend on waiting for vehicle of another connection segment when they cannot board the first coming vehicle of the first connection segment because of insufficient vehicle capacity
d
s:
Passenger overload delay on connection segments
t
t
c:
Travel time on connectionc
t
t
s:
Travel time on connection segments
d
t
c:
Departure time of connectionc
d
t
s:
Departure time of connection segments
d
t
E:
Expected departure time of a trip
a
t
c:
Arrival time of connectionc
a
t
s:
Arrival time of connection segments
g
c
c:
Generalized cost of connectionc
g
c
s:
Generalized cost of connection segments
I:
Analysis time span
t
c
w:
Waiting time on connectionc
t
s
w:
Waiting time on connection segments
t
c
v:
In-vehicle time on connectionc
t
s
v:
In-vehicle time on connection segments
t
c
d:
Riding time on connectionc
t
s
d:
Riding time on connection segments
t
c
n:
Number of transfers of connectionc
t
s
n:
Number of transfers of connection segments
T
B
-
(
+
):
The minimum (maximal) transfer wait timeTB-
d
c:
Passenger overload delay on connectionc
d
s:
Passenger overload delay on connection segments
Y
c:
Monetary cost of connectionc
Y
s:
Monetary cost of connection segments
ξ
s
(
c
)
I:
A nonnegative function ofdist(dts(c),dtE), which represents the functions of difference between the real departure time dts/c and the expected departure time dtE
ca
p
v
-
s
l:
The vehicle capacity of transit linel
δ
c
w:
0-1 variable, if connectionc connects between OD pair w, it equals to 1 and otherwise 0.
δ
s
,
c
w:
0-1 variable, it equals to 1 if connectionc associating OD pair w consists of connection segment s, and 0 otherwise.


### 2.3. Basic Assumptions

Assume that (a) the transit service considered has a schedule but passengers do not know exactly the schedule. The service behaves as if it was frequency based, (b) the OD demand is fixed, at any given time interval (e.g., the peak hour), and (c) all vehicles strictly operate under the sequence defined by the timetable without overtaking each other. (d) Other assumptions are drawn as Lam et al. [11].


## 2.1. Concepts

We provide here an overview of terms used in this paper such as line, line section, and line route before embarking on a discussion of the common lines problem and SUE transit assignment. We adopt the definitions of these terms from the previous work: definitions of the transit line, transit arc, and line segment from Lam et al. [11], definitions of route segment, connection and connection segment from Friedrich and Wekeck [19].A connection is a line that a passenger chooses to travel from his/her origin node to the destination node. In the schedule-based transit network, each connection is composed of origin node, destination node, walking link, transfer nodes, departure time, arrival time, in-vehicle time, transfer time, number of transfers, and the total travel time.A connection segment is a portion of a connection which describes a part of a journey and is also endowed with a departure and arrival time, and which is the building block of a connection. In this paper, the connection segments using access and egress walk links would not be considered.The example network (shown in Figure1) used by Friedrich and Wekeck [19] is adopted here to explain the definition of line (segment), line route (segment) and connection (segment). In this example, the given network consists of a bus line and a train line, passengers traveling from origin A-Village to destination X-City may choose between direct bus connections and faster bus-train connections.Figure 1
An example schedule-based transit network (Friedrich and Wekeck [19]).Since a transit line is characterized by an initial stop node, a terminal stop node, length and running time, the connection segments can be calculated from a set of line sections. For the example network given in Figure1, bus line 1 from node A-Village to station has three connection segments, that is, boarding and departing at node A-Village at 6:10, arriving at station at 6:22; or departing at 6:55, arriving at 7:07; or departing at 7:25 and arriving at 7:37. A given transit line with n stations would include n(n-1)/2 line sections and consequently include a total of k×n(n-1)/2 connection segments (where k is the total number of vehicle runs). The connections of the example transit network of Figure 1 are shown in Table 1.Table 1
Connections of example schedule-based transit network.
Connection ID
Passing stations
Departure time
Arrival time
In-vehicle  time
Transfer time
Total travel time
Number of transfers
c
1
A-S-B-X
6:10
6:55
45 min
0 min
45 min
0
c
2
A-S-B-X
6:55
7:40
45 min
0 min
45 min
0
c
3
A-S-B-X
7:25
8:10
45 min
0 min
45 min
0
c
4
A-S-X
6:10
6:41
28 min
3 min
31 min
1
c
5
A-S-X
7:25
8:01
28 min
8 min
36 min
1From the above example, we can conclude that in a schedule-based transit network a connection is a route path plus a series of time strategies, including the departure time, arrival time and transfer time. When an incoming bus is operating at its capacity level, passengers may choose not to board but opt to wait for the next one with successor connections. In this situation, we can call this attractive connection problem for a schedule-based transit network with capacity constraints. Namely, passengers choose their journey strategy at a station from an attractive connection set.


## 2.2. Notations

W:
Set of OD pairs
w:
An element of setW
g
w:
Passenger demand between OD pairw
C
w:
Set of attractive connections associated with OD pairw
c:
Index of connection
S:
Set of connection segments of the attractive connections
s:
Index of connection segment
v
c:
Passenger flow on connectionc
v
s:
Passenger flow on connection segments
d
c:
Passenger overload delay, that is, the time that passengers spend on waiting for vehicle of another connection segment when they cannot board the first coming vehicle of the first connection segment because of insufficient vehicle capacity
d
s:
Passenger overload delay on connection segments
t
t
c:
Travel time on connectionc
t
t
s:
Travel time on connection segments
d
t
c:
Departure time of connectionc
d
t
s:
Departure time of connection segments
d
t
E:
Expected departure time of a trip
a
t
c:
Arrival time of connectionc
a
t
s:
Arrival time of connection segments
g
c
c:
Generalized cost of connectionc
g
c
s:
Generalized cost of connection segments
I:
Analysis time span
t
c
w:
Waiting time on connectionc
t
s
w:
Waiting time on connection segments
t
c
v:
In-vehicle time on connectionc
t
s
v:
In-vehicle time on connection segments
t
c
d:
Riding time on connectionc
t
s
d:
Riding time on connection segments
t
c
n:
Number of transfers of connectionc
t
s
n:
Number of transfers of connection segments
T
B
-
(
+
):
The minimum (maximal) transfer wait timeTB-
d
c:
Passenger overload delay on connectionc
d
s:
Passenger overload delay on connection segments
Y
c:
Monetary cost of connectionc
Y
s:
Monetary cost of connection segments
ξ
s
(
c
)
I:
A nonnegative function ofdist(dts(c),dtE), which represents the functions of difference between the real departure time dts/c and the expected departure time dtE
ca
p
v
-
s
l:
The vehicle capacity of transit linel
δ
c
w:
0-1 variable, if connectionc connects between OD pair w, it equals to 1 and otherwise 0.
δ
s
,
c
w:
0-1 variable, it equals to 1 if connectionc associating OD pair w consists of connection segment s, and 0 otherwise.


## 2.3. Basic Assumptions

Assume that (a) the transit service considered has a schedule but passengers do not know exactly the schedule. The service behaves as if it was frequency based, (b) the OD demand is fixed, at any given time interval (e.g., the peak hour), and (c) all vehicles strictly operate under the sequence defined by the timetable without overtaking each other. (d) Other assumptions are drawn as Lam et al. [11].


## 3. The Attractive Connection Set

De Cea and Fernandez [26] indicated that in a congested transit network, there exists more than one type of route segments between a given pair of nodes representing the set of desirable lines. However, in a schedule-based network, there would also be more than one type of connection segments which would result in an attractive connection set as described above. Different from the determination of different classes of route types of uncongested network by solving the hyperbolic common lines problem [26], an important process needs to be emphasized to determine the most attractive connection set. This will be discussed as follows.According to the timetable, the frequency of a transit vehicle is fixed. Assume that the preceding vehicle would not be overrun, the set of attractive connections based on some specific rules could be determined.  The algorithm used by Friedrich and Wekeck [19] is employed to build a connection tree. Every connection segment s is described by departure time dts and arrival time ats, travel time tts, cost costs, and number of transfer tsn. If connection c is made up of n connection segments, the number of its transfers is n-1. As shown in Figure 2 [19], let s be the current processed connection segment from station B to station C, let c* be the new connection between the original station A and station C formed by adding s to some connection c arriving at B, finally let CS-C be the set of all known connections to stop C. Connection segment s is inserted into the tree as an successor of c, if and only if the following conditions hold.Figure 2
Structure of connection.(1)
Temporal suitability: The connection segments departs from node B only after the arrival of connection c plus a minimum transfer wait time TB-, and before the maximum transfer wait time TB+ has elapsed, namely.
(3.1)dts-atc∈[TB-,TB+].
(2)
Dominance: there is no known connectionc'∈CS-C, such that
(3.2)dtc'≥dtc*,atc′≤atc*,gcc′≤gcc*,tc′n≤tc*n.
(3)
Tolerance constraints: none of the following rules are violated:(3.3)gcc*≤b1×min{gcc′,∀c′∈CS-C}+b2,tc*n≤d1×min{tc′n,∀c′∈CS-C}+d2ttc*≤φ1×min{ttc′,∀c′∈CS-C}+φ2,tc*n≤N+,where  bi,  di,  φi are user-defined global tolerance parameters, and N+ is the user-defined bound for the number of transfers within a connection.Using this approach which is the same as the branch and bound algorithm, we can determine all connections between any two nodes of the network. For a given OD pair (or any two nodes), we can then determine the attractive connection set according to some attributes of connection, for instance, the number of transfers or the departure time. As an example, we can set the attractive connection setCS-C from node A to node C in Figure 2 as all connections of which the departure times are earlier than 8:00, or, all the connections of which the number of transfers do not exceed 3.


## 4. SUE Assignment Model for Schedule-Based Transit Network with Capacity Constraints

### 4.1. Generalized Travel Time Cost Function of a Connection

Waiting at a transit station can be described as a process like this: at a given time intervalI, consider a passenger heading towards the destination, whose original node is r and terminal node t. To exit from r he/she can use the connection segment sto reach the next station j. The decision faced at station r is determined via the generalized cost gcs(vs) corresponding to the services operating on the connection segment s such that
(4.1)gcs(vs)=αtsW+βtsV+φtsn+γds+ρξsI+ϖYs=dtsd+φtsn+γds+ρξsI+ϖYs,
where, parameters α=β=d and φ are user-defined factors. γ, ρ, ϖ are the conversion factors of time value.The cost to reach at the destination using connectionc can be determined as follows:
(4.2)gcc=∞ifdtc,atc∉Igcc=∑∀s∈Sδs,cwgcsotherwise.∀c∈Cw


### 4.2. Flow Conservation in a Congested Network

Passenger flows on connections which satisfy the following constraints. For each OD pairw, its trip demand gw can be split into all possible attractive connections as
(4.3)gw=∑c∈Cwvc.Each connection segments should satisfy the flow conservation of each specific connection c, that is
(4.4)vs=∑w∈W∑c∈Cwδs,cwvc.Furthermore, connection flow should satisfy the capacity constraint so that there would not be an overload in the transit vehicle to which connection segments belongs
(4.5)vs≤capv-sl.


### 4.3. SUE Assignment Model Formulation

Definition 4.1.
A SUE is achieved in a schedule-based transit network with capacity constraints when the allocation of passengers between alternative connections conforms to the following logit model:(4.6)-θ(gcc-gcc′)=ln(vcvc′)∀c∈Cw,
where c and c' are the alternative connections associated with the same OD pair w, and θ>0 is a given parameter used to measure the degree of passengers' knowledge about the travel cost on a specific connection. In general, the corresponding θ value for schedule-based network would be smaller than the transportation system based or frequency-based transit system. As θ→∞, the result of SUE approximates that of user equilibrium (UE).Based on (4.1) and (4.6), we have
(4.7)ln(vcvc′)=-θ(gcc-gcc′)=-θ[d(tcd-tc′d)+φ(tcn-tc′n)+γ(dc-dc′)+ρ(ξcI-ξc′I)+ϖ(Yc-Yc′)].As the total demand increases, the proportionate distribution of passenger flow between the two connections remains the same until one or more segments on either connection are overloaded.We formulate the SUE assignment problem as follows:(4.8a)(NP1)minz=∑s∈S∫0vsgcs(x)dx+1θ∑w∈W∑c∈Cwvclnvc,S.t.(4.8b)gw=∑c∈Cwvc,(4.8c)vs=∑w∈W∑c∈Cwδs,cwvc,(4.8d)vs≤capv-sl,(4.8e)vc≥0,w∈W,c∈Cw.The Lagrangian function for NP1 can be formulated by(4.9)L=∑s∈S∫0vsgcs(x)dx+1θ∑w∈W∑c∈Cwvclnvc+χw(gw-∑c∈Cwvc)+εs(vs-capv-sl)-μcwvc.The Kuhn-Tucker conditions for problem NP1 can be formulated as follows:(4.10)1θ(lnvc+1)+∑s∈Sδs,cw·gcs(vs)-χw+εc-μcw=0,(4.11)-μcwvc=0,
where  χw,  εc  and  μcw are the corresponding Lagrangian multipliers to (4.8b)–(4.8d).We have that ifvc>0 then  μcw=0; gcc=∑s∈Sδs,cw·gcs(vs)forallc∈Cw, so that we can easily formulate the following logit model for the connection flow split between OD pair w:
(4.12)vc=gwexp(-θ·gcc+εc)∑k∈Cwexp(-θ·gck+εk)For each connection segment,εs=-θγds is a condition for SUE transit assignment with bottlenecks. If θ is very large, the second term of the objective function of problem NP1 will become insignificant and hence this is an approximation to the UE problem.


### 4.4. Solution Algorithm for SUE Assignment Problem

There are several solution algorithms for the standard SUE assignment problem, such as the method of successive averages [27], the partial convex combination method [28], and the iterative balancing and convex combination method [29]. The SUE assignment problem with capacity constraints like NP1, however, cannot apply these approaches directly. Bell proposed an advanced method of successive average to solve a SUE road traffic assignment problem [30], which was adopted by Lam et al. [11] to solve the transit assignment problem like NP1 with bottlenecks. Based on the solution method of Lam et al. [11], we designed a method to solve the SUE assignment problem for schedule-based transit network.Rewrite (4.10) as
(4.13)vc=exp(-θ(gcc+χw-εc+1θ))=exp(-θ·gcc)∏s∈cEsMw,
where connection c connects OD pair w, Mw=exp(χw+1/θ), while factor Es=exp(-εs), a simple procedure is proposed to solve the SUE transit assignment problem NP1 with given OD flows at time interval I.Step 1.
n
=
1. Calculate an attractive connection set, and corresponding s∈S for all OD pairs w∈W according to the algorithm mentioned in the previous Section. Set Es(n)=1 for each s∈S, and Mw(n)=1 for w∈W.Step 2.
n
=
2. If the convergence condition is satisfied, then stop; otherwise, for each s∈S, calculate
(4.14)vc(E(n),M(n))=exp(-θ·gcc)∏s∈cEs(n)Mw(n),βs(n)=capv-sl∑w∈W∑c∈Cwδs,cwvc(Es(n),Mw(n)),Es(n+1)=min[1,βs(n)Es(n)].
For each w∈W, set
(4.15)βw(n)=gw∑c∈Cwδcwvc(E(n),M(n)),Mw(n+1)=βw(n)Mw(n).Step 3.
n
=
n
+
1, back to Step 2.Step 4.
For eachc∈Cw, calculate
(4.16)vc(n)=v(E(n),M(n)).For eachs∈S, calculate vs(n)=∑w∈W∑c∈Cwδs,cwvc(n), ds=-(lnEs)/γθ.For eachc∈Cw, calculate dc=∑s∈c-(lnEs)/γθ.Step 5.
For all OD pairs, if the gap functionG(n)=∑w∈W∑c∈Cwδs,cw|vc(n+1)-vc(n)|/∑w∈Wgw<ς, then stop. (where  ς is an user-defined parameter).


## 4.1. Generalized Travel Time Cost Function of a Connection

Waiting at a transit station can be described as a process like this: at a given time intervalI, consider a passenger heading towards the destination, whose original node is r and terminal node t. To exit from r he/she can use the connection segment sto reach the next station j. The decision faced at station r is determined via the generalized cost gcs(vs) corresponding to the services operating on the connection segment s such that
(4.1)gcs(vs)=αtsW+βtsV+φtsn+γds+ρξsI+ϖYs=dtsd+φtsn+γds+ρξsI+ϖYs,
where, parameters α=β=d and φ are user-defined factors. γ, ρ, ϖ are the conversion factors of time value.The cost to reach at the destination using connectionc can be determined as follows:
(4.2)gcc=∞ifdtc,atc∉Igcc=∑∀s∈Sδs,cwgcsotherwise.∀c∈Cw


## 4.2. Flow Conservation in a Congested Network

Passenger flows on connections which satisfy the following constraints. For each OD pairw, its trip demand gw can be split into all possible attractive connections as
(4.3)gw=∑c∈Cwvc.Each connection segments should satisfy the flow conservation of each specific connection c, that is
(4.4)vs=∑w∈W∑c∈Cwδs,cwvc.Furthermore, connection flow should satisfy the capacity constraint so that there would not be an overload in the transit vehicle to which connection segments belongs
(4.5)vs≤capv-sl.


## 4.3. SUE Assignment Model Formulation

Definition 4.1.
A SUE is achieved in a schedule-based transit network with capacity constraints when the allocation of passengers between alternative connections conforms to the following logit model:(4.6)-θ(gcc-gcc′)=ln(vcvc′)∀c∈Cw,
where c and c' are the alternative connections associated with the same OD pair w, and θ>0 is a given parameter used to measure the degree of passengers' knowledge about the travel cost on a specific connection. In general, the corresponding θ value for schedule-based network would be smaller than the transportation system based or frequency-based transit system. As θ→∞, the result of SUE approximates that of user equilibrium (UE).Based on (4.1) and (4.6), we have
(4.7)ln(vcvc′)=-θ(gcc-gcc′)=-θ[d(tcd-tc′d)+φ(tcn-tc′n)+γ(dc-dc′)+ρ(ξcI-ξc′I)+ϖ(Yc-Yc′)].As the total demand increases, the proportionate distribution of passenger flow between the two connections remains the same until one or more segments on either connection are overloaded.We formulate the SUE assignment problem as follows:(4.8a)(NP1)minz=∑s∈S∫0vsgcs(x)dx+1θ∑w∈W∑c∈Cwvclnvc,S.t.(4.8b)gw=∑c∈Cwvc,(4.8c)vs=∑w∈W∑c∈Cwδs,cwvc,(4.8d)vs≤capv-sl,(4.8e)vc≥0,w∈W,c∈Cw.The Lagrangian function for NP1 can be formulated by(4.9)L=∑s∈S∫0vsgcs(x)dx+1θ∑w∈W∑c∈Cwvclnvc+χw(gw-∑c∈Cwvc)+εs(vs-capv-sl)-μcwvc.The Kuhn-Tucker conditions for problem NP1 can be formulated as follows:(4.10)1θ(lnvc+1)+∑s∈Sδs,cw·gcs(vs)-χw+εc-μcw=0,(4.11)-μcwvc=0,
where  χw,  εc  and  μcw are the corresponding Lagrangian multipliers to (4.8b)–(4.8d).We have that ifvc>0 then  μcw=0; gcc=∑s∈Sδs,cw·gcs(vs)forallc∈Cw, so that we can easily formulate the following logit model for the connection flow split between OD pair w:
(4.12)vc=gwexp(-θ·gcc+εc)∑k∈Cwexp(-θ·gck+εk)For each connection segment,εs=-θγds is a condition for SUE transit assignment with bottlenecks. If θ is very large, the second term of the objective function of problem NP1 will become insignificant and hence this is an approximation to the UE problem.


## 4.4. Solution Algorithm for SUE Assignment Problem

There are several solution algorithms for the standard SUE assignment problem, such as the method of successive averages [27], the partial convex combination method [28], and the iterative balancing and convex combination method [29]. The SUE assignment problem with capacity constraints like NP1, however, cannot apply these approaches directly. Bell proposed an advanced method of successive average to solve a SUE road traffic assignment problem [30], which was adopted by Lam et al. [11] to solve the transit assignment problem like NP1 with bottlenecks. Based on the solution method of Lam et al. [11], we designed a method to solve the SUE assignment problem for schedule-based transit network.Rewrite (4.10) as
(4.13)vc=exp(-θ(gcc+χw-εc+1θ))=exp(-θ·gcc)∏s∈cEsMw,
where connection c connects OD pair w, Mw=exp(χw+1/θ), while factor Es=exp(-εs), a simple procedure is proposed to solve the SUE transit assignment problem NP1 with given OD flows at time interval I.Step 1.
n
=
1. Calculate an attractive connection set, and corresponding s∈S for all OD pairs w∈W according to the algorithm mentioned in the previous Section. Set Es(n)=1 for each s∈S, and Mw(n)=1 for w∈W.Step 2.
n
=
2. If the convergence condition is satisfied, then stop; otherwise, for each s∈S, calculate
(4.14)vc(E(n),M(n))=exp(-θ·gcc)∏s∈cEs(n)Mw(n),βs(n)=capv-sl∑w∈W∑c∈Cwδs,cwvc(Es(n),Mw(n)),Es(n+1)=min[1,βs(n)Es(n)].
For each w∈W, set
(4.15)βw(n)=gw∑c∈Cwδcwvc(E(n),M(n)),Mw(n+1)=βw(n)Mw(n).Step 3.
n
=
n
+
1, back to Step 2.Step 4.
For eachc∈Cw, calculate
(4.16)vc(n)=v(E(n),M(n)).For eachs∈S, calculate vs(n)=∑w∈W∑c∈Cwδs,cwvc(n), ds=-(lnEs)/γθ.For eachc∈Cw, calculate dc=∑s∈c-(lnEs)/γθ.Step 5.
For all OD pairs, if the gap functionG(n)=∑w∈W∑c∈Cwδs,cw|vc(n+1)-vc(n)|/∑w∈Wgw<ς, then stop. (where  ς is an user-defined parameter).


## 5. Numerical Example

We test the NP1 problem with the example network shown in Figure1. Let the capacity of bus line 1 be 200 persons/vehicle and the capacity of the train line 600 persons/train. Let fare of Bus 1 be 1.00 Rmb, and fare of Train be 3.00 Rmb. The OD demand between A-Village and X-City is 450 persons. The parameters for calculating the generalized cost of connections: d=1.0; φ=0.5; ρ=1.0; ϖ=0.1; ξcI=(dtc-dtE)2/2; dtE=6:10. Let the allowed maximum waiting time be 15 min and the maximum total number of transfers N+ = 2 and other parameters the same as [19] and all other user-defined parameters are set equal to 1.0 to calculate the attractive connection set between the OD pair from A-Village to X-City. The convergence tolerance gap is set equal to 0.01.The assignment was run on a PIIII/3.0 MHz, 1 GB Ram computer. The computation time is approximately 1 min. Figure3 illustrates that for θ=1.0, the gap function converges very rapidly in the beginning and shows small fluctuation after 10 iterations. The MSA algorithm converges very rapidly. Moreover, the final gap function of the converged solution is less than 0.1%, which indicates that the solution is sufficiently close to the equilibrium solution. On the other hand, Figure 4 illustrates that the flows assigned to the five connections have small fluctuations after 70 iterations, suggesting the good convergence property of this MSA algorithm. Each connection has got an excellent flow solution for the overload delay.Figure 3
Convergence characteristics of assigned flow forθ=1.0.Figure 4
Assigned flows the five connections forθ=1.0.The resultant connection flows and their overload delays withγ=1.0 are shown in Tables 2 and 3 for θ=0.1, 1.0, 2.0, and 5.0.Table 2
The resultant connection flows for variousθ in comparison with UE result, in persons.
θ
Connections
c
1
c
2
c
3
c
4
c
5
0.1
94.57
93.10
89.30
89.35
83.68
1.0
124.47
127.24
83.88
70.62
43.79
2.0
147.82
163.93
71.24
47.59
19.42
5.0
176.17
190.13
50.00
23.83
9.87
UE
200.00
200.00
50.00
0.00
0.00Table 3
The resultant connection overload delay for variousθ, in minute.
θ
Connections
c
1
c
2
c
3
c
4
c
5
0.1
0.00
0.00
0.00
0.00
0.00
1.0
24.15
0.00
0.00
9.15
0.00
2.0
32.32
2.21
0.00
17.32
0.00
5.0
33.43
5.32
0.00
26.06
0.00It can be seen in Table2 that, with capacity constraints, the total flow of c1 and c4 could not exceed the vehicle capacity, 200 persons, because these two connections use the same vehicle of bus line 1, which departs at 6:10, visits station at 6:22, and then arrives at X-city at 6:55. The same thing happens among c2 and Con5. The flow of c1 increases as θ increases. For the uncongested connection, the flow for c5 decreases as θ increases because the passenger perceived a reduced travel cost. For congested connections, in spite of the capacity deficiency, their flows still increase, in other words, in the situation of vehicle capacity deficiency, people would still get on the congested vehicles even though they know the routes and the vehicle schedule clearly. The reason might be, they know clearly that waiting for the successor connection would not be able to reduce the total cost anyway. Consequently, they would rather catch the first incoming vehicle until its capacity runs out. When θ=5.0, the stochastic connection flows are close to that of UE pattern.It can be seen in Table3 that the overload delay of congested connection (c1~c4) would increase with the increase of θ. This is because passengers have more information about the route and the vehicle schedule and are thus clear that there would be no way to find another connection with smaller cost between origin and destination. As a result everyone would get on the first arriving bus until it becomes full, which would result in an increase in congestion delay.For variousθ, the passenger behaviour embodied in choosing the departure time, and the connection is shown in Figure 5. We can clearly see that for θ=0.1, passengers have limited information about the network condition, so that they would choose their departure time evenly. On the other hand, when they have more knowledge about the connections and the schedule, they would choose the connection vehicle which would result in a smaller total cost. For instance, less passengers would choose to board the vehicle of this connection (c5) if they know more (increase of θ) about the schedule at time interval 7:25~8:01.Figure 5
Passenger behaviour in choosing the departure time and the connection for variousθ.


## 6. Conclusions

In this paper, a SUE assignment model is proposed for schedule-based transit networks with vehicle capacity constraints. A solution algorithm is developed. The stochastic effects of the passenger's behavior and vehicle timetable, vehicle capacity are incorporated in the model.The attractive set problem which is conventionally considered only for frequency-based transit networks is formulated for the schedule-based transit network. The generalized cost model is set to determine the costs of connections between OD pairs. We also analyzed a mathematical programming problem equivalent to the SUE assignment problem in schedule-based transit networks with capacity constraints. When a connection segment reaches its capacity level, it is proven that the Lagrange multipliers of the mathematical problem give the equilibrium passenger overload delays in this transit network.Passenger overload delay is determined endogenously by the equilibrium characteristics and vehicle capacity of the schedule-based transit network in addition to the cost functions of each link used in the existing approaches. The overload delay varies with passenger’s knowledge about the scheduled time and the transit lines.The model proposed in this paper was applied to one special situation for congested transit networks. We found that greater knowledge of the capacity overrun path would result in more overload delay, but with little time to get to the destinations. For future research, several extensions of this model are possible and have the potential to enrich the models available for transit planning such as a SUE assignment with elastic transit demand, SUE assignment for multiple classes of passengers, and dynamic SUE assignment for transit systems.



---

*Source: 910754-2012-10-05.xml*