International Journal of Transportation Engineering

International Journal of Transportation Engineering

Presenting an Algebraic Method for Optimally Locating Counter Sensors on a Traffic Network for Estimating the OD Matrix

Document Type : Research Paper

Authors
Navid Hosseini Taleghani 1
Seyed Ehsan Seyedabrishami 2
Mahmoud Saffarzadeh 3
1 Ph.D., Tarahan Parseh Transportation Research Institute, Tehran, Iran
2 Associate Professor, Faculty of Civil and Environmental Engineering, Tarbiat Modares University, Tehran, Iran
3 Professor, Faculty of Civil and Environmental Engineering, Tarbiat Modares University, Tehran, Iran
10.22119/ijte.2024.412826.1647
Abstract
For several decades, finding the optimal location of counting sensors in a traffic network to obtain the best estimates of the O-D matrix has attracted a growing amount of attention. The availability and the accuracy of a priori data in a network such as O-D matrix and route choice probabilities on one hand, and the complexity of the mathematical operations for solving the location problem even in not a large network, on the other hand, are two main concerns of the presented methods. This paper aims to propose a method that identifies optimum locations for counting sensors without utilizing any a priori data. Relying on the network topological characteristics and link travel times as the representation of the network’s pattern of trips is the core concept of this study. By taking benefit of the frame theory algebraic operations, needless of any pre-given a priori data, the location set vector with higher coverage on the network route vectors is identified as the optimal location set of the sensor-equipped network links based on its representation in the route-vectors frame. The most probable used paths are identified utilizing an efficient path algorithm. Additionally, by taking advantage of the matrix operations, the novel method obviates the calculations required in methods using linear or non-linear programming solutions. The presented method is applied on a test network and the results show that in comparison to the non-linear programming method, the proposed method finds a better solution.
Keywords
Counting Sensors Location
Frame Theory
O-D Matrix Estimation
Traffic Network
  • Cascetta, Transportation_Systems_Analysis: Models and Applications, New York: Springer, 2009.

 

  • J. Van Zuylen and L. G. Willumsen, "The Most Likely Trip Matrix Estimated from Traffic Counts," Transportation Research Part B: Vol. 14B, pp. 281-293, 1980.

 

  • H. K. Lam and H. P. Lo, "Estimation of origin-destination matrix from traffic counts: a comparison of entropy maximizing and information minimizing models," Transportation Planning and Technology, Vol. 16, pp. 85-104, 1991.

 

  • Gentili and P. Mirchandani, "Locating sensors on traffic networks- Models, challenges and research opportunities," Transportation Research Part C 24, p. 227–255, 2012.

 

  • Bianco, G. Confessore and P. Reverberi, "A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates," Transportation Science, pp. Vol. 35, No. 1, pp. 50–60, 2001.

 

  • Bianco, G. Confessore and M. Gentili, "Combinatorial aspects of the sensor location problem," Annals of Operations Research 144, p. 201–234, 2006.

 

  • Morrison and S. Martonosi, "Where are all the cars? Characteristics of optimal solutions to the sensor location problem," INFORMS Annual Meeting 2008, Washington DC, 2008.

 

  • Morrison, S. Martosoni and K. Tucker, "Characteristics of Optimal Solutions to the Sensor Location Problem.," Thesis, Harvey Mudd College, Department of Mathematics, 2008.

 

  • Bianco, R. Cerulli, C. Cerrone and M. Gentili, "An optimization mathematical model and an exact algorithm for the sensor location problem," In: Proceedings of Euro Working Group in Location Analysis, 2010.

 

  • Castillo, Z. Grande, A. Calviño, W. Y. Szeto and H. K. Lo, "A State-of-the-Art Review of the Sensor Location, Flow Observability, Estimation, and Prediction Problems in Traffic Networks," Hindawi Journal of Sensors, 2015.

 

  • Hu, S. Peeta and C. Chu, "Identification of vehicle sensor locations for link-based network traffic applications," Transportation Research Part B 43 (8–9), p. 873–894, 2009.

 

  • -x. He, "A graphical approach to identify sensor locations for link flow inference," Transportation Research Part B, p. 65–76, 2013.

 

  • Viti, M. Rinaldi, F. Corman and C. M. Tampère, "Assessing partial observability in network sensor location Problems," Transportation Research Part B 70 (2014), p. 65–89, 2014.

 

  • Ng, "Partial link flow observability in the presence of initial sensors: Solution without path enumeration," Transportation Research Part E, 51, p. 62–66, 2013.

 

  • Rinaldi and F. Viti, "Exact and approximate route set generation for resilient partial observability in sensor location problems," Transportation Research Part B 105, p. 86–119, 2017.

 

  • Sun, W.-L. Jin and M. Ng, "Network sensor health problem," Transportation Research Part C 68, pp. 300-310, 2016.

 

  • Ng, "Synergistic sensor location for link flow inference without path enumeration: a node-based approach," Transportation Research Part B: Methodological 46 (3), p. 781–788, 2012.

 

  • Salari, L. Kattan, W. H. Lam and H. Lo, "Optimization of traffic sensor location for complete link flow observability in traffic network considering sensor failure," Transportation Research Part B 121, p. 216–251, 2019.

 

  • Shao, L. Sun and X. Shao, "Sensor location problem for network traffic flow derivation based on turning ratios at intersection," Mathematical Problems in Engineering, 2016.

 

  • Bao, H. Li, L. Qin, D. Xu, B. Ran and J. Rong, "Sensor Location Problem Optimization for Traffic Network with Different Spatial Distributions of Traffic Information," Sensors, 2016.

 

  • Ahmed, D. Watling and D. Ngoduy, "Significance of sensor location in real-time traffic state estimation," in Fourth International Symposium on Infrastructure Engineering in Developing Countries, IEDC, Karachi, Pakistan, 2013.

 

  • Castillo, I. Gallego, S. Sánchez-Cambronero and A. Rivas, "Matrix Tools for General Observability Analysis in Traffic Networks," IEEE Transactions on Intelligent Tranportation Systems, Vol. 11, No. 4, pp. 799-812, 2010a.

 

  • Castillo, I. Gallego, J. M. Menéndez and A. Rivas, "Optimal Use of Plate-Scanning Resources for Route Flow Estimation in Traffic Networks," IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, VOL. 11, NO. 2,, 2010b.

 

  • Xu, K. L. Hong, A. Chen and E. Castillo, "Robust network sensor location for complete link flow observability under uncertainty," Transportation Research Part B 88, pp. 1-20, 2016.

 

  • Wang and P. Mirchandani, "Sensor location model to optimize origin-destination estimation with a bayesian statistical procedure," Transportation Research Record, pp. No. 2334, pp. 29–39., 2013.

 

  • Cascetta, "Estimation of trip matrices from traffic counts and survey data: a generalized least squares estimator," Transportation Research Part B 18 (4–5), p. 289–, 1984.

 

  • Spiess, "A maximum likelihood model for estimating origin–destination matrices," Transportation Research Part B 21 (5), p. 395–412, 1987.

 

  • Teodorovic, M. van Aerde, F. Zhu and F. Dion, "Genetic algorithms approach for locating automatic vehicle identification equipment locations," Journal of Advanced Transportation 36 (1), p. 1–21, 2002.

 

  • Nihan and G. Davis, "Recursive estimation of origin–destination matrices from input/output counts," Transp. Res. Part B 21 (2), p. 149–163, 1987.

 

  • Fei, S. Eisenman and H. Mahmassani, "Sensor coverage and location for real-time traffic prediction in large-scale networks," In: Proceedings of the 86th Annual Meeting of the Transportation Research Board, Washington DC, 2007.

 

  • Fisk, "On combining maximum entropy trip matrix estimation with user optimal assignmwnt," Transportation Research B, pp. Vol. 22, pp. 69–79, 1988.

 

  • Maher, "Inferences on trip matrices from observations on link volumes: a Bayesian statistical approach," Transp. Res. Part B 17 (6), p. 435–447, 1983.

 

  • Yang, T. Sasaki, Y. Iida and Y. Asakura, "Estimation of origin–destination matrices from link traffic counts on congested networks," Transp. Res. Part B26, p. 417–434, 1992.

 

  • Yang and J. Zhou, "Optimal traffic counting locations for origin–destination matrix estimation," Transportation Research Part B 32, p. 109–126, 1998.

 

  • Sherali, R. Sivanandan and A. Hobeika, "A linear programming approach for synthesizing origin–destination trip tables from link traffic volumes," Transp. Res. Part B 28 (3), p. 213–233, 1994.

 

  • Liu, N. Zhu, S. Ma and N. Jia, "Traffic sensor location approach for flow inference," IET Intelligent Transport Systems, 2014.

 

  • Larsson, "Allocation of Link Flow Detectors for Origin-Destination Matrix Estimation— A Comparative Study," Computer-Aided Civil and Infrastructure Engineering 25, p. 116–131, 2010.

 

  • H. Souza de Abreu, P. H. Gonz´alez, G. R. Mauri, G. M. Ribeiro, R. D. Orrico, N. F. R. Campos Júnior and C. A. Abramides, "Network sensor location problem with monitored lanes: Branch-and-cut and clustering search solution techniques," Computers & Industrial Engineering 150, 2020.

 

  • Fei and H. S. Mahmassani, "Structural analysis of near-optimal sensor locations for a stochastic," Transportation Research Part C 19, pp. 440-453, 2011.

 

  • Rodriguez-Vega, C. C.-d.-W. Canudas-de-Wit and H. Fourati, "Location of turning ratio and flow sensors for flow reconstruction in large traffic networks," Transportation Research Part B 121, pp. 21-40, 2019.

 

  • Zhou and G. F. List, "An Information-Theoretic Sensor Location Model for Traffic Origin-Destination Demand Estimation Applications," Transportation Science, Vol. 44, No. 2, p. 254–273, 2010.

 

  • -R. Hu and H.-T. Liou, "A generalized sensor location model for the estimation of network origin–destination matrices," Transportation Research Part C 40, pp. 93-110, 2014.

 

  • -R. Hu, S. Peeta and H.-T. Liou, "Integrated Determination of Network Origin–Destination Trip Matrix and Heterogeneous Sensor Selection and Location Strategy," in IEEE Transactions on Intelligent Tranportation Systems, 2015.

 

  • Fu, N. Zhu, S. Ling, S. Ma and Y. Huang, "Heterogeneous sensor location model for path reconstruction," Transportation Research Part B, p. 77–97, 2016.

 

  • Gentili and P. B. Mirchandani, "Review of optimal sensor location models for travel time estimation," Transportation Research Part C 90, p. 74–96, 2018.
  • Zhu, F. Fu and S. Ma, "Data-driven distributionally robust optimization approach for reliable travel-time-information-gain-oriented traffic sensor location model," Transportation Research Part B 113, p. 91–120, 2018.

 

  • Yang, Y. Iida and T. Sasaki, "An analysis of the reliability of an origin-destination trip matrix estimated from traffic counts," Transportation Research Part B 25, pp. 351-363, 1991.

 

  • Yang, C. Yang and L. Gan, "Models and algorithms for the screen line-based traffic-counting location problems," Computers & Operations Research 33, p. 836–858, 2006.

 

  • U. Pando, R. Luders, K. V. O. Fonseca and M. O. Rosa, "Influence of Virtual Road Traffic Sensors of Oporto for Origin-Destination Matrix Estimation," in LADaS 2018 - Latin America Data Science Workshop, Rio de Janeiro, Brazil, 2018.

 

  • IGENT TRANSPORTATION SYSTEMS, 2016.

 

  • Castillo, A. Cobo, F. Jubete, R. E. Pruneda and C. Castillo, "An Orthogonally Based Pivoting Transformation of Matrice and Some Applications," Siam Journal of Matrix analysis and Applications, pp. 666-681, 2000.

 

  • Christensen, An Introduction to Frame and Riesz Bases, Boston: Birkhäuser - Springer Science + Business Media, 2003.

 

  • Kovacevic and A. Chebira, "An Introduction to Frames," Foundations and Trends in Signal Processing, p. 1–94, 2008.

 

  • G. Casazza and G. Kutyniok, Finite Frames, Theory and Applications, New York: Springer Science+Business Media, 2013.
  • Hadavi and Y. Shafahi, "Vehicle identification sensor models for origin–destination estimation," Transportation Research Part B - 89, p. 82–106, 2016.

 

  • Gentili and P. Mirchandani, "Locating Active Sensors on Traffic Networks," Annals of Operations Research volume 136, p. 229–257, 2005.

 

  • Castillo, P. Jimenez, J. Menendez and J. Conejo, "The observability problem in traffic models: algebraic and topological methods," IEEE Transactions on Intelligent Transportation Systems, Vol 9, no. 2, p. 275–287, 2008.

 

  • Sun and X. (. Ban, "Vehicle trajectory reconstruction for signalized intersections using mobile traffic sensors," Transportation Research Part C 36, p. 268–283, 2013.

 

  • P. Dixon, "Real-Time OD Estimation Using Automatic Vehicle Identification and Traffic Count Data," Computer-Aided Civil and Infrastructure Engineering 17, p. 7–21, 2002.

 

  • Park and A. Haghani, "Optimal number and location of Bluetooth sensors considering stochastic travel time prediction," Transportation Research Part C 55, pp. 203-216, 2015.

 

  • Bekhor, M. E. Ben-Akiva and M. S. Ramming, "Evaluation of choice set generation algorithms for route choice models," Annals of Operations Research 144, p. 235–247, 2006.

 

  • B. Dial, "A Probabilistic Multipath Assignment Model which Obviates Path Enumeration." Transportation Research 8, pp. 83-111, 1971.

 

  • Ben-Akiva, M. J. Bergman, A. J. Daly and R. Ramaswamy, "Modelling inter urban route choice behaviour," in Ninth International Symposium on Transportation and Traffic Theory, Delft - The Netherlands, 1984.

 

  • de la Barra, B. Pérez and J. Anez, "Multidimensional path search and assignment," in 21st PTRC Summer Meeting, 1993.

 

  • Azevedo, M. Costa, J. Madeira and E. Martins, "An algorithm for the ranking of shortest paths," European Journal of Operational Research, 69 (1), pp. 97-106, 1993.

 

  • Ramming, Network Knowledge and Route Choice, PhD thesis, Massachusetts Institute of Technology, 2001.
International Journal of Transportation Engineering
Volume 12, Issue 3 - Serial Number 47
Winter 2025
Pages 1835-1857