Sensor Location For Network Flow And Origin-Destination Estimation With Multiple Vehicle Classes
The need for multi-class origin-destination (O-D) estimation and link volume estimation requires multi-class observations from sensors. This dissertation has established a new sensor location model that includes: 1) multiple vehicle classes; 2) a variety of data types from different types of sensors; and 3) a focus on both link-based and O-D based flow estimation. The model seeks a solution that maximizes the overall information content from sensors, subject to a budget constraint. An efficient twophase metaheuristic algorithm is developed to solve the problem. The model is based on a set of linear equations that connect O-D flows, link flows and sensor observations. Concepts from Kalman filtering are used to define the information content from a set of sensors as the trace of the posterior covariance matrix of flow estimates, and to create a linear update mechanism for the precision matrix as new sensors are added or deleted from the solution set. Sensor location decisions are nonlinearly related to information content because the precision matrix must be inverted to construct the covariance matrix which is the basis for measuring information. The resulting model is a nonlinear knapsack problem. The two-phase search algorithm proposed addresses this nonlinear, nonseparable integer sensor location problem. A greedy phase generates an initial solution, feeding into a Tabu Search phase which swaps sensors along the budget constraint. The neighbor generation in Tabu search is a combination of a fixed swapout strategy with a guided random swap-in strategy. Extensive computational experiments have been performed on a standard test network. These tests verify the effectiveness of the problem formulation and solution algorithm. A case study on Rockland County, NY demonstrates that the sensor location method developed in this dissertation can successfully allocate sensors in realistic networks, and thus has significant practical value.
Sensor location; Network flow estimation; Metaheuristics
Civil & Environmental Engr
Ph.D. of Civil & Environmental Engr
Doctor of Philosophy
dissertation or thesis