Paper Info
Title
Locating sensors to observe network arc flows: Exact and heuristic approaches
Abstract
The problem of optimally locating sensors on a traffic network to monitor flows has been an object of growing interest in the past few years, due to its relevance in the field of traffic management and control. Sensors are often located in a network in order to observe and record traffic flows on arcs and/or nodes. Given traffic levels on arcs within the range or covered by the sensors, traffic levels on unobserved portions of a network can then be computed. In this paper, the problem of identifying a sensor configuration of minimal size that would permit traffic on any unobserved arcs to be exactly inferred is discussed. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be NP-complete, and the existing studies about the problem analyze some polynomial cases and present local search heuristics to solve it. In this paper we further extend the study of the problem by providing a mathematical formulation that up to now has been still missing in the literature and present an exact branch and bound approach, based on a binary branching rule, that embeds the existing heuristics to obtain bounds on the solution value. Moreover, we apply a genetic approach to find good quality solutions. Extended computational results show the effectiveness of the proposed approaches in solving medium-large instances.
Year
DOI
Venue
2014
10.1016/j.cor.2013.12.013
Computers & OR
Keywords
DocType
Volume
traffic management,traffic network,traffic level,proposed approach,network arc flow,existing heuristics,bound approach,heuristic approach,Locating sensor,genetic approach,existing study,present local search heuristics,record traffic flow
Journal
46,
ISSN
Citations 
PageRank 
0305-0548
3
0.41
References 
Authors
8
4
Name
Order
Citations
PageRank
L. Bianco130.41
C. Cerrone2151.04
R. Cerulli325223.85
M. Gentili4323.35