Detecting accidental contaminations in municipal water networks

A methodology for finding the optimal layout of a detection system in a municipal water network is formulated and demonstrated. The detection system considered consists of a set of monitoring stations aimed at detecting a random external input of water pollution. The level of service provided to the consumers is defined by the maximum volume of consumed polluted water prior to detection. The methodology involves the establishment of an auxiliary network that represents all possible flow directions for a typical demand cycle, an "all shortest paths" algorithm to identify domains of pollution, and a "set covering" algorithm to optimally allocate the monitoring stations. The algorithm outcome is a minimal set of monitoring stations that satisfies a given level of service. The methodology is demonstrated on a small illustrative case and on a midsize water network.