# Least Expected Time Paths in Stochastic Schedule-Based Transit Networks

Authors: Dang Khoa Vo; Tran Vu Pham; Nguyen Huynh Tuong; Van Hoai Tran
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

We consider the problem of determining a least expected time (LET) path that minimizes the number of transfers and the expected total travel time in a stochastic schedule-based transit network. A time-dependent model is proposed to represent the stochastic transit network where vehicle arrival times are fully stochastically correlated. An exact label-correcting algorithm is developed, based on a proposed dominance condition by which Bellman’s principle of optimality is valid. Experimental results, which are conducted on the Ho Chi Minh City bus network, show that the running time of the proposed algorithm is suitable for real-time operation, and the resulting LET paths are robust against uncertainty, such as unknown traffic scenarios.


---

## Body

## 1. Introduction

The routing problem in a schedule-based transit network involves scheduling decisions made by a traveler, for example, accessing to a stop (station), walking between stops, waiting to board, traveling in-vehicle, alighting, and egressing. These decisions guide the traveler from an origin to a destination with minimum travel costs, such as number of transfers, total travel time, walking time, and waiting time. The decisions of the traveler are not only constrained by the network configuration, that is, transit routes (lines), but also constrained by the schedules of transit vehicles. However, due to the stochastic and time-varying nature of vehicle travel time, as well as the effects of the arrival of a transit vehicle at upstream stop on its arrivals at downstream stops, the arrival times of transit vehicles usually do not follow their schedules. Therefore, the determination of robust routing decisions can greatly affect the quality of the routing service provided under uncertain conditions.Along with the stochasticity of vehicle travel times and the relationship between vehicle arrival times on the same transit route, there might also exist overlaps between transit routes in the network. Therefore, the arrival times of transit vehicles would be not only stochastic but also fully stochastically correlated. The routing problem with stochastically correlated link travel times has been investigated intensively in highway networks [1–6]. However, its counterpart in transit networks, where vehicle arrival times are considered as stochastically correlated, has not been addressed, while existing works in literature assumed vehicle arrival times to be deterministic [7–13] or statistically independent [14]. The main issue when designing a routing algorithm in a schedule-based transit network with correlated vehicle arrival times is to model the stochastic correlation of vehicle arrival times. This issue is related to the question of how to incorporate the correlation of vehicle arrival times into the routing process, in which not only constraints on transit routes but also constraints on vehicle arrival times are taken into account:(i)
A time-dependent model is proposed for stochastic schedule-based transit networks where the correlation of all vehicle arrival times is presented as a scenario. The graph model captures travelers’ decisions, namely, boarding, traveling in-vehicle, alighting, walking, and time constraints of these decisions in each scenario.
(ii)
A new dominance condition for paths is established with respect to number of transfers and travel times over a set of possible scenarios. Then a formal proof that Bellman’s principle of optimality is valid with nondominated paths is presented. This theoretical establishment enables the use of pretrip online information to reduce uncertainties for more robust LET paths.
(iii)
An exact link-based routing algorithm is proposed for efficiently determining LET paths, based on Bellman’s principle of optimality. The results from experiments, which are conducted using data from a real-size bus network in Ho Chi Minh City, show that the running time of the proposed algorithm is feasible for online applications. Also, LET paths are shown to be robust in the presence of unknown scenarios.The remaining of the paper is organized as follows. We present related researches on the routing problem in transit networks in Section2. In Section 3, we define components used to develop the algorithm for our routing problem. Then we propose the solution algorithm for determining the LET path in Section 4. Various experiments are conducted, and their results are discussed in Section 5. Finally, the conclusion is given in Section 6.


## 2. Related Work

A transit routing algorithm in literature has been built on the notion ofpath [7, 8, 15] orhyperpath [16–18]. A path consists of fixed decisions made by a traveler at stops, which are determined before he/she leaves the origin. In contrast, a hyperpath represents routing strategies in which the traveler is allowed to change his/her decision at each intermediate stop, depending on the previous decisions and what are likely to happen in the future. Routing based on hyperpath was shown to make better travel costs under uncertainty but requires the incorporation of online information and high computational complexity [19].Treatment for the routing problem in a transit network can be different, depending on the type of transit services, that is, eitherheadway-based [15–17] orschedule-based [7, 8, 11, 12]. In the former, transit services are represented by transit routes, and arrival/departure times of transit vehicles are not explicitly considered. This results in an approximation in calculating boarding times and in-vehicle travel times. In the latter, transit services are explicitly specified in terms of trips (runs), in which arrival/departure times of transit vehicles at stops are considered. Meanwhile the routing algorithm in a headway-based transit network can employ shortest path algorithms, for example, Dijkstra’s algorithm [20], which are the same as those used for highway networks. A schedule-based transit network requires a time-dependent network presentation where routing processes of travelers are not only constrained by the network topology but also constrained by scheduled arrival/departure times of transit vehicles. Therefore, modeling transit services is the first and important task in solving the routing problem in a schedule-based transit network. As classified by Nuzzolo and Crisalli [21], the representation of a schedule-based transit network can be one of the three forms: the diachronic (time-expanded) network [9, 10, 13], the dual network [22], and the mixed line-based/database supply model (time-dependent model) [11, 23, 24].In the context where transit services are insufficiently reliable, headways and arrival/departure times of transit vehicles are commonly modeled as random variables with well-known forms of probability distribution, for example, exponentially distributed headways [25, 26], Gaussian distributed headways [27, 28], and Gaussian distributed scheduled times [14]. Along with the stochasticity of transit services, the uncertainty in travelers’ perceptions on different types of travel costs can be also regarded as a source of stochasticity in a transit routing problem [8, 27, 28]. In these works, random weights for different travel cost components, such as transfer penalty, walking time, and waiting time, were incorporated into the routing process.The routing problem in transit networks has been investigated with various assumptions on many aspects, such as capacity limitation, congestion and overcrowding issues, vehicle capacity, and boarding failures [29]. Nuzzolo and Crisalli [21] investigated various routing models forlow- andhigh-frequency schedule-based transit networks. In the former, for example, in regional bus or railway networks, routing processes are based on arrival/departure times of transit vehicles [30, 31]. In the latter, typically in urban areas, travelers usually have a large number of options at stops to reach their destination. In this case, arrivals of travelers at stops do not rely heavily on vehicle arrival/departure times but are significantly affected by vehicle congestion, which are defined in literature as situations in which a traveler cannot board the first arriving vehicle and has to wait for next vehicles. Vehicle congestion can be modeled implicitly as increasing discomfort functions [11, 12, 32] or explicitly with vehicle capacity or set availability constraints [33–35].


## 3. Network Modeling

In this section, we define components used to develop the algorithm for determining LET paths in stochastic schedule-based transit networks.


### 3.1. Stochastic Schedule-Based Transit Network

We consider transit networkB
=
(
S
,
R
,
T
,
Q
,
C
), where S is the set of stops and R is the set of routes. A route, r
∈
R, is a fixed sequence of stops through which transit vehicles run periodically with fixed trips and defined by a set (1)
S
r
=
S
r
k
:
k
=
1
,
…
,
K
r
⊆
S
,where S
r
k is the kth stop and K
r is the number of stops on route r. Let I
r be the number of trips of route r over a set of time intervals T
=
{
0
,
σ
,
2
σ
,
…
,
T
σ
}, where σ is unit of time and T is the last time interval. The universal stochastic scenario set Q is a set of all known possible scenarios in the network such that (2)
∑
q
∈
Q
p
q
=
1
,where p
q is the occurrence probability of scenario q
∈
Q. Each scenario q can be defined by a set of stop times(3)
C
q
=
⋃
r
∈
R
⋃
i
=
1
I
r
⋃
k
=
1
K
r
θ
r
i
k
q
,where θ
r
i
k
q
∈
T denotes the stop time (scheduled arrival time of a transit vehicle) at the kth stop of the ith trip on route r in scenario q and C is the universal set of all stop times in all possible scenarios such that (4)
C
=
⋃
q
∈
Q
C
q
.In the context of transit networks, there might exist overlaps among routes. A scenario presents a stochastic correlation of not only stop times on the same route but also stop times on routes sharing the same physical links. The probability of a scenario happening is the full joint probability of all stop times taking place, and stop times are known for each scenario a priori. This allows us explicitly to take into account delays resulting from transfer failures due to late arrivals and their effects on the total travel time in each scenario.For example, consider the transit network shown in Figure1 with S
=
{
A
,
B
,
C
} and R
=
{
1,2
,
3
}. In this network, there are three routes in which routes 1 and 2 provide services from stop A to stop B with S
1
1
=
S
2
1
=
A and S
1
2
=
S
2
2
=
B, and route 3 provides services from stop B to stop C with S
3
1
=
B and S
3
2
=
C. The stop times of transit vehicles in the network are shown in Table 1 with T
=
{
0
,
…
,
16
}, Q
=
{
q
1
,
q
2
,
q
3
}, and C
=
{
C
1
,
C
2
,
C
3
} in which each of the routes has two trips and each scenario q
∈
Q has an occurrence probability of p
q
=
1
/
3.Table 1
Stop times of trips in the network presented in Figure1 over three possible scenarios each of which has an occurrence probability of 1
/
3.
Route
Trip
Stop
C
1
C
2
C
3
1
1
A
1
1
1
B
5
5
7
2
A
4
4
4
B
7
8
9
2
1
A
1
1
1
B
7
7
5
2
A
4
4
4
B
10
9
11
3
1
B
6
6
6
C
11
12
10
2
B
10
10
10
C
14
14
16Figure 1
A simple transit network.In this network, a traveler, who starts from origin stopA at time t
=
0, has two choices of routes to reach destination stop C, namely, p
1
:
A
→
r
o
u
t
e
1
B
→
r
o
u
t
e
3
C and p
2
:
A
→
r
o
u
t
e
2
B
→
r
o
u
t
e
3
C. With Assumption (4), the choices of trips for the earliest arrival time at stop C in different scenarios are shown in Table 2. In particular, if the traveler uses the choice of routes p
1, his/her expected arrival time at stop C equals (
11
+
12
+
16
)
/
3
=
13. In this case, the choice of trips for p
1 can be interpreted that, at stop B, the traveler transfers to trip 1 of route 3 successfully in scenarios q
1 and q
2 but misses this trip in scenario q
3. This leads to a later arrival time, that is, 16 instead of 10, at stop C, which contributes to the expected arrival time of the choice of routes p
1. Similarly, we have the expected arrival time at stop C of the choice of routes p
2 that equals 12.66. Note that transfer failures might spread over several later trips, depending on scenario.Table 2
The choices of trips for the earliest arrival time from stopA to stop C at time t
=
0 in different scenarios in the network shown in Figure 1 and the schedules shown in Table 1.
Choice of routes
Scenario
Choice of trips
Arrival time
p
1
q
1
A
→
t
r
i
p
1
,
r
o
u
t
e
1
B
→
t
r
i
p
1
,
r
o
u
t
e
3
C
11
q
2
A
→
t
r
i
p
1
,
r
o
u
t
e
1
B
→
t
r
i
p
1
,
r
o
u
t
e
3
C
12
q
3
A
→
t
r
i
p
1
,
r
o
u
t
e
1
B
→
t
r
i
p
2
,
r
o
u
t
e
3
C
16
p
2
q
1
A
→
t
r
i
p
1
,
r
o
u
t
e
2
B
→
t
r
i
p
2
,
r
o
u
t
e
3
C
14
q
2
A
→
t
r
i
p
1
,
r
o
u
t
e
2
B
→
t
r
i
p
2
,
r
o
u
t
e
3
C
14
q
3
A
→
t
r
i
p
1
,
r
o
u
t
e
2
B
→
t
r
i
p
1
,
r
o
u
t
e
3
C
10In this paper, the following assumptions are adopted:(1)
Actual travel times of transit vehicles between stops on a given route are nonnegative; that is,(5)
θ
r
i
k
q
<
θ
r
i
,
k
+
1
q
,
∀
r
,
i
,
k
,
q
.
(2)
Actual arrival times of transit vehicles for later trips cannot be earlier than those of earlier trips; that is,(6)
θ
r
i
k
q
<
θ
r
,
i
+
1
,
k
q
,
∀
r
,
i
,
k
,
q
.
(3)
Arrival times of transit vehicles in different scenarios are statistically independent.
(4)
Vehicle capacity, overcrowding, and fare issues are not considered. In other words, it is assumed that passengers always board any arriving transit vehicle successfully.
(5)
There is a similar perception for passengers on different time components, such as waiting time, walking time, and in-vehicle time.Assumptions (1) and (2) are expected to be valid in practice where it is conventional that transit vehicles serving trips on the same route keep away from each other at certain distance and their travel times are always positive. Assumption (3) is equivalent to the assumption used in the routing problem in highway network with correlated link travel times [4–6]; that is, link travel times in different scenarios are stochastically independent. Assumptions (4) and (5) have been widely adopted in literature, for example, [14, 18, 19, 25, 26].


### 3.2. Time-Dependent Model

A time-dependent graph model (similar to [24]) is used to present the transit network as a directed graph whose arcs model travelers’ decisions, namely, boarding, traveling in vehicles, alighting, and walking.LetG
=
(
N
,
A
,
T
) denote the graph modeling the transit network B, where the set of nodes N and the set of arcs A are defined as(i)
N
=
⋃
r
∈
R
N
r
∪
N
S,
(ii)
A
=
⋃
r
∈
R
A
r
∪
A
B
∪
A
D
∪
A
W,in which subsets ofN and A are defined as follows:N
S is the set ofstop nodes—a node V
s
∈
N
S represents the location of stop s
∈
S.
N
r is the set ofroute nodes associated with route r
∈
R—a node V
s
r
∈
N
r represents a transfer point where route r
∈
R visits stop s
∈
S
r.
A
B is the set ofboarding arcs—arc 〈
u
,
v
〉
∈
A
B, where u
≡
V
s
∈
N
S and v
≡
V
s
r
∈
N
r, represents the action of a traveler boarding an arriving vehicle of route r at stop s.
A
r is the set ofin-vehicle arcs of route r
∈
R—arc 〈
u
,
v
〉
∈
A
r, where u
≡
V
s
r
∈
N
r and v
≡
V
s
′
r
∈
N
r, represents the action of a traveler being in-vehicle of route r from stop s to stop s
′.
A
W is the set ofwalking arcs—arc 〈
u
,
v
〉
∈
A
W, where u
≡
V
s
∈
N
S and v
≡
V
s
′
∈
N
S, represents the action of a traveler walking from stop s to stop s
′.
A
D is the set ofalighting arcs—arc 〈
u
,
v
〉
∈
A
D, where u
≡
V
s
r
∈
N
r and v
≡
V
s
∈
N
S, represents the action of a traveler alighting the current vehicle of route r at stop s.Figure2 presents the graph model for the transit network as shown in Figure 1. Let P
o
v denote all paths connecting node o
∈
N and node v
∈
N in graph G or all o
-
v
paths in short. A well-defined o
-
v path p, defined in Definition 1, in graph G represents a choice of routes when he/she travels from origin stop S
o
∈
S to destination stop S
d
∈
S within the transit network B.Figure 2
The graph that models the network shown in Figure1.Definition 1 (well-definedo
-
v path).
Pathp
=
〈
o
≡
v
1
,
…
,
v
n
≡
v
〉
∈
P
o
v is well-defined if o
,
v
∈
N
S and 〈
v
i
,
v
i
+
1
〉
∈
A, i
=
1
,
…
,
n
-
1, n
>
2.


### 3.3. Arc Time and Transfer Weights

Note that only travelers’ decisions are captured in Section3.2. For modeling constraints on times when the schedules of transit vehicles are taken into account, times are then assigned to arcs as arc weights.Letτ
u
v
q
(
t
) be the time weight on arc 〈
u
,
v
〉
∈
A with time t
∈
T at node u in scenario q
∈
Q. Depending on the type of arc 〈
u
,
v
〉, the time weight is eitherboarding penalty,in-vehicle travel time,alighting penalty, orwalking time. In particular, τ
u
v
q
(
t
) can be assigned according to the four following cases.Case 1.
If〈
u
,
v
〉
∈
A
B, where u
≡
V
S
r
k and v
≡
V
S
r
k
r, the traveler stands at the kth stop at time t and boards a vehicle of arriving trip of route r. Due to unlimited vehicle capacity assumption, the boarded trip is commonly the first arriving one [24, 36, 37]. For boarding an arriving trip, the traveler must be at the stop before the bus of that trip leaves the stop by at least ε
¯
r
i
k units of time (note that herein σ is set to one and will be omitted for convenience in the rest of the paper). The boarding penalty for the first arriving trip if the traveler stands at the kth stop of route r at time t is expressed by(7)
τ
u
v
q
t
=
min
⁡
θ
r
i
k
q
≥
t
+
ε
¯
r
i
k
:
i
=
1
,
…
,
I
r
-
t
,
u
≡
V
S
r
k
,
v
≡
V
S
r
k
r
.Case 2.
If〈
u
,
v
〉
∈
A
r, r
∈
R, where u
≡
V
S
r
k
-
1
r and v
≡
V
S
r
k
r, the traveler rides on a vehicle serving a certain trip, for example, the ith trip, and travels from the (
k
-
1
)th stop to kth stop on route r. The time weight on arc 〈
u
,
v
〉 is therefore the in-vehicle travel time of the ith trip from the (
k
-
1
)th to kth stop. The in-vehicle travel time of the ith trip from the (
k
-
1
)th stop to kth stop on route r is(8)
τ
u
v
q
t
=
θ
r
i
k
q
-
θ
r
i
,
k
-
1
q
,
u
≡
V
S
r
k
-
1
r
,
v
≡
V
S
r
k
r
,
t
=
θ
r
i
,
k
-
1
q
,where the traveler’s arrival time t at the (
k
-
1
)th stop is the stop time θ
r
i
,
k
-
1
q of the vehicle in scenario q.Case 3.
If〈
u
,
v
〉
∈
A
D, where u
≡
V
S
r
k
r and v
≡
V
S
r
k, the traveler alights from a vehicle serving a trip, for example, the ith trip, at the kth stop of route r. The arc time weight can be expressed by(9)
τ
u
v
q
t
=
ε
_
r
i
k
,
u
≡
V
S
r
k
r
,
v
≡
V
S
r
k
,where ε
_
r
i
k is the alighting time for the ith trip at the kth stop on route r.Case 4.
If〈
u
,
v
〉
∈
A
W, where u
≡
V
s and v
≡
V
s
′, the traveler walks from stop s to stop s
′. Let ω
s
s
′ be the minimum time required for walking between stops s and s
′, and the walking time weight is given by(10)
τ
u
v
q
t
=
ω
s
s
′
,
u
≡
V
s
,
v
≡
V
s
′
.Letf
u
v be the weight for the number of transfers on arc 〈
u
,
v
〉. Note that f
u
v does not depend on time and scenario. The arc weight for number of transfers equals one if the arc is a boarding arc and zero for otherwise. Therefore,(11)
f
u
v
=
1
if
u
,
v
∈
A
B
,
0
o
t
h
e
r
w
i
s
e
.In summary, Table3 shows the arc time weights in the example graph model in Figure 2 after applying (7), (8), (9), and (10) with boarding penalty ε
¯
r
i
k
=
1 and alighting penalty ε
_
r
i
k
=
0. Each arc with symbol “—” at a given time and in a given scenario means the traveler’s action associated with that arc is restricted at that time and scenario. For example, considering arc 〈
V
B
,
V
B
2
〉, in scenario q
1, from times 0 to 9 the arc represents the traveler’s action of boarding route 2 at stop B with different boarding penalties; that is, from times 0 to 6 the traveler boards trip 1 with penalties from 7 to 1, and from times 7 to 9 the traveler boards trip 2 with penalties from 3 to 1. After time 9 the traveler’s boarding action is restricted since no trip of route 2 will arrive at stop B in scenario q
1 (see the timetable in Table 1). Note that only walking arcs, that is, 〈
V
A
,
V
B
〉 and 〈
V
B
,
V
A
〉, are available at any time since travelers can walk freely. For shortest path problems, restricted actions can be set with very large integer weights.Table 3
Arc time weights with boarding penaltyε
-
r
i
k
=
1 and alighting penalty ε
_
r
i
k
=
0 in the network shown in Figure 2.
Time
〈
V
A
,
V
A
1
〉
〈
V
A
,
V
A
2
〉
〈
V
B
,
V
B
1
〉
〈
V
B
,
V
B
2
〉
〈
V
B
,
V
B
3
〉
〈
V
C
,
V
C
3
〉
〈
V
A
1
,
V
B
1
〉
〈
V
A
2
,
V
B
2
〉
〈
V
B
3
,
V
C
3
〉
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
0
1
1
1
1
1
1
5
5
7
7
7
5
6
6
6
11
12
10
—
—
—
—
—
—
—
—
—
1
3
3
3
3
3
3
4
4
6
6
6
4
5
5
5
10
11
9
4
4
6
6
6
4
—
—
—
2
2
2
2
2
2
2
3
3
5
5
5
3
4
4
4
9
10
8
—
—
—
—
—
—
—
—
—
3
1
1
1
1
1
1
2
2
4
4
4
2
3
3
3
8
9
7
—
—
—
—
—
—
—
—
—
4
—
—
—
—
—
—
1
1
3
3
3
1
2
2
2
7
8
6
3
4
5
6
5
7
—
—
—
5
—
—
—
—
—
—
2
3
2
2
2
6
1
1
1
6
7
5
—
—
—
—
—
—
—
—
—
6
—
—
—
—
—
—
1
2
1
1
1
5
4
4
4
5
6
4
—
—
—
—
—
—
5
6
4
7
—
—
—
—
—
—
—
1
2
3
2
4
3
3
3
4
5
3
—
—
—
—
—
—
—
—
—
8
—
—
—
—
—
—
—
—
1
2
1
3
2
2
2
3
4
2
—
—
—
—
—
—
—
—
—
9
—
—
—
—
—
—
—
—
—
1
—
2
1
1
1
2
3
1
—
—
—
—
—
—
—
—
—
10
—
—
—
—
—
—
—
—
—
—
—
1
—
—
—
1
2
6
—
—
—
—
—
—
4
4
6
11
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
3
1
5
—
—
—
—
—
—
—
—
—
12
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
2
2
4
—
—
—
—
—
—
—
—
—
13
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
1
1
3
—
—
—
—
—
—
—
—
—
14
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
2
—
—
—
—
—
—
—
—
—
15
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
1
—
—
—
—
—
—
—
—
—
16
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
Time
〈
V
A
1
,
V
A
〉
〈
V
A
2
,
V
A
〉
〈
V
B
1
,
V
B
〉
〈
V
B
2
,
V
B
〉
〈
V
B
3
,
V
B
〉
〈
V
C
3
,
V
C
〉
〈
V
A
,
V
B
〉
〈
V
B
,
V
A
〉
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
0
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
1
0
0
0
0
0
0
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
2
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
3
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
4
0
0
0
0
0
0
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
5
—
—
—
—
—
—
0
0
—
—
—
0
—
—
—
—
—
—
11
11
11
11
11
11
6
—
—
—
—
—
—
—
—
—
—
—
—
0
0
0
—
—
—
11
11
11
11
11
11
7
—
—
—
—
—
—
0
—
0
0
0
—
—
—
—
—
—
—
11
11
11
11
11
11
8
—
—
—
—
—
—
—
0
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
9
—
—
—
—
—
—
—
—
0
—
0
—
—
—
—
—
—
—
11
11
11
11
11
11
10
—
—
—
—
—
—
—
—
—
0
—
—
0
0
0
—
—
0
11
11
11
11
11
11
11
—
—
—
—
—
—
—
—
—
—
—
0
—
—
—
0
—
—
11
11
11
11
11
11
12
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
0
—
11
11
11
11
11
11
13
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
14
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
0
0
—
11
11
11
11
11
11
15
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
16
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
0
11
11
11
11
11
11


## 3.1. Stochastic Schedule-Based Transit Network

We consider transit networkB
=
(
S
,
R
,
T
,
Q
,
C
), where S is the set of stops and R is the set of routes. A route, r
∈
R, is a fixed sequence of stops through which transit vehicles run periodically with fixed trips and defined by a set (1)
S
r
=
S
r
k
:
k
=
1
,
…
,
K
r
⊆
S
,where S
r
k is the kth stop and K
r is the number of stops on route r. Let I
r be the number of trips of route r over a set of time intervals T
=
{
0
,
σ
,
2
σ
,
…
,
T
σ
}, where σ is unit of time and T is the last time interval. The universal stochastic scenario set Q is a set of all known possible scenarios in the network such that (2)
∑
q
∈
Q
p
q
=
1
,where p
q is the occurrence probability of scenario q
∈
Q. Each scenario q can be defined by a set of stop times(3)
C
q
=
⋃
r
∈
R
⋃
i
=
1
I
r
⋃
k
=
1
K
r
θ
r
i
k
q
,where θ
r
i
k
q
∈
T denotes the stop time (scheduled arrival time of a transit vehicle) at the kth stop of the ith trip on route r in scenario q and C is the universal set of all stop times in all possible scenarios such that (4)
C
=
⋃
q
∈
Q
C
q
.In the context of transit networks, there might exist overlaps among routes. A scenario presents a stochastic correlation of not only stop times on the same route but also stop times on routes sharing the same physical links. The probability of a scenario happening is the full joint probability of all stop times taking place, and stop times are known for each scenario a priori. This allows us explicitly to take into account delays resulting from transfer failures due to late arrivals and their effects on the total travel time in each scenario.For example, consider the transit network shown in Figure1 with S
=
{
A
,
B
,
C
} and R
=
{
1,2
,
3
}. In this network, there are three routes in which routes 1 and 2 provide services from stop A to stop B with S
1
1
=
S
2
1
=
A and S
1
2
=
S
2
2
=
B, and route 3 provides services from stop B to stop C with S
3
1
=
B and S
3
2
=
C. The stop times of transit vehicles in the network are shown in Table 1 with T
=
{
0
,
…
,
16
}, Q
=
{
q
1
,
q
2
,
q
3
}, and C
=
{
C
1
,
C
2
,
C
3
} in which each of the routes has two trips and each scenario q
∈
Q has an occurrence probability of p
q
=
1
/
3.Table 1
Stop times of trips in the network presented in Figure1 over three possible scenarios each of which has an occurrence probability of 1
/
3.
Route
Trip
Stop
C
1
C
2
C
3
1
1
A
1
1
1
B
5
5
7
2
A
4
4
4
B
7
8
9
2
1
A
1
1
1
B
7
7
5
2
A
4
4
4
B
10
9
11
3
1
B
6
6
6
C
11
12
10
2
B
10
10
10
C
14
14
16Figure 1
A simple transit network.In this network, a traveler, who starts from origin stopA at time t
=
0, has two choices of routes to reach destination stop C, namely, p
1
:
A
→
r
o
u
t
e
1
B
→
r
o
u
t
e
3
C and p
2
:
A
→
r
o
u
t
e
2
B
→
r
o
u
t
e
3
C. With Assumption (4), the choices of trips for the earliest arrival time at stop C in different scenarios are shown in Table 2. In particular, if the traveler uses the choice of routes p
1, his/her expected arrival time at stop C equals (
11
+
12
+
16
)
/
3
=
13. In this case, the choice of trips for p
1 can be interpreted that, at stop B, the traveler transfers to trip 1 of route 3 successfully in scenarios q
1 and q
2 but misses this trip in scenario q
3. This leads to a later arrival time, that is, 16 instead of 10, at stop C, which contributes to the expected arrival time of the choice of routes p
1. Similarly, we have the expected arrival time at stop C of the choice of routes p
2 that equals 12.66. Note that transfer failures might spread over several later trips, depending on scenario.Table 2
The choices of trips for the earliest arrival time from stopA to stop C at time t
=
0 in different scenarios in the network shown in Figure 1 and the schedules shown in Table 1.
Choice of routes
Scenario
Choice of trips
Arrival time
p
1
q
1
A
→
t
r
i
p
1
,
r
o
u
t
e
1
B
→
t
r
i
p
1
,
r
o
u
t
e
3
C
11
q
2
A
→
t
r
i
p
1
,
r
o
u
t
e
1
B
→
t
r
i
p
1
,
r
o
u
t
e
3
C
12
q
3
A
→
t
r
i
p
1
,
r
o
u
t
e
1
B
→
t
r
i
p
2
,
r
o
u
t
e
3
C
16
p
2
q
1
A
→
t
r
i
p
1
,
r
o
u
t
e
2
B
→
t
r
i
p
2
,
r
o
u
t
e
3
C
14
q
2
A
→
t
r
i
p
1
,
r
o
u
t
e
2
B
→
t
r
i
p
2
,
r
o
u
t
e
3
C
14
q
3
A
→
t
r
i
p
1
,
r
o
u
t
e
2
B
→
t
r
i
p
1
,
r
o
u
t
e
3
C
10In this paper, the following assumptions are adopted:(1)
Actual travel times of transit vehicles between stops on a given route are nonnegative; that is,(5)
θ
r
i
k
q
<
θ
r
i
,
k
+
1
q
,
∀
r
,
i
,
k
,
q
.
(2)
Actual arrival times of transit vehicles for later trips cannot be earlier than those of earlier trips; that is,(6)
θ
r
i
k
q
<
θ
r
,
i
+
1
,
k
q
,
∀
r
,
i
,
k
,
q
.
(3)
Arrival times of transit vehicles in different scenarios are statistically independent.
(4)
Vehicle capacity, overcrowding, and fare issues are not considered. In other words, it is assumed that passengers always board any arriving transit vehicle successfully.
(5)
There is a similar perception for passengers on different time components, such as waiting time, walking time, and in-vehicle time.Assumptions (1) and (2) are expected to be valid in practice where it is conventional that transit vehicles serving trips on the same route keep away from each other at certain distance and their travel times are always positive. Assumption (3) is equivalent to the assumption used in the routing problem in highway network with correlated link travel times [4–6]; that is, link travel times in different scenarios are stochastically independent. Assumptions (4) and (5) have been widely adopted in literature, for example, [14, 18, 19, 25, 26].


## 3.2. Time-Dependent Model

A time-dependent graph model (similar to [24]) is used to present the transit network as a directed graph whose arcs model travelers’ decisions, namely, boarding, traveling in vehicles, alighting, and walking.LetG
=
(
N
,
A
,
T
) denote the graph modeling the transit network B, where the set of nodes N and the set of arcs A are defined as(i)
N
=
⋃
r
∈
R
N
r
∪
N
S,
(ii)
A
=
⋃
r
∈
R
A
r
∪
A
B
∪
A
D
∪
A
W,in which subsets ofN and A are defined as follows:N
S is the set ofstop nodes—a node V
s
∈
N
S represents the location of stop s
∈
S.
N
r is the set ofroute nodes associated with route r
∈
R—a node V
s
r
∈
N
r represents a transfer point where route r
∈
R visits stop s
∈
S
r.
A
B is the set ofboarding arcs—arc 〈
u
,
v
〉
∈
A
B, where u
≡
V
s
∈
N
S and v
≡
V
s
r
∈
N
r, represents the action of a traveler boarding an arriving vehicle of route r at stop s.
A
r is the set ofin-vehicle arcs of route r
∈
R—arc 〈
u
,
v
〉
∈
A
r, where u
≡
V
s
r
∈
N
r and v
≡
V
s
′
r
∈
N
r, represents the action of a traveler being in-vehicle of route r from stop s to stop s
′.
A
W is the set ofwalking arcs—arc 〈
u
,
v
〉
∈
A
W, where u
≡
V
s
∈
N
S and v
≡
V
s
′
∈
N
S, represents the action of a traveler walking from stop s to stop s
′.
A
D is the set ofalighting arcs—arc 〈
u
,
v
〉
∈
A
D, where u
≡
V
s
r
∈
N
r and v
≡
V
s
∈
N
S, represents the action of a traveler alighting the current vehicle of route r at stop s.Figure2 presents the graph model for the transit network as shown in Figure 1. Let P
o
v denote all paths connecting node o
∈
N and node v
∈
N in graph G or all o
-
v
paths in short. A well-defined o
-
v path p, defined in Definition 1, in graph G represents a choice of routes when he/she travels from origin stop S
o
∈
S to destination stop S
d
∈
S within the transit network B.Figure 2
The graph that models the network shown in Figure1.Definition 1 (well-definedo
-
v path).
Pathp
=
〈
o
≡
v
1
,
…
,
v
n
≡
v
〉
∈
P
o
v is well-defined if o
,
v
∈
N
S and 〈
v
i
,
v
i
+
1
〉
∈
A, i
=
1
,
…
,
n
-
1, n
>
2.


## 3.3. Arc Time and Transfer Weights

Note that only travelers’ decisions are captured in Section3.2. For modeling constraints on times when the schedules of transit vehicles are taken into account, times are then assigned to arcs as arc weights.Letτ
u
v
q
(
t
) be the time weight on arc 〈
u
,
v
〉
∈
A with time t
∈
T at node u in scenario q
∈
Q. Depending on the type of arc 〈
u
,
v
〉, the time weight is eitherboarding penalty,in-vehicle travel time,alighting penalty, orwalking time. In particular, τ
u
v
q
(
t
) can be assigned according to the four following cases.Case 1.
If〈
u
,
v
〉
∈
A
B, where u
≡
V
S
r
k and v
≡
V
S
r
k
r, the traveler stands at the kth stop at time t and boards a vehicle of arriving trip of route r. Due to unlimited vehicle capacity assumption, the boarded trip is commonly the first arriving one [24, 36, 37]. For boarding an arriving trip, the traveler must be at the stop before the bus of that trip leaves the stop by at least ε
¯
r
i
k units of time (note that herein σ is set to one and will be omitted for convenience in the rest of the paper). The boarding penalty for the first arriving trip if the traveler stands at the kth stop of route r at time t is expressed by(7)
τ
u
v
q
t
=
min
⁡
θ
r
i
k
q
≥
t
+
ε
¯
r
i
k
:
i
=
1
,
…
,
I
r
-
t
,
u
≡
V
S
r
k
,
v
≡
V
S
r
k
r
.Case 2.
If〈
u
,
v
〉
∈
A
r, r
∈
R, where u
≡
V
S
r
k
-
1
r and v
≡
V
S
r
k
r, the traveler rides on a vehicle serving a certain trip, for example, the ith trip, and travels from the (
k
-
1
)th stop to kth stop on route r. The time weight on arc 〈
u
,
v
〉 is therefore the in-vehicle travel time of the ith trip from the (
k
-
1
)th to kth stop. The in-vehicle travel time of the ith trip from the (
k
-
1
)th stop to kth stop on route r is(8)
τ
u
v
q
t
=
θ
r
i
k
q
-
θ
r
i
,
k
-
1
q
,
u
≡
V
S
r
k
-
1
r
,
v
≡
V
S
r
k
r
,
t
=
θ
r
i
,
k
-
1
q
,where the traveler’s arrival time t at the (
k
-
1
)th stop is the stop time θ
r
i
,
k
-
1
q of the vehicle in scenario q.Case 3.
If〈
u
,
v
〉
∈
A
D, where u
≡
V
S
r
k
r and v
≡
V
S
r
k, the traveler alights from a vehicle serving a trip, for example, the ith trip, at the kth stop of route r. The arc time weight can be expressed by(9)
τ
u
v
q
t
=
ε
_
r
i
k
,
u
≡
V
S
r
k
r
,
v
≡
V
S
r
k
,where ε
_
r
i
k is the alighting time for the ith trip at the kth stop on route r.Case 4.
If〈
u
,
v
〉
∈
A
W, where u
≡
V
s and v
≡
V
s
′, the traveler walks from stop s to stop s
′. Let ω
s
s
′ be the minimum time required for walking between stops s and s
′, and the walking time weight is given by(10)
τ
u
v
q
t
=
ω
s
s
′
,
u
≡
V
s
,
v
≡
V
s
′
.Letf
u
v be the weight for the number of transfers on arc 〈
u
,
v
〉. Note that f
u
v does not depend on time and scenario. The arc weight for number of transfers equals one if the arc is a boarding arc and zero for otherwise. Therefore,(11)
f
u
v
=
1
if
u
,
v
∈
A
B
,
0
o
t
h
e
r
w
i
s
e
.In summary, Table3 shows the arc time weights in the example graph model in Figure 2 after applying (7), (8), (9), and (10) with boarding penalty ε
¯
r
i
k
=
1 and alighting penalty ε
_
r
i
k
=
0. Each arc with symbol “—” at a given time and in a given scenario means the traveler’s action associated with that arc is restricted at that time and scenario. For example, considering arc 〈
V
B
,
V
B
2
〉, in scenario q
1, from times 0 to 9 the arc represents the traveler’s action of boarding route 2 at stop B with different boarding penalties; that is, from times 0 to 6 the traveler boards trip 1 with penalties from 7 to 1, and from times 7 to 9 the traveler boards trip 2 with penalties from 3 to 1. After time 9 the traveler’s boarding action is restricted since no trip of route 2 will arrive at stop B in scenario q
1 (see the timetable in Table 1). Note that only walking arcs, that is, 〈
V
A
,
V
B
〉 and 〈
V
B
,
V
A
〉, are available at any time since travelers can walk freely. For shortest path problems, restricted actions can be set with very large integer weights.Table 3
Arc time weights with boarding penaltyε
-
r
i
k
=
1 and alighting penalty ε
_
r
i
k
=
0 in the network shown in Figure 2.
Time
〈
V
A
,
V
A
1
〉
〈
V
A
,
V
A
2
〉
〈
V
B
,
V
B
1
〉
〈
V
B
,
V
B
2
〉
〈
V
B
,
V
B
3
〉
〈
V
C
,
V
C
3
〉
〈
V
A
1
,
V
B
1
〉
〈
V
A
2
,
V
B
2
〉
〈
V
B
3
,
V
C
3
〉
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
0
1
1
1
1
1
1
5
5
7
7
7
5
6
6
6
11
12
10
—
—
—
—
—
—
—
—
—
1
3
3
3
3
3
3
4
4
6
6
6
4
5
5
5
10
11
9
4
4
6
6
6
4
—
—
—
2
2
2
2
2
2
2
3
3
5
5
5
3
4
4
4
9
10
8
—
—
—
—
—
—
—
—
—
3
1
1
1
1
1
1
2
2
4
4
4
2
3
3
3
8
9
7
—
—
—
—
—
—
—
—
—
4
—
—
—
—
—
—
1
1
3
3
3
1
2
2
2
7
8
6
3
4
5
6
5
7
—
—
—
5
—
—
—
—
—
—
2
3
2
2
2
6
1
1
1
6
7
5
—
—
—
—
—
—
—
—
—
6
—
—
—
—
—
—
1
2
1
1
1
5
4
4
4
5
6
4
—
—
—
—
—
—
5
6
4
7
—
—
—
—
—
—
—
1
2
3
2
4
3
3
3
4
5
3
—
—
—
—
—
—
—
—
—
8
—
—
—
—
—
—
—
—
1
2
1
3
2
2
2
3
4
2
—
—
—
—
—
—
—
—
—
9
—
—
—
—
—
—
—
—
—
1
—
2
1
1
1
2
3
1
—
—
—
—
—
—
—
—
—
10
—
—
—
—
—
—
—
—
—
—
—
1
—
—
—
1
2
6
—
—
—
—
—
—
4
4
6
11
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
3
1
5
—
—
—
—
—
—
—
—
—
12
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
2
2
4
—
—
—
—
—
—
—
—
—
13
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
1
1
3
—
—
—
—
—
—
—
—
—
14
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
2
—
—
—
—
—
—
—
—
—
15
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
1
—
—
—
—
—
—
—
—
—
16
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
Time
〈
V
A
1
,
V
A
〉
〈
V
A
2
,
V
A
〉
〈
V
B
1
,
V
B
〉
〈
V
B
2
,
V
B
〉
〈
V
B
3
,
V
B
〉
〈
V
C
3
,
V
C
〉
〈
V
A
,
V
B
〉
〈
V
B
,
V
A
〉
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
q
1
q
2
q
3
0
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
1
0
0
0
0
0
0
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
2
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
3
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
4
0
0
0
0
0
0
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
5
—
—
—
—
—
—
0
0
—
—
—
0
—
—
—
—
—
—
11
11
11
11
11
11
6
—
—
—
—
—
—
—
—
—
—
—
—
0
0
0
—
—
—
11
11
11
11
11
11
7
—
—
—
—
—
—
0
—
0
0
0
—
—
—
—
—
—
—
11
11
11
11
11
11
8
—
—
—
—
—
—
—
0
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
9
—
—
—
—
—
—
—
—
0
—
0
—
—
—
—
—
—
—
11
11
11
11
11
11
10
—
—
—
—
—
—
—
—
—
0
—
—
0
0
0
—
—
0
11
11
11
11
11
11
11
—
—
—
—
—
—
—
—
—
—
—
0
—
—
—
0
—
—
11
11
11
11
11
11
12
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
0
—
11
11
11
11
11
11
13
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
14
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
0
0
—
11
11
11
11
11
11
15
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
11
11
11
11
11
11
16
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
0
11
11
11
11
11
11


## 4. Least Expected Time (LET) Path Problem

In Section3, we propose and explain the graph modeling transit network that captures travelers’ actions, namely, boarding, in-vehicle, alighting, and walking, and time constraints associated with travelers’ decisions. Below we will study the LET path problem in stochastic schedule-based transit networks using the graph model.


### 4.1. Problem Definition

The LET path problem in this paper is studied from one origin nodeo
∈
N for a fixed departure time t to all destination nodes v
∈
N over a scenario set Ω
⊆
Q. The criteria used for evaluating a path include the number of transfers and the expected total travel time across the set of scenarios Ω.Letτ
λ
q
(
u
,
t
) be the travel time on o-u path λ, u
∈
N, in scenario q
∈
Ω. Let us consider o-v path λ
′ that is expanded from o-u path λ via arc 〈
u
,
v
〉
∈
A, denoted by λ
′
=
λ
♢
〈
u
,
v
〉. The relationship between travel time on path λ
′ and that of its subpath λ for departure time t in scenario q is given by(12)
τ
λ
′
q
v
,
t
=
τ
λ
q
u
,
t
+
τ
u
v
q
t
+
τ
λ
q
u
,
t
,where τ
u
v
q
(
t
) is the time weight on arc 〈
u
,
v
〉 at time t. Depending on the type of arc 〈
u
,
v
〉, arc weight τ
u
,
v
q
(
t
) is determined by one of (7), (8), (9), and (10). When Assumption (3) holds, the expected (mean) travel time of o-v path λ
′ with departure time t over scenario set Ω, denoted by T
λ
′
(
v
,
t
,
Ω
), is given by(13)
T
λ
′
v
,
t
,
Ω
=
1
∑
q
∈
Ω
p
q
∑
q
∈
Ω
τ
λ
′
q
v
,
t
p
q
,where p
q is the occurrence probability of scenario q and T
λ
′
(
o
,
t
,
Ω
)
=
0.We also have the relationship between the number of transfers on pathλ
′, that is, f
λ
′
(
v
), and the number of transfers on its subpath λ, that is, f
λ
(
u
), in the following:(14)
f
λ
′
v
=
f
u
v
+
f
λ
u
,where weight f
u
v for the number of transfers on arc 〈
u
,
v
〉 is given by (11), and f
λ
′
(
o
)
=
0.From the transit travelers’ perspective, it is more useful that we aim to minimize the number of transfers first and then the expected travel time across the scenario set. The LET path is given by Definition2.Definition 2 (LETo-v path).
The LETo-v path λ
∗ with departure time t
∈
T over scenario set Ω
⊆
Q, ∀
v
∈
N, is given by(15)
λ
∗
=
a
r
g
m
i
n
λ
∈
P
o
v
T
λ
v
,
t
,
Ω
,
s.t.
f
λ
∗
v
=
min
λ
∈
P
ov
⁡
f
λ
v
.


### 4.2. Dominance Condition

A LETo-v path problem with departure time t
∈
T over scenario set Ω
∈
Q defined in (15) can be solved by enumerating all possible o-v paths P
o
v and then minimizing the number of transfers and the expected travel time of each o-v path in P
o
v for departure time t over Ω using (12) and (14). Such a brute force algorithm is inefficient. We therefore propose a dominance condition by which the optimal LET path is satisfied. First, we define a dominance condition in Definition 3. Then, the LET o-v path for departure time t over scenario set Ω is found in the set of nondominated o-v paths at time t over Ω by Proposition 4.Note that the dominance condition in Definition3 is not asstrict as the one with at least one scenario q
∈
Q such that τ
λ
′
q
v
,
t
<
τ
λ
q
(
v
,
t
). This is because, in the constructed graph described in Section 3.2, there might exist many nondominated paths, which present the same choice of routes and are only different from each other in transfer locations.Definition 3 (nondominatedo-v path).
Given a departure timet
∈
T, o-v path λ
′, ∀
v
∈
N, dominates another o-v path over the scenario set Ω
⊆
Q, if(16)
f
λ
′
v
<
f
λ
v
,
o
r
(17)
f
λ
′
v
=
f
λ
v
,
τ
λ
′
q
v
,
t
≤
τ
λ
q
v
,
t
,
∀
q
∈
Ω
. Then o-v path λ
′ is nondominated in P
o
v for departure time t over scenario set Ω if λ
′ is not dominated by any o-v path at time t over Ω.Proposition 4.
Given a departure timet
∈
T and a set of scenarios Ω
⊆
Q, the LET o-v path at time t over Ω, ∀
v
∈
N, belongs to the set of nondominated o-v paths at time t over Ω.By Definition3, the problem of determining nondominated o-d paths can be treated as multicriteria shortest path problem with (
Q
+
1
) independent criteria, namely, number of transfers, as well as travel times corresponding to Q scenarios. Theorem 7 below implies that Bellman’s principle of optimality is valid when nondominated paths are defined with respect to their nondominated subpaths. We later develop a forward label-correcting algorithm to solve the LET path problem based on Theorem 7. Note that Theorem 7 is established on the grounds of Lemmas 5 and 6, being only valid when Assumptions (1) and (2) hold.Lemma 5.
For any given arc〈
u
,
v
〉
∈
A, f
u
v
≥
0, and τ
u
v
q
(
t
)
≥
0, ∀
t
∈
T, ∀
q
∈
Q.Lemma 6.
For any given arc〈
u
,
v
〉
∈
A, if t
1
≤
t
2, (18)
t
1
+
τ
u
v
q
t
1
≤
t
2
+
τ
u
v
q
t
2
,
∀
t
1
,
t
2
∈
T
,
∀
q
∈
Q
.Theorem 7.
Given departure timet
∈
T and a set of scenarios Ω
⊆
Q, every nondominated o-v path λ
∗ is made up from nondominated o-u subpaths, where u is any intermediate node on path λ.


### 4.3. Relationship between Nondominated, LET, and the Fastest Paths

Definition 8 (the fastesto-v path).
Given departure timet
∈
T and scenario q
∈
Q, the fastest o-v path γ
∗ at time t in scenario q, ∀
v
∈
N, is given by(19)
γ
∗
=
a
r
g
m
i
n
λ
∈
P
o
v
τ
λ
q
v
,
t
,
s.t.
f
γ
∗
v
=
m
i
n
λ
∈
P
o
v
f
λ
v
.Proposition 9.
Given the fastesto-v path γ
∗ at time t in scenario q
∈
Q, ∀
v
∈
N, and a set of nondominated o-v paths at time t over the scenario set Ω
⊆
Q, if q
∈
Ω, γ
∗ belongs to the set of nondominated o-v paths at time t over Ω.Proposition 10.
Given departure timet and two sets of scenarios Ω
,
Ω
′
⊆
Q, if Ω
⊆
Ω
′, the set of nondominated o-v paths at time t over Ω is a subset of the set of nondominated o-v paths at time t over Ω
′, ∀
v
∈
N.By Propositions4, 9, and 10, we can establish the relationship between nondominated, LET, and the fastest o-v paths for departure time t over universal scenario set Q and its subset Ω as shown in Figure 3. By determining the set of nondominated o-v paths over the universal scenario set Q at departure time t, we can obtain LET o-v path at time t over any subset of Q. The relationship is beneficial when prejourney online information is used to determine these subsets.Figure 3
The relationship between nondominated and LET and the fastesto-v paths for departure time t over the universal scenario set Q and its subset Ω.


### 4.4. Label-Correcting Algorithm

The algorithm for determining the LET paths is based on the link-based approach, using the optimality condition stated in Theorem7, which is only valid as Assumptions (1) and (2) hold. Since the proposed approach helps avoid enumerating all possible origin-destination paths, it is feasible in real-time applications. Note that Theorem 7 can be still valid with simple modifications in the dominance condition when other criteria, such as fare and walking distance, are taken into account as long as the arc weights for these criteria are positive and time-independent. Consequently, we can incorporate travelers’ weightings on different criteria, such as number of transfers, total travel time, fare, and walking distance, in the routing process.Nevertheless, one drawback of our approach is that it does not allow taking into account travelers’ weightings on different time components, such as boarding time and in-vehicle travel time, since the arc weights for these time components are time-dependent. Several works in literature solved this issue using the path enumeration method [27, 28] or the branch and bound method [8]. However, these solution approaches are infeasible for real-time applications, especially in stochastic transit networks herein considering the stochastic correlation among stop times of transit vehicles. Our proposed algorithm is developed as follows.Given departure timet, for each node u
∈
N and each o-u path λ, the algorithm maintains a vector label (20)
Λ
λ
u
=
f
λ
u
,
τ
λ
q
u
,
t
,
∀
q
∈
Q
. Let L
(
u
) be the set of nondominated labels corresponding to the set of nondominated o-u paths at time t over the set of scenarios Q. According to Theorem 7, each label Λ
λ
(
u
)
∈
L
(
u
) contains the information of nondominated o-u path λ that has potential to be a nondominated origin-destination path at time t over Q when the algorithm terminates, where label Λ
λ
(
u
) is nondominated in L
(
u
) at time t over Q if λ is a nondominated o-u path at time t over Q (see Definition 3).At each iteration of the algorithm, labelΛ
λ
(
u
) is selected from queue X that contains a nondominated candidate path λ. Path λ is expanded via arc 〈
u
,
v
〉
∈
A. Depending on the type of arc 〈
u
,
v
〉, a temporary label Λ
λ
′
(
v
) for path λ
′
=
λ
♢
〈
u
,
v
〉 is constructed with weights calculated by (12) and (14). To determine if a new label Λ
λ
′
(
v
) is nondominated, it is compared with the nondominated labels L
(
v
) at node v. Details for the algorithm are presented in Algorithm 1.Algorithm 1:LET-Path search.
Input:  the origin o, the destination d, the departure time t, and the universal set of scenarios Q
Output: the LET o-d path at time t over Ω
⊆
Q, where Ω is the realized scenarios at time t
(1)    Create an initial path λ
0 with the origin node o;
(2)    L
(
u
)
=
∅ for all u
∈
N;
(3)    Create label Λ
λ
0
(
o
) with τ
λ
0
q
(
o
,
t
)
=
0, ∀
q
∈
Q, and f
λ
0
(
o
)
=
0;
(4)    L
o
=
Λ
λ
0
o;
(5)    X
=
Λ
λ
0
o;
(6)    while
Q
≠
∅
do
(7)      Extract and remove a label Λ
λ
(
u
) from queue X;
(8)      for
v
∈
Γ
(
u
)
,
Γ
(
u
)
=
{
v
:
〈
u
,
v
〉
∈
A
}
do
(9)       Create a new path λ
′
=
λ
♢
〈
u
,
v
〉;
(1
0)    Depending on the type of 〈
u
,
v
〉, calculate travel time weight τ
u
v
q
(
t
), ∀
q
∈
Q, using one of  (7)–(10), and calculate
transfer weightf
u
v using  (11);
(11)    Calculate τ
λ
′
q
(
v
,
t
), ∀
q
∈
Q, using (12), and calculate f
λ
′
(
v
) using (14);
(1
2)    Create a new label Λ
λ
′
(
v
) with f
λ
′
(
v
), and τ
λ
′
q
(
v
,
t
), ∀
q
∈
Q;
(1
3)    if label Λ
λ
′
(
v
) is non-dominated in L
(
v
)
then
(1
4)     Remove all labels Λ
λ
′
′
(
v
)
∈
L
(
v
) dominated by Λ
λ
′
(
v
);
(1
5)     L
v
=
L
v
∪
Λ
λ
′
v;
(1
6)     X
=
X
∪
Λ
λ
′
v;
(1
7) Let Ω
⊆
Q be the scenarios realized at time t;
(1
8) Apply (13) and (15) for the set of non-dominated paths L
(
d
) over the set of scenarios Ω to obtain the LET o-d path;Algorithm1 is equivalent to multicriteria shortest path algorithm for (
Q
+
1
) independent criteria and terminates after a finite number of steps with a set of nondominated paths at each node [38]. The algorithm is computationally intractable as the number of nondominated paths examined by the algorithm grows exponentially in the worst case [39]. However, the experiments in Section 5 show that the number of examined nondominated paths in a typical transit network is much smaller than that of the worst case.


### 4.5. Illustrative Example

Consider the transit network in Figure1 and its schedules as shown in Table 1. The time-dependent graph and its arc times are shown in Figure 2 and Table 3, respectively, with boarding penalty ε
¯
r
i
k
=
1 and alighting penalty ε
_
r
i
k
=
0. Figure 4 shows nondominated vector labels at all nodes in the time-dependent graph for origin node o
=
V
A, destination node d
=
V
C, and departure time t
=
0 over the universal scenario set Q
=
{
q
1
,
q
2
,
q
3
} and two nondominated o-d paths:(21)
λ
1
=
o
=
V
A
,
V
A
1
,
V
B
1
,
V
B
,
V
B
3
,
V
C
3
,
V
C
=
d
,
λ
2
=
o
=
V
A
,
V
A
2
,
V
B
2
,
V
B
,
V
B
3
,
V
C
3
,
V
C
=
d
, after the termination of the LET-Path Algorithm 1. Each sequence of dashed-line arrows in Figure 4 gives travel times along a nondominated path in the corresponding scenario. Note that each path corresponds to a choice of routes and each sequence of dashed-line arrows corresponds to a choice of trips as shown in Table 2.Figure 4
Illustration of vector labels at nodes in the graph shown in Figure2 after the termination of LET-Path algorithm. In each vector label, each value at t
f is the number of transfers, and each value at each of the scenarios q
1, q
2, q
3 is the travel time of path from origin V
A to the current node in that scenario. Each sequence of solid arrows from origin to destination represents o-d path, and each sequence of dashed-line arrows represents the travel times from origin to intermediate nodes along the path in each scenario.Table4 gives the summary of the obtained LET o-d paths with respect to subsets Ω of Q. As the relationship shown in Figure 3, the set of nondominated o-d paths over Q is the superset of all sets of nondominated o-d paths over Ω
⊆
Q and also contains the fastest o-d paths when each of scenarios q
1, q
2, and q
3 occurs.Table 4
Summary of nondominatedo-d path sets and LET o-d paths in the graph shown in Figure 2 with respect to subsets Ω of Q.
Scenario setΩ
Nondominatedo-d path set
LETo-d path λ
∗
T
λ
∗
(
d
,
t
,
Ω
)
q
1
λ
1
λ
1
11
q
2
λ
1
λ
1
12
q
3
λ
2
λ
2
10
q
1
,
q
2
λ
1
λ
1
11.5
q
1
,
q
3
λ
1
,
λ
2
λ
2
12
q
2
,
q
3
λ
1
,
λ
2
λ
2
12
q
1
,
q
2
,
q
3
λ
1
,
λ
2
λ
2
12.66


## 4.1. Problem Definition

The LET path problem in this paper is studied from one origin nodeo
∈
N for a fixed departure time t to all destination nodes v
∈
N over a scenario set Ω
⊆
Q. The criteria used for evaluating a path include the number of transfers and the expected total travel time across the set of scenarios Ω.Letτ
λ
q
(
u
,
t
) be the travel time on o-u path λ, u
∈
N, in scenario q
∈
Ω. Let us consider o-v path λ
′ that is expanded from o-u path λ via arc 〈
u
,
v
〉
∈
A, denoted by λ
′
=
λ
♢
〈
u
,
v
〉. The relationship between travel time on path λ
′ and that of its subpath λ for departure time t in scenario q is given by(12)
τ
λ
′
q
v
,
t
=
τ
λ
q
u
,
t
+
τ
u
v
q
t
+
τ
λ
q
u
,
t
,where τ
u
v
q
(
t
) is the time weight on arc 〈
u
,
v
〉 at time t. Depending on the type of arc 〈
u
,
v
〉, arc weight τ
u
,
v
q
(
t
) is determined by one of (7), (8), (9), and (10). When Assumption (3) holds, the expected (mean) travel time of o-v path λ
′ with departure time t over scenario set Ω, denoted by T
λ
′
(
v
,
t
,
Ω
), is given by(13)
T
λ
′
v
,
t
,
Ω
=
1
∑
q
∈
Ω
p
q
∑
q
∈
Ω
τ
λ
′
q
v
,
t
p
q
,where p
q is the occurrence probability of scenario q and T
λ
′
(
o
,
t
,
Ω
)
=
0.We also have the relationship between the number of transfers on pathλ
′, that is, f
λ
′
(
v
), and the number of transfers on its subpath λ, that is, f
λ
(
u
), in the following:(14)
f
λ
′
v
=
f
u
v
+
f
λ
u
,where weight f
u
v for the number of transfers on arc 〈
u
,
v
〉 is given by (11), and f
λ
′
(
o
)
=
0.From the transit travelers’ perspective, it is more useful that we aim to minimize the number of transfers first and then the expected travel time across the scenario set. The LET path is given by Definition2.Definition 2 (LETo-v path).
The LETo-v path λ
∗ with departure time t
∈
T over scenario set Ω
⊆
Q, ∀
v
∈
N, is given by(15)
λ
∗
=
a
r
g
m
i
n
λ
∈
P
o
v
T
λ
v
,
t
,
Ω
,
s.t.
f
λ
∗
v
=
min
λ
∈
P
ov
⁡
f
λ
v
.


## 4.2. Dominance Condition

A LETo-v path problem with departure time t
∈
T over scenario set Ω
∈
Q defined in (15) can be solved by enumerating all possible o-v paths P
o
v and then minimizing the number of transfers and the expected travel time of each o-v path in P
o
v for departure time t over Ω using (12) and (14). Such a brute force algorithm is inefficient. We therefore propose a dominance condition by which the optimal LET path is satisfied. First, we define a dominance condition in Definition 3. Then, the LET o-v path for departure time t over scenario set Ω is found in the set of nondominated o-v paths at time t over Ω by Proposition 4.Note that the dominance condition in Definition3 is not asstrict as the one with at least one scenario q
∈
Q such that τ
λ
′
q
v
,
t
<
τ
λ
q
(
v
,
t
). This is because, in the constructed graph described in Section 3.2, there might exist many nondominated paths, which present the same choice of routes and are only different from each other in transfer locations.Definition 3 (nondominatedo-v path).
Given a departure timet
∈
T, o-v path λ
′, ∀
v
∈
N, dominates another o-v path over the scenario set Ω
⊆
Q, if(16)
f
λ
′
v
<
f
λ
v
,
o
r
(17)
f
λ
′
v
=
f
λ
v
,
τ
λ
′
q
v
,
t
≤
τ
λ
q
v
,
t
,
∀
q
∈
Ω
. Then o-v path λ
′ is nondominated in P
o
v for departure time t over scenario set Ω if λ
′ is not dominated by any o-v path at time t over Ω.Proposition 4.
Given a departure timet
∈
T and a set of scenarios Ω
⊆
Q, the LET o-v path at time t over Ω, ∀
v
∈
N, belongs to the set of nondominated o-v paths at time t over Ω.By Definition3, the problem of determining nondominated o-d paths can be treated as multicriteria shortest path problem with (
Q
+
1
) independent criteria, namely, number of transfers, as well as travel times corresponding to Q scenarios. Theorem 7 below implies that Bellman’s principle of optimality is valid when nondominated paths are defined with respect to their nondominated subpaths. We later develop a forward label-correcting algorithm to solve the LET path problem based on Theorem 7. Note that Theorem 7 is established on the grounds of Lemmas 5 and 6, being only valid when Assumptions (1) and (2) hold.Lemma 5.
For any given arc〈
u
,
v
〉
∈
A, f
u
v
≥
0, and τ
u
v
q
(
t
)
≥
0, ∀
t
∈
T, ∀
q
∈
Q.Lemma 6.
For any given arc〈
u
,
v
〉
∈
A, if t
1
≤
t
2, (18)
t
1
+
τ
u
v
q
t
1
≤
t
2
+
τ
u
v
q
t
2
,
∀
t
1
,
t
2
∈
T
,
∀
q
∈
Q
.Theorem 7.
Given departure timet
∈
T and a set of scenarios Ω
⊆
Q, every nondominated o-v path λ
∗ is made up from nondominated o-u subpaths, where u is any intermediate node on path λ.


## 4.3. Relationship between Nondominated, LET, and the Fastest Paths

Definition 8 (the fastesto-v path).
Given departure timet
∈
T and scenario q
∈
Q, the fastest o-v path γ
∗ at time t in scenario q, ∀
v
∈
N, is given by(19)
γ
∗
=
a
r
g
m
i
n
λ
∈
P
o
v
τ
λ
q
v
,
t
,
s.t.
f
γ
∗
v
=
m
i
n
λ
∈
P
o
v
f
λ
v
.Proposition 9.
Given the fastesto-v path γ
∗ at time t in scenario q
∈
Q, ∀
v
∈
N, and a set of nondominated o-v paths at time t over the scenario set Ω
⊆
Q, if q
∈
Ω, γ
∗ belongs to the set of nondominated o-v paths at time t over Ω.Proposition 10.
Given departure timet and two sets of scenarios Ω
,
Ω
′
⊆
Q, if Ω
⊆
Ω
′, the set of nondominated o-v paths at time t over Ω is a subset of the set of nondominated o-v paths at time t over Ω
′, ∀
v
∈
N.By Propositions4, 9, and 10, we can establish the relationship between nondominated, LET, and the fastest o-v paths for departure time t over universal scenario set Q and its subset Ω as shown in Figure 3. By determining the set of nondominated o-v paths over the universal scenario set Q at departure time t, we can obtain LET o-v path at time t over any subset of Q. The relationship is beneficial when prejourney online information is used to determine these subsets.Figure 3
The relationship between nondominated and LET and the fastesto-v paths for departure time t over the universal scenario set Q and its subset Ω.


## 4.4. Label-Correcting Algorithm

The algorithm for determining the LET paths is based on the link-based approach, using the optimality condition stated in Theorem7, which is only valid as Assumptions (1) and (2) hold. Since the proposed approach helps avoid enumerating all possible origin-destination paths, it is feasible in real-time applications. Note that Theorem 7 can be still valid with simple modifications in the dominance condition when other criteria, such as fare and walking distance, are taken into account as long as the arc weights for these criteria are positive and time-independent. Consequently, we can incorporate travelers’ weightings on different criteria, such as number of transfers, total travel time, fare, and walking distance, in the routing process.Nevertheless, one drawback of our approach is that it does not allow taking into account travelers’ weightings on different time components, such as boarding time and in-vehicle travel time, since the arc weights for these time components are time-dependent. Several works in literature solved this issue using the path enumeration method [27, 28] or the branch and bound method [8]. However, these solution approaches are infeasible for real-time applications, especially in stochastic transit networks herein considering the stochastic correlation among stop times of transit vehicles. Our proposed algorithm is developed as follows.Given departure timet, for each node u
∈
N and each o-u path λ, the algorithm maintains a vector label (20)
Λ
λ
u
=
f
λ
u
,
τ
λ
q
u
,
t
,
∀
q
∈
Q
. Let L
(
u
) be the set of nondominated labels corresponding to the set of nondominated o-u paths at time t over the set of scenarios Q. According to Theorem 7, each label Λ
λ
(
u
)
∈
L
(
u
) contains the information of nondominated o-u path λ that has potential to be a nondominated origin-destination path at time t over Q when the algorithm terminates, where label Λ
λ
(
u
) is nondominated in L
(
u
) at time t over Q if λ is a nondominated o-u path at time t over Q (see Definition 3).At each iteration of the algorithm, labelΛ
λ
(
u
) is selected from queue X that contains a nondominated candidate path λ. Path λ is expanded via arc 〈
u
,
v
〉
∈
A. Depending on the type of arc 〈
u
,
v
〉, a temporary label Λ
λ
′
(
v
) for path λ
′
=
λ
♢
〈
u
,
v
〉 is constructed with weights calculated by (12) and (14). To determine if a new label Λ
λ
′
(
v
) is nondominated, it is compared with the nondominated labels L
(
v
) at node v. Details for the algorithm are presented in Algorithm 1.Algorithm 1:LET-Path search.
Input:  the origin o, the destination d, the departure time t, and the universal set of scenarios Q
Output: the LET o-d path at time t over Ω
⊆
Q, where Ω is the realized scenarios at time t
(1)    Create an initial path λ
0 with the origin node o;
(2)    L
(
u
)
=
∅ for all u
∈
N;
(3)    Create label Λ
λ
0
(
o
) with τ
λ
0
q
(
o
,
t
)
=
0, ∀
q
∈
Q, and f
λ
0
(
o
)
=
0;
(4)    L
o
=
Λ
λ
0
o;
(5)    X
=
Λ
λ
0
o;
(6)    while
Q
≠
∅
do
(7)      Extract and remove a label Λ
λ
(
u
) from queue X;
(8)      for
v
∈
Γ
(
u
)
,
Γ
(
u
)
=
{
v
:
〈
u
,
v
〉
∈
A
}
do
(9)       Create a new path λ
′
=
λ
♢
〈
u
,
v
〉;
(1
0)    Depending on the type of 〈
u
,
v
〉, calculate travel time weight τ
u
v
q
(
t
), ∀
q
∈
Q, using one of  (7)–(10), and calculate
transfer weightf
u
v using  (11);
(11)    Calculate τ
λ
′
q
(
v
,
t
), ∀
q
∈
Q, using (12), and calculate f
λ
′
(
v
) using (14);
(1
2)    Create a new label Λ
λ
′
(
v
) with f
λ
′
(
v
), and τ
λ
′
q
(
v
,
t
), ∀
q
∈
Q;
(1
3)    if label Λ
λ
′
(
v
) is non-dominated in L
(
v
)
then
(1
4)     Remove all labels Λ
λ
′
′
(
v
)
∈
L
(
v
) dominated by Λ
λ
′
(
v
);
(1
5)     L
v
=
L
v
∪
Λ
λ
′
v;
(1
6)     X
=
X
∪
Λ
λ
′
v;
(1
7) Let Ω
⊆
Q be the scenarios realized at time t;
(1
8) Apply (13) and (15) for the set of non-dominated paths L
(
d
) over the set of scenarios Ω to obtain the LET o-d path;Algorithm1 is equivalent to multicriteria shortest path algorithm for (
Q
+
1
) independent criteria and terminates after a finite number of steps with a set of nondominated paths at each node [38]. The algorithm is computationally intractable as the number of nondominated paths examined by the algorithm grows exponentially in the worst case [39]. However, the experiments in Section 5 show that the number of examined nondominated paths in a typical transit network is much smaller than that of the worst case.


## 4.5. Illustrative Example

Consider the transit network in Figure1 and its schedules as shown in Table 1. The time-dependent graph and its arc times are shown in Figure 2 and Table 3, respectively, with boarding penalty ε
¯
r
i
k
=
1 and alighting penalty ε
_
r
i
k
=
0. Figure 4 shows nondominated vector labels at all nodes in the time-dependent graph for origin node o
=
V
A, destination node d
=
V
C, and departure time t
=
0 over the universal scenario set Q
=
{
q
1
,
q
2
,
q
3
} and two nondominated o-d paths:(21)
λ
1
=
o
=
V
A
,
V
A
1
,
V
B
1
,
V
B
,
V
B
3
,
V
C
3
,
V
C
=
d
,
λ
2
=
o
=
V
A
,
V
A
2
,
V
B
2
,
V
B
,
V
B
3
,
V
C
3
,
V
C
=
d
, after the termination of the LET-Path Algorithm 1. Each sequence of dashed-line arrows in Figure 4 gives travel times along a nondominated path in the corresponding scenario. Note that each path corresponds to a choice of routes and each sequence of dashed-line arrows corresponds to a choice of trips as shown in Table 2.Figure 4
Illustration of vector labels at nodes in the graph shown in Figure2 after the termination of LET-Path algorithm. In each vector label, each value at t
f is the number of transfers, and each value at each of the scenarios q
1, q
2, q
3 is the travel time of path from origin V
A to the current node in that scenario. Each sequence of solid arrows from origin to destination represents o-d path, and each sequence of dashed-line arrows represents the travel times from origin to intermediate nodes along the path in each scenario.Table4 gives the summary of the obtained LET o-d paths with respect to subsets Ω of Q. As the relationship shown in Figure 3, the set of nondominated o-d paths over Q is the superset of all sets of nondominated o-d paths over Ω
⊆
Q and also contains the fastest o-d paths when each of scenarios q
1, q
2, and q
3 occurs.Table 4
Summary of nondominatedo-d path sets and LET o-d paths in the graph shown in Figure 2 with respect to subsets Ω of Q.
Scenario setΩ
Nondominatedo-d path set
LETo-d path λ
∗
T
λ
∗
(
d
,
t
,
Ω
)
q
1
λ
1
λ
1
11
q
2
λ
1
λ
1
12
q
3
λ
2
λ
2
10
q
1
,
q
2
λ
1
λ
1
11.5
q
1
,
q
3
λ
1
,
λ
2
λ
2
12
q
2
,
q
3
λ
1
,
λ
2
λ
2
12
q
1
,
q
2
,
q
3
λ
1
,
λ
2
λ
2
12.66


## 5. Experiments

In this section we conduct large numerical experiments aiming to investigate (1) the average running time of the proposed LET-Path algorithm; (2) the set of nondominatedo-d paths; and (3) the robustness of LET paths in the presence of unknown scenarios.


### 5.1. Experiment Setups

The experiments are conducted on Ho Chi Minh City (HCMC) bus network (Figure5). The network consists of 1,340 stops, 40 routes, and 1,445 physical links, that is, direct links connecting pairs of consecutive stops on routes. Walking shortcuts are available between stops in a radius of less than 500 meters, and the average walking speed is approximately 2 km/h. Intervals between consecutive trips are 15 minutes and scheduled stop times are generated from 7:00 am to 4:00 pm. The graph model has 5,943 nodes and 13,227 arcs with boarding penalty ε
¯
r
i
k
=
1 minute and alighting penalty ε
_
r
i
k
=
0 minutes.Figure 5
The experimental area of HCMC bus network that consists of 1,340 stops (red), 40 routes (blue), and 1,445 direct stop links.The data set for experiments is made up from 500 random user requests(
o
,
d
,
t
) where o-d pairs are generated randomly with the constraint that the distance between origin and destination is at least 5 km, and departure time t is generated from 7:30 am 1:00 pm to make sure that path times are not later than the ending time at 4:00 pm. The experimental environment is 2.6 GHz dual-core Intel Xeon ES405 2.00 Hz, 3 GB RAM, on CentOS under Java Runtime Environment 1.6 (JRE 1.6) and MySQL 5.2 database.For studying the robustness of the proposed scenario-based approach, we compare the path found by our approach with that of certain equivalence (CE) approximation [5], in which stop times of transit vehicles are deterministic.The CE approximation replaces every stop time random variable by its expected value over the margin distribution. In particular, the expected stop time for theith trip at the kth stop on route r over the scenario set Ω
⊆
Q is calculated by(22)
E
X
r
i
k
Ω
=
1
∑
q
∈
Ω
p
q
∑
q
∈
Ω
θ
r
i
k
q
p
q
,where X
r
i
k
Ω is the independent random stop time for the ith trip at the kth stop on route r over Ω. Thus, the stochastic network with Q scenarios is transformed into a deterministic network with only one scenario.So far, we assume that exact information on the probability distribution of stop times is not available, and therefore it is impossible to build a sufficient number of scenarios that can precisely describe the uncertainty of schedules. Suppose thatq
∈
Q is the unknown scenario that will actually happen and Ω
=
Q
∖
{
q
} is the set of known scenarios. For a given o-d pair and departure time t, let λ
∗ and γ
∗ be the LET o-d path at time t over scenarios Ω and the fastest o-d path at time t in scenario q, where paths λ
∗ and γ
∗ are given by (19) and (15), respectively. Then, when scenario q actually happens, the desired optimal path will be γ
∗. However, since only scenario set Ω is known, the proposed approach is robust if the expected travel time of path λ
∗ does not deviate much from that of path γ
∗. Hence, the robustness of proposed approach is evaluated using the deviation of travel times of paths λ
∗ and γ
∗ in all unknown scenarios q
∈
Q for all triples (
o
,
d
,
t
). The evaluated criteria (or considered performance metrics) are as follows:(1)
Precision, the ratio between the number of cases in which LETo-d path λ
∗ is also the fastest o-d path γ
∗ and the number of total cases.
(2)
Mean absolute percentage error (MAPE), the average deviation percentage between the actual and expected travel time of the LETo-d path λ
∗.
(3)
The fastest path mean absolute percentage error (FMAPE), the average deviation percentage between the actual travel time of the fastesto-d path γ
∗ and the actual travel time of LET o-d path λ
∗.The metrics Precision, MAPE, and FMAPE are given by(23)
P
r
e
c
i
s
i
o
n
=
1
Q
N
∑
o
,
d
,
t
∑
q
∈
Q
m
τ
γ
∗
q
d
,
t
,
τ
λ
∗
q
d
,
t
,where m
x
,
y
=
1 if x
=
y and m
(
x
,
y
)
=
0 otherwise, and(24)
M
A
P
E
=
1
Q
N
∑
o
,
d
,
t
∑
q
∈
Q
T
λ
∗
d
,
t
,
Ω
-
τ
λ
∗
q
d
,
t
τ
λ
∗
q
d
,
t
,
F
M
A
P
E
=
1
Q
N
∑
o
,
d
,
t
∑
q
∈
Q
τ
γ
∗
q
d
,
t
-
τ
λ
∗
q
d
,
t
τ
λ
∗
q
d
,
t
,where N is number of triples (
o
,
d
,
t
) being experimented, and Ω
=
Q
∖
{
q
}.


### 5.2. Schedule Generations

To generate scheduled stop times of transit vehicles (or buses), for each time intervalt
∈
T and each scenario q
∈
Q, a direct link between two stops s and s
′ is assigned a random integer speed v
(
s
,
s
′
,
t
,
q
), which follows the normal probability distribution ~ N
(
μ
=
18
,
σ
2
=
5
2
) km/h. The number of generated scenarios is Q
=
400, which is equivalent to 400 days of tracking trajectories of all buses in the network, and the scenarios are assumed to be uniformly distributed. The stop time for the ith trip at the (
k
+
1
)th stop on route r in scenario q is calculated by(25)
θ
r
i
,
k
+
1
q
=
θ
r
i
k
q
+
d
S
k
r
,
S
k
+
1
r
v
S
k
r
,
S
k
+
1
r
,
θ
r
i
k
q
,
q
,
1
<
k
≤
K
r
,where d
(
s
,
s
′
) is the travel distance between stops s and s
′ and stop time θ
r
i
(
1
)
q is a perscheduled value at the begining of the trip. Assumption (1) is always true with (25). To make sure Assumption (2) holds, we use the following constraint for each time a new stop time is being calculated by (25):(26)
θ
r
,
i
+
1
,
k
q
=
max
⁡
θ
r
i
k
q
,
θ
r
,
i
+
1
,
k
q
.Figures 6(a) and 6(b) plot trajectories generated for one trip under 400 scenarios and for all trips in one scenario, respectively.Figure 6
Illustration of generated stop times.
(a)
Trajectories for one trip in all 400 scenarios
(b)
Trajectories for all trips in one scenario from 7:00 am to 4:00 pmNote that no stochastic dependency is applied to stop time generations and link speeds independently fluctuate within a range[
3,33
] km/h underpinned by the normal distribution ~ N
(
μ
=
18
,
σ
2
=
5
2
). However, by (25) and (26), only stop times of trips on the same route or on routes with shared links are correlated which is also observable in practice.


### 5.3. Results

To give an overview of LET paths found in the experiments, we first examine the impact of different sets of scenarios on LETo-d paths. We conduct the experiments on random subsets of the universal scenario set Q with different numbers of sampled scenarios being 1,50
,
…
,
400. Table 5 shows that, due to (15), numbers of transfers of LET o-d paths are always minimized and do not depend on the scenario set. This also implies that the number of transfers of LET o-d path only depends on the topology of the network. Similarly, different subsets of Q do not cause significant impacts on waiting times, as well as travel and walking distances.Table 5
Summary of experimental results of LET paths with different subsets ofQ.
Number of scenarios
1
50
100
150
200
250
300
350
400
Expected travel time (min)
68.10
69.90
70.78
71.18
71.25
71.54
71.62
71.83
71.92
Travel time standard deviation (min)
0
6.19
6.40
6.41
6.42
6.46
6.46
6.52
6.50
Number of transfers
1.98
1.98
1.98
1.98
1.98
1.98
1.98
1.98
1.98
Waiting time (min) per transfer
6.16
7.63
7.66
7.73
7.72
7.81
7.79
7.78
7.81
Travel distance (meter)
12,285
12,658
12,845
12,949
12,943
12,988
13,008
13,059
13,067
Walking distance (meter)
267
253
252
248
249
250
252
254
255For investigating the average running time of LET-Path algorithm, Figures7 and 8 show the average running time of the LET-Path algorithm and the average number of nondominated paths at all nodes after the termination of algorithm. Note that the algorithm finds nondominated paths from one origin to all nodes. Hence, the running time of the algorithm increases when the number of nondominated paths at each node increases. In particular, as the scenario set increases, by Definition 3 the condition for a path dominated by another path in all scenarios is looser. This results in an increase in the number of nondominated paths. The results also show that the number of nondominated paths generated is not exponential as proved in the worst case, and running times are feasible for real-time applications.Figure 7
Average CPU running time of the LET-Path algorithm with different subsets ofQ per o-d pair.Figure 8
Average number of nondominated paths generated by the LET-Path algorithm with different subsets ofQ per o-d pair.For studying the impact of scenario sets on the number of nondominatedo-d paths, Figure 9 shows that the number of nondominated o-d paths is proportional to the size of scenario set. The result also comes from the looser dominance condition when the size of the scenario set increases.Figure 9
Average number of nondominatedo-d paths per o-d pair.Table6 compares the robustnesses of scenario-based approach and the certain equivalence approach. The results show that scenario-based approach is superior to the certain equivalence approach in all the evaluated criteria, namely, Precision, MAPE, and FMAPE. In addition, despite a high MAPE (
8.52
%
), which is still less than that of certain equivalence approach (11.59
%), the difference between actual travel time of the LET o-d path and that of the fastest o-d path for the same departure time and scenario set is only 1.82
%, and in up to 86.58
% of queries the LET o-d path is also the fastest o-d path. Although scenario-based approach produces a large error in travel time prediction (
8.52
%
) when the actual scenario is unknown, the travel time of found LET o-d path and the travel time of the fastest path in the actual scenario do not deviate much (1.82%). These results prove that LET o-d paths are robust even when the actual scenario is unknown.Table 6
Comparison of robustnesses of scenario-based (SB) and certain equivalence (CE) approach.
CE
SB
Avg. expected travel time of LET paths
66.63 min
67.82 min
Avg. actual travel time of LET paths
72.37 min
68.31 min
Precision
66.04%
86.58%
MAPE
11.59%
8.52%
FMAPE
8.22%
1.82%


## 5.1. Experiment Setups

The experiments are conducted on Ho Chi Minh City (HCMC) bus network (Figure5). The network consists of 1,340 stops, 40 routes, and 1,445 physical links, that is, direct links connecting pairs of consecutive stops on routes. Walking shortcuts are available between stops in a radius of less than 500 meters, and the average walking speed is approximately 2 km/h. Intervals between consecutive trips are 15 minutes and scheduled stop times are generated from 7:00 am to 4:00 pm. The graph model has 5,943 nodes and 13,227 arcs with boarding penalty ε
¯
r
i
k
=
1 minute and alighting penalty ε
_
r
i
k
=
0 minutes.Figure 5
The experimental area of HCMC bus network that consists of 1,340 stops (red), 40 routes (blue), and 1,445 direct stop links.The data set for experiments is made up from 500 random user requests(
o
,
d
,
t
) where o-d pairs are generated randomly with the constraint that the distance between origin and destination is at least 5 km, and departure time t is generated from 7:30 am 1:00 pm to make sure that path times are not later than the ending time at 4:00 pm. The experimental environment is 2.6 GHz dual-core Intel Xeon ES405 2.00 Hz, 3 GB RAM, on CentOS under Java Runtime Environment 1.6 (JRE 1.6) and MySQL 5.2 database.For studying the robustness of the proposed scenario-based approach, we compare the path found by our approach with that of certain equivalence (CE) approximation [5], in which stop times of transit vehicles are deterministic.The CE approximation replaces every stop time random variable by its expected value over the margin distribution. In particular, the expected stop time for theith trip at the kth stop on route r over the scenario set Ω
⊆
Q is calculated by(22)
E
X
r
i
k
Ω
=
1
∑
q
∈
Ω
p
q
∑
q
∈
Ω
θ
r
i
k
q
p
q
,where X
r
i
k
Ω is the independent random stop time for the ith trip at the kth stop on route r over Ω. Thus, the stochastic network with Q scenarios is transformed into a deterministic network with only one scenario.So far, we assume that exact information on the probability distribution of stop times is not available, and therefore it is impossible to build a sufficient number of scenarios that can precisely describe the uncertainty of schedules. Suppose thatq
∈
Q is the unknown scenario that will actually happen and Ω
=
Q
∖
{
q
} is the set of known scenarios. For a given o-d pair and departure time t, let λ
∗ and γ
∗ be the LET o-d path at time t over scenarios Ω and the fastest o-d path at time t in scenario q, where paths λ
∗ and γ
∗ are given by (19) and (15), respectively. Then, when scenario q actually happens, the desired optimal path will be γ
∗. However, since only scenario set Ω is known, the proposed approach is robust if the expected travel time of path λ
∗ does not deviate much from that of path γ
∗. Hence, the robustness of proposed approach is evaluated using the deviation of travel times of paths λ
∗ and γ
∗ in all unknown scenarios q
∈
Q for all triples (
o
,
d
,
t
). The evaluated criteria (or considered performance metrics) are as follows:(1)
Precision, the ratio between the number of cases in which LETo-d path λ
∗ is also the fastest o-d path γ
∗ and the number of total cases.
(2)
Mean absolute percentage error (MAPE), the average deviation percentage between the actual and expected travel time of the LETo-d path λ
∗.
(3)
The fastest path mean absolute percentage error (FMAPE), the average deviation percentage between the actual travel time of the fastesto-d path γ
∗ and the actual travel time of LET o-d path λ
∗.The metrics Precision, MAPE, and FMAPE are given by(23)
P
r
e
c
i
s
i
o
n
=
1
Q
N
∑
o
,
d
,
t
∑
q
∈
Q
m
τ
γ
∗
q
d
,
t
,
τ
λ
∗
q
d
,
t
,where m
x
,
y
=
1 if x
=
y and m
(
x
,
y
)
=
0 otherwise, and(24)
M
A
P
E
=
1
Q
N
∑
o
,
d
,
t
∑
q
∈
Q
T
λ
∗
d
,
t
,
Ω
-
τ
λ
∗
q
d
,
t
τ
λ
∗
q
d
,
t
,
F
M
A
P
E
=
1
Q
N
∑
o
,
d
,
t
∑
q
∈
Q
τ
γ
∗
q
d
,
t
-
τ
λ
∗
q
d
,
t
τ
λ
∗
q
d
,
t
,where N is number of triples (
o
,
d
,
t
) being experimented, and Ω
=
Q
∖
{
q
}.


## 5.2. Schedule Generations

To generate scheduled stop times of transit vehicles (or buses), for each time intervalt
∈
T and each scenario q
∈
Q, a direct link between two stops s and s
′ is assigned a random integer speed v
(
s
,
s
′
,
t
,
q
), which follows the normal probability distribution ~ N
(
μ
=
18
,
σ
2
=
5
2
) km/h. The number of generated scenarios is Q
=
400, which is equivalent to 400 days of tracking trajectories of all buses in the network, and the scenarios are assumed to be uniformly distributed. The stop time for the ith trip at the (
k
+
1
)th stop on route r in scenario q is calculated by(25)
θ
r
i
,
k
+
1
q
=
θ
r
i
k
q
+
d
S
k
r
,
S
k
+
1
r
v
S
k
r
,
S
k
+
1
r
,
θ
r
i
k
q
,
q
,
1
<
k
≤
K
r
,where d
(
s
,
s
′
) is the travel distance between stops s and s
′ and stop time θ
r
i
(
1
)
q is a perscheduled value at the begining of the trip. Assumption (1) is always true with (25). To make sure Assumption (2) holds, we use the following constraint for each time a new stop time is being calculated by (25):(26)
θ
r
,
i
+
1
,
k
q
=
max
⁡
θ
r
i
k
q
,
θ
r
,
i
+
1
,
k
q
.Figures 6(a) and 6(b) plot trajectories generated for one trip under 400 scenarios and for all trips in one scenario, respectively.Figure 6
Illustration of generated stop times.
(a)
Trajectories for one trip in all 400 scenarios
(b)
Trajectories for all trips in one scenario from 7:00 am to 4:00 pmNote that no stochastic dependency is applied to stop time generations and link speeds independently fluctuate within a range[
3,33
] km/h underpinned by the normal distribution ~ N
(
μ
=
18
,
σ
2
=
5
2
). However, by (25) and (26), only stop times of trips on the same route or on routes with shared links are correlated which is also observable in practice.


## 5.3. Results

To give an overview of LET paths found in the experiments, we first examine the impact of different sets of scenarios on LETo-d paths. We conduct the experiments on random subsets of the universal scenario set Q with different numbers of sampled scenarios being 1,50
,
…
,
400. Table 5 shows that, due to (15), numbers of transfers of LET o-d paths are always minimized and do not depend on the scenario set. This also implies that the number of transfers of LET o-d path only depends on the topology of the network. Similarly, different subsets of Q do not cause significant impacts on waiting times, as well as travel and walking distances.Table 5
Summary of experimental results of LET paths with different subsets ofQ.
Number of scenarios
1
50
100
150
200
250
300
350
400
Expected travel time (min)
68.10
69.90
70.78
71.18
71.25
71.54
71.62
71.83
71.92
Travel time standard deviation (min)
0
6.19
6.40
6.41
6.42
6.46
6.46
6.52
6.50
Number of transfers
1.98
1.98
1.98
1.98
1.98
1.98
1.98
1.98
1.98
Waiting time (min) per transfer
6.16
7.63
7.66
7.73
7.72
7.81
7.79
7.78
7.81
Travel distance (meter)
12,285
12,658
12,845
12,949
12,943
12,988
13,008
13,059
13,067
Walking distance (meter)
267
253
252
248
249
250
252
254
255For investigating the average running time of LET-Path algorithm, Figures7 and 8 show the average running time of the LET-Path algorithm and the average number of nondominated paths at all nodes after the termination of algorithm. Note that the algorithm finds nondominated paths from one origin to all nodes. Hence, the running time of the algorithm increases when the number of nondominated paths at each node increases. In particular, as the scenario set increases, by Definition 3 the condition for a path dominated by another path in all scenarios is looser. This results in an increase in the number of nondominated paths. The results also show that the number of nondominated paths generated is not exponential as proved in the worst case, and running times are feasible for real-time applications.Figure 7
Average CPU running time of the LET-Path algorithm with different subsets ofQ per o-d pair.Figure 8
Average number of nondominated paths generated by the LET-Path algorithm with different subsets ofQ per o-d pair.For studying the impact of scenario sets on the number of nondominatedo-d paths, Figure 9 shows that the number of nondominated o-d paths is proportional to the size of scenario set. The result also comes from the looser dominance condition when the size of the scenario set increases.Figure 9
Average number of nondominatedo-d paths per o-d pair.Table6 compares the robustnesses of scenario-based approach and the certain equivalence approach. The results show that scenario-based approach is superior to the certain equivalence approach in all the evaluated criteria, namely, Precision, MAPE, and FMAPE. In addition, despite a high MAPE (
8.52
%
), which is still less than that of certain equivalence approach (11.59
%), the difference between actual travel time of the LET o-d path and that of the fastest o-d path for the same departure time and scenario set is only 1.82
%, and in up to 86.58
% of queries the LET o-d path is also the fastest o-d path. Although scenario-based approach produces a large error in travel time prediction (
8.52
%
) when the actual scenario is unknown, the travel time of found LET o-d path and the travel time of the fastest path in the actual scenario do not deviate much (1.82%). These results prove that LET o-d paths are robust even when the actual scenario is unknown.Table 6
Comparison of robustnesses of scenario-based (SB) and certain equivalence (CE) approach.
CE
SB
Avg. expected travel time of LET paths
66.63 min
67.82 min
Avg. actual travel time of LET paths
72.37 min
68.31 min
Precision
66.04%
86.58%
MAPE
11.59%
8.52%
FMAPE
8.22%
1.82%


## 6. Conclusions

The LET path problem, which minimizes the expected travel time between a given origin-destination pair for a given departure time across a set of known scenarios, has been investigated. A dominance condition was established and a formal proof has been provided that Bellman’s principle of optimality is valid with the established dominance condition. An exact label-correcting algorithm was developed based on Bellman’s principle. Comprehensive computational studies have been conducted using the real-size bus network in Ho Chi Minh City (HCMC, Vietnam). The experimental results show that the running time of LET-Path algorithm is suitable for real-time applications and LET paths are robust. However, scenario-based approach has two major issues:(1)
It is impossible to build a sufficient number of scenarios that can precisely describe the uncertainties due to the lack of information on probability distribution of stop times.
(2)
Even if all stop time information is available, the number of scenarios will grow exponentially. In particular,L
∑
r
∈
R
‍
I
r
×
K
r scenarios are required to present all possible scenarios, which are generated from independent stop times, where L is average number of support points of marginal probability distribution of one stop time.For the first issue, the computational results from Table6 proved the robustness of LET paths found by scenario-based approach when unknown scenarios happen. Regarding the second issue, as results shown in Table 5, the number of transfers of a LET path does not depend on the scenario set, but on the network topology, and the average number of transfers is small, that is, approximately 2. In addition, the average size of set of nondominated origin-destination paths over 400 scenarios is less than 6 (Figure 9). That means in average only maximum 2
×
6 routes make up a nondominated origin-destination path set. Hence, for a given origin-destination pair, we can determine the set of routes that cover nondominated origin-destination paths. Then we can treat these routes as an impact area of the origin-destination pair and generate stop time scenarios for this area instead of the complete network.



---

*Source: 7609572-2016-03-13.xml*