Vehicle identification sensors location problem for large networks

Finding the optimal location for sensors is a key problem in flow estimation. There are several location models that have been developed recently for vehicle identification (ID) sensors. However, these location models cannot be applied to large networks because there are many constraints and integer variables. Based on a property of the location problem for vehicle ID sensors, given the initial vehicle ID sensors that are pre-installed and fixed on the network, this article presents a solution that greatly reduces the size of this location problem. An applied example demonstrates that when 8% of the arcs from a real network that are randomly selected have a vehicle ID sensor, the reductions are as large as 97% for the number of remaining constraints in the location model and 84% for the adjusted diameter of the feasible region of target flow. Using these two indices as target functions, two greedy algorithms are presented for solving the vehicle ID sensor location problem. These two algorithms were applied to an example in Mashhad city with 2,526 arcs, 7,157 origin-destination pairs and 121,627 paths. Using these algorithms, installing vehicle ID sensors on 8% of the network arcs results in satisfaction of 99.82% of the constraints in the location model and 97.6% reduction in the adjusted maximum possible error index. This means that deploying a low number of vehicle ID sensors on a real large network, with these greedy algorithms, yields a high level of observability.