The Use of Graph Theory for Search Space Reduction in Contaminant Source Identification
Publication: Journal of Pipeline Systems Engineering and Practice
Volume 14, Issue 2
Abstract
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%.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
All data, models, or codes that support the findings of this study are available from the corresponding author upon reasonable request.
References
Adedoja, O. S., Y. Hamam, B. Khalaf, and R. Sadiku. 2018. “Towards development of an optimization model to identify contamination source in a water distribution network.” Water 10 (5): 579. https://doi.org/10.3390/w10050579.
Alfonso, L., A. Jonoski, and D. Solomatine. 2010. “Multi objective optimization of operational responses for contaminant flushing in water distribution networks.” J. Water Resour. Plann. Manage. 136 (1): 48–58. https://doi.org/10.1061/(ASCE)0733-9496(2010)136:1(48).
Barandouzi, M., and R. Kerachian. 2016. “Probabilistic contaminant source identification in water distribution infrastructure systems.” Civ. Eng. Infrastruct. J. 49 (2): 311–326. https://doi.org/10.7508/ceij.2016.02.008.
Berry, J., E. Boman, L. A. Riesen, W. E. Hart, C. A. Phillips, and J. P. Watson. 2012. User’s manual: TEVA-SPOT toolkit 2.5. 2. Cincinnati: USEPA.
Bondy, J. A., and U. S. R. Murty. 1976. Vol. 290 of Graph theory with applications. London: Macmillan.
CWS (Centre for Water Systems). 2001. “CWS benchmarks.” Accessed June 9, 2019. http://emps.exeter.ac.uk/engineering/research/cws/.
Dawsey, W. J., B. S. Minsker, and V. L. VanBlaricum. 2006. “Bayesian belief networks to integrate monitoring evidence of water distribution system contamination.” J. Water Resour. Plann. Manage. 132 (4): 234–241. https://doi.org/10.1061/(ASCE)0733-9496(2006)132:4(234).
De Sanctis, A. E., D. L. Boccelli, F. Shang, and J. G. Uber. 2008. “Probabilistic approach to characterize contamination sources with imperfect sensors.” In Proc., Environmental and Water Resources Institute of ASCE, Honolulu, Hawaii, 1–10. Reston, VA: ASCE. https://doi.org/10.1061/40976(316)512.
De Sanctis, A. E., F. Shang, and J. G. Uber. 2010. “Real-time identification of possible contamination sources using network backtracking methods.” J. Water Resour. Plann. Manage. 136 (4): 444–453. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000050.
De Winter, C., V. R. Palleti, D. Worm, and R. Kooij. 2019. “Optimal placement of imperfect water quality sensors in water distribution networks.” Comput. Chem. Eng. 121 (Feb): 200–211. https://doi.org/10.1016/j.compchemeng.2018.10.021.
Eliades, D. G., M. M. Polycarpou, and B. Charalambous. 2011. “A security-oriented manual quality sampling methodology for water systems.” Water Resour. Manage. 25 (4): 1219–1228. https://doi.org/10.1007/s11269-010-9674-0.
Giudicianni, C., A. Di Nardo, M. Di Natale, R. Greco, G. F. Santonastaso, and A. Scala. 2018. “Topological taxonomy of water distribution networks.” Water 10 (4): 444. https://doi.org/10.3390/w10040444.
Guan, J., M. M. Aral, M. L. Maslia, and W. M. Grayman. 2006. “Identification of contaminant sources in water distribution systems using simulation–optimization method: Case study.” J. Water Resour. Plann. Manage. 132 (4): 252–262. https://doi.org/10.1061/(ASCE)0733-9496(2006)132:4(252).
Hart, W. E., and R. Murray. 2010. “Review of sensor placement strategies for contamination warning systems in drinking water distribution systems.” J. Water Resour. Plann. Manage. 136 (6): 611–619. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000081.
Haxton, T., R. Murray, and K. Klise. 2012. “Examining the application of modeling tools to identify effective flushing locations.” In Proc., Environmental and Water Resources Institute of ASCE, Albuquerque, New Mexico, 3071–3081. Reston, VA: ASCE. https://doi.org/10.1061/9780784412312.309.
Huang, J. J., and E. A. McBean. 2009. “Data mining to identify contaminant event locations in water distribution systems.” J. Water Resour. Plann. Manage. 135 (6): 466–474. https://doi.org/10.1061/(ASCE)0733-9496(2009)135:6(466).
Jafari, H., S. Nazif, and T. Rajaee. 2022. “A multi-objective optimization method based on NSGA-III for water quality sensor placement with the aim of reducing potential contamination of important nodes.” Water Supply 22 (1): 928–944. https://doi.org/10.2166/ws.2021.222.
Kim, M., C. Y. Choi, and C. P. Gerba. 2008. “Source tracking of microbial intrusion in water systems using artificial neural networks.” Water Res. 42 (4–5): 1308–1314. https://doi.org/10.1016/j.watres.2007.09.032.
Klise, K. A., C. A. Phillips, and R. J. Janke. 2013. “Two-tiered sensor placement for large water distribution network models.” J. Infrastruct. Syst. 19 (4): 465–473. https://doi.org/10.1061/(ASCE)IS.1943-555X.0000156.
Koch, M. W., and S. A. McKenna. 2011. “Distributed sensor fusion in water quality event detection.” J. Water Resour. Plann. Manage. 137 (1): 10–19. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000094.
Laird, C. D., L. T. Biegler, and B. G. van Bloemen Waanders. 2007. “Real-time, large-scale optimization of water network systems using a subdomain approach.” In Real-time PDE-constrained optimization, 289–306. Philadelphia: Society for Industrial and Applied Mathematics.
Laird, C. D., L. T. Biegler, B. G. van Bloemen Waanders, and R. A. Bartlett. 2005. “Contamination source determination for water networks.” J. Water Resour. Plann. Manage. 131 (2): 125–134. https://doi.org/10.1061/(ASCE)0733-9496(2005)131:2(125).
Liu, L., S. R. Ranjithan, and G. Mahinthakumar. 2011. “Contamination source identification in water distribution systems using an adaptive dynamic optimization procedure.” J. Water Resour. Plann. Manage. 137 (2): 183–192. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000104.
Lučin, I., L. Grbčić, S. Družeta, and Z. Čarija. 2021. “Source contamination detection using novel search space reduction coupled with optimization technique.” J. Water Resour. Plann. Manage. 147 (2): 04020100. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001308.
Mann, A. V., S. A. McKenna, W. E. Hart, and C. D. Laird. 2012. “Real-time inversion in large-scale water networks using discrete measurements.” Comput. Chem. Eng. 37 (Feb): 143–151. https://doi.org/10.1016/j.compchemeng.2011.08.001.
Masud Rana, S. M., and D. L. Boccelli. 2016. “Contaminant spread forecasting and confirmatory sampling location identification in a water-distribution system.” J. Water Resour. Plann. Manage. 142 (12): 04016059. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000704.
Mukherjee, R., U. M. Diwekar, and A. Vaseashta. 2017. “Optimal sensor placement with mitigation strategy for water network systems under uncertainty.” Comput. Chem. Eng. 103 (Aug): 91–102. https://doi.org/10.1016/j.compchemeng.2017.03.014.
Neupauer, R. M., M. K. Records, and W. H. Ashwood. 2010. “Backward probabilistic modeling to identify contaminant sources in water distribution systems.” J. Water Resour. Plann. Manage. 136 (5): 587–591. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000057.
Ortega, E., A. Braunstein, and A. Lage-Castellanos. 2020. “Contamination source detection in water distribution networks using belief propagation.” Stochastic Environ. Res. Risk Assess. 34 (3): 493–511. https://doi.org/10.1007/s00477-020-01788-y.
Ostfeld, A., et al. 2008. “The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms.” J. Water Resour. Plann. Manage. 134 (6): 556–568. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:6(556).
Perelman, L., and A. Ostfeld. 2013. “Bayesian networks for source intrusion detection.” J. Water Resour. Plann. Manage. 139 (4): 426–432. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000288.
Preis, A., and A. Ostfeld. 2007. “A contamination source identification model for water distribution system security.” Eng. Optim. 39 (8): 941–947. https://doi.org/10.1080/03052150701540670.
Preis, A., and A. Ostfeld. 2008. “Genetic algorithm for contaminant source characterization using imperfect sensors.” Civ. Eng. Environ. Syst. 25 (1): 29–39. https://doi.org/10.1080/10286600701695471.
Preis, A., and A. Ostfeld. 2011. “Hydraulic uncertainty inclusion in water distribution systems contamination source identification.” Urban Water J. 8 (5): 267–277. https://doi.org/10.1080/1573062X.2011.596549.
Price, K. V., R. M. Storn, and J. A. Lampinen. 2005. “The differential evolution algorithm.” In Differential evolution: A practical approach to global optimization, 37–134. Berlin: Springer. https://doi.org/10.1007/3-540-31306-0.
Propato, M., F. Sarrazy, and M. Tryby. 2010. “Linear algebra and minimum relative entropy to investigate contamination events in drinking water systems.” J. Water Resour. Plann. Manage. 136 (4): 483–492. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000059.
Qin, T., and D. L. Boccelli. 2017. “Grouping water-demand nodes by similarity among flow paths in water-distribution systems.” J. Water Resour. Plann. Manage. 143 (8): 04017033. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000788.
Qiu, M., E. Salomons, and A. Ostfeld. 2020. “A framework for real-time disinfection plan assembling for a contamination event in water distribution systems.” Water Res. 174 (May): 115625. https://doi.org/10.1016/j.watres.2020.115625.
Rutkowski, T. A., and F. Prokopiuk. 2018. “Identification of the contamination source location in the drinking water distribution system based on the neural network classifier.” IFAC-PapersOnLine 51 (24): 15–22. https://doi.org/10.1016/j.ifacol.2018.09.523.
Sankary, N., and A. Ostfeld. 2018. “Multiobjective optimization of inline mobile and fixed wireless sensor networks under conditions of demand uncertainty.” J. Water Resour. Plann. Manage. 144 (8): 04018043. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000930.
Shang, F., J. G. Uber, and M. M. Polycarpou. 2002. “Particle backtracking algorithm for water distribution system analysis.” J. Environ. Eng. 128 (5): 441–450. https://doi.org/10.1061/(ASCE)0733-9372(2002)128:5(441).
Shen, H., and E. McBean. 2012. “False negative/positive issues in contaminant source identification for water-distribution systems.” J. Water Resour. Plann. Manage. 138 (3): 230–236. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000162.
Sun, L., H. Yan, K. Xin, and T. Tao. 2019. “Contamination source identification in water distribution networks using convolutional neural network.” Environ. Sci. Pollut. Res. 26 (36): 36786–36797. https://doi.org/10.1007/s11356-019-06755-x.
Tao, T., H. D. Huang, K. L. Xin, and S. M. Liu. 2012. “Identification of contamination source in water distribution network based on consumer complaints.” J. Central South Univ. 19 (6): 1600–1609. https://doi.org/10.1007/s11771-012-1182-3.
Ung, H., O. Piller, D. Gilbert, and I. Mortazavi. 2017. “Accurate and optimal sensor placement for source identification of water distribution networks.” J. Water Resour. Plann. Manage. 143 (8): 04017032. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000777.
Vrachimis, S. G., R. Lifshitz, D. G. Eliades, M. M. Polycarpou, and A. Ostfeld. 2020. “Active contamination detection in water-distribution systems.” J. Water Resour. Plann. Manage. 146 (4): 324–335. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001176.
Wong, A., J. Young, C. D. Laird, W. E. Hart, and S. A. McKenna. 2010. “Optimal determination of grab sample locations and source inversion in large-scale water distribution systems.” In Proc., 12th Annual Conf. on Water Distribution Systems Analysis (WDSA), 412–425. Reston, VA: ASCE. https://doi.org/10.1061/41203(425)39.
Xuesong, Y., S. Jie, and H. Chengyu. 2017. “Research on contaminant sources identification of uncertainty water demand using genetic algorithm.” Cluster Comput. 20 (2): 1007–1016. https://doi.org/10.1007/s10586-017-0787-6.
Yan, X., T. Li, C. Hu, and Q. Wu. 2019. “Real-time localization of pollution source for urban water supply network in emergencies.” Supplement, Cluster Comput. 22 (S3): 5941–5954. https://doi.org/10.1007/s10586-018-1725-y.
Yang, X., and D. L. Boccelli. 2014. “Bayesian approach for real-time probabilistic contamination source identification.” J. Water Resour. Plann. Manage. 140 (8): 04014019. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000381.
Yang, X., and D. L. Boccelli. 2016. “Model-based event detection for contaminant warning systems.” J. Water Resour. Plann. Manage. 142 (11): 04016048. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000689.
Zafari, M., M. Tabesh, and S. Nazif. 2017. “Minimizing the adverse effects of contaminant propagation in water distribution networks considering the pressure-driven analysis method.” J. Water Resour. Plann. Manage. 143 (12): 04017072. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000848.
Zhao, Y., R. Schwartz, E. Salomons, A. Ostfeld, and H. V. Poor. 2016. “New formulation and optimization methods for water sensor placement.” Environ. Modell. Software 76 (Feb): 128–136. https://doi.org/10.1016/j.envsoft.2015.10.030.
Zierolf, M. L., M. M. Polycarpou, and J. G. Uber. 1998. “Development and autocalibration of an input-output model of chlorine transport in drinking water distribution systems.” IEEE Trans. Control Syst. Technol. 6 (4): 543–553. https://doi.org/10.1109/87.701351.
Information & Authors
Information
Published In
Journal of Pipeline Systems Engineering and Practice
Volume 14 • Issue 2 • May 2023
Copyright
© 2023 American Society of Civil Engineers.
History
Received: Jun 28, 2022
Accepted: Jan 24, 2023
Published online: Mar 10, 2023
Published in print: May 1, 2023
Discussion open until: Aug 10, 2023
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.