Structural analysis of near-optimal sensor locations for a stochastic large-scale network

Finding a set of optimal sensor locations in terms of estimated demand uncertainty minimization for a sensor network is a network design problem. This paper presents a multi-objective model, which considers link information gains (weights of each link, in order to correct a priori origin-destination demands) and origin-destination demand coverage to locate a minimal number of passive point sensors in a roadway network constrained by available resources (e.g., budget limits). We discuss a conceptual link framework for structural analysis, which involves network observability (mean of eigenvolume) and uncertainty (variance of eigenvolume). The general idea behind this method is that the first few installed sensors will account for most of the uncertainty of the origin-destination flow if sensors have substantial correlations among each other (e.g., if each link has a sensor installed). The link structure analysis explores the theoretical structure for understanding the essentials of considering network uncertainty and demand coverage simultaneously in the sensor location problem, as well as providing search directions in the hereafter solution procedure. Consequently, a bi-objective model that balances the trade-off between reducing the network uncertainty and covering demand under a budgetary constraint in the context of traffic dynamics is proposed. A heuristic procedure, the hybrid Greedy Randomized Adaptive Search Procedure (HGRASP), is applied to find Pareto optimal solutions. A case study on the CHART (Washington, DC-Baltimore, Maryland corridor) network was used to demonstrate the proposed methodology. (C) 2010 Elsevier Ltd. All rights reserved.