Structural estimation for a route choice modelwith uncertain measurement
Yuki Oyama* & Eiji Hato
*PhD student
Behavior in Networks studies unit
Department of Urban Engineering
School of Engineering, The University of Tokyo

September 25, 2016

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 25, 2016

Outline

OutlineOutline1. Introduction
2. Link-based route measurement model
3. Structural estimation method
4. Numerical examples
5. Conclusions

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

2

Outline

OutlineOutline1. Introduction
2. Link-based route measurement model
3. Structural estimation method
4. Numerical examples
5. Conclusions

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

3

Motivation

Introduction

Route choice analysis
Parameter estimation results largely depend on accuracy of route measurement

GPS data
Route measurement model
Route choice data
Route choice model
Estimated parameters

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

4

Motivation

Introduction

Route choice analysis
Parameter estimation results largely depend on accuracy of route measurement

GPS data
Route measurement model
Route choice data
Route choice model
Estimated parameters

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

5

Motivation

Introduction

Pedestrian route choice analysis
Measurement uncertainty; Dense and high-resolution network

N•

Dense network•

Spatial dependence of
Measurement errors
ü
ü
ü
ü

0 100 200

400

Along river
Wide street
Narrow street
With arcade

800(m)

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

6

Literature review

Introduction

Route measurement models (1)Sequential approach infers the true location at each data in chorological order: GPS data

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

7

Literature review

Introduction

Route measurement models (1)Sequential approach can output meaningless paths

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

8

Literature review

Introduction

Route measurement models (2)Path-based probabilistic approach evaluates path likelihood regarding all GPS data
included in a trip
Pyo et al. (2001); Bierlaire et al. (2013)

Domain of Data
Relevance
Likelihood

10%

Path 1
Oyama, Y. (The University of Tokyo)

40%

Path 2
15th Behavior Modeling summer course

50%

Path 3
Sep. 29,25, 2016
2016
Jury

9

Literature review

Introduction

Route measurement models (2)Path-based probabilistic approach suffers with trade-off between computational
efficiency and measurement accuracy
Pyo et al. (2001); Bierlaire et al. (2013)

Large

Small
Path candidate set

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

10

Literature review

Introduction

Route measurement models (2)Assuming error variance constant on network distort measurement probabilities

σ : Large

σ : Small

0.04

x̂ tj − x j = d

0.01

0.02

0.03

σ = 10σ = 50σ = 100
0.00

Measurement probability

0.05

PDF of GPS measurement error:

2%"x̂ j − x j$ − x̂ j − x j 'p( x̂ j | x j ;σ ) =exp$
σ2
2σ 2 '
#
&

−200

−100

0

100

200

Distance from the true location
Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

11

Literature review

Introduction

Route measurement models (3)Bayesian approach incorporates behavioral models into measurement models
Chen et al. (2013); Danalet et al. (2014)

Prior(Route choicemodel)

Measurement

Posterior

Oyama, Y. (The University of Tokyo)

25%

15%

60%

10%

40%

50%

16%

6%

78%

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

12

Literature review

Introduction

Route measurement models (3)Bayesian approach has a problem regarding parameter inconsistency

Given parameters

GPS data•••

ArbitraryPrevious study
Other data

Route choice model
Prob.

Route measurement model
Route choice data
Route choice model
Estimated parameters
Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

13

Literature review

Introduction

Route measurement models• Challenges:– Disconnected path
• Not suitable for route choice models– Setting of the measurement parameter• Possible to miss the true path
• Ignorance of spatial difference distorts path likelihood– Parameter inconsistency of route choice model• Estimated parameter includes biases regarding initial parameter

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

14

Framework

Introduction

Framework
1. Link-based route measurement model– Matching each decomposed trip data to a link
– Estimating a measurement parameter for each link
– Incorporating a link-based route choice model as prior

2. Structural estimation method– Parameters at convergence satisfy the parameter consistency of
the route choice model

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

15

Outline

OutlineOutline1. Introduction
2. Link-based route measurement model
3. Structural estimation method
4. Numerical examples
5. Conclusions

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

16

Problem & Notation

Link-based route measurement model

Problem & Notation
Matching row GPS data m̂ to the transportation network G• GPS data m̂ = ( x̂, τˆ )– Pair of coordinates x̂ = ( x̂lat , x̂lon ) with error variance σ– Timestamp τˆ
– A given trip m̂ = (m̂1,..., m̂n ,..., m̂N )• Network G = (V, A)– Node v ∈ V : the horizontal position xv = {xlat , xlon }– Link a = (vu , vd ) ∈ A : the vector of spatial attributes ya– Network connection δ (a' | a) : 1/0

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

17

Flow

Link-based route measurement model

Link-based route measurement
Matching all data observed within a period to the same linkm̂1 m̂2

m̂n

・・・

m̂N

・・・

t =1

m̂11

・・・

m̂1J

m̂12

a1

p(at | m̂t , at 1 )

a1

m̂JT

・・・

a2

aT

p(m̂t | at ;a2

at)p(at | at 1; )

・・・

aT

GPS data of a tripm̂ = (m̂1,..., m̂n ,..., m̂N )m̂n = ( x̂n , ˆn )Data decompopsitionm̂ = (m̂1,..., m̂t ,..., m̂T )m̂t = (m̂1t ,..., m̂ tj ,..., m̂Jt )Estimation:at

Link probabilities
Path inference:= [a1,..., at ,..., aT ]p(m̂t | at ) : Measurement probability of m̂t given at ; measurement equationp(at | at−1 ) : Prior probability of at given at−1
Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course; system equation
Sep. 29,25, 2016
2016
Jury

18

Link probability

Link-based route measurement model

Link probability p(at | m̂t , at−1 )The probability of at given measurements m̂t and state at−1•

Candidate set: A(at−1 ) = {at | δ (at | at−1 ) = 1}
– Calculate link probabilities for all at ∈ A(at−1 )

1

m̂1t

m̂3t

2

at 1

m̂2t

3
t

t

t

t

: GPS data m̂ = {m̂1 , m̂2 , m̂3 }Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

19

Measurement equation

Link-based route measurement model

Measurement equation p(m̂t | at ;σ a )t

The probability of measurements m̂t given at•Assumption:– Timestamp τˆ has no measurement error; p(m̂t | at ) = p(x̂ t | at )– Measurement probability of data is independent from each other– Traveler moves at the constant speed on the same linkJp( x̂ ,..., x̂ | at ;σ at ) = ∏ p( x̂ tj | at ;σ at )
t
1

t
J

j=1
J

=∏ ∫
j=1

x j ∈atp( x̂ tj | x tj , at ;σ at )p(x j | at )dx j

PDF of GPS measurement error: Rayleigh distribution (van Diggelen, 2007)2%"tx̂ − x jx̂ j − x j 'tt$p( x̂ j | x j , at ;σ at ) =
exp −
2
$
σ at
2σ a2t '#&tjOyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

20

Measurement equation

Link-based route measurement model

Estimation of measurement parameter σ atLink-based map matching can regard error variance as a link peculiar variable

Measurement likelihood maximization

σ at = argmax p(m̂t | at ;σ )σWhere,
2%
) t
"
t
x̂
−
x
x̂
−
x
+ j
j
j
$− j
' ⋅ p(x | a )+.dxp(m̂t | at ;σ at ) = ∏ ∫
exp
*
j
t
j
2
2
x j ∈at
$
'
σ
2
σ
+,
+/
at
at
j=1
#
&
J

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

21

System equation

Link-based route measurement model

System equation p(at | at−1;θ )The prior probability of at given a state at−1

Link-based route choice model
Utility function:A(at 1 )

1
2

at 1

u(at | at−1 ) = v(at | at−1 ) + ε (at ) = θ y at |at−1 + ε (at )v(⋅) : Deterministic component of utility

ε (⋅) : Probabilistic component of utility(i.i.d. gumbel distribution)3y at |at−1 : Vector of explanatory variables

θ

Oyama, Y. (The University of Tokyo): Vector of parameters

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

22

System equation

Link-based route measurement model

System equation p(at | at−1;θ )The prior probability of at given a state at−1

Link-based route choice model
Choice probability option:A(at 1 )1

Markov modelp(at | at−1 ) =e v(at |at−1 )∑ ev(at |at−1 )at ∈A(at−1 )

2

at 1

Recursive logit model

Fosgerau et al. (2013)d3p(at | at−1 ) =e v(at |at−1 )+V (at )v(at |at−1 )+V d (at )e∑
at ∈A(at−1 )And others: e.g.,
Mai et al. (2015); Mai (2016); Oyama et al. (2016)
Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

23

Link inference

Link-based route measurement model

Link inference•

Link (posterior) probability:– The probability of at given measurements m̂t and a state at−1p(at | m̂t , at−1 ) ∝ p(m̂t | at ;σ at )p(at | at−1;θ )•Link inference:– Link likelihood maximization subject to switching conditionat = argmax p(at | m̂t , at−1 )at ∈A(at−1 )s.t.,Oyama, Y. (The University of Tokyo)

max p(m̂t+1 | a;σ a ) > γa∈A(at )15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

24

Outline

OutlineOutline1. Introduction
2. Link-based map matching algorithm
3. Structural estimation method
4. Numerical examples
5. Conclusions

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

25

Methodology

Structural estimation method

A fixed point problem
Need to solve a fixed point problem of route measurement and estimation

Route measurement
Route choice probabilityp(at | at−1;θ! )Route choice modelθ = argmax LL(θ ; ψ )
θ

s.t.,

Path ψ

Measurement probabilityp(m̂t | at ;σ at )| θ − θ! |< ζ

Where,T#&δai t
LL(θ ; ψ ) = ln % ∏ ∏ p(at | at−1;θ ) ($ i t=2'"1, if ai,t ∈ ψi
δ =#$0, otherwiseiatOyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

26

Methodology

Structural estimation method

Structural estimation
A method for parameter estimation of models with fixed point problem
NFXP (Nested Fixed Point) Rust (1987)
NPL (Nested Pseudo Likelihood) Aguirregabiria and Mira (2002)
MPEC (Mathematical Programming with Equilibrium Constraint) Su and Judd (2012)
…

•
•
•
•

Structural estimation for route choice model with uncertain data•

Solving a fixed problem regarding parameter of route choice model•

Inner problem: Route measurement model•

Outer problem: Parameter estimation of route choice model

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

27

Methodology

Structural estimation method

Structural estimation
A estimation method for solving a fixed point problem of route choice parameterh = 1,(h)GPS data m̂=Measurement modelp(m̂ | at ;pi (at | m̂it , at 1 ) =

at

t
i

p(m̂it | at ;at

)p(at | at 1;
at

(h)

)

ai,t = argmax pi (at | m̂ , at 1;(h)i

max LL( ) = log)p(at | at 1; (h) )(h)m̂i = (m̂1i ,..., m̂it ,..., m̂Ti )tiat

Behavior model

(h)
ai,t
(h)

)

(h+1)

= [ai,1,..., ai,t ,..., ai,T ](h)h := h+1

No

=

I

T

i

t=2

(h)

pi (at | at 1; ) ai,t1, if ai,t(h)
i0, otherwise= argmax LL( ;

(h+1)

(h)

(h)

)

<

Yes

=
Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

(h)

,

=

(h)

Sep. 29,25, 2016
2016
Jury

28

Outline

OutlineOutline1. Introduction
2. Link-based map matching algorithm
3. Structural estimation method
4. Numerical examples
5. Conclusions

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

29

Twins experiment

Numerical examples

Twins experiments | Simulationyy = 90(2/0/5)(2/1/5)y = 60(2/0/5)(2/1/5)(1/0/20)(3/1/5)y = 30(2/0/5)(2/1/5)(1/0/20)(3/1/5)(3/1/5)(3/1/5)(1/1/5)x = 40v(a | k) = θ1TTa + θ 2CCa + θ 3 DCa + θ 4UTa|k(2/1/10)(3/1/5)O o(3/1/5)(2/1/5)(2/1/10)(2/1/5)

Settings(1/0/20)(2/0/5)(2/1/10)dD(2/1/5)(2/1/5)x = 80x = 120

True parameter:

θ! = [−0.1, −2, −1.5, −4]

Period interval:

t = 30s

Data generation:

τˆ j − τˆ j−1 = 10sx*(continuous cost: CCa / discrete cost: DCa / variance:

a

)

y

y

y

x

x

(a)

Oyama, Y. (The University of Tokyo): True path(b)

15th Behavior Modeling summer course: Measurementx(c)Sep. 29,25, 2016
2016
Jury

30

Twins experiment

Numerical examples

Twins experiments | Measurement results
Which model improves the route measurement accuracy ?

Table: Measurement accuracy and the difference of the parameter from the true value

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

31

Twins experiment

Numerical examples

Twins experiments | Estimation results
Does structural estimation method improve the parameter estimation results ?

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

32

Real data

Numerical examples

Real data
Matsuyama Probe Person data in 2007, 30 pedestrians, 729 locations
N

0 100 200

400

Oyama, Y. (The University of Tokyo)

800(m)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

33

Real data

Numerical examples

Real data | Model specification••

Route choice model: (static) Markov model
Target: Pedestrian trip in city center•

Utility function:v(a | k) = θ1TTa + θ 2CU a + θ 3 DU a + θ 4UTa|k
TT : Travel time (min.)

CU : Sidewalk width (m)DU : Arcade dummy variable
UT : U-turn dummy variableOyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

34

Real data

Numerical examples

Real data | Parameter estimation results•••

Travel time ( θ1 ) seems to be significant from the result of one-way model, however,
Structural estimation results show that links with arcade ( θ 3 ) are the most likely to bepassed by pedestrians; travel time ( θ1 ) is not significant
2
Other t-values and rho-square ( ρ ) indicate that the structural estimation improvesparameter estimation results

Travel time (min.)Sidewalk width (m)With arcade
U-turnOyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

35

Real data

Numerical examples

Real data | Estimation results of error variance
Estimated measurement error variance is dependent on each link

Estimation result of σ
~ 20 (or no measurement)
20 ~ 3030 ~ 50
50 ~ 100
100 ~Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

36

Outline

OutlineOutline1. Introduction
2. Link-based map matching algorithm
3. Structural estimation method
4. Numerical examples
5. Conclusions

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

37

Conclusions

Conclusions

Conclusions and Future work
• Conclusions– A link-based measurement model with route choice model– Estimation of measurement parameter for each link
– Structural estimation method for solving a fixed point problem
regarding route choice parameters• Future work
– Comparison of computational efficiency with previous
measurement models– Alternatives and utility of pedestrian link choice– Characteristics of the fixed point problem

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

38

Thank you for attention!
Questions?
oyama@bin.t.u-tokyo.ac.jp

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

39

Reference

Reference

References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

Bierlaire, M., Chen, J., Newman, J., 2013. A probabilistic map matching method for smartphone GPS data.
Transportation Research Part C: Emerging Technologies 26, 78-98.
Bierlaire, M., Frejinger, E., 2008. Route choice modeling with network-free data. Transportation Research Part C:
Emerging Technologies 16(2), 187-198.
Chen, J., Bierlaire, M., 2015. Probabilistic multimodal map matching with rich smartphone data. Journal of Intelligent
Transportation System 19(2), 134-148.
Danalet, A., Farooq, B., Bierlaire, M., 2014. A bayesian approach to detect pedestrian destination-sequences from WiFi
signatures. Transportation Research Part C: Emerging Technologies 44, 146-170.
Fuse, T., Nakanishi, W., 2012. A study on multiple human tracking by integrating pedestrian behavior model (inJapanese). Journal of JSCE Series D3: Infrastructure Planning and Management 68(2), 92-104.
Fosgerau, M., Frejinger, E. and Karlstrm A., 2013. A link-based network route choice model with unrestricted choice set.
Transportation Research Part B, 56, pp.70-80.
Hunter, T., Abbeel, P., Bayen, A., 2014. The path inference filter: model-based low-latency map matching of probevehicle data. IEEE Transactions on Intelligent Transportation Systems 15(2), 507-529.
Pyo, J.S., Shin, D.H., Sung, T.K., 2001. Development of a map matching method using the multiple hypothesis
technique. IEEE Proceedings on Intelligent Transportation Systems, 23-27.
Quddus, M.A., Noland, R.B., Ochieng, W.Y., 2005. Validation of map matching algorithms using high precision
positioning with GPS. The Journal of Navigation 58(2), 257-271.
Quddus, M.A., Ochieng, W.Y., Noland, R.B., 2007. Current map-matching algorithms for transport applications: Stateof-the art and future research directions. Transportation Research Part C: Emerging Technologies 15(5), 312-328.
Quddus, M.A., Ochieng, W.Y., Zhao, L., Noland, R.B., 2003. A general mao matching algorithm for transport telematics
applications. GPS Solutions 7(3), 157-167.
Quddus, M.A., Washington, S., 2015. Shortest path and vehicle trajectory aided mapmatching for low frequency GPS
data. Transportation Research Part C: Emerging Technologies 55, 328-339.
van Diggelen, F., 2007. GNSS accuracy: lies, damn lies, and statistics. GPS World 18(1), 26-32.
Velaga, N.R., Quddus, M.A., Bistow, A.L., 2009. Developing an enhanced weight-based topological map-matchingalgorithm for intelligent transport systems. Transportation Research Part C: Emerging Technologies 17, 672-683.
White, C.E., Bernstein, D., Kornhauser, A.L., 2000. Some map matching algorithms for personal navigation assistants.
Transportation Research Part C: Emerging Technologies 8, 91-108.

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

40

Appendix

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury

41

Literature review

Introduction

Previous route measurement models
Geometric
White et al. (2000)

TopologicalGreenfield (2002)

Probabilistic
Ouchieng et al. (2004)
Quddus et al. (2006)- Point-to-point- Point-to-curve- Curve-to-curve- Adjacency- Connectivity- Vehicle heading- Error region- Fuzzy logic

Path-based- MHT

Pyo et al. (2006)- Measurement
equation

Bielraire et al. (2013)

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course

70%
30%

Sep. 29,25, 2016
2016
Jury

42

Methodology

Link-based route measurement model

Link switching | errors
Difficulties regarding link connectivity because of myopic optimization

3
6

1
4
2
m̂

1
1

m̂

1
3

8

m̂12

11

m̂32

9

m̂22 7

m̂

1
2

12

m̂

3
1

m̂23

5

10
m̂33

Oyama, Y. (The University of Tokyo)

15th Behavior Modeling summer course: Estimated path

: More likely path

Sep. 29,25, 2016
2016
Jury

43

Link switching

Link-based route measurement model

Link switching | algorithm
STEP1: Calculating probabilities

pi (at | m̂ , at 1 ) =ti

p(m̂it | at ;at A(at 1 )at)p(at | at 1; )p(m̂ | at ;ti

at)p(at | at 1; )STEP2: Sorting candidates by probabilitiesp(at,1 )[at,1,..., at,r ,..., at,|A(at 1 )| ]p(at,r )p(at,|A(at 1 )| )r=1
STEP3: Calculating measurement equation at (t+1)

LLmr = log ( p(m̂t+1 | at+1;

at+1

))

t+1
where, at+1 = argmax p(a | m̂ , at,r )r := r+1

a

No

LLmr
<
J

No

r =| A(at 1 ) |Yes

at = at,rOyama, Y. (The University of Tokyo)

r := 1

15th Behavior Modeling summer course

Yes

Sep. 29,25, 2016
2016
Jury

44

Real data

Numerical exampless
Twins experiments | iterations

Ave.
25.0
a

80

Estimation error:

Link accuracy (%)

100

60
40
20
0

1

2

3

4

5

6

7

20.0
15.0
10.0
5.0
0

8

1

2

3

Sum.

Estimation error:

6.0
4.0
2.0
0

1

2

3

4

Oyama, Y. (The University of Tokyo)

5

6

7

4
5
#iteration

6

7: input= [ 1.5, 0.1, 2, 10](wrong parameters): input= [0, 0, 0, 0](no information): input= [ 0.1, 2, 1.5, 4](true parameters)

8

8

15th Behavior Modeling summer course

Sep. 29,25, 2016
2016
Jury45