The Use of Graph Theory for Search Space Reduction in Contaminant Source Identification

Contaminant intrusion in water distribution networks is an important concern and must be identified as soon as possible. Although optimization techniques are widely used for source identification, the performance of these methods decreases with increasing the size of the water network. To overcome this problem, this paper presents a new approach to reduce the search space, based on network topology, as a prior step to applying a search algorithm. In this method, all hydraulically connected nodes to the sensor node (with a positive detection) are identified using graph theory and considered as the new reduced search space in the optimization process. The effectiveness of the proposed method was investigated on three different benchmark water networks with different complexity and sizes. The results showed that the proposed approach can decrease the computational time by 18% to 63% while improving the success rate of contaminant source identification by 14% to 150%.