Exact and approximate route set generation for resilient partial observability in sensor location problems

in Transportation Research. Part B : Methodological (2017), 105

Sensor positioning is a fundamental problem in transportation networks, as the location of sensors strongly determines how traffic flows are observable and hence manageable. This paper aims to develop a ... [more ▼]

Sensor positioning is a fundamental problem in transportation networks, as the location of sensors strongly determines how traffic flows are observable and hence manageable. This paper aims to develop a methodology to determine sensor locations on a network such that an optimal trade-off solution is found between the amount of sensors installed and the resilience of the sensor set. In particular, we propose exact and heuristic solutions for identifying the optimal route sets such that no other route would include any additional information for finding optimal full and partial observability solutions. This is an important contribution to sensor location problems, as route-based link flow inference problems have non-unique solutions, strongly depending on the used link-route information. The properties of the new methodology are analyzed and illustrated through different case studies, and the advantages of the algorithms are quantified both for full and for partial observability solutions. Due to the route sets found by our approach, we are able to find full observability solutions characterized by a small number of sensors, while yet being efficient also in terms of partial observability. We perform validation tests on both small and real-life sized network instances. © 2017 Elsevier Ltd [less ▲]

Assessing partial observability in network sensor location problems

in Transportation Research. Part B : Methodological (2014), 70

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 ... [more ▼]

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. [less ▲]