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 & 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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[13]

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

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[22]

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

[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.  Google Scholar

[24]

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

[25]

, , ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[13]

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

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[22]

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

[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.  Google Scholar

[24]

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

[25]

, , ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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]

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

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
[5]

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

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

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
[8]

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 & Heterogeneous Media, 2013, 8 (3) : i-ii. doi: 10.3934/nhm.2013.8.3i
[9]

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

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
[11]

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

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

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

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

Á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
[16]

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

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

Jinliang Wang, Jiying Lang, Yuming Chen. Global dynamics of an age-structured HIV infection model incorporating latency and cell-to-cell transmission. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3721-3747. doi: 10.3934/dcdsb.2017186
[19]

Jinhu Xu, Yicang Zhou. Bifurcation analysis of HIV-1 infection model with cell-to-cell transmission and immune response delay. Mathematical Biosciences & Engineering, 2016, 13 (2) : 343-367. doi: 10.3934/mbe.2015006
[20]

Chjan C. Lim, Joseph Nebus, Syed M. Assad. Monte-Carlo and polyhedron-based simulations I: extremal states of the logarithmic N-body problem on a sphere. Discrete & Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313

2019 Impact Factor: 1.053

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences