Designing Contamination Warning Systems for Municipal Water Networks Using Imperfect Sensors

We consider the problem of designing a contaminant warning system for a municipal water distribution network that uses imperfect sensors, which can generate false-positive and false-negative detections. Although sensor placement optimization methods have been developed for contaminant warning systems, most sensor placement formulations assume perfect sensors, which does not accurately reflect the behavior of real sensor technology. We describe a general exact nonlinear formulation for imperfect sensors and a linear approximation. We consider six general solution strategies, some of which have multiple solution methods. We applied these methods to three test networks, including one with over 10,000 nodes. Our experiments indicate that it is worth deploying a sensor network even when sensors have low detection probability. They also indicate it is worth paying attention to sensor imperfections when placing sensors even when there is a response delay of up to 8 h. The best choice of solution strategy depends upon the user’s goals and the problem size. However, for large-scale problems with a moderate number of sensors, using a local search for the linear approximation formulation provides a reasonable-quality solution in a few minutes of computation. Our models assume that sensors can fail via false negatives. Additionally, we discuss ways to model false positives, ways to limit them, and how to trade them off against false negatives. All of our solution methods can handle false positives but our experiments do not explicitly consider them.