×

Vehicle-ID sensor location for route flow recognition: models and algorithms. (English) Zbl 1346.90486

Summary: We address an important problem in the context of traffic management and control related to the optimum location of vehicle-ID sensors on the links of a network to derive route flow volumes. We consider both the full observability version of the problem, where one seeks for the minimum number of sensors (or minimum cost) such that all the route flow volumes can be derived, and the estimation version of the problem, that arises when there is a limited budget in the location of sensors. Four mathematical formulations are presented. These formulations improve the existing ones in the literature since they better define the feasible region of the problem by taking into account the temporal dimension of the license plate scanning process. The resulting mathematical formulations are solved to optimality and compared with the existing mathematical formulations. The results show that new and better solutions can be achieved with less computational effort. We also present two heuristic approaches: a greedy algorithm and a tabu search algorithm that are able to efficiently solve the analyzed problems and they are a useful tool able to find a very good trade-off between quality of the solution and computational time.

MSC:

90B80 Discrete location and assignment
90B20 Traffic problems in operations research
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Castillo, E.; Gallego, I.; Menéndez, J. M.; Rivas, A., Optimal use of plate-scanning resources for route flow estimation in traffic networks, IEEE Transaction on Intelligent Transportation Systems, 11, 380-391 (2010)
[2] Castillo, E.; Calvino, A.; Menendez, J. M.; Jimenez, P.; Rivas, A., Deriving the upper bound of the number of sensors required to know all link flows in a traffic network, Intelligent Transportation Systems, IEEE Transactions on, 14, 2, 761-771 (2013)
[3] Castillo, E.; Conejo, A. J.; Menéndez, J. M.; Jiménez, P., The observability problem in traffic network models, Computer-Aided Civil and Infrastructure Engineering, 23, 208-222 (2008)
[4] Castillo, E.; Conejo, A. J.; Pruneda, R. E.; Solares, C., Observability in linear systems of equations and inequalities: Applications, Computers and Operations Research, 34, 1708-1720 (2007) · Zbl 1159.90318
[5] Castillo, E.; Jiménez, P.; Menéndez, J. M.; Conejo, A. J., The observability problem in traffic models: Algebraic and topological methods, IEEE Transactions on Intelligent Transportation Systems, 9, 275-287 (2008)
[6] Castillo, E.; Nogal, M.; Rivas, A.; Snchez-Cambronero, S., Observability of traffic networks. optimal location of counting and scanning devices, Transportmetrica B: Transport Dynamics, 1, 1, 68-102 (2013)
[7] Chootinan, P.; Chen, A.; Yang, H., A bi-objective traffic location problem for origin -destination trip table estimation, Transportmetrica, 1, 65-80 (2005)
[8] Castillo, E.; Menéndez, J. M.; Jiménez, P., Trip matrix and path flow reconstruction and estimation based on plate scanning and link observations, Transportation Research Part B, 42, 5, 455-481 (2008)
[9] Eisenman, Stacy M.; Fei, Xiang.; Zhou, Xuesong.; Mahmassani, Hani S., Number and location of sensors for real-time network traffic estimation and prediction: Sensitivity analysis, Transportation Research Record, 1964, 253-259 (2006)
[10] Elhert, A.; Bell, M. G.H.; Grosso, S., The optimization of traffic count locations in road networks, Transportation Research Part B, 40, 460-479 (2006)
[11] Fei, X.; Mahmassani, H. S., Structural analysis of near-optimal sensor locations for a stochastic large-scale network, Transportation Research Part C, 19, 440-453 (2011)
[12] Fei, X.; Mahmassani, Hani S.; Murray-Tuite, Pamela, Vehicular network sensor placement optimization under uncertainty, Transportation Research Part C: Emerging Technologies, 29, 0, 14-31 (2013)
[13] Gentili, M.; Mirchandani, P., Survey of models to locate sensors to estimate traffic flows, Transportation Research Record, 2243, 108-116 (2011)
[14] Gentili, M.; Mirchandani, P., Locating sensors on traffic networks: Models, challenges and research opportunities, Transportation Research Part C, 24, 227-255 (2012)
[15] Gentili, M.; Mirchandani, P. B., Location of active sensors on traffic network, Annals of Operations Research, 136, 229-257 (2005) · Zbl 1114.90067
[16] Hu, Shou -Ren; Peeta, Srinivas; Chu, Chun -Hsiao, Identification of vehicle sensor locations for link-based network traffic applications, Transportation Research Part B: Methodological, 43, 89, 873-894 (2009)
[17] Yang, H.; Yang, C.; Gan, L., Models and algorithms for the screen line-based traffic counting location problem, Computers and Operations Research, 33, 836-858 (2006) · Zbl 1088.90006
[18] Kim, H. J.; Chung, H.; Chung, S. Y., Selection of the optimal traffic counting locations for estimating origin-destination trip matrix, Journal of Eastern Asian Society for Transportation Studies, 5, 1353-1365 (2003)
[19] Lam, W. H.K.; Lo, H. P., Accuracy of o-d estimates from traffic counts, Traffic Engineering and Control, 31, 435-447 (1990)
[20] Li, X.; Ouyang, Y., Reliable sensor deployment for network traffic surveillance, Transportation Research Part B, 45, 218-231 (2011)
[21] Mínguez, R.; Sánchez-Cambronero, S.; Castillo, E.; Jiménez, P., Optimal traffic plate scanning location for od trip matrix and route estimation in road networks, Transportation Research Part B, 44, 282-298 (2010)
[22] Ng, ManWo, Synergistic sensor location for link flow inference without path enumeration: A node-based approach, Transportation Research Part B: Methodological, 46, 6, 781-788 (2012)
[23] Simonelli, Fulvio; Marzano, Vittorio; Papola, Andrea; Vitiello, Iolanda, A network sensor location procedure accounting for od matrix estimate variability, Transportation Research Part B: Methodological, 46, 10, 1624-1638 (2012)
[24] xue He, Sheng, A graphical approach to identify sensor locations for link flow inference, Transportation Research Part B: Methodological, 51, 0, 65-76 (2013)
[25] Yang, H.; Zhou, J., Optimal traffic counting locations for origin-destination matrix estimation, Transportation Research Part B, 32, 109-126 (1998)
[26] Zhou, X.; List, G. F., An information-theoretic sensor location model for traffic origin-destination demand estimation applications, Transportation Science, 44, 254-273 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.