Robust Analysis of Sensor Coverage and Location for Real-Time Traffic Estimation and Prediction in Large-Scale Networks

Abstract

The growing need of agencies to obtain real-time information on the traffic state of key facilities in the systems they manage is driving interest in cost-effective deployment of sensor technologies across the networks they manage. This has led to greater interest in the sensor location problem. Finding a set of optimal sensor locations is a network design problem. This dissertation addresses a series of critical and challenging issues in the robustness analysis of sensor coverage and location under different traffic conditions, in the context of real-time traffic estimation and prediction in a large scale traffic network.

The research presented in this dissertation represents an important step towards optimization of sensor locations based on dynamic traffic assignment methodology. It proposes an effective methodology to find optimal sensor coverage and locations, for a specified number of sensors, through an iterative mathematical bi-level optimization framework, The proposed methods help transportation planners locate a minimal number of sensors to completely cover all or a subset of OD pairs in a network without budgetary constraints, or optimally locate a limited number of sensors by considering link information gains (weights of each link brought to correct a-priori origin-destination flows) and flow coverage with budgetary constraints.

Network uncertainties associated with the sensor location problem are considered in the mathematical formulation. The model is formulated as a two stage stochastic model. The first stage decision denotes a strategic sensor location plan before observations of any randomness events, while the recourse function associated with the second stage denotes the expected cost of taking corrective actions to the first stage solution after the occurrence of the random events.

Recognizing the location problem as a NP-hard problem, a hybrid Greedy Randomized Adaptive Search Procedure (GRASP) is employed to circumvent the difficulties of exhaustively exploring the feasible solutions and find a near-optimal solution for this problem. The proposed solution procedure is operated in two stages. In stage one, a restricted candidate list (RCL) is generated from choosing a set of top candidate locations sorted by the link flows. A predetermined number of links is randomly selected from the RCL according to link independent rule. In stage two, the selected candidate locations generated from stage one are evaluated in terms of the magnitude of flow variation reduction and coverage of the origin-destination flows using the archived historical and simulated traffic data. The proposed approaches are tested on several actual networks and the results are analyzed.