Using Heuristic Techniques to Account for Engineering Aspects in Modularity-Based Water Distribution Network Partitioning Algorithm
Publication: Journal of Water Resources Planning and Management
Volume 145, Issue 12
Abstract
This paper shows how heuristic techniques can be used to account for engineering aspects in the application of a water distribution network (WDN) partitioning algorithm. In fact, being based on graph-theory concepts, most WDN partitioning algorithms fail to consider explicitly such aspects as the number of boundary pipes and the similarity of district metered areas (DMAs) in terms of number of nodes, total demand, and total pipe length, which are often considered by water utility managers to make their decisions. The algorithm considered is the fast-greedy partitioning algorithm (FGPA), based on the original formulation of modularity as an indicator of the strength of WDN partitioning. This algorithm operates by merging the elementary parts of the WDN in sequential steps until the desired number of district metered areas is reached. Two heuristic optimization techniques were combined with FGPA to propose different merging combinations: the former reproduces some specific features of the simulated annealing algorithm while the latter is based on the multiobjective genetic algorithm. Applications were carried out on a real WDN considering the actual system of isolation valves. The partitioning solutions obtained by the traditional FGPA without heuristics and by a literature algorithm based on spectral clustering were taken as benchmark. The results proved that the former heuristic can help in obtaining numerous WDN partitioning solutions with high modularity. The performance of these solutions can be evaluated in terms of practical engineering aspects to help WDN managers make an informed choice about the ultimate solution. If the trade-off between engineering criteria needs to be thoroughly analyzed in the context of WDN partitioning, the latter heuristic, in which FGPA creates DMAs through information encoded in proper weights, can be effectively used. Compared to the benchmark solutions, the FGPA with the latter heuristic can yield solutions with fewer boundary pipes and better demand uniformity over the DMAs.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
The readers can access the data upon request to the corresponding author. The software used in this study is made available upon request by the authors of the paper. The data related to the real water distribution network are confidential and can be provided with restrictions.
References
Alvisi, S., E. Creaco, and M. Franchini. 2011. “Segment identification in water distribution systems.” Urban Water J. 8 (4): 203–217. https://doi.org/10.1080/1573062X.2011.595803.
Alvisi, S., and M. Franchini. 2013. “A heuristic procedure for the automatic creation of district metered areas in water distribution systems.” Urban Water J. 11 (2): 137–159. https://doi.org/10.1080/1573062X.2013.768681.
Campbell, E., J. Izquierdo, I. Montalvo, A. Ilaya-Ayza, R. Perez-Garcia, and M. Tavera. 2016. “A flexible methodology to sectorize water supply networks based on social network theory concepts and multiobjective optimization.” J. Hydroinf. 18 (1): 62–76. https://doi.org/10.2166/hydro.2015.146.
Candelieri, A., D. Conti, and F. Archetti. 2014. “A graph based analysis of leak localization in urban water networks.” Procedia Eng. 70 (Jan): 228–237. https://doi.org/10.1016/j.proeng.2014.02.026.
Ciaponi, C., E. Murari, and S. Todeschini. 2016. “Modularity-based procedure for partitioning water distribution systems into independent districts.” Water Resour. Manage. 30 (6): 2021–2036. https://doi.org/10.1007/s11269-016-1266-1.
Clauset, A., M. E. J. Newman, and C. Moore. 2004. “Finding community structure in very large networks.” Phys. Rev. E 70 (6): 066111. https://doi.org/10.1103/PhysRevE.70.066111.
Creaco, E., A. Di Nardo, M. Di Natale, C. Giudicianni, and G. F. Santonastaso. 2017. “Multi-object approach for WSN partitioning in the framework of pressure driven analysis.” Accessed September 01, 2017. https://figshare.com/articles/CCWI2017_F19_Multi-object_approach_for_WSN_Partitioning_in_the_framework_of_Pressure_Driven_Analysis_/5364121/1.
Creaco, E., M. Franchini, and S. Alvisi. 2010. “Optimal placement of isolation valves in water distribution systems based on valve cost and weighted average demand shortfall.” Water Resour. Manage. 24 (15): 4317–4338. https://doi.org/10.1007/s11269-010-9661-5.
Creaco, E., M. Franchini, and E. Todini. 2016. “Generalized resilience and failure indices for use with pressure driven modeling and leakage.” J. Water Resour. Plann. Manage. (ISI) 142 (8): 04016019. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000656.
Deb, K., S. Agrawal, A. Pratapm, and T. Meyarivan. 2002. “A fast and elitist multi-objective genetic algorithm: NSGA-II.” IEEE Trans. Evol. Comput. 6 (2): 182–197. https://doi.org/10.1109/4235.996017.
Deuerlein, J. 2008. “Decomposition model of a general water supply network 357 graph.” J. Hydraul. Eng. 136 (6): 822–832. https://doi.org/10.1061/(ASCE)0733-9429(2008)134:6(822).
Diao, K. G., Y. W. Zhou, and W. Rauch. 2013. “Automated creation of district metered areas boundaries in water distribution systems.” J. Water Resour. Plann. Manage. 139 (2): 184–190. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000247.
Di Nardo, A., M. Di Natale, C. Giudicianni, R. Greco, and G. F. Santonastaso. 2016. “Weighted spectral clustering for water distribution network partitioning.” Appl. Network Sci. 2 (1): 19. https://doi.org/10.1007/s41109-017-0033-4.
Di Nardo, A., M. Di Natale, C. Giudicianni, G. F. Santonastaso, V. G. Tzatchkov, J. M. R. Varela, and V. H. A. Yamanaka. 2017. “Economic and energy criteria for district meter areas design of water distribution networks.” Water 9 (463): 1–13. https://doi.org/10.3390/w9070463.
Farley, M. 2001. “Leakage monitoring and control.” In Leakage management and control: A best practice training manual, 58–98. Geneva: World Health Organization.
Ferrari, G., D. A. Savic, and G. Becciu. 2014. “A graph theoretic approach and sound engineering principles for design of district metered areas.” J. Water Resour. Plann. Manage. 140 (12): 04014036. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000424.
Galdiero, E., F. De Paola, N. Fontana, M. Giugni, and D. Savic. 2016. “Decision support system for the optimal design of district metered areas.” J. Hydroinf. 18 (1): 49–61. https://doi.org/10.2166/hydro.2015.023.
Giugni, M., N. Fontana, D. Portolano, and D. Romanelli. 2008. “A DMA design for ‘Napoli Est’ water distribution system.” In Proc., 13th IWRA World Water Congress. Montpellier, France: International Water Resources Association.
Giustolisi, O., and L. Ridolfi. 2014a. “A new modularity-based approach to segmentation of water distribution network.” J. Hydraul. Eng. 140 (10): 04014049. https://doi.org/10.1061/(ASCE)HY.1943-7900.0000916.
Giustolisi, O., and L. Ridolfi. 2014b. “A novel infrastructure modularity index for the segmentation of water distribution networks.” Water Resour. Res. 50 (10): 7648–7661. https://doi.org/10.1002/2014WR016067.
Giustolisi, O., and D. Savic. 2010. “Identification of segments and optimal isolation valve system design in water distribution networks.” Urban Water 7 (1): 1–15. https://doi.org/10.1080/15730620903287530.
Hajebi, S., E. Roshani, and N. Cardozo. 2016. “Water distribution network sectorisation using graph theory and many-objective optimisation.” J. Hydroinf. 18 (1): 77–95. https://doi.org/10.2166/hydro.2015.144.
Herrera, M., E. Abraham, and I. Stoianov. 2016. “A graph-theoretic framework for assessing the resilience of sectorised water distribution networks.” Water Resour. Manage. 30 (5): 1685–1699. https://doi.org/10.1007/s11269-016-1245-6.
Jun, H., and G. V. Loganathan. 2007. “Valve-controlled segments in water distribution systems.” J. Water Resour. Plann. Manage. 133 (2): 145–155. https://doi.org/10.1061/(ASCE)0733-9496(2007)133:2(145).
Kirkpatrick, S., and C. D. Gelatt Jr. 1983. “Optimization by simulated annealing.” Science 220 (4598): 671–680. https://doi.org/10.1126/science.220.4598.671.
Laucelli, D., B. A. Simone, L. Berardi, and O. Giustolisi. 2017. “Optimal design of district metering areas for the reduction of leakages.” J. Water Resour. Plann. Manage. 143 (6): 04017017. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000768.
Liu, J., and R. Han. 2018. “Spectral clustering and multicriteria decision for design of district metered areas.” J. Water Resour. Plann. Manage. 144 (5): 04018013. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000916.
Morrison, J. 2004. “Managing leakage by district metered areas: A practical approach.” Water 21 (Feb): 44–46.
Newman, M. E. J. 2004a. “Analysis of weighted networks.” Phys. Rev. E 70 (5): 056131. https://doi.org/10.1103/PhysRevE.70.056131.
Newman, M. E. J. 2004b. “Fast algorithm for detecting community structure in networks.” Phys. Rev. E 69 (6): 066133. https://doi.org/10.1103/PhysRevE.69.066133.
Perelman, L., and A. Ostfeld. 2011. “Topological clustering for water distribution systems analysis.” Environ. Modell. Software 26 (7): 969–972. https://doi.org/10.1016/j.envsoft.2011.01.006.
Perelman, L. S., M. Allen, A. Preis, M. Iqbal, and A. J. Whittle. 2015. “Flexible reconfiguration of existing urban water infrastructure systems.” Environ. Sci. Technol. 49 (22): 13378–13384. https://doi.org/10.1021/acs.est.5b03331.
Walski, T. M., D. V. Chase, D. A. Savic, W. Grayman, S. Beckwith, and E. Koelle. 2003. “Introduction to water distribution modeling; using models for water distribution system design.” In Vol. 4 of Advanced water distribution modeling and management. 1st ed., 333–337. Waterbury, CT: Haestad Press.
Zhang, Q. 2017. “Automatic partitioning of water distribution networks using multiscale community detection and multiobjective optimization.” J. Water Resour. Plann. Manage. 143 (9): 04017057. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000819.
Zheng, F., A. R. Simpson, A. C. Zecchin, and J. W. Deuerlein. 2013. “A graph decomposition based approach for water distribution network optimization.” Water Resour. Res. 49 (4): 2093–2109. https://doi.org/10.1002/wrcr.20175.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 145 • Issue 12 • December 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Nov 18, 2018
Accepted: Apr 15, 2019
Published online: Oct 3, 2019
Published in print: Dec 1, 2019
Discussion open until: Mar 3, 2020
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.