Graph-Theoretic Approach and Sound Engineering Principles for Design of District Metered Areas
Publication: Journal of Water Resources Planning and Management
Volume 140, Issue 12
Abstract
The design of district metered areas (DMAs) in existing water distribution networks, especially in urban areas, involves a high number of decision variables, and the effects of implementing them in districts have to be evaluated in order not to affect the quality of the service to customers. A new methodology for designing a given number of districts in looped water distribution networks is proposed here. It is based on graph theory and takes into account some important DMA design criteria: the maximum and minimum size recommended for a district, the connectedness of each district to the water supply source, and the absence of links between the districts. Therefore, it allows the creation of DMAs that are independent from each other. A recursive bisection procedure has been applied to create districts, while an algorithm for graph traversal has been used to verify whether each district can be reached from the water source and connectivity between the nodes. The successful application of the proposed methodology to a case study has proven its effectiveness for district metered areas design in real urban water distribution networks.
Get full access to this article
View all available purchase options and get full access to this article.
References
Alvisi, S., and Franchini, M. (2014). “A heuristic procedure for the automatic creation of district metered areas in water distribution systems.” Urban Water J., 11(2), 137–159.
American Water Works Association (AWWA) Water Loss Control Committee. (2003). “Applying worldwide BMPs in water loss control.” J. Am. Water Works Assoc., 95(8), 65–71.
Awad, H., Kapelan, Z., and Savić, D. (2009). “Optimal setting of time-modulated pressure reducing valves in water distribution networks using genetic algorithms.” Integrating Water Systems, J. Boxall and C. Maksimovic, eds., Taylor and Francis, London, 31–37.
Baker, M. (2009). “The Baker report: Municipal water distribution system security study-recommendations for science and technology investments.” U.S. Dept. of Homeland Security, Washington, DC.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to algorithms, MIT Press, Cambridge, MA.
Deuerlein, J. (2008). “Decomposition model of a graph water supply network graph.” J. Hydraul. Eng., 822–832.
Diao, K., Zhou, Y., and Rauch, W. (2013). “Automated creation of district metered area boundaries in water distribution systems.” J. Water Resour. Plann. Manage., 184–190.
Dijkstra, E. (1959). “A note on two problems in connections with graphs.” Numerische Mathematik, 1, 269–271.
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., Di Natale, M., Santonastaso, G., Tzatchkov, V., and Alcocer-Yamanaka, V. (2013). “Water network sectorization based on graph theory and energy performance indices.” J. Water Resour. Plann. Manage., 620–629.
Di Nardo, A., Di Natale, M., Santonastaso, G., and Venticinque, S. (2011). “Graph partitioning for automatic sectorization of a water distribution system.” Proc. Control and Computing for the Water Industry, Vol. 3, Centre for Water Systems, Univ. of Exeter, Exeter, UK, 841–846.
Farley, M. R. (1985). “District metering.” Part 1—System design and installation, WRc, Swindon, U.K.
Grayman, W. M., Murray, R. E., and Savic, D. A. (2009). “Effects of redesign of water distribution system for water security and water quality factors.” Proc. EWRI-ASCE World Water Environment Resources Congress, ASCE, Reston, VA.
Jacobs, P., and Goulter, I. C. (1989). “Optimization of redundancy in water distribution networks using graph theoretic principles.” Eng. Optim., 15(1), 71–82.
Karapys, G., and Kumar, V. (1995). “METIS—Unstructured graph partitioning and sparse matrix ordering system. Version 2.0.” Univ. of Minnesota, Minneapolis.
Kesavan, H. K., and Chandrashekar, M. (1972). “Graph theoretic models for pipe network analysis.” J. Hydraul. Div., 98(2), 345–363.
MacDonald, G., and Yates, C. (2005). “DMA design and implementation, an American context.” Proc. IWA Specialised Conf. Leakage, IWA Publishing, Halifax, NS.
MATLAB 7.10 Release 2010a [Computer software]. Natick, Massachusetts, The MathWorks Inc.
Morrison, J., Tooms, S., and Rogers, D. (2007). DMA management guidance notes, IWA Publication, London.
Murray, R. E., Grayman, W. M., Savic, D. A., and Farmani, R. (2010). “Effects of DMA redesign on water distribution system performance.” Integrating water systems, J. Boxall and C. Maksimovíc, eds., Taylor and Francis Group, London.
Ostfeld, A. (2005). “Water distribution systems connectivity analysis.” J. Water Resour. Plann. Manage., 58–66.
Ostfeld, A., et al. (2008). “The battle of the water sensor networks: A design challenge for engineers and algorithms.” J. Water Resour. Plann. Manage., 556–568.
Ostfeld, A., and Shamir, U. (1996). “Design reliable multiquality water-supply systems.” J. Water Resour. Plann. Manage., 322–333.
Pohl, I. S. (1989). “Bi-directional and heuristic search in path problems.” Ph.D. thesis, Stanford Linear Accelereator Centre, Stanford Univ., Stanford, CA.
Roger, D. (2005). “Reducing leakage in Jakarta, Indonesia.” Proc. IWA Specialised Conf. Leakage, IWA Publishing, Halifax, NS.
Rossman, L. A. (2000). “EPANET2.”, Water Supply and Water Resources Division, National Risk Management Research Laboratory, Office of Research and Development, U.S. EPA, Cincinnati.
Todini, E., and Pilati, S. (1987). “A gradient method for the analysis of pipe networks.” Proc. Int. Conf. on Computer Applications for Water Supply and Distribution, Leicester Polythechnic, U.K.
Tzatchkov, V., Alcocer-Yamanaka, V., and Ortiz, V. (2006). “Graph theory based algorithms for water distribution network sectorization projects.” Proc. 8th Annual Water Distribution Systems Analysis Symp., ASCE, Reston, VA, 323–330.
Information & Authors
Information
Published In
Copyright
© 2014 American Society of Civil Engineers.
History
Received: Aug 13, 2013
Accepted: Nov 20, 2013
Published online: Nov 23, 2013
Discussion open until: Oct 28, 2014
Published in print: Dec 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.