Automatic Partitioning of Water Distribution Networks Using Multiscale Community Detection and Multiobjective Optimization
Publication: Journal of Water Resources Planning and Management
Volume 143, Issue 9
Abstract
Partitioning water distribution networks into district metered areas (DMAs) is a challenge for water utilities due to the complexity of network topology, especially for large-scale and highly looped water supply systems. This paper presents a novel approach, using complex network theory and multiobjective optimization, for efficiently partitioning of water distribution networks. In this approach, a water distribution network is first mapped on to a weighted undirected graph, and its strength is measured by an extended modularity by a random walk strategy. Then, the Louvain algorithm is employed for network partitioning based on the modularity. Finally, boundary pipes between DMAs are determined by applying an evolutionary algorithm to minimize the number of boundary pipes and maximize the network pressure and water age uniformity. The approach has been tested on a real-world distribution system to demonstrate the effectiveness of the method. The results indicate that the method is effective at partitioning the network into DMAs with a similar pressure and water age.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The part of work is financially supported by the National Science and Technology Major Project (2014ZX07406003).
References
Alhimiary, H., and Alsuhaily, R. (2007). “Minimizing leakage rates in water distribution networks through optimal valves settings.” World Environmental and Water Resources Congress 2007, ASCE, Reston, VA, 1–13.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). “Fast unfolding of communities in large networks.” J. Stat. Mech: Theory Exp., 2008(10), P10008.
Campbell, E., et al. (2016). “A flexible methodology to sectorize water supply networks based on social network theory concepts and multi-objective optimization.” J. Hydroinf., 18(1), 62–76.
Campbell, E., Ayala-Cabrera, D., Izquierdo, J., Pérez-García, R., and Tavera, M. (2014). “Water supply network sectorization based on social networks community detection algorithms.” Procedia Eng., 89, 1208–1215.
Candelieri, A., Conti, D., and Archetti, F. (2014). “A graph based analysis of leak localization in urban water networks.” Procedia Eng., 70, 228–237.
Ciaponi, C., Murari, E., and Todeschini, S. (2016). “Modularity-based procedure for partitioning water distribution systems into independent districts.” Water Resour. Manage., 30(6), 2021–2036.
Deuerlein, J. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 822–832.
Diao, K. G., Zhou, Y. W., and Rauch, W. (2013). “Automated creation of district metered areas boundaries in water distribution systems.” J. Water Resour. Plann. Manage., 184–190.
Di Nardo, A., Di Natale, M., Musmarra, D., Santonastaso, G. F., Tzatchkov, V. G., and Alcocer-Yamanaka, V. H. (2015). “Dual-use value of network partitioning for water system management and protection from malicious contamination.” J. Hydroinf., 17(3), 361–376.
EPANET 2.0 [Computer software]. National Risk Management Research Laboratory, Cincinnati.
Farley, M. (2001). “Leakage monitoring and control.” Leakage management and control: A best practice training manual, World Health Organization, Geneva, 58–98.
Ferrari, G., Savic, D., and Becciu, G. (2014). “Graph-theoretic approach and sound engineering principles for design of district metered areas.” J. Water Resour. Plann. Manage., 04014036.
Fortunato, S. (2010). “Community detection in graphs.” Phys. Rep., 486(3–5), 75–174.
Fortunato, S., and Barthelemy, M. (2007). “Resolution limit in community detection.” Proc. Natl. Acad. Sci. U.S.A., 104(1), 36–41.
Galdiero, E., De Paola, F., Fontana, N., Giugni, M., and Savic, D. (2016). “Decision support system for the optimal design of district metered areas.” J. Hydroinf., 18(1), 49–61.
Girvan, M., and Newman, M. E. J. (2002). “Community structure in social and biological networks.” Proc. Natl. Acad. Sci. U.S.A., 99(12), 7821–7826.
Giustolisi, O., and Ridolfi, L. (2014). “New modularity-based approach to segmentation of water distribution networks.” J. Hydraul. Eng., 04014049.
Giustolisi, O., Ridolfi, L., and Berardi, L. (2015). “General metrics for segmenting infrastructure networks.” J. Hydroinf., 17(4), 505–517.
Grayman, W. M., Murray, R., and Savic, D. A. (2009). “Effects of redesign of water systems for security and water quality factors.” Proc., World Environmental and Water Resources Congress 2009, ASCE, Reston, VA, 504–514.
Hadka, D., and Reed, P. (2013). “BORG: An auto-adaptive many-objective evolutionary computing framework.” Evol. Comput., 21(2), 231–259.
Hajebi, S., Roshani, E., Cardozo, N., et al. (2016). “Water distribution network sectorisation using graph theory and many-objective optimisation.” J. Hydroinf., 18(1), 77–95.
Herrera, M., Abraham, E., and Stoianov, I. (2016). “A graph-theoretic framework for assessing the resilience of sectorised water distribution networks.” Water Resour. Manage., 30(5), 1685–1699.
Lambiotte, R., Delvenne, J.-C., and Barahona, M. (2014). “Random walks, Markov processes and the multiscale modular organization of complex networks.” IEEE Trans. Network Sci. Eng., 1(2), 76–90.
Maier, H., et al. (2014). “Evolutionary algorithms and other metaheuristics in water resources: Current status, research challenges and future directions.” Environ. Modell. Software, 62(9), 271–299.
Marchi, A., et al. (2014). “Battle of the water networks II.” J. Water Resour. Plann. Manage., 04014009.
Newman, M. E. J., and Girvan, M. (2004). “Finding and evaluating community structure in networks.” Phys. Rev. E, 69(2), 026113.
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., 556–568.
Perelman, L., and Ostfeld, A. (2011). “Topological clustering for water distribution systems analysis.” Environ. Modell. Software, 26(7), 969–972.
Perelman, L. S., Allen, M., Preis, A., Iqbal, M., and Whittle, A. J. (2015). “Automated sub-zoning of water distribution systems.” Environ. Model1. Software, 65, 1–14.
Perelman, L. S., Allen, M., Preisc, A., Iqbal, M., and Whittle, A. J. (2014). “Multi-level automated sub-zoning of water distribution systems.” Proc., 7th Int. Congress on Environmental Modelling and Software, San Diego.
Reed, P. M., Hadka, D., Herman, J., Kasprzyk, J., and Kollat, J. (2013). “Evolutionary multiobjective optimization in water resources: The past, present, and future.” Adv. Water Resour., 51(1), 438–456.
Scarpa, F., Lobba, A., and Becciu, G. (2016). “Elementary DMA design of looped water distribution networks with multiple sources.” J. Water Resour. Plann. Manage., 04016011.
Scibetta, M., Boano, F., Revelli, R., and Ridolfi, L. (2014). “Community detection as a tool for district metered areas identification.” Procedia Eng., 70, 1518–1523.
Wang, Q., Guidolin, M., Savic, D., and Kapelan, Z. (2015). “Two-objective design of benchmark problems of a water distribution system via MOEAs: Towards the best-known approximation of the true Pareto front.” J. Water Resour. Plann. Manage., 04014060.
Zheng, F., Simpson, A. R., Zecchin, A. C., and Deuerlein, J. W. (2013). “A graph decomposition-based approach for water distribution network optimization.” Water Resour. Res., 49(4), 2093–2109.
Zheng, F., Zecchin, A., Maier, H., and Simpson, A. (2016). “Comparison of the searching behavior of NSGA-II, SAMODE, and Borg MOEAs applied to water distribution system design problems.” J. Water Resour. Plann. Manage., 04016017.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 143 • Issue 9 • September 2017
Copyright
©2017 American Society of Civil Engineers.
History
Received: Sep 16, 2016
Accepted: Apr 14, 2017
Published online: Jul 14, 2017
Published in print: Sep 1, 2017
Discussion open until: Dec 14, 2017
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.