Exact and approximate route set generation for resilient partial observability in sensor location problems. (November 2017)

• Record Type: Journal Article
• Authors: Rinaldi, Marco; Viti, Francesco
• Is Part Of: Transportation research. Volume 105(2017)
• Page Start: 86
• Page End: 119
• Publication Date: 2017-11
• Subjects: Network Sensor Location Problem -- Partial link flow observability -- Route set generation -- Maximum clique problem -- Genetic algorithm; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2017.08.007
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: A comprehensive analysis of route set generation approaches in network sensor location problems is performed. A relationship between route set composition and quantity of information in link flow inference problems is hypothesized. An optimization approach for the maximum independent route set problem is formulated, based upon graph theory. Algorithms capable of generating exact and approximate solutions to the aforementioned problem are proposed. The algorithms are validated on several small and real-life sized case studies. Our key hypothesis is shown to hold. Abstract: 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.