A Submodular Approach for Optimal Sensor Placement in Traffic Networks

Precious measurements from infrastructure traffic sensors versus their high-priced installation and maintenance costs, make sensor placement a paramount problem for traffic networks. We study sensor placement for traffic networks in two settings. When no routing information is available, we propose to maximize the identifiability of all link flows in the network. When the network routing is known, we use a previously defined metric of minimizing estimation error of a BLUE (Best Linear Unbiased Estimator) estimator. We prove that in both cases, the problem is submodular. By exploiting the submodularity of the problem, we can use polynomial-time approximations of the combinatorial placement problem with guaranteed optimality bounds, which is of importance due to the inherent large-scale nature of transportation networks. We demonstrate the performance of our method in a grid example network.