American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Probability hypothesis density filtering for real-time traffic state estimation and prediction
  • NHM Home
  • This Issue
  • Next Article
    Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming
September  2013, 8(3): 803-824. doi: 10.3934/nhm.2013.8.803

Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data

Olli-Pekka Tossavainen 1, and  Daniel B. Work 2,

1. 

Microsoft, 1065 La Avenida St, Mountain View, CA 94043, United States
2. 

University of Illinois at Urbana-Champaign, 1203 Newmark Civil Engineering Laboratory, 205 N. Mathews Ave, Urbana, IL 61801, United States

Received  October 2012 Revised  June 2013 Published  October 2013

In large scale deployments of traffic flow models, estimation of the model parameters is a critical but cumbersome task. A poorly calibrated model leads to erroneous estimates in data--poor environments, and limited forecasting ability. In this article we present a method for calibrating flow model parameters for a discretized scalar conservation law using only velocity measurements. The method is based on a Markov Chain Monte Carlo technique, which is used to approximate statistics of the posterior distribution of the model parameters. Numerical experiments highlight the difficulty in estimating jam densities and provide a new approach to improve performance of the sampling through re-parameterization of the model. Supporting source code for the numerical experiments is available for download at https://github.com/dbwork/MCMC-based-inverse-modeling-of-traffic.
Keywords: Markov Chain, Monte Carlo, cell transmission model., Parameter estimation, fundamental diagram, traffic flow.
Mathematics Subject Classification: 90B20, 65C05, 65C40, 35L65, 65N2.
Citation: Olli-Pekka Tossavainen, Daniel B. Work. Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data. Networks and Heterogeneous Media, 2013, 8 (3) : 803-824. doi: 10.3934/nhm.2013.8.803
References:
[1]

T. Bellemans, B. D. Schutter and B. D. Moor, Model predictive control with repeated model fitting for ramp metering, in "Proceedings of the IEEE 5th Conference on Intelligent Transportation Systems," (2002), 236-241. doi: 10.1109/ITSC.2002.1041221.

[2]

T. Bellemans, B. D. Schutter, G. Wets and B. D. Moor, Model predictive control for ramp metering combined with extended Kalman filter-based traffic state estimation, in "Proceedings of IEEE Intelligent Transportation Systems Conference," (2006), 406-411. doi: 10.1109/ITSC.2006.1706775.

[3]

S. Blandin, A. Couque, A. Bayen and D. Work, On sequential data assimilation for scalar macroscopic traffic flow models, Physica D: Nonlinear Phenomena, 241 (2012), 1421-1440.

[4]

G. Bretti and B. Piccoli, A tracking algorithm for car paths on road networks, SIAM Journal on Applied Dynamical Systems, 7 (2008), 510-531. doi: 10.1137/070697768.

[5]

R. M. Colombo and A. Marson, A Hölder continuous ode related to traffic flow, Proceedings of the Royal Society of Edinburgh: Section A Mathematics, 133 (2003), 759-772. doi: 10.1017/S0308210500002663.

[6]

M. Cremer and M. Papageorgiou, Parameter identification for a traffic flow model, Automatica J. IFAC, 17 (1981), 837-843. doi: 10.1016/0005-1098(81)90071-6.

[7]

E. Cristiani, C. de Fabritiis and B. Piccoli, A fluid dynamic approach for traffic forecast from mobile sensor data, Communications in Applied and Industrial Mathematics, 1 (2010), 54-71.

[8]

G. Dervisoglu, G. Gomes, J. Kwon, R. Horowitz and P. Varaiya, Automatic calibration of the fundamental diagram and empirical observations on capacity, in "Proceedings of the 88th Annual Meeting," Washington, D.C., 2009, Transportation Research Board.

[9]

M. Garavello and B. Piccoli, "Traffic Flow on Networks," Conservation laws models. AIMS Series on Applied Mathematics, 1. American Institute of Mathematical Sciences (AIMS), Springfield, MO, 2006. xvi+243 pp.

[10]

W. Gilks, S. Richardson and D. Spegelhalter, "Markov Chain Monte Carlo in Practice," Interdisciplinary Statistics. Chapman & Hall, London, 1996.

[11]

S. Godunov, A difference method for the numerical calculation of discontinuous solutions of hydrodynamic equations, (Russian) Mat. Sb. (N. S.), 47 (1959), 271-306.

[12]

A. Hegyi, D. Girimonte, R. Babŭska and B. D. Schutter, A comparison of filter configurations for freeway traffic state estimation, in "Proceedings of the 2006 IEEE Intelligent Transportation Systems Conference," Toronto, Canada, 2006, ITSC, 1029-1034. doi: 10.1109/ITSC.2006.1707357.

[13]

J. Kaipio and E. Somersalo, "Statistical and Computational Inverse Problems," Springer, 2005.

[14]

J. Lebacque, The Godunov scheme and what it means for first order traffic flow models, in "13th International Symposium on Transportation and Traffic Theory," (1996), 647-677.

[15]

R. J. LeVeque, "Numerical Methods for Conservation Laws," Second edition. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1992. x+214 pp. doi: 10.1007/978-3-0348-8629-1.

[16]

M. Lighthill and G. Whitham, On kinematic waves. II. A theory of traffic flow on long crowded roads, Proc. Roy. Soc. London. Ser. A. 229 (1955), 317-345. doi: 10.1098/rspa.1955.0089.

[17]

J. V. Lint, S. Hoogendoorn and A. Hegyi, Dual EKF state and parameter estimation in multi-class first-order traffic flow models, in "Proceedings of the 17th World Congress," Seoul, Korea, (2008), The International Federation of Automatic Control.

[18]

X.-Y. Lu, P. Varaiya and R. Horowitz, Fundamental diagram modeling and analysis based on NGSIM data, in "12th IFAC Symposium on Control in Transportation Systems," (2009).

[19]

L. Mihaylova, R. Boel and A. Hegyi, Freeway traffic estimation within particle filtering framework, Automatica J. IFAC, 43 (2007), 290-300. doi: 10.1016/j.automatica.2006.08.023.

[20]

L. Munoz, X. Sun, D. Sun, G. Gomez and R. Horowitz, Methodological calibration of the cell transmission model, in "Proceedings of the American Control Conference," 1, 2004, 798-803.

[21]

A. Muralidharan, G. Dervisoglu and R. Horowitz, Probabilistic graphical models of fundamental diagram parameters for freeway traffic simulations, in "Proceedings of the 90th Annual Meeting," Washington, D.C., (2011), Transportation Research Board. doi: 10.3141/2249-10.

[22]

P. I. Richards, Shock waves on the highway, Operations Research, 4 (1956), 42-51. doi: 10.1287/opre.4.1.42.

[23]

S. Smulders, Control of freeway traffic flow by variable speed signs, Transportation Research Part B: Methodological, 24 (1990), 111-132. doi: 10.1016/0191-2615(90)90023-R.

[24]

Transportation Research Board, "HCM 2010: Highway Capacity Manual," (2010).

[25]

, http://traffic.berkeley.edu.

[26]

Y. Wang, M. Papageorgiou and A. Messmer, RENAISSANCE - A unified macroscopic model-based approach to real-time freeway network traffic surveillance, Transportation Research Part C: Emerging Technologies, 14 (2006), 190-212. doi: 10.1016/j.trc.2006.06.001.

[27]

Y. Wang, M. Papageorgiou and A. Messmer, Real-time freeway traffic state estimation based on extended kalman filter: A case study, Transportation Science, 41 (2007), 167-181. doi: 10.1287/trsc.1070.0194.

[28]

D. Work, S. Blandin, O.-P. Tossavainen, B. Piccoli and A. Bayen, A traffic model for velocity data assimilation, Appl. Math. Res. Express. AMRX, 2010 (2010), 1-35.

[29]

J. Yan, Parameter identification of freeway traffic flow model and adaptive ramp metering, in "2009 Second International Symposium on Electronic Commerce and Security," (2009), 235-238. doi: 10.1109/ISECS.2009.39.

show all references

References:
[1]

T. Bellemans, B. D. Schutter and B. D. Moor, Model predictive control with repeated model fitting for ramp metering, in "Proceedings of the IEEE 5th Conference on Intelligent Transportation Systems," (2002), 236-241. doi: 10.1109/ITSC.2002.1041221.

[2]

T. Bellemans, B. D. Schutter, G. Wets and B. D. Moor, Model predictive control for ramp metering combined with extended Kalman filter-based traffic state estimation, in "Proceedings of IEEE Intelligent Transportation Systems Conference," (2006), 406-411. doi: 10.1109/ITSC.2006.1706775.

[3]

S. Blandin, A. Couque, A. Bayen and D. Work, On sequential data assimilation for scalar macroscopic traffic flow models, Physica D: Nonlinear Phenomena, 241 (2012), 1421-1440.

[4]

G. Bretti and B. Piccoli, A tracking algorithm for car paths on road networks, SIAM Journal on Applied Dynamical Systems, 7 (2008), 510-531. doi: 10.1137/070697768.

[5]

R. M. Colombo and A. Marson, A Hölder continuous ode related to traffic flow, Proceedings of the Royal Society of Edinburgh: Section A Mathematics, 133 (2003), 759-772. doi: 10.1017/S0308210500002663.

[6]

M. Cremer and M. Papageorgiou, Parameter identification for a traffic flow model, Automatica J. IFAC, 17 (1981), 837-843. doi: 10.1016/0005-1098(81)90071-6.

[7]

E. Cristiani, C. de Fabritiis and B. Piccoli, A fluid dynamic approach for traffic forecast from mobile sensor data, Communications in Applied and Industrial Mathematics, 1 (2010), 54-71.

[8]

G. Dervisoglu, G. Gomes, J. Kwon, R. Horowitz and P. Varaiya, Automatic calibration of the fundamental diagram and empirical observations on capacity, in "Proceedings of the 88th Annual Meeting," Washington, D.C., 2009, Transportation Research Board.

[9]

M. Garavello and B. Piccoli, "Traffic Flow on Networks," Conservation laws models. AIMS Series on Applied Mathematics, 1. American Institute of Mathematical Sciences (AIMS), Springfield, MO, 2006. xvi+243 pp.

[10]

W. Gilks, S. Richardson and D. Spegelhalter, "Markov Chain Monte Carlo in Practice," Interdisciplinary Statistics. Chapman & Hall, London, 1996.

[11]

S. Godunov, A difference method for the numerical calculation of discontinuous solutions of hydrodynamic equations, (Russian) Mat. Sb. (N. S.), 47 (1959), 271-306.

[12]

A. Hegyi, D. Girimonte, R. Babŭska and B. D. Schutter, A comparison of filter configurations for freeway traffic state estimation, in "Proceedings of the 2006 IEEE Intelligent Transportation Systems Conference," Toronto, Canada, 2006, ITSC, 1029-1034. doi: 10.1109/ITSC.2006.1707357.

[13]

J. Kaipio and E. Somersalo, "Statistical and Computational Inverse Problems," Springer, 2005.

[14]

J. Lebacque, The Godunov scheme and what it means for first order traffic flow models, in "13th International Symposium on Transportation and Traffic Theory," (1996), 647-677.

[15]

R. J. LeVeque, "Numerical Methods for Conservation Laws," Second edition. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1992. x+214 pp. doi: 10.1007/978-3-0348-8629-1.

[16]

M. Lighthill and G. Whitham, On kinematic waves. II. A theory of traffic flow on long crowded roads, Proc. Roy. Soc. London. Ser. A. 229 (1955), 317-345. doi: 10.1098/rspa.1955.0089.

[17]

J. V. Lint, S. Hoogendoorn and A. Hegyi, Dual EKF state and parameter estimation in multi-class first-order traffic flow models, in "Proceedings of the 17th World Congress," Seoul, Korea, (2008), The International Federation of Automatic Control.

[18]

X.-Y. Lu, P. Varaiya and R. Horowitz, Fundamental diagram modeling and analysis based on NGSIM data, in "12th IFAC Symposium on Control in Transportation Systems," (2009).

[19]

L. Mihaylova, R. Boel and A. Hegyi, Freeway traffic estimation within particle filtering framework, Automatica J. IFAC, 43 (2007), 290-300. doi: 10.1016/j.automatica.2006.08.023.

[20]

L. Munoz, X. Sun, D. Sun, G. Gomez and R. Horowitz, Methodological calibration of the cell transmission model, in "Proceedings of the American Control Conference," 1, 2004, 798-803.

[21]

A. Muralidharan, G. Dervisoglu and R. Horowitz, Probabilistic graphical models of fundamental diagram parameters for freeway traffic simulations, in "Proceedings of the 90th Annual Meeting," Washington, D.C., (2011), Transportation Research Board. doi: 10.3141/2249-10.

[22]

P. I. Richards, Shock waves on the highway, Operations Research, 4 (1956), 42-51. doi: 10.1287/opre.4.1.42.

[23]

S. Smulders, Control of freeway traffic flow by variable speed signs, Transportation Research Part B: Methodological, 24 (1990), 111-132. doi: 10.1016/0191-2615(90)90023-R.

[24]

Transportation Research Board, "HCM 2010: Highway Capacity Manual," (2010).

[25]

, http://traffic.berkeley.edu.

[26]

Y. Wang, M. Papageorgiou and A. Messmer, RENAISSANCE - A unified macroscopic model-based approach to real-time freeway network traffic surveillance, Transportation Research Part C: Emerging Technologies, 14 (2006), 190-212. doi: 10.1016/j.trc.2006.06.001.

[27]

Y. Wang, M. Papageorgiou and A. Messmer, Real-time freeway traffic state estimation based on extended kalman filter: A case study, Transportation Science, 41 (2007), 167-181. doi: 10.1287/trsc.1070.0194.

[28]

D. Work, S. Blandin, O.-P. Tossavainen, B. Piccoli and A. Bayen, A traffic model for velocity data assimilation, Appl. Math. Res. Express. AMRX, 2010 (2010), 1-35.

[29]

J. Yan, Parameter identification of freeway traffic flow model and adaptive ramp metering, in "2009 Second International Symposium on Electronic Commerce and Security," (2009), 235-238. doi: 10.1109/ISECS.2009.39.

[1]

Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
[2]

Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683
[3]

Juntao Yang, Viet Ha Hoang. Multilevel Markov Chain Monte Carlo for Bayesian inverse problem for Navier-Stokes equation. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022033
[4]

Luisa Fermo, Andrea Tosin. Fundamental diagrams for kinetic equations of traffic flow. Discrete and Continuous Dynamical Systems - S, 2014, 7 (3) : 449-462. doi: 10.3934/dcdss.2014.7.449
[5]

Zhiyan Ding, Qin Li. Constrained Ensemble Langevin Monte Carlo. Foundations of Data Science, 2022, 4 (1) : 37-70. doi: 10.3934/fods.2021034
[6]

Azmy S. Ackleh, Jeremy J. Thibodeaux. Parameter estimation in a structured erythropoiesis model. Mathematical Biosciences & Engineering, 2008, 5 (4) : 601-616. doi: 10.3934/mbe.2008.5.601
[7]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic and Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[8]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems and Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[9]

Theodore Papamarkou, Alexey Lindo, Eric B. Ford. Geometric adaptive Monte Carlo in random environment. Foundations of Data Science, 2021, 3 (2) : 201-224. doi: 10.3934/fods.2021014
[10]

Alex Capaldi, Samuel Behrend, Benjamin Berman, Jason Smith, Justin Wright, Alun L. Lloyd. Parameter estimation and uncertainty quantification for an epidemic model. Mathematical Biosciences & Engineering, 2012, 9 (3) : 553-576. doi: 10.3934/mbe.2012.9.553
[11]

Alexandre M. Bayen, Hélène Frankowska, Jean-Patrick Lebacque, Benedetto Piccoli, H. Michael Zhang. Special issue on Mathematics of Traffic Flow Modeling, Estimation and Control. Networks and Heterogeneous Media, 2013, 8 (3) : i-ii. doi: 10.3934/nhm.2013.8.3i
[12]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[13]

Gianni Gilioli, Sara Pasquali, Fabrizio Ruggeri. Nonlinear functional response parameter estimation in a stochastic predator-prey model. Mathematical Biosciences & Engineering, 2012, 9 (1) : 75-96. doi: 10.3934/mbe.2012.9.75
[14]

Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Numerical approximations of a traffic flow model on networks. Networks and Heterogeneous Media, 2006, 1 (1) : 57-84. doi: 10.3934/nhm.2006.1.57
[15]

Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427
[16]

Wen Shen, Karim Shikh-Khalil. Traveling waves for a microscopic model of traffic flow. Discrete and Continuous Dynamical Systems, 2018, 38 (5) : 2571-2589. doi: 10.3934/dcds.2018108
[17]

Michael Herty, J.-P. Lebacque, S. Moutari. A novel model for intersections of vehicular traffic flow. Networks and Heterogeneous Media, 2009, 4 (4) : 813-826. doi: 10.3934/nhm.2009.4.813
[18]

Ángela Jiménez-Casas, Aníbal Rodríguez-Bernal. Linear model of traffic flow in an isolated network. Conference Publications, 2015, 2015 (special) : 670-677. doi: 10.3934/proc.2015.0670
[19]

Zhigang Ren, Shan Guo, Zhipeng Li, Zongze Wu. Adjoint-based parameter and state estimation in 1-D magnetohydrodynamic (MHD) flow system. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1579-1594. doi: 10.3934/jimo.2018022
[20]

Jingzhi Tie, Qing Zhang. An optimal mean-reversion trading rule under a Markov chain model. Mathematical Control and Related Fields, 2016, 6 (3) : 467-488. doi: 10.3934/mcrf.2016012

2021 Impact Factor: 1.41

Tools

Metrics

  • PDF downloads (148)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy