Abstract
In this paper we address the Sensor Location Problem, that is the location of the minimum number of counting sensors, on the nodes of a network, in order to determine the arc flow volume of all the network. Despite the relevance of the problem from a practical point of view, there are very few contributions in the literature and no combinatorial analysis is performed to take into account particular structure of the network. We prove the problem is \(\cal N \cal P\)-complete in different cases. We analyze special classes of graphs that are particularly interesting from an application point of view, for which we give low order polynomial solution algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berman, O., D. Krass, and C.W. Xu. (1995). “Locating Discretionary Service Facilities Based on Probabilistic Customer Flows.” Transportation Science, 29(3), 276–290.
Bianco, L., G. Confessore, and P. Reverberi. (2001). “A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates.” Transportation Science, 35(1), 50–60.
Cockaine, E., S. Goodman, and S. Hedetniemi. (1975). A Linear Algorithm for the Domination Number of a Tree.” Information Processing Letters, 4(2), 41–44.
Chandnani, D. and P.B. Mirchandani. (2002). “Real-Time Estimation of Travel Speeds with Digital Cameras.” Research Center Technical Report May, 27.
Gentili, M. (2002). “New Models and Algorithms for the Location of Sensors on Traffic Networks.” PhD Dissertation, University of Rome “La Sapienza”, Department of Statistics Probability and Applied Statistics.
Gentili, M. and P.B. Mirchandani. “Location of Active Sensors on a Traffic Network.” Annals of Operations Research , 136, 1, 229-257.
Gentili, M. and P.B. Mirchandani. (2006) “Location of Image Sensors on a Traffic Network.” Working Paper.
Gionfriddo, M., F. Harary, and Z. Tuza. (1997). “The Color Cost of a Caterpillar.” Discrete Mathematics, 174, 125–130.
Hedetniemi, S.T. and R.C. Laskar. (1991). “Topics on Domination.” Annals of Discrete Mathematics, 48.
Lam, W.H.K. and H.P. Lo. (1990). “Accuracy of O-D Estimates from Traffic Counts.” Traffic Engineering and Control, 31, 358–37.
Nobe, S. (2002). “On-line Estimation of Traffic Split Parameters based on Lane Counts.” PhD Dissertation, Systems and Industrial Engineering Department, University of Arizona.
Yang, H., Y. Iida, and T. Sasaki. (1991). “An Analysis of the Reliability of an Origin/Destination trip Matrix Estimated from Traffic Counts.” Transportation Research B, 25, 351–363.
Yang, H. and J. Zhou. (1998). “Optimal Traffic Counting Locations for Origin-Destination Matrix Estimation.” Transportation Research, 32B(2), 109–126.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bianco, L., Confessore, G. & Gentili, M. Combinatorial aspects of the sensor location problem. Ann Oper Res 144, 201–234 (2006). https://doi.org/10.1007/s10479-006-0016-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-006-0016-9