Assessing partial observability in network sensor location problems

The quality of information on a network is crucial for different transportation planning and management applications. Problems focusing on where to strategically extract this information can be broadly subdivided into observability problems, which rely on the topological properties of the network, and flow-estimation problems, where (prior) information on observed flows is needed to identify optimal sensor locations. This paper contributes mainly to the first category: more specifically, it presents a new methodology and an intuitive metric able to quantify the quality of a solution in case of partial observability, i.e. when not all flow variables are observed or can be uniquely determined from the observed flows. This methodology is based on existing approaches that can efficiently find solutions for full observability (i.e., the set of sensors needed to make the system fully determined), and exploits only the algebraic relations between link, route and origin destination flow variables to quantify the information contained in any arbitrary subset of these variables. The new metric allows, through its adoption within simple search algorithms, to efficiently select sensor locations when the number of available sensors is limited by, for example, budget constraints and is less than the number needed to guarantee full observability. The chosen positions aim at selecting those locations that contain the largest information content on the whole network. This is an important contribution in this field, since even in small sized networks the solution for full observability requires an exceedingly large amount of sensors. The assessment of partial observability solutions, based on explicit route enumeration, allows one to categorize families of full observability solutions, and shows that these contain different information potential. This way, it is possible to rank solutions requiring a lower number of sensors while containing the same information content. We tested this new methodology both on toy networks, in order to analyse the properties of the metric and illustrate its logic, and to explain and test heuristic search algorithms for optimal sensor positioning on a real-sized network. Analysis of partial observability solutions shows that the basic search algorithms succeed in finding the links that contain the largest deal of information in a network. (C) 2014 Elsevier Ltd. All rights reserved.