Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Estimation of sparse O–D matrix accounting for demand volatility

© The Institution of Engineering and Technology
Received 26/01/2018, Accepted 24/05/2018, Revised 22/04/2018, Published 16/07/2018

A critical issue in origin–destination (O–D) demand estimation is under-determination: the number of O–D pairs to be estimated is often much greater than the number of monitored links. In real world, some centroids tend to be more popular than others, and only few trips are made for intro-zonal travel. Consequently, a large portion of trips will be made for a small portion of O–D pairs, meaning many O–D pairs have only a few or even zero trips. Mathematically, this implies that the O–D matrix is sparse. Also, the correlation between link flows is often neglected in the O–D estimation problem, which can be obtained from day-to-day loop detector count data. Thus, sparsity regularisation is combined with link flow correlation to provide additional inputs for the O–D estimation process to mitigate the issue of under-determination and thereby improve estimation quality. In addition, a novel strategic user equilibrium model is implemented to provide route choice of users for the O–D estimation problem, which explicitly accounts for demand and link flow volatility. The model is formulated as a convex generalised least squares problem with regularisation, the usefulness of sparsity assumption, and link flow correlation is presented in the numerical analysis.

Inspec keywords: least squares approximations; convex programming; behavioural sciences; matrix algebra; vehicle routing

Other keywords: strategic user equilibrium model; link flow correlation; route choice; O-D demand estimation; sparse O-D matrix estimation; day-to-day loop detector count data; estimation quality; demand volatility; numerical analysis; intro-zonal travel; O-D estimation process; convex generalised least squares problem-with-regularisation; O-D pairs; origin-destination demand estimation; sparsity regularisation

Subjects: Linear algebra (numerical analysis); Systems theory applications in transportation; Interpolation and function approximation (numerical analysis); Optimisation techniques; Systems theory applications in social science and politics

References

    1. 1)
      • 22. Cipriani, E., Nigro, M., Fusco, G., et al: ‘Effectiveness of link and path information on simultaneous adjustment of dynamic od demand matrix’, Eur. Transp. Res. Rev., 2014, 6, (2), pp. 139–148.
    2. 2)
      • 54. Chen, S.S., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAM Rev., 2001, 43, (1), pp. 129–159.
    3. 3)
      • 1. Castillo, E., Menéndez, J.M., Sánchez-Cambronero, S., et al: ‘A hierarchical optimization problem: estimating traffic flow using gamma random variables in a Bayesian context’, Comput. Oper. Res., 2014, 41, pp. 240–251.
    4. 4)
      • 31. Reddy, K.H., Chakroborty, P.: ‘A fuzzy inference based assignment algorithm to estimate OD matrix from link volume counts’, Comput. Environ. Urban Syst., 1998, 22, (5), pp. 409–423.
    5. 5)
      • 28. Baek, S., Kim, H., Lim, Y.: ‘Multiple-vehicle origin-destination matrix estimation from traffic counts using genetic algorithm’, J. Transp. Eng., 2004, 130, (3), pp. 339–347.
    6. 6)
      • 4. Menon, A.K., Cai, C., Wang, W., et al: ‘Fine-grained OD estimation with automated zoning and sparsity regularisation’, Transp. Res. B, Methodol., 2015, 80, pp. 150–172.
    7. 7)
      • 7. Goel, P., McCord, M., Park, C.: ‘Exploiting correlations between link flows to improve estimation of average annual daily traffic on coverage count segments: methodology and numerical study’, Transp. Res. Rec., J. Transp. Res. Board, 2005, 1917, pp. 100–107.
    8. 8)
      • 41. Szeto, W., Jiang, Y., Sumalee, A.: ‘A cell-based model for multi-class doubly stochastic dynamic traffic assignment’, Comput.-Aided Civ. Infrastruct. Eng., 2011, 26, (8), pp. 595–611.
    9. 9)
      • 39. Nie, Y., Zhang, H., Recker, W.: ‘Inferring origin–destination trip matrices with a decoupled GLS path flow estimator’, Transp. Res. B, Methodol., 2005, 39, (6), pp. 497–518.
    10. 10)
      • 3. Bera, S., Rao, K.: ‘Estimation of origin-destination matrix from traffic counts: the state of the art’, Eur. Transp., 2011, 49, pp. 2–23.
    11. 11)
      • 27. Kattan, L., Abdulhai, B.: ‘Noniterative approach to dynamic traffic origin-destination estimation with parallel evolutionary algorithms’, Transp. Res. Rec., J. Transp. Res. Board, 2006, 1964, pp. 201–210.
    12. 12)
      • 57. Clark, S., Watling, D.: ‘Modelling network travel time reliability under stochastic demand’, Transp. Res. B, Methodol., 2005, 39, (2), pp. 119–140.
    13. 13)
      • 33. Cao, J., Davis, D., Vander Wiel, S., et al: ‘Time-varying network tomography: router link data’, J. Am. Stat. Assoc., 2000, 95, (452), pp. 1063–1075.
    14. 14)
      • 23. Nie, Y.M., Zhang, H.M.: ‘A variational inequality formulation for inferring dynamic origin–destination travel demands’, Transp. Res. B, Methodol., 2008, 42, (7), pp. 635–662.
    15. 15)
      • 34. Airoldi, E.M., Blocker, A.W.: ‘Estimating latent processes on a network from indirect measurements’, J. Am. Stat. Assoc., 2013, 108, (501), pp. 149–164.
    16. 16)
      • 10. Wen, T., Cai, C., Gardner, L., et al: ‘A strategic user equilibrium for independently distributed origin-destination demands’, Comput.-Aided Civ. Infrastruct. Eng., 2018, 33, (4), pp. 316–332.
    17. 17)
      • 47. Wen, T., Cai, C., Gardner, L., et al: ‘A strategic user equilibrium for independently distributed origin-destination demands’, Comput.-Aided Civ. Infrastruct. Eng., 2018, 33, (4), pp. 316–332.
    18. 18)
      • 60. Bar-Gera, H.: ‘Transportation test problems of Sioux falls network’, 2012. Available at http://www.bgu.ac.il/~bargera/tntp/.
    19. 19)
      • 8. Hazelton, M.L.: ‘Inference for origin–destination matrices: estimation, prediction and reconstruction’, Transp. Res. B, Methodol., 2001, 35, (7), pp. 667–676.
    20. 20)
      • 51. Chawla, S., Zheng, Y., Hu, J.: ‘Inferring the root cause in road traffic anomalies’. 2012 IEEE 12th Int. Conf. on Data Mining, Brussels, Belgium, 2012.
    21. 21)
      • 38. Sherali, H.D., Narayanan, A., Sivanandan, R.: ‘Estimation of origin–destination trip-tables based on a partial set of traffic link volumes’, Transp. Res. B, Methodol., 2003, 37, (9), pp. 815–836.
    22. 22)
      • 36. Bell, M.G.H.: ‘The estimation of an origin-destination matrix from traffic counts’, Transp. Sci., 1983, 17, (2), pp. 198–217.
    23. 23)
      • 58. Tibshirani, R.: ‘Regression shrinkage and selection via the Lasso’, J. R. Stat. Soc. B, Methodol., 1996, 58, (1), pp. 267–288.
    24. 24)
      • 15. Kim, H., Baek, S., Lim, Y.: ‘Origin-destination matrices estimated with a genetic algorithm from link traffic counts’, Transp. Res. Rec., J. Transp. Res. Board, 2001, 1771, pp. 156–163.
    25. 25)
      • 16. Tebaldi, C., West, M.: ‘Bayesian inference on network traffic using link count data’, J. Am. Stat. Assoc., 1998, 93, (442), pp. 557–573.
    26. 26)
      • 32. Gong, Z.: ‘Estimating the urban OD matrix: a neural network approach’, Eur. J. Oper. Res., 1998, 106, (1), pp. 108–115.
    27. 27)
      • 61. Hurley, N., Rickard, S.: ‘Comparing measures of sparsity’, IEEE Trans. Inf. Theory, 2009, 55, (10), pp. 4723–4741.
    28. 28)
      • 42. Brilon, W., Geistefeldt, J., Regler, M.: ‘Reliability of freeway traffic flow: a stochastic concept of capacity’. Proc. of the 16th Int. Symp. on Transportation and Traffic Theory, Maryland, USA, 2005.
    29. 29)
      • 29. Wong, S., Tong, C., Wong, K., et al: ‘Estimation of multiclass origin-destination matrices from traffic counts’, J. Urban Plan. Dev., 2005, 131, (1), pp. 19–29.
    30. 30)
      • 52. Zhang, Y., Ge, Z., Greenberg, A., et al: ‘Network anomography’. Proc. of the 5th ACM SIGCOMM Conf. on Internet Measurement, Berkeley, CA, USA, 2005.
    31. 31)
      • 21. Frederix, R., Viti, F., Tampère, C.M.J.: ‘Dynamic origin–destination estimation in congested networks: theoretical findings and implications in practice’, Transportmetrica A, Transp. Sci., 2011, 9, (6), pp. 494–513.
    32. 32)
      • 35. Cremer, M., Keller, H.: ‘A new class of dynamic methods for the identification of origin-destination flows’, Transp. Res. B, Methodol., 1987, 21, (2), pp. 117–132.
    33. 33)
      • 49. Duell, M., Gardner, L., Dixit, V., et al: ‘Evaluation of a strategic road pricing scheme accounting for day-to-day and long term demand uncertainty’. Transportation Research Board 93rd Annual Meeting, Washington, DC, USA, 2014.
    34. 34)
      • 5. Cascetta, E.: ‘Estimation of trip matrices from traffic counts and survey data: a generalized least squares estimator’, Transp. Res. B, Methodol., 1984, 18, (4–5), pp. 289–299.
    35. 35)
      • 37. Chen, A., Chootinan, P., Recker, W.: ‘Norm approximation method for handling traffic count inconsistencies in path flow estimator’, Transp. Res. B, Methodol., 2009, 43, (8), pp. 852–872.
    36. 36)
      • 24. Sherali, H.D., Park, T.: ‘Estimation of dynamic origin–destination trip tables for a general network’, Transp. Res. B, Methodol., 2001, 35, (3), pp. 217–235.
    37. 37)
      • 62. Hoyer, P.O.: ‘Non-negative matrix factorization with sparseness constraints’, J. Mach. Learn. Res., 2004, 5, pp. 1457–1469.
    38. 38)
      • 56. Zou, H., Hastie, T.: ‘Regularization and variable selection via the elastic net’, J. R. Stat. Soc. B, Stat. Methodol., 2005, 67, (2), pp. 301–320.
    39. 39)
      • 25. Lo, H., Zhang, N., Lam, W.: ‘Decomposition algorithm for statistical estimation of od matrix with random link choice proportions from traffic counts’, Transp. Res. B, Methodol., 1999, 33, (5), pp. 369–385.
    40. 40)
      • 6. Bell, M.G.H.: ‘The estimation of origin-destination matrices by constrained generalised least squares’, Transp. Res. B, Methodol., 1991, 25, (1), pp. 13–22.
    41. 41)
      • 12. Appiah, J.: ‘Quantifying uncertainties in synthetic origin-destination trip matrix estimates’, The University of Nebraska-Lincoln, 2009.
    42. 42)
      • 55. Cheman, K.M.: ‘Optimization techniques for solving basis pursuit problems’, North Carolina State University, 2006.
    43. 43)
      • 48. Waller, S.T., Fajardo, D., Duell, M., et al: ‘Linear programming formulation for strategic dynamic traffic assignment’, Netw. Spat. Econ., 2013, 13, (4), pp. 1–17.
    44. 44)
      • 11. Willumsen, L.: ‘Simplified transport models based on traffic counts’, Transportation, 1981, 10, (3), pp. 257–278.
    45. 45)
      • 14. Spiess, H.: ‘A maximum likelihood model for estimating origin-destination matrices’, Transp. Res. B, Methodol., 1987, 21, (5), pp. 395–412.
    46. 46)
      • 45. Duthie, J.C., Unnikrishnan, A., Waller, S.T.: ‘Influence of demand uncertainty and correlations on traffic predictions and decisions’, Comput.-Aided Civ. Infrastruct. Eng., 2011, 26, (1), pp. 16–29.
    47. 47)
      • 43. Wu, X., Michalopoulos, P., Liu, H.X.: ‘Stochasticity of freeway operational capacity and chance-constrained ramp metering’, Transp. Res. C, Emerg. Technol., 2010, 18, (5), pp. 741–756.
    48. 48)
      • 40. Kim, J., Kurauchi, F., Uno, N.: ‘Analysis of variation in demand and performance of urban expressways using dynamic path flow estimation’, Transportmetrica, 2009, 7, (1), pp. 63–84.
    49. 49)
      • 20. Bierlaire, M., Toint, P.L.: ‘Meuse: an origin-destination matrix estimator that exploits structure’, Transp. Res. B, Methodol., 1995, 29, (1), pp. 47–60.
    50. 50)
      • 50. Mardani, M., Giannakis, G.: ‘Robust network traffic estimation via sparsity and low rank’. 2013 IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), Vancouver, Canada, 2013.
    51. 51)
      • 46. Dixit, V., Gardner, L.M., Waller, S.T.: ‘Strategic user equilibrium assignment under trip variability’. Transportation Research Board 92nd Annual Meeting, Washington, DC, USA, 2013.
    52. 52)
      • 19. Aerde, M., Rakha, H., Paramahamsan, H.: ‘Estimation of origin-destination matrices: relationship between practical and theoretical considerations’, Transp. Res. Rec., J. Transp. Res. Board, 2003, 1831, pp. 122–130.
    53. 53)
      • 44. Uchida, T., Iida, Y.: ‘Risk assignment. A new traffic assignment model considering the risk of travel time variation’. Proc. of the 12th Int. Symp. on the Theory of Traffic Flow and Transportation, Berkeley, CA, USA, 21–23 July 1993.
    54. 54)
      • 9. Hazelton, M.L.: ‘Some comments on origin–destination matrix estimation’, Transp. Res. A, Policy Pract., 2003, 37, (10), pp. 811–822.
    55. 55)
      • 18. Fisk, C.S.: ‘On combining maximum entropy trip matrix estimation with user optimal assignment’, Transp. Res. B, Methodol., 1988, 22, (1), pp. 69–73.
    56. 56)
      • 13. Bierlaire, M.: ‘Mathematical models for transportation demand analysis’, Transp. Res. A, Policy Pract., 1997, 31, (1), pp. 86–86.
    57. 57)
      • 59. Donoho, D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1289–1306.
    58. 58)
      • 2. Hazelton, M.L.: ‘Network tomography for integer-valued traffic’, Ann. Appl. Stat., 2015, 9, (1), pp. 474–506.
    59. 59)
      • 30. Foulds, L.R., do Nascimento, H.A.D., Calixto, I.C.A.C., et al: ‘A fuzzy set-based approach to origin–destination matrix estimation in urban traffic networks with imprecise data’, Eur. J. Oper. Res., 2013, 231, (1), pp. 190–201.
    60. 60)
      • 17. Li, B.: ‘Bayesian inference for origin-destination matrices of transport networks using the EM algorithm’, Technometrics, 2005, 47, (4), pp. 399–408.
    61. 61)
      • 26. Wen, T., Gardner, L., Dixit, V., et al: ‘Two methods to calibrate the total travel demand and variability for a regional traffic network’, Comput.-Aided Civ. Infrastruct. Eng., 2018, 33, (4), pp. 282–299.
    62. 62)
      • 53. Sanandaji, B.M., Varaiya, P.P.: ‘Compressive origin-destination matrix estimation’, arXiv preprint arXiv:1404.3263, 2014.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2018.0069
Loading

Related content

content/journals/10.1049/iet-its.2018.0069
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address