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

Previous Article
Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming
NHM Home
This Issue
Next Article
Probability hypothesis density filtering for real-time traffic state estimation and prediction

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

Abstract
Related Papers

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, (2002), 236. 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, (2006), 406. 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.
[4]	G. Bretti and B. Piccoli, A tracking algorithm for car paths on road networks,, SIAM Journal on Applied Dynamical Systems, 7 (2008), 510. 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. doi: 10.1017/S0308210500002663.
[6]	M. Cremer and M. Papageorgiou, Parameter identification for a traffic flow model,, Automatica J. IFAC, 17 (1981), 837. 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.
[8]	G. Dervisoglu, G. Gomes, J. Kwon, R. Horowitz and P. Varaiya, Automatic calibration of the fundamental diagram and empirical observations on capacity,, in, (2009).
[9]	M. Garavello and B. Piccoli, "Traffic Flow on Networks,", Conservation laws models. AIMS Series on Applied Mathematics, (2006).
[10]	W. Gilks, S. Richardson and D. Spegelhalter, "Markov Chain Monte Carlo in Practice,", Interdisciplinary Statistics. Chapman & Hall, (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.
[12]	A. Hegyi, D. Girimonte, R. Babŭska and B. D. Schutter, A comparison of filter configurations for freeway traffic state estimation,, in, (2006), 1029. 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, (1996), 647.
[15]	R. J. LeVeque, "Numerical Methods for Conservation Laws,", Second edition. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, (1992). 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), 229* (1955), 317. 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, (2008).
[18]	X.-Y. Lu, P. Varaiya and R. Horowitz, Fundamental diagram modeling and analysis based on NGSIM data,, in, (2009).
[19]	L. Mihaylova, R. Boel and A. Hegyi, Freeway traffic estimation within particle filtering framework,, Automatica J. IFAC, 43 (2007), 290. 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, 1 (2004), 798.
[21]	A. Muralidharan, G. Dervisoglu and R. Horowitz, Probabilistic graphical models of fundamental diagram parameters for freeway traffic simulations,, in, (2011). doi: 10.3141/2249-10.
[22]	P. I. Richards, Shock waves on the highway,, Operations Research, 4 (1956), 42. 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. doi: 10.1016/0191-2615(90)90023-R.
[24]	Transportation Research Board, "HCM 2010: Highway Capacity Manual,", (2010)., (2010).
[25]	, , ().
[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. 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. 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.
[29]	J. Yan, Parameter identification of freeway traffic flow model and adaptive ramp metering,, in, (2009), 235. 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, (2002), 236. 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, (2006), 406. 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.
[4]	G. Bretti and B. Piccoli, A tracking algorithm for car paths on road networks,, SIAM Journal on Applied Dynamical Systems, 7 (2008), 510. 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. doi: 10.1017/S0308210500002663.
[6]	M. Cremer and M. Papageorgiou, Parameter identification for a traffic flow model,, Automatica J. IFAC, 17 (1981), 837. 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.
[8]	G. Dervisoglu, G. Gomes, J. Kwon, R. Horowitz and P. Varaiya, Automatic calibration of the fundamental diagram and empirical observations on capacity,, in, (2009).
[9]	M. Garavello and B. Piccoli, "Traffic Flow on Networks,", Conservation laws models. AIMS Series on Applied Mathematics, (2006).
[10]	W. Gilks, S. Richardson and D. Spegelhalter, "Markov Chain Monte Carlo in Practice,", Interdisciplinary Statistics. Chapman & Hall, (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.
[12]	A. Hegyi, D. Girimonte, R. Babŭska and B. D. Schutter, A comparison of filter configurations for freeway traffic state estimation,, in, (2006), 1029. 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, (1996), 647.
[15]	R. J. LeVeque, "Numerical Methods for Conservation Laws,", Second edition. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, (1992). 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), 229* (1955), 317. 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, (2008).
[18]	X.-Y. Lu, P. Varaiya and R. Horowitz, Fundamental diagram modeling and analysis based on NGSIM data,, in, (2009).
[19]	L. Mihaylova, R. Boel and A. Hegyi, Freeway traffic estimation within particle filtering framework,, Automatica J. IFAC, 43 (2007), 290. 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, 1 (2004), 798.
[21]	A. Muralidharan, G. Dervisoglu and R. Horowitz, Probabilistic graphical models of fundamental diagram parameters for freeway traffic simulations,, in, (2011). doi: 10.3141/2249-10.
[22]	P. I. Richards, Shock waves on the highway,, Operations Research, 4 (1956), 42. 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. doi: 10.1016/0191-2615(90)90023-R.
[24]	Transportation Research Board, "HCM 2010: Highway Capacity Manual,", (2010)., (2010).
[25]	, , ().
[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. 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. 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.
[29]	J. Yan, Parameter identification of freeway traffic flow model and adaptive ramp metering,, in, (2009), 235. doi: 10.1109/ISECS.2009.39.

[1]	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
[2]	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
[3]	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
[4]	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
[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]	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
[7]	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
[8]	Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-23. doi: 10.3934/dcdsb.2018335
[9]	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
[10]	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
[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 - A, 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]	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
[18]	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
[19]	Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125
[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

2017 Impact Factor: 1.187

American Institute of Mathematical Sciences