Efficiency of Travel Time Prediction
Chiwei Yana,∗ , James Johndrowb and Dawn Woodardc
a Department of Industrial and Systems Engineering, University of Washington, Seattle

chiwei@uw.edu

b Department of Statistics and Data Science, Wharton School, University of Pennsylvaniac Uber Technologies∗ 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 3, 2022
Keywords: travel time prediction, statistical efficiency, spatial granularity

1

INTRODUCTION

Geospatial (maps) technologies underlie a broad spectrum of modern mobile applications. For
example, consumer-facing navigation applications (such as Google Maps and Waze) provide recommended routes along with associated times, as well as turn-by-turn navigation along those routes.
Geospatial technologies are also the foundation of decision systems for ride-sharing (such as Uber,
Lyft, Didi Chuxing and Ola) and delivery platforms (such as UberEats and Doordash). For example, riders on these platforms are presented with expected pickup time and time to destination,and drivers are provided with turn-by-turn navigation. Matching and pricing decisions on theseplatforms also heavily rely on mapping inputs to optimize for efficiency and reliability (Yan et al.,2020).
An important geospatial technology is prediction of the time required for a driver (or biker,
or pedestrian) to travel a particular route in the road network. Two general classes of approaches
have been proposed for this travel time prediction problem: (1) approaches based on predicting
traffic and travel time at the level of road segments and turns, and aggregating across the route(“segment-based approaches”); and (2) approaches that use generic information about the origin,destination, and route to predict the travel time (“route-based approaches”). Both of these methods
leverage location data traces from past vehicle trips in the road network, typically gathered (withpermission) from users of the particular application, such as a consumer-facing navigation service.
Though many variations of the these methods have been proposed in the literature and inpractice, there has been no rigorous theoretical comparison of the accuracy of these two approaches.
Empirical studies have in many cases drawn opposite conclusions. To fill this gap, we conduct first
theoretical analyses comparing these two classes of methods in terms of their predictive accuracy
as a function of the training data sample size (the statistical efficiency).
Summary of Contributions and Results• Modeling. We introduce a modeling framework for the travel time estimation problem.
This framework uses general priors on mean travel times and allows arbitrary road networkand spatial correlation structure among segment travel times, and thus lays a theoreticalfoundation for analyzing the accuracy of different travel time estimation methods. Under
TRISTAN XI Symposium

Original abstract submittal

C. Yan, J. Johndrow and D. Woodard

2

this framework, we formally define a family of segment-based estimators and route-based
estimators that resemble many practical estimators proposed in the literature and used inpractice. Furthermore, we explicitly characterize the optimal estimators within each family
in terms of minimizing integrated risks based on squared error loss.
• Finite Sample Analysis. Under any amount of samples, when segment travel times are
non-negatively correlated spatially within the route, we show that the integrated risk (basedon squared error loss) of the optimal segment-based estimator is always lower than that of a
special case of the optimal route-based estimator where one is only allowed to use historical
trips that traverse the exact same route as the predicting route. We show that the nonnegative correlation assumption, though being not quite restrictive in practice, is necessary
for the result to hold.
• Asymptotic Analysis. To achieve more general results regarding their comparison, we
extend our analysis to an asymptotic setting where the number of trip observations grows
as the size of the road network increases and trip observations are sampled randomly from ageneric route distribution. We give conditions under which a large family of simple segmentbased estimators can deliver integrated risk of smaller order than that of the optimal routebased estimator when the road network size is large enough. This family of estimators only
requires information of the prior means of segment travel times and encompasses popular
estimators used in practice. Intuitively, the conditions require that data accumulates fasteron each segment of the route than on “similar” routes in a defined neighborhood of thepredicting route times the length of the predicting route (number of segments on the route).
We show that such conditions hold naturally in a grid network when considering a route-based
estimator that uses all historical routes that are similar in origin and destination to those of
the predicting route. We also give explicit rates of the integrated risk of this family of simple
segment-based estimators as the grid size grows.

2

Brief Overview of Model and Analysis

We give a brief overview of our model, analysis, and two of the key results. Note that many results
are omitted or presented in a simplified way due to page limit, the complete set of results can befound at https://arxiv.org/abs/2112.09993.
We consider a setting where we are given N historical trips on an arbitrary road network (V, S)
where V is a vertex set and S is an edge (road segment) set. Let y1 , . . . , yN be the routes foreach trip. Let [N ] denote the set {1, · · · , N }. Each route consists of a sequence of road segmentss ∈ S. Note that road segment here is defined generally that could include a segment along witha particular direction of traversing that segment and a following turn direction. To simplify thenotation, we use y[N ] := {yn }n∈{1,...,N } . Let Tn,s be the travel time on segment s ∈ yn for the nthobserved trip. We give the following assumption regarding the generative process of Tn,s .
Assumption 1 We make the following assumptions about Tn,s ,1. For the nth trip, {Tn,s }s∈yn are drawn from a distribution with means {θs }s∈yn and covariances {σst }s,t∈yn , where σss = σs2 is the variance of the travel time on segment s.
2. For any n 6= n0 and any s ∈ yn , t ∈ yn0 , Tn,s and Tn0 ,t are independent conditional on θs , θt .
3. {θs }s∈S are drawn independently from a distribution with population mean θ and variance τ 2 .
We first consider a family of segment-based estimators. Intuitively, this family of estimators
uses segment-level traversal data to estimate mean segment travel times and then aggregate over
all the segments on a route to obtain an estimate for the mean route travel time. One typical way
TRISTAN XI Symposium

Original abstract submittal

C. Yan, J. Johndrow and D. Woodard

3of estimating mean
P segment travel time is by solving a regularized regression (e.g., ridge regression)
problem: minθ̂s n:s∈yn (θ̂s −Tn,s )2 +λ(θ̂s −θ)2 where λ ≥ 0 is a regularization parameter that helps
to “shrink” the estimate towards the prior mean θ if there is not much traversal data on segment s.
Let Ns := |{yn : s ∈ yn , n ∈ [N ]}| denote the sample size of traversals on segmentPs. It is not hard
to check that θ̂s here has a closed form: θ̂s = (λ/(λ + Ns ))θ + (Ns /(λ + Ns ))( n:s∈yn Tn,s /Ns ).
(seg)
Generalizing this observation, we now define a family of segment-based estimators Θ̂y.
Definition 1 (Segment-Based Estimator) A segment-based estimator takes the form
X
(seg)
Θ̂y
:=
θ̂s ,
s∈y

P
θ̂s := (1 − φs (Ns ))θ + φs (Ns )n:s∈yn Tn,s

Ns,

for some φs (Ns ) : Z≥0 7→ R such that φs (0) = 0 and define φs (0)/0 = 0, for all s ∈ y.
(seg)
In other words, Θyis the summation of segment-level estimators θ̂s that are constructedusing a weighted average of the sample mean and the population mean of the prior distribution,
where the weight is sample size dependent. One would typically expect the weights {φs (Ns )}s∈y ∈[0, 1] to converge to 1 as the sample size Ns grows to infinity. Such behavior ensures consistencyof the estimator, though this is not required for our analysis. The aforementioned estimator basedon ridge regression takes the form of φs (Ns ) = Ns /(λ + Ns ). Another example of such φs (Ns ) is
the Bayes estimator φs (Ns ) = τ 2 Ns /(τ 2 Ns + σs2 ) when the segment travel times are independently
distributed, i.e., σst = 0, ∀s 6= t (see e.g., Gelman et al. (2013)). Note that one could also consider
a more general family of segment-based estimators that uses traversal data on other road segments
in S other than s to predict θ̂s , e.g., the Bayes estimator under the general correlation structure.
Here we are going to put a disadvantage to the segment-based estimator by excluding such optionsin Definition 1. In other words, the accuracy of the segment-based estimators we analyze can beconsidered as upper bounds. Importantly, from a practical point of view, such simplification ofsegment-based estimators is also aligned with industry practice of implementing segment-based
methods (Derrow-Pinion et al., 2021).
We then consider a family of route-based estimators which uses route-level traversal data toestimate the travel time on a new route y. Denote δ(y) ⊂ y[N ] as a subset of historical routes
which represents the neighbor of route y. For example, δ(y) can be historical routes that sharethe same or similar origin and destination (but possibly with different sequence of segments) as
y. These neighboring
routes are representative observations to estimate travel time on route y.
P
Let Mδ(y) = N
1{yn ∈ δ(y)} be the sample size of traversals within route y’s neighborhood,n=1
and |y| be the number of segments traversed on route y. Similar to the segment-based
estimator,P
one can consider an estimator Θ̂y by solving the ridge regression problem: minΘ̂y n:yn ∈δ(y) (Θ̂y −P
2s∈yn Tn,s ) + λ(Θ̂y − |y|θ) where λ ≥ 0 is a regularization parameter. The estimator will shrink to
the prior mean of the travel time on route y, |y|θ, if there is not much P
traversal data
P in δ(y). Again,Θ̂y has a closed form: Θ̂y = (λ/(λ+Mδ(y) ))|y|θ+(Mδ(y) /(λ+Mδ(y) ))( n:yn ∈δ(y) s∈yn Tn,s /Mδ(y) ).
This motivates the following formal definition of route-based estimators.

Definition 2 (Route-Based Estimator) A route-based estimator takes the formPP
n:yn ∈δ(y)s∈yn Tn,s(route)Θ̂y:= (1 − φy (Mδ(y) ))|y|θ + φy (Mδ(y) ),Mδ(y)for some φy (Mδ(y) ) : Z≥0 7→ R such that φy (0) = 0 and define φy (0)/0 = 0.
∗(seg)
Our first main result investigates the comparison of the two optimal estimators Θ̂yand∗(route)Θ̂yunder a special case where δ(y) is chosen to be the set of historical routes that are exactly

TRISTAN XI Symposium

Original abstract submittal

C. Yan, J. Johndrow and D. Woodard

4

the same as y, i.e., δ(y) = {yn : yn = y}. The optimal
estimator minimizes
the integrated risk




2
of the estimator Θy , defined as R Θ̂y y[N ] := E Θ̂y − Θyy[N ] . Minimizing the integrated
risk is equivalent to minimizing the predictive mean squared error, which is often used in evaluating
various predictive models in practice.
For any route y, when the covariances of the segment travel times within the route are non∗(seg)negative, σst ≥ 0, ∀s 6= t ∈ y, we prove that the optimal segment-based estimator Θ̂yalways hasa weakly lower integrated risk based on squared loss compared to that of the optimal route-based∗(route)estimator Θ̂y.
Theorem 1 When δ(y) = {yn : yn = y}, for any route y such that σst ≥ 0 for all s 6= t ∈ y, andany historical routes y[N ] , the integrated risk of the optimal segment-based estimator is at least as
low as that of the optimal route-based estimator:∗(seg)
route) yR Θ̂yy[N ] ≤ R Θ̂∗([N ] .
yWe then give our main asymptotic result. We compare a large family of simple segment-based(seg)∗(route)with a sequence of routes {yp }p∈N
to the optimal route-based estimator Θ̂ypestimator Θ̂yp
within a growing network of size p and growing sample size N . The family of simple segment-based
estimators only requires information of the prior means of segment travel times and encompasses
popular estimators used in practice. We give conditions under which the segment-based estimatoris more accurate when the size of the road network gets larger. The key quantities determining theefficiency of estimators are the rates at which training data accumulates on particular road segments
and on particular routes. We denote the probability that a specific road segment s is traversed bya randomly generated route Y ∼ µ as qs := P[s ∈ Y ]. Similarly, we define qδ(y) := P[Y ∈ δ(y)] as
the probability that a particular route within a neighborhood δ(y) is sampled.
Theorem 2 Under the data-rich regime with N qδ(yp ) = ω(1), if limp→∞ maxs∈yp |yp |qδ(yp ) /qs =√0 then any segment-based estimator with φs (Ns ) = 1 − O(1/ Ns ) for all road segments in yp ,dominates the optimal route-based estimator:


(seg)
R Θ̂yp = 0.
lim ∗(route)p→∞
R Θ̂ypAn alternative sufficient condition is that both limp→∞ maxs∈yp qδ(yp ) /qs = 0 and σst ≥ 0, ∀s, t ∈yp , ∀p ∈ N.
Under the data-scarce regime N qδ(yp ) = O(1), the route-based estimator is always inconsistent.
However, it may hold√ that mins∈yp N qs = ω(|yp |), in which case any segment-based estimator withφs (Ns ) = 1 − O(1/ Ns ) for all road segments in yp is consistent.
We show that the conditions in Theorem 2 hold naturally in a grid network. In summary,
we recommend the use of segment-based approaches if one has to make a choice between the two
methods. Our work highlights that the accuracy of travel time prediction is driven not just by thesophistication of the model, but also the spatial granularity at which those methods are applied.

References
Derrow-Pinion, Austin, She, Jennifer, Wong, David, Lange, Oliver, Hester, Todd, Perez, Luis, Nunkesser,
Marc, Lee, Seongjae, Guo, Xueying, Wiltshire, Brett, et al. 2021. ETA Prediction with Graph Neural
Networks in Google Maps. arXiv preprint arXiv:2108.11482.
Gelman, Andrew, Carlin, John B, Stern, Hal S, Dunson, David B, Vehtari, Aki, & Rubin, Donald B. 2013.
Bayesian data analysis. CRC press.
Yan, Chiwei, Zhu, Helin, Korolko, Nikita, & Woodard, Dawn. 2020. Dynamic pricing and matching inride-hailing platforms. Naval Research Logistics (NRL), 67(8), 705–724.

TRISTAN XI Symposium

Original abstract submittal