Multi-modal Transit Design with Stochastic Demands
Hongyi Jianga∗ , Samitha Samaranayakeaa School of Civil and Environmental Engineering, Cornell University, U.S.

hj348@cornell.edu, samitha@cornell.edu∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 4, 2022
Keywords: multimodal transit, network design, long-term planning, stochastic origin-to-destination
demand1

INTRODUCTION

Transit line-planning is a long standing transportation problem that is getting renewed attention
due to the recent interest in multi-modal transit systems that incorporate Mobility-on-Demand(MoD) services. A multi-modal system aims to provide an efficient and cost effective mix oftransportation modes to overcome the limitations of any single mode. One of the major challenges
and opportunities in designing such systems is the fact that part of the system is fixed (e.g.,bus routes are fixed), while the demand responsive MoD component can dynamically adjust todemand uncertainty. There have been a number of recent algorithms proposed to design andoperate such systems Maheo et al. (2019), Pinto et al. (2020), Dalmeijer & Van Hentenryck(2020), Périvier et al. (2021), Banerjee et al. (2021)). However, most of these studies assume
that the underlying travel demand is deterministic, even though the demand is stochastic—
and importantly, a factor that makes multi-modal transit systems with MoD components more
attractive.
This work aims to provide some guidance on how demand uncertainty should be accounted
for with respect to a general class multi-modal transit network planning problems, by providing
theoretical bounds on common approaches used in the literature (without theoretical justification). In particular, we show that when the demand for each origin-to-destination pair follows abounded distribution independent of time and the known information about the distribution is
its expectation and its upper and lower bounds, we can replace the actual (stochastic) demandwith its expectation to approximate the (stochastic) true values as long as the span of planning time length is reasonably long. We also show that this framework can be used to compare
between two different combinations of modes.

2Modeling

Although our framework is generally applicable to many models of transit network design, forclarity and conciseness we illustrate it with one such model in this abstract, specifically a derivative of the ODMTS (On-Demand Multimodal Transit Systems) model from Dalmeijer & Van Hentenryck (2020). Let G = (V, A) with vertices V = {1, . . . , n} and arc set A. Let M be the set of
possible transportation modes, and F be set of the frequency options for transportation modes.
Then a ∈ A is defined by a = (i, j, f, m) ∈ V × V × M × F, ∀i ̸= j.
TRISTAN XI Symposium

Original abstract submittal

H. Jiang, S. Samaranayake

2To design a multi-modal transit network over T time intervals, we need to determine whicharcs are going to be opened to serve passengers over the given time span. Let the decisionvariables be z := (za )a∈A such that za = 1 if a is opened and za = 0 otherwise. Let βa ≥ 0 be
the operating cost for each time interval and a ∈ A, and ca be the travelling cost incurred byone passenger using arc a within one time interval.
Once z is fixed, a passenger’s trip r is routed based on the given network design, her origin
node, destination node and specified routing rules for all the passengers. For example, in theODMTS model, one of the rules is that each passenger can use at most K arcs in G, where K
is a fixed positive integer. Then let R be the set of all passenger trips, and let each trip r ∈ R
be defined by (o(r), d(r)) ∈ V × V , where o(r) is the origin of r, d(r) is a destination of r. Notethat here we assume the route for r is a simple path, i.e. each arc a is only traveled once by r.
Also, let pt (r) be the number of passengers on r within time interval t.
Given route planning rules and a network design z, there is a fixed route and travelling cost
RC(z, r) incurred by a passenger of trip r traveling within one time interval. Note that here weimplicitly state that for passengers of the same trip, the corresponding travelling costs are equal.
This is because we assume that each transportation mode has no capacity constraints and therouting rules are applicable to all the passengers. Now we can formulate the whole problem as
the following.

minzTXX

t=1a∈A!
βa za+pt (r)RC(z, r) ,(1a)r

Xs.t.

!
XXf (a)za −a∈δ + (i,m)f (a)za∈δ − (i,m)f (a)za

Xf (a)za = 0∀i ∈ V, m ∈ M(1b)∀i ∈ V, m ∈ M,(1c)∀a ∈ A,(1d)az(i,j,m,f ) ≤ 1

f ∈F,(i,j,m,f )∈Aza ∈ {0, 1}
which is equivalent tominzs.t.

X

β a za +X PT

t=1 pt (r)ra∈AXa∈δ + (i,m)f (a)zTa(2a)Xf (a)za −XRC(z, r),a∈δ − (i,m)f (a)zz(i,j,m,f ) ≤ 1

f (a)za = 0∀i ∈ V, m ∈ M(2b)∀i ∈ V, m ∈ M(2c)∀a ∈ A.

(2d)

af ∈F,(i,j,m,f )∈Aza ∈ {0, 1}

Here (2b) guarantees the in-flow is equal to the out-flow for each mode and each node, and (2c)assures each arc can only adopt one frequency.
Note that the formulation here is different from the one by Dalmeijer & Van Hentenryck(2020) in two aspects: (1) we add time t as a new dimension to our model, (2) routing rules canbe more general here than in ODMTS model in which the number of transfers is restricted, andtrips are routed for minimal costs.
When pt (r) is known for every t and r, we can solve (2) with an exact algorithm or heuristic. However, in real life, pt (r) is usually uncertain (especially when T is large). As we havementioned, in this work we try to deal with the issue caused by the uncertainty. Specifically,
we will assume that pt (r) ∈ [lr , ur ] for ur ≥ lr ≥ 0, and E(pt (r)) is known, and denoted by Er .
Without loss of generality, we can assume pt (r) ∈ [0, u] by setting u = max ur . Note that pt (r)ris independent w.r.t. t but not necessarily w.r.t. r. We also assume that there exists λ > 1 suchthat for each r, λEr ≥ ur .
TRISTAN XI Symposium

Original abstract submittal

H. Jiang, S. Samaranayake

33

Methodology and Results

We will show that under the above assumptions, when T is larger than a threshold polynomialin the input size, the solution of (2) can be approximated well by the following deterministic
optimization problem.

minzX

β a za +Xa∈AXs.t.

Er · RC(z, r),(3a)r

Xf (a)za −X

f (a)za = 0∀i ∈ V, m ∈ M,(3b)∀i ∈ V, m ∈ M,(3c)∀a ∈ A,(3d)a∈δ − (i,m)f (a)zaa∈δ + (i,m)f (a)zaz(i,j,m,f ) ≤ 1

f ∈F,(i,j,m,f )∈Aza ∈ {0, 1}

where Er and RC(z, r) are defined same as in Section 2.
PP PT p (r)For simplicity, let objT (z) := a∈A βa za + r t=1T t RC(z, r), and |R| be the size of the trip
set R.
Our first result shows that as T increases, the solution of (3) converges1 to an optimal solutionof (2).
Theorem 3.1. Let OPTT and OPTE be the optimal values of (2), and (3). Also, let z (T ) :=(T )(E)(za )a∈A and z (E) := (za )a∈A be the optimal solution to (2) and (3). Then we havea.s.

OPTT −→ OPTE
a.s.

objT (z (E) ) − OPTT −→ 0

as T → ∞,(4)

as T → ∞.

(5)

Although the above result shows that the estimation converges to the real optimal value asT increases, it will be unrealistic if T needs to be exponential in the input size of the original
problem to attain a desired error rate. Fortunately, the following results show that T only needs
to be polynomial in the input size so that the approximation is close to the original optimal
solution.
Theorem 3.2. With the same notation as in Theorem 3.1, for 0 < α ≤ 1, we havenPobjT (z(E)) − OPTT ≥ αOPTTo
≤ 2|R| exp −T α2(2(1 + α)|R| + α)2 λ2

.

(6)

Hence for α > 1, we havenPobjT (z(E)) − OPTT ≥ αOPTTo
≤ 2|R| exp −T(4|R| + 1)2 λ2

.

(7)

2
12
Corollary 3.3. Given 0 < δ < 1 and 0 < α ≤ 1, if T ≥ log( 2|R|δ )λ 2(1 + α )R + 1 , we havenP1objT (z (E) ) − OPTT ≥ αOPTTo≤ δ.

(8)

a.s.

Here −→ refers to almost surely convergence.

TRISTAN XI Symposium

Original abstract submittal

H. Jiang, S. Samaranayake

4

In some application scenarios, comparison between different combinations of modes is needed.
For example, a transit agency might be deciding whether to introduce a BRT or light-rail service
in combination with regular bus service and a demand responsive shuttle service. To estimate thecost ratio, we need to estimate the corresponding costs by solving (3) with different transportation
modes constraints, and show that the estimated ratio of costs is close to the true ratio if theestimated solutions are employed. Particularly, we prove the following theorem.
Theorem 3.4. Given A1 , A2 ⊆ A, let OPT1 and OPT2 be the solutions to (3) with added
constraints za = 0 for a ∈ A1 and za = 0 for a ∈ A2 respectively. Let z (1) and z (2) be thecorresponding solutions. Then for α > 0, we have()objT (z (2) ) OPT2
OPT2
α2 TP
≥α
≤ 4|R| exp −(9)−OPT1(2 + α)2 |R|2 λ2
objT (z (1) ) OPT1In Theorem 3.4, A1 and A2 are the sets of arcs that are not considered. Consider the caseof comparing the solution z (1) corresponding to the case when only a subset of transportation
modes M 1 ⊆ M can be selected with the solution z (2) corresponding to only M 2 ⊆ M being
available for adoption. Then we can let A1 be the set of arcs that correspond to the modes notin M 1 , and A2 be the set of arcs that correspond to the modes not in M 2 .
In addition to this concentration result, we can also prove the convergence and a thresholdfor T similar to Theorem 3.1 and Corollary 3.3.
Corollary 3.5. With the same notation as in Theorem 3.4, we haveobjT (z (2) ) a.s. OPT2−→OPT1
objT (z (1) )as T → ∞.

(10)

222
Corollary 3.6. Given 0 < δ < 1 and 0 < α ≤ 1, if T ≥ log( 4|R|δ )λ (1 + α )|R| , we have()objT (z (2) ) OPT2
OPT2P−≥α≤ δ.
(11)
OPT1
objT (z (1) ) OPT1
Remark. At this point, we have shown that the optimal solution to (2) is an estimation withdesired error rate as long as T is polynomially large. However, solving (2) exactly can be timeconsuming. Fortunately, if there is an algorithm or heuristic that returns a near-optimal solutionto (3) with some approximation ratio, then it can be demonstrated that this solution is also anear-optimal solution to (2) with a similar performance guarantee as long as T is polynomial in
the input size of the original problem. We will also conduct numerical experiments in the future.

References
Banerjee, Siddhartha, Hssaine, Chamsi, Luo, Qi, & Samaranayake, Samitha. 2021. Plan Your Systemand Price for Free: Fast Algorithms for Multimodal Transit Operations. Available at SSRN.
Dalmeijer, Kevin, & Van Hentenryck, Pascal. 2020. Transfer-expanded graphs for on-demand multimodaltransit systems. Pages 167–175 of: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer.
Maheo, Arthur, Kilby, Philip, & Van Hentenryck, Pascal. 2019. Benders decomposition for the design ofa hub and shuttle public transit system. Transportation Science, 53(1), 77–88.
Périvier, Noémie, Hssaine, Chamsi, Samaranayake, Samitha, & Banerjee, Siddhartha. 2021. Real-time
Approximate Routing for Smart Transit Systems. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(2), 1–30.
Pinto, Helen KRF, Hyland, Michael F, Mahmassani, Hani S, & Verbas, I Ömer. 2020. Joint design ofmultimodal transit networks and shared autonomous mobility fleets. Transportation Research Part C:
Emerging Technologies, 113, 2–20.

TRISTAN XI Symposium

Original abstract submittal