Arc travel time and path choice model estimation subsumed Sobhan Mohammadpour1and Emma Frejinger1

2025-04-30 0 0 1.51MB 32 页 10玖币

侵权投诉

Arc travel time and path choice model

estimation subsumed

Sobhan Mohammadpour1and Emma Frejinger1

1Université de Montréal

October 27, 2022

Abstract

We propose a method for maximum likelihood estimation of path

choice model parameters and arc travel time using data of diﬀerent lev-

els of granularity. Hitherto these two tasks have been tackled separately

under strong assumptions. Using a small example, we illustrate that this

can lead to biased results. Results on both real (New York yellow cab)

and simulated data show strong performance of our method compared to

existing baselines.

1 Introduction

An extensive literature on traﬃc-related problems aims at decreasing congestion

through improved strategic and tactical planning as well as real-time traﬃc

management. Central to many of these problems is, on the one hand, the

problem of estimating travel times in a network and, on the other hand, the

problem of predicting traﬃc ﬂow. As we discuss in the following, these two

problems are intrinsically connected and both require traﬃc data. However,

they have been tackled separately in the literature under strong assumptions.

Consider a network of nodes and arcs representing a given congested geo-

graphical area. Estimating the travel times between any origin and destination

node pair in this network is diﬃcult because it depends on numerous factors

such as speed limit, traﬃc ﬂow, road capacity, accidents, construction work,

traﬃc light states, etc. Some factors are easy to observe (e.g., speed limit),

whereas others are not (e.g., state of traﬃc lights and accidents). Even if the

factors are observable, the sources of data are diverse, for example, ﬁxed sensors

and ﬂoating car data. Travel time estimation methods are often tailor-made to

the speciﬁcity of available data sources.

As pointed out in Bertsimas et al. (2019), for strategic and tactical planning

purposes (e.g., routing and network design), it is more useful to estimate arc

travel times as opposed to origin-destination (OD) travel times. Assuming that

arXiv:2210.14351v1 [stat.ME] 25 Oct 2022

travelers follow a shortest path, Bertsimas et al. (2019) propose a methodology

to estimate arc travel time by only observing the network and trip travel time

between diﬀerent OD pairs. Neatly, they do not need to observe the paths taken,

nor the data on the demand structure (total demand between OD pairs).

The assumption that travelers follow paths minimizing travel time is strong

in light of numerous empirical studies in the literature on route choice modeling

(see Frejinger and Zimmermann, 2021, for a survey). In general, travelers do not

follow the shortest paths with respect to some perfectly known generalized cost

function. This motivates the use of stochastic prediction models where discrete

choice (random utility maximization) models are the most widely used ones.

Moreover, there is a related extensive literature on stochastic user equilibrium

models (e.g., Baillon and Cominetti, 2008, Dial, 1971, Fisk, 1980). Notewor-

thy and complementary to the latter is the mean-risk traﬃc assignment model

proposed by (Nikolova and Stier-Moses, 2014) based on the assumption that

travel times (as opposed to the choice model) are stochastic and travelers mini-

mize the expected travel time plus a multiple of the standard deviation of travel

time (a stochastic shortest path problem). To summarize, methods in the afore-

mentioned literature are based on the assumption that travelers do not follow

(deterministic) shortest paths. Either because the analyst, or the travelers, do

not perfectly observe relevant network attributes, such as travel time.

Discrete choice models are widely used to predict traﬃc ﬂow. They are cen-

tral to variety of problems where the purpose is to predict ﬂow in response to

changes in network attributes, such as travel time, or its structure (e.g., network

design or facility location problems). Two data sources are required to estimate

values of related unknown parameters: First, a representation of the network in

question, including attributes such as arc travel times. With relatively few ex-

ceptions (e.g., Ding-Mastera et al., 2019, Gao et al., 2010, Mai et al., 2021), the

attributes are assumed to be deterministic. Second, path choice observations.

Most commonly, model parameters are estimated by maximum likelihood using

path observations. The estimation is done assuming that network attributes are

exogenously given. The latter assumption stands in contrast with the literature

on travel time estimation and equilibrium models. It is a strong assumption as

the data generation process (by the travelers) is the same as, for example, Bert-

simas et al. (2019) even if the required level of detail is higher (path observations

as opposed to only path travel time).

The objective of this work is to relax the assumption that travel times are

exogenous when estimating path choice models. In addition, we aim to design

a maximum likelihood estimator for travel time estimation that is based data

assumptions similar to Bertsimas et al. (2019) but with weaker assumptions on

the path choice model.

We provide the following contributions:

•We propose a methodology to simultaneously estimate arc travel times

and parameters of diﬀerentiable path choice models. We show that under

weak assumptions we can conveniently formulate a maximum likelihood

estimator for the seemingly more complex joint estimation problem. Fur-

thermore, we show that under the assumptions made by Bertsimas et al.

(2019), their method is, in fact, corresponds to maximum likelihood esti-

mation.

•An attractive property of our proposed joint likelihood is that it allows

naturally to mix observations of diﬀerent levels of granularity.

•We show through an illustrative example that treating travel time as ex-

ogenous variables can lead to biased results.

•Numerical results based on New York City taxi data show that estimating

a maximum likelihood estimation of the joint likelihood is fast and perfor-

mant. Measured by root mean-squared log error, we reach a performance

and computing times comparable to those of Bertsimas et al. (2019) while

solving the joint estimation problem. Results on synthetic data illustrate

that our travel time estimates better reproduce ground truth ones and

achieves better path choice model parameter estimates than a sequential

approach (ﬁrst estimating arc travel times, followed by the choice model).

The remainder of the paper is structured as follows. In Section 2, we describe

the work of Bertsimas et al. (2019), and the arc-based path choice model of

Fosgerau et al. (2013) that we use in our our experiments. In Section 3 we

provide an illustrative example, and in Section 4 we introduce our method. We

report numerical experiments in Section 5, and ﬁnally, we provide concluding

remarks in Section 6.

2 Related work

Our work is situated at the intersection between the literature on arc travel

time estimation and path choice model estimation. A comprehensive litera-

ture review on these two topics is out of the scope of this paper. Instead, we

focus this section on the most closely related works and refer to Mori et al.

(2015) or Oh et al. (2015) for broader reviews on travel time estimation and re-

fer to Prato (2009), Frejinger and Zimmermann (2021), and Zimmermann and

Frejinger (2020) for broader reviews concerning path choice models. First, we

brieﬂy outline the method of Bertsimas et al. (2019) that we base our work on.

Second, in Section 2.2, we describe recursive path choice models (Zimmermann

and Frejinger, 2020) that allow for maximum likelihood estimation of unknown

parameters based on trajectory observations. Finally, in Section 2.3 we discuss

contrasts and synergies between these works.

2.1 A method for arc travel time estimation

Given a graph G= (N, A)where Nis the set of nodes and Athe set of arcs,

let Obe multi-set (i.e., a set with the possibility of duplicate elements) of

observations (o, d, t)∈N2×R+from trajectories in Gsuch that ois the origin,

dis the destination, and tis the travel time. Bertsimas et al. (2019) focus on

estimating the travel time of a∈Ausing O.

Based on the assumption that the quality of travel time estimations is per-

ceived on a multiplicative rather than an additive scale, Bertsimas et al. (2019)

propose using the mean-squared log error (MSLE),

MSLE(ˆ

t, t) = (ln t−ln ˆ

t)2= ln2(t/ˆ

t),(1)

as a loss function to compare estimate ˆ

tand the observed t. Furthermore, they

propose the convex surrogate,

max ˆ

t,t

t,(2)

for MSLE(ˆ

t, t)which they model using a second order cone and a linear con-

straint.

Bertsimas et al. (2019) formulate the estimation problem as a mixed-integer

program whose objective is to minimize MSLE between travel times of short-

est paths (i.e., predicted travel times) and observed travel times. We refer to

this mixed-integer program as BDJM model (from the ﬁrst letter of each con-

tributing author’s name). The objective also has a regularization term which

we describe in more detail below. The BDJM model has two sets of variables:

Binary variables to select the shortest path between each OD pair and a set

of continuous variables corresponding to arc and path travel times. Linear (in-

cluding big-M) constraints ensure that, for each OD pair, the travel time of the

shortest path is the sum of its arc travel times and is shorter than all other

paths.

The regularization term plays an important role in this formulation. Bertsi-

mas et al. (2019) deﬁne the regularization for the 3-tuple (i, j, k)such that (i, j)

and (j, k)are arcs as



Tij

Lij −Tjk

Ljk 

Lij +Ljk

,(3)

where Tij and Lij are, respectively, the length and the travel time of the arc

(i, j)∈A. The regularization for the whole problem is the sum of the regu-

larization for all 3-tuples like (i, j, k). This term introduces a notion of smooth

solutions, which helps to navigate the undetermined solution space, obtain more

realistic solutions, and mitigate the risk of overﬁtting.

Since this program is hard to solve, they ﬁrst relax some of the constraints

related to the shortest paths and use a decomposition scheme where they itera-

tively solve the program on the real and binary variables until convergence. We

call this the BDJM method.

Bertsimas et al. (2019) evaluate their method on New York city’s yellow

cab dataset (New York City Taxi and Limousine Commission, 2016) limited to

Manhattan and obtain high-quality results. Solving the problem is challenging

due to the large network and the many observations.

2.2 Path choice models

A path choice model is a mathematical object that takes the arc travel time T,

a parameter vector b, and other exogenous attributes as inputs. Path choice

models can be used to sample paths conditioned on an OD pair, or to compute

traﬃc ﬂow between OD pairs. Furthermore, path choice models can estimate

the probability of sampling any path. We call a path choice model diﬀerentiable

if the probability of sampling any path is diﬀerentiable with regards to the path

choice model’s inputs. This point of view helps us to reason about most work

that deals with modeling path choice preferences. It is possible to model path

choices as a Markov Decision Process (MDP), in that case we call it a recursive

path choice model.

The recursive logit – a recursive path choice model – was introduced in Fos-

gerau et al. (2013) with the objective to analyze and predict travelers’ path

choices. They show that the multinomial logit (MNL) of McFadden (1977) on

the set of all paths can be formulated as a parametric MDP. The MDP struc-

ture allows parameter estimation without deﬁning a set of alternative paths.

More recent studies propose models that relax the restrictive assumptions of

the MNL model. We refer to Zimmermann and Frejinger (2020) and Frejinger

and Zimmermann (2021) for overviews.

The MDP proposed by Fosgerau et al. (2013) has similarities with the work of

Ziebart et al. (2008) in the inverse reinforcement learning community. The main

diﬀerence between these two work is that while conditioned on OD, the ratio of

probability for any two path is the same, Fosgerau et al. (2013) proposes an MDP

with only negative rewards and an absorbing state while Ziebart et al. (2008)’s

model has no absorbing state. Furthermore, Fosgerau et al. (2013) proposes to

solve a system of linear equations instead of doing value iteration and conditions

the MDP on the destination. We focus this section on the recursive logit model

as we use it to illustrate our method.

Like McFadden (1977), Fosgerau et al. (2013) assume that people are rational

in the sense that they choose the path that maximizes a utility function. Let

u(r)be the utility of selecting a path r; the probability of someone choosing r

over the set of all paths from oto d,R(o, d), is

P(r) = P(u(r)> u(s)|∀s6=r∈R(o, d)).(4)

Since people have diﬀerent preferences, they model it as the sum of a deter-

ministic term v(r)and a random variable ε(r). The random variable models

personal diﬀerences, the unknown to the analyst, the ever-changing environ-

mental factors, and the alignment of stars.

Fosgerau et al. (2013) assume that both deterministic and stochastic parts

are arc-additive and that state transitions are deterministic. This way, the

deterministic component of the utility v(r)can be written as the sum of arc

utilities, i.e., P(i,j)∈rv(j|i)where v(j|i)is the utility of traversing an arc (i, j)

and (i, j)∈rrepresent all traversed arcs in r. The stochastic term ε(r)is also

the sum of per arc stochasticity i.e., P(i,j)∈rε(j|i). They assume that ε(j|i)are

independent and identically distributed (i.i.d.) random variables following the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ArctraveltimeandpathchoicemodelestimationsubsumedSobhanMohammadpour1andEmmaFrejinger11UniversitédeMontréalOctober27,2022AbstractWeproposeamethodformaximumlikelihoodestimationofpathchoicemodelparametersandarctraveltimeusingdataofdierentlev-elsofgranularity.Hithertothesetwotaskshavebeentackledseparat...

展开>> 收起<<

Arc travel time and path choice model estimation subsumed Sobhan Mohammadpour1and Emma Frejinger1.pdf

共32页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Arc travel time and path choice model estimation subsumed Sobhan Mohammadpour1and Emma Frejinger1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: