Submodularity of optimal sensor placement for traffic networks

The need for monitoring the state of a traffic network versus the costly installation and maintenance of roadside sensors constitutes the tough sensor placement problem in designing transportation networks. Placement problems naturally lie in the category of subset selection problems, which are known to be inherently combinatorial, and therefore, finding their exact solution is intractable for large problems. Due to this intractability, numerous heuristics have been proposed in the literature for approximately solving placement problems for traffic networks. Among these approaches, it has been observed that greedy algorithms normally outperform other heuristics. In this paper, we show the mathematics of why greedy algorithms are appropriate proxies for solving these subset selection problems; similar to placement problems for linear systems, placement problems for traffic networks also normally have a submodular structure. In this work, we analyze the problem of road sensor placement for transportation networks under different information structures available: when no vehicle routing information is available, when vehicles’ routings are known, and when it is necessary to maximize the number of origin–destination (O/D) traffic flows that are monitored with a set of sensors. We show that in all these cases, the placement problem has a submodular monotone structure. It is well known that the submodularity and monotonicity of discrete optimization problems can be leveraged to derive greedy algorithms that approximate the optimal solution. Consequently, our result is of great practical importance since by exploiting the submodularity and monotonicity of a problem, we show that it is possible to use polynomial-time greedy algorithms to approximate the combinatorial optimization problem with guaranteed optimality bounds for large problems, which are intractable to solve otherwise. Our results shed light upon the success of heuristic greedy algorithms that have been developed in some of the literature for solving placement problems at scale. To demonstrate the applicability of submodular optimization for solving placement problems, we first compare the performance of our polynomial-time approximation algorithm with the true optimum in an example traffic network which is small enough for finding the exact optimal solution with enumerating all possible subsets. Then, we investigate and validate our submodular approach in a case study involving a large-scale traffic network in Berkeley, California, where finding the exact optimal solution is intractable. Submodularity of the placement problem in these scenarios provides a powerful computational tool which can be further extended to other placement problem formulations that can become a reference for solving similar problems in the transportation literature.