Water Network Sectorization Based on Graph Theory and Energy Performance Indices
Publication: Journal of Water Resources Planning and Management
Volume 140, Issue 5
Abstract
This paper proposes a new methodology for the optimal design of water network sectorization, which is an essential technique for improving the management and security of multiple-source water supply systems. In particular, the network sectorization problem under consideration concerns the definition of isolated district meter areas, each of which is supplied by its own source (or sources) and is completely disconnected from the rest of the water system through boundary valves or permanent pipe sectioning. The proposed methodology uses graph theory principles and a heuristic procedure based on minimizing the amount of dissipated power in the water network. The procedure has been tested on two existing water distribution networks (WDNs) (in Parete, Italy and San Luis Rio Colorado, Mexico) using different performance indices. The simulation results, which confirmed the effectiveness of the proposed methodology, surpass empirical trial-and-error approaches and offer water utilities a tool for the design of multiple-source WDNs in isolated districts.
Get full access to this article
View all available purchase options and get full access to this article.
References
Alonso, J. M., et al. (2000). “Parallel computing in water network analysis and leakage minimization.” J. Water Resour. Plann. Manage., 251–260.
American Water Works Association (AWWA) Water Loss Control Committee. (2003). “Applying wordwide BMPs in water loss control.” Water Distribution Systems Analysis Symp. 2006, ASCE, Reston, VA, 1–3.
Biggs, N., Lloyd, E., and Wilson, R., (1986). Graph theory 1736–1936, Oxford University Press, New York.
Chevalier, C., and Safro, I., (2009). “Comparison of coarsening schemes for multilevel graph partitioning.” Lect. Notes Comput. Sci., 5851, 191–205.
Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1990). Introduction to algorithms, MIT Press, Cambridge, MA.
Deuerlein, J. W. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 822–832.
Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. (1999). Graph drawing (Algorithms for the visualization of graphs), Prentice Hall, Upper Saddle River, NJ.
Di Nardo, A., and Di Natale, M. (2011). “A heuristic design support methodology based on graph theory for district metering of water supply networks.” Eng. Optim., 43(2), 193–211.
Di Nardo, A., and Di Natale, M. (2012). “A design support methodology for district metering of water supply networks.” Proc., 12th Annual Int. Conf. on Water Distribution Systems Analysis 2010, WDSA 2010, ASCE, Reston, VA, 870–877.
Di Nardo, A., Di Natale, M., Guida, M., and Musmarra, D. (2012a). “Water network protection from intentional contamination by sectorization.” Water Resour. Manage., 27(6), 1837–1850.
Di Nardo, A., Di Natale, A., and Di Mauro, A. (2012b). Water supply network district metering: Theory and Case Study, CISM courses and lectures, Vol. 543, Springer, Vienna-Heidelberg, Austria.
Di Nardo, A., Di Natale, M., Santonastaso, G. F., and Venticinque, S. (2011). “Graph partitioning for automatic sectorization of a water distribution system.” Proc., 11th Int. Conf. on Computing and Control for Water Industry (CCWI). Urban Water Management: Challenges and Opportunities, Vol. 3, Centre for Water Systems, Univ. of Exeter, Exeter, U.K., 841–846.
Fanner, V. P. R., Sturm, J., and Thornton, R. (2007). Leakage management technologies, Awwa Research Foundation (AwwaRF) and American Waterworks Association (AWWA), Denver.
Farley, M. (2001). Leakage management and control. A best practice training manual, World Health Organization, Geneva.
Fiduccia, C. M., and Mattheyses, R. M. (1982). “A linear time heuristic for improving network partitions.” Proc., 19th IEEE Design Automation Conf., IEEE Press, Piscataway, NJ, 175–181.
Giustolisi, O., Kapelan, Z., and Savic, D. A. (2008a). “An algorithm for automatic detection of topological changes in water distribution networks.” J. Hydraul. Eng., 435–446.
Giustolisi, O., Kapelan, Z., and Savic, D. A., (2008b). “Extended period simulation analysis considering valve shutdowns.” J. Water Resour. Plann. Manage., 527–537.
Giustolisi, O., and Savic, D. A. (2010). “Identification of segments and optimal isolation valve system design in water distribution networks.” Urban Water, 7(1), 1–15.
Giustolisi, O., Savic, D. A., Berardi, L., and Laucelli, D. (2011). “An Excel-based solution to bring water distribution network analysis closer to users.” Proc., Computer and Control in Water Industry (CCWI), September 5–7, D. A. Savic, Z. Kapelan, and D. Butler, eds., Vol. 3, Univ. of Exeter, U.K., 805–810.
Giustolisi, O., Savic, D. A., and Kapelan, Z., (2008c). “Pressure-driven demand and leakage simulation for water distribution networks.” J. Hydraul. Eng., 626–635.
Goldberg, D. E., (1989). Genetic algorithms in search, optimization and machine learning, Addison Wesley, Boston, MA.
Goulter, I. C., and Morgan, D. R. (1985). “An integrated approach to the layout and design of water distribution networks.” Civ. Eng. Syst., 2(2), 104–113.
Grayman, W. M., Murray, R., and Savic, D. A. (2009). “Effects of redesign of water systems for security and water quality actors.” Proc., World Environmental and Water Resources Congress, S. Starrett, ed., Kansas City, MO, ASCE, Reston, VA.
Greco, R., Di Nardo, A., and Santonastaso, G. F. (2012). “Resilience and entropy as indices of robustness of water distribution networks.” J. Hydroinf., 14(3), 761–771.
Herrera, M., Canu, S., Karatzoglou, A., Pérez-García, R., and Izquierdo, J. (2010). “An approach to water supply clusters by semi-supervised learning.” Proc., iEMSs Fourth Biennial Meeting: Int. Congress on Environmental Modelling and Software (iEMSs 2010), 3, International Environmental Modelling and Software Society, Ottawa, Canada, 1925–1932.
Izquierdo, J., Herrera, M., Montalvo, I., and Pérez-García, R. (2011). “Division of water distribution systems into district metered areas using a multi-agent based approach.” Commun. Comput. Inf. Sci., 50(4), 167–180.
Kernighan, B. W., and Lin, S. (1970). “An efficient heuristic procedure for partitioning graphs.” Bell Sys. Tech. J., 49(2), 291–307.
Lambert, A. O. (2002). “International report: Water losses management and techniques.” Water Sci. Technol. Water Supply, 2(4), 1–20.
MATLAB [Computer software]. Mathworks, Inc, Natick, MA.
Mays, L. W. (2000). Water distribution systems handbook, McGraw-Hill, New York.
Morrison, J., Tooms, S., and Rogers, D. (2007). District metered areas guidance notes, International Water Association Water Loss Task Force, London, U.K.
Ng, A. Y., Jordan, M. I., and Weiss, Y. (2001). “On spectral clustering: Analysis and an algorithm.” Advances in neural information processing systems 14, MIT Press, Cambridge, MA, 849–856.
Nicolini, M., and Zovatto, L. (2009). “Optimal location and control of pressure reducing valves in water networks.” J. Water Resour. Plann. Manage., 178–187.
Ostfeld, A. (2005). “Water distribution systems connectivity analysis.” J. Water Resour. Plann. Manage., 58–66.
Ostfeld, A., and Salomon, E. (2004). “Optimal layout of early warning detection stations for water distribution systems security.” J. Water Resour. Plann. Manage., 377–385.
Ostfeld, A., and Shamir, U. (1996). “Design of reliable multiquality water-supply systems.” J. Water Resour. Plann. Manage., 322–333.
Perelman, L., and Ostfeld, A. (2011). “Topological clustering for water distribution systems analysis.” Environ. Model. Software, 26(7), 969–972.
Pohl, I. S. (1969). “Bi-directional and heuristic search in path problems.” Ph.D. thesis, Stanford Linear Accelerator Center, Stanford Univ., Stanford, CA.
Poulin, A., Mailhot, A., Periche, N., Delorme, L., and Villeneuve, J. P. (2010). “Planning unidirectional flushing operations as a response to drinking water distribution system contamination.” J. Water Resour. Plann. Manage., 647–657.
Prasad, T. D., and Park, N.-S. (2004). “Multiobjective genetic algorithms for design of water distribution networks.” J. Water Resour. Plann. Manage., 73–82.
Sempewo, J., Pathirana, A., and Vairavamoorthy, K. (2008). “Spatial analysis tool for development of leakage control zones from the analogy of distributed computing.” Proc., 10th Annual Water Distribution Systems Analysis Conf. WDSA 2008, J. E. Van Zyl, A. A. Ilemobade, and H. E. Jacobs, eds., ASCE, Reston, VA, 1–15.
Sturm, R., and Thornton, J. (2005). “Proactive leakage management using district metered areas (DMA) and pressure management: Is it applicable in North America?” Proc., Leakage 2005 Conf., Halifax, Canada.
Tarjan, R. (1972). “Depth-first search and linear graph algorithms.” SIAM J. Comput. 1(2), 146–160.
Todini, E., and Pilati, S. (1988). “A gradient algorithm for the analysis of pipe networks.” Computer application in water supply, system analysis and simulation, B. Coulbeck and O. Choun-Hou, eds., Vol. 1, Wiley, London, 1–20.
Tzatchkov, V. G., Alcocer-Yamanaka, V. H., and Bourguett-Ortız, V. H. (2006a). “Graph theory based algorithms for water distribution network sectorization projects.” Proc., 8th Annual Water Distribution Systems Analysis Symposium WDSA, ASCE, Reston, VA.
Tzatchkov, V. G., Alcocer-Yamanaka, V. H., and Rodriguez-Varela, J. M. (2006b). “Water distribution network sectorization projects in Mexican cities along the border with USA.” Proc., 3rd Int. Symp. on Transboundary Water Management, Univ. of Castilla-La Mancha, Ciudad Real Spain, 1–13.
Wagner, J. M., Shamir, U., and Marks, D. H. (1988a). “Water distribution reliability: Analytical methods.” J. Water Resour. Plann. Manage., 253–274.
Wagner, J. M., Shamir, U., and Marks, D. H. (1988b). “Water distribution reliability: Simulation methods.” J. Water Resour. Plann. Manage., 276–293.
Water Authorities Association, and Water Research Centre. (1985). Leakage control policy and practice. Technical working group on waste of water, WRC Group, London.
Water Industry Research Ltd. (1999). A manual of DMA practice, Water Industry Research, London.
Water Research Centre (WRC), WSA, WCA. (1994). “U.K. water industry: Managing leakage.” Rep. A-J, WRC, Engineering and Operations Committee, London.
Wooldridge, M. (2002). An introduction to multiagent systems, Wiley, Chichester, U.K.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 140 • Issue 5 • May 2014
Pages: 620 - 629
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Aug 7, 2012
Accepted: Feb 26, 2013
Published online: Feb 28, 2013
Discussion open until: Jul 28, 2013
Published in print: May 1, 2014
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.