Sequential transit route design by link expansion
using knowledge gradient with correlated beliefs
Gyugeun Yoon, Joseph Y. J. Chow*
C2SMART University Transportation Center, Tandon School of Engineering, New York University, Brooklyn,NY, USAggyoon@nyu.edu, joseph.chow@nyu.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

January 16, 2022
Keywords: optimal learning, knowledge gradient, sequential route design, correlation, mobility service

1INTRODUCTION

Mobility service route design depends upon identifying the demand level in the potential service regionof the system. In conventional transportation planning, an operator would collect survey data fromtravelers in the region and use that to forecast the demand. However, one of the shortcomings of surveys
is the limited sampling rates. For example, the 2010/2011 Regional Household Travel Survey (RHTS)
of the New York Metropolitan Transportation Council sampled 18,965 households, smaller than theentire population of about 7 million households (Census Reporter, 2021) in the area. In addition, thedataset may not be useful when it comes to emerging transit technologies that have never operated in
the region before, such as modular autonomous vehicle fleets (e.g. Caros and Chow, 2020) or moreelaborate feeder-trunk route systems that make use of various emerging shared mobility options (e.g.
Ma et al., 2019).
Operated routes of a mobility service can act as sensors for valuable data generated during theoperation, including vehicle trajectory, load profile, revealed preferences, ridership, average wait time,and user ratings. Routes should be implemented with explicit consideration of impacts on the service
provided to travelers and the knowledge gained. In this way, an operator can use these data to design
their route system to fit the prevailing demand in a sequential or phased implementation (Yoon andChow, 2020) instead of implementing a single design at once. This explicit consideration of route design
as sensors is called transit service route design with “optimal learning.”
In optimal learning, sequential decisions are made such that the information gained each decisionepoch is optimized to reduce the uncertainty for subsequent decisions. This study proposes a new
approach to design mobility service routes tailored to local demand patterns by adapting a learningbased scheme. Due to the dependence between choices in a network setting, the knowledge gradient(Frazier et al., 2008) could be a suitable method because it does not require an assumption ofindependence between options. However, this can still be problematic because of the way the covariancematrix between different route elements scale up (Ryzhov et al., 2012).
We propose several contributions to resolve this issue for transit route design. First, the proposedframework clarifies how the procedure of sequential route design can be formulated. It also describes
the flow of data to illustrate the inputs required and outputs being developed. Second, different learning
policies are compared based on two performance measures: total covered demand, and optimal choicerate. We study three different learning policies to identify the conditions where one policy is mostappropriate.

TRISTAN XI Symposium

Original abstract submittal

G. Yoon and J.Y.J. Chow

2

METHODOLOGY

2.1

Problem Definition

2First, let us clarify the concepts of “extension” and “expansion” in a transit network. An extension
appends a link to a current route and elongates the route length. After a few observations, newinformation is obtained from users served by that additional link. A route can be built by repeating until
the predefined maximum length. On the contrary, an expansion adds a new route to an existing route set
and improves the coverage of the system. This approach can benefit operators in several ways:
improvement of current knowledge, prompt responses to dynamic demand, and dealing with sequential
budget investments.
Consider a system that is gradually expanded on a network 𝐺(𝑁, 𝐴). Flows of 𝑁(𝑁 − 1) available
OD pairs on 𝐺 are denoted as 𝑥𝑜,𝑑 , where 𝑜 is the origin and 𝑑 the destination. When a 𝑘-th route 𝑅𝑘
consists of 𝑙 nodes, it can serve 𝑙(𝑙 − 1) OD flows alone. This coverage grows if there is another routeintersecting with 𝑅𝑘 , allowing potential passengers to travel further by transfer. For each decision epoch𝑡, a link 𝑎𝑡 is chosen from a set 𝐴𝑡 to append to {𝑅𝑘 }𝑘∈𝐾 , where the set of corresponding nodes 𝑐 𝑡 isdefined as 𝐶 𝑡 ⊂ 𝑁. The algorithm evaluates 𝑎𝑡 by 𝑣𝑎𝑡 , the value of 𝑎𝑡 that consists of stochastic rewardand exploration term that represents the potential benefit of exploration by collecting additional
information from the option. A deterministic version of the network expansion problem is shown in
Fragkos et al. (2021).
𝑎𝑡 ′ = arg max
𝑣 𝑡𝑡𝑡 𝑎(1)𝑎 ∈𝐴

Various policies use different structures of values for the evaluation, and this study compares
Knowledge Gradient (KG), KG with Correlated Belief (KGCB), and Multi-Armed Bandit (MAB).
While these learning algorithms already exist, a network design algorithmic framework is needed tomake use of them properly. In general, 𝑎𝑡 ′, the optimum among available 𝑎𝑡 can be found by Eq. (1).
After the evaluation, 𝑅𝑘 is extended to 𝑎𝑡 ′, and the next extension at 𝑡 + 1 is conducted. This repeats
until the termination criteria are satisfied, and the generation of the next route begins while the budget
remains. For example, if 𝐿 is the maximum number of nodes covered by 𝑅𝑘 , it will have a sequence ofnodes {𝑛𝑅𝑘,1 , 𝑛𝑅𝑘 ,2 , ⋯ , 𝑛𝑅𝑘 ,𝐿 }. The next route 𝑅𝑘+1 will begin from 𝑛𝑅𝑘+1,1 .

2.2

Sequential transit route design algorithmic framework

Figure 1 – Framework of learning-based link-level extension route system design
Figure 1 describes the algorithmic framework. Box 1 represents unknown true reward. Therefore, thesequential route design is initiated with a sampling, i.e. the pilot project(s), to build a base knowledge(or prior) about them, described in Box 2. Box 3 show a designation of the first node to initiate link-TRISTAN XI Symposium

Original abstract submittal

G. Yoon and J.Y.J. Chow3

based route extension. During the extension, only links that can be appended to a currently extending
route are included in the set. In Box 4, the illustration shows the aggregation of individual choices tocreate link-level knowledge. It returns to Box 2 until the current route reaches the maximum distance,stopping the extension. Box 5 is the final output of a route extension, and the procedure returns to Box
2 if there are more routes to be designed. Note the difference between the inner and outer loops. The
inner loop in Box 4 is represents simulated scenarios used to feed the learning algorithms to determine
the link expansion in one epoch. The outer loop between Box 2 and 4 is the sequential transit route
extensions conducting over multiple epochs taking place in real time.

2.3

Numerical Experiment

Two sets of numerical experiments are conducted to test the proposed sequential route design
framework: an artificial 10-by-10 grid network and a real-world example based on New York City(NYC) data.
First, the generated grid includes 100 nodes and 360 unidirectional links. The prior mean vector has
9,900 elements, representing the number of observable OD flows on this network (100×99). True mean
OD flows are randomly generated based on a gravity model, defining the amount of OD flow between
two zones as the product of zonal attributes and the inverse of the power of the distance. The true demandis hidden to the operator. Multiple scenarios are established to see the difference between urban settings
and transferability (e.g. monocentric vs polycentric cities). Select comparisons between three learning
policies are shown in Fig. 1.
Second, an experimental network is generated from 55 Public Use Microdata Areas (PUMAs) inNYC. After reviewing the roadway network, 246 links connect 55 nodes in this network shown in Fig.
2(a). The mean OD flows between zones are drawn from the RHTS while their standard deviations andcovariances are randomly assumed. Single transfers are allowed between routes.
Due to the limitation on actual experiments, observed OD flows were randomly drawn fromassumed true values under the assumption that they follow normal distribution but are correlated,
forming a multivariate normal distribution. The covariance matrix of OD flow is also artificially created
but required to be a positive semidefinite matrix to derive multivariate normal random numbers fromgiven mean vector and covariance matrix. Three scenarios are considered: a base scenario, in which OD
pairs in the RHTS having 0 values are assumed to always be 0; a scenario where 0 value OD pairs fromRHTS can still have demand; and a “high variation” scenario where the covariance matrix values areincreased significantly.

3RESULTS

3.1

Example Grid Network

KGCB shows the best total covered demand (Table 1): KGCB outperforms KG on average of 27%,
increasing to 33% when transfers are allowed. When correlations are ignored using KG, its average
performance is even slightly worse than MAB.

Figure 1 – Box plots of results from example grid network
Table 1 – Mean of covered demand from example grid network relative to KG (%)
Policy
KGCB
KG
MAB#1 – Random
w/o transferw. transfer122%110%
100%
100%
112%
92%

TRISTAN XI Symposium#2 – Monocentric
w/o transfer
w. transfer
119%
134%
100%
100%
99%
115%

#3 – Polycentric
w/o transfer
w. transfer
122%
155%
100%
100%
95%
113%

Original abstract submittal

G. Yoon and J.Y.J. Chow

3.2

4

Real-world Example: New York City

The results for the NYC example (Table 2, Fig. 2(b)) indicate MAB has much larger variances, while
KGCB attains the highest mean (average of 19% higher than KG) and lowest variance.

(a)(b)
Figure 2 – (a) Map of NYC PUMA network and (b) box plots of results from NYC case
Table 2 – Mean, (standard deviation), [% of KG] of covered demand from NYC case
(unit: M trips)
KGCB
KG
MAB

4

#1 – Base
10.264 (0.887) [122%]
8.380 (1.282) [100%]6.618 (2.618) [79%]#2 – No zero-flows
10.949 (0.391) [114%]
9.564 (0.468) [100%]
9.887 (0.312) [103%]#3 – High variation
9.925 (1.192) [119%]8.330 (1.345) [100%]
6.877 (2.471) [83%]DISCUSSION

This study proposes a new approach based on an optimal learning technique within a sequential transit
route design framework. Since it sequentially extends the system by choosing an option within a given
set based on the most recent knowledge updated after observing the consequence of choices made,optimal learning techniques are employed. Three learning policies, KGCB, KG, and MAB arecompared, and KGCB shows the best performance represented by mean covering demand.
This artificial intelligence (AI) methodology is designed for designing systems without abundant
demand data to begin with and makes use of the sequential to “grow” this knowledge base. It reduces
the dependency on existing data sources and promotes active information accumulation which makes
the system more responsive to gaps that could not be captured by previous data collection. Furthermore,
due to its gradual expansion of the system, it can be more attractive when the project budget is divided
over time and sequentially executed.

References
Caros, N. S. & Chow, J. Y., 2021. Day-to-day market evaluation of modular autonomous vehicle fleet
operations with en-route transfers. Transportmetrica B: Transport Dynamics, 9(1), pp. 109-133.
Census Reporter, 2021. Census data for New York-Newark-Jersey City, NY-NJ-PA Metro Area.
https://censusreporter.org/profiles/31000US35620-new-york-newark-jersey-city-ny-nj-pa-metroarea/, Accessed on Jul 30, 2021.
Fragkos, I., Cordeau, J. F., & Jans, R. (2021). Decomposition methods for large-scale network expansion
problems. Transportation Research Part B: Methodological, 144, 60-80.
Frazier, P.I., Powell, W.B. and Dayanik, S., 2008. A knowledge-gradient policy for sequential
information collection. SIAM Journal on Control and Optimization, 47(5), pp.2410-2439.
Ma, T.Y., Rasulkhani, S., Chow, J.Y. and Klein, S., 2019. A dynamic ridesharing dispatch and idle
vehicle repositioning strategy with integrated transit transfers. Transportation Research Part E:Logistics and Transportation Review, 128, pp.417-442.
NYMTC, 2010. Household travel survey: Executive summary.
Ryzhov, I.O., Powell, W.B. and Frazier, P.I., 2012. The knowledge gradient algorithm for a generalclass of online learning problems. Operations Research, 60(1), pp.180-195.
Yoon, G. and Chow, J.Y., 2020. Contextual bandit-based sequential transit route design under demanduncertainty. Transportation Research Record, 2674(5), pp.613-625.

TRISTAN XI Symposium

Original abstract submittal