Optimal Rehabilitation of Water Distribution Systems Using a Cluster-Based Technique
Publication: Journal of Water Resources Planning and Management
Volume 143, Issue 7
Abstract
Optimal rehabilitation of large water distribution systems (WDSs) with many decision variables is often time consuming and computationally expensive. This paper presents a new optimal rehabilitation methodology for WDSs based on the graph theory clustering concept. The methodology starts with partitioning the WDS based on its connectivity properties into a number of clusters (small subsystems). Pipes that might have direct impact on system performance are identified and considered for the rehabilitation problem. Three optimization-based strategies are then considered for pipe rehabilitation in the clustered network: (1) rehabilitation of some of the pipes inside the clusters, (2) rehabilitation of pipes in the path supplying water to the clusters, and (3) a combination of Strategies 1 and 2. In all optimization strategies, the decision variables for the rehabilitation problem are the diameters of duplicated pipes; the objective functions are to minimize the total cost of duplicated pipes and the number of nodes with pressure deficiency. The performance of proposed strategies was demonstrated in a large WDS with pressure deficiencies. The performance of these strategies was also compared to the full search space optimization strategy and engineering judgment–based optimization strategy in which all pipes and selection of pipes are considered as decision variables, respectively. The results show that Strategy 3 is able to generate solutions with similar performance that are cheaper by around 53% and 35% in comparison with the full search space and engineering judgment–based optimization strategies, respectively. The results also demonstrate that the cluster-based approach can reduce the computational efforts for achieving optimum solutions compared to the other optimization strategies.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The work reported is supported by the U.K. Engineering & Physical Sciences Research Council (EPSRC) project Safe & SuRe (EP/K006924/1).
References
Blondel, V., Guillaume, J., Lambiotte, R., and Lefebvre, E. (2008). “Fast unfolding of communities in large networks.” J. Stat. Mech.: Theory Exp., 2008(10), .
Cheung, P. B., Reis, L. F., Formiga, K. T., Chaudhry, F. H., and Ticona, W. G. (2003). “Multi-objective evolutionary algorithms applied to the rehabilitation of a water distribution system: A comparative study.” Evolutionary multi-criterion optimization, Springer, Berlin, 662–676.
Clauset, A., Newman, M., and Moore, C. (2004). “Finding community structure in very large networks.” Phys. Rev. E, 70(6), .
CWS. (2016). “EXNET network benchmarks at centre for water systems.” ⟨http://emps.exeter.ac.uk/engineering/research/cws/resources/benchmarks/expansion/exnet.php⟩ (Nov. 2014).
Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, Indian Institute of Technology, Kanpur Genetic Algorithms Laboratory, Kanpur, India.
Deuerlein, J. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 822–832.
Deuerlein, J., Elhay, S., and Simpson, A. (2016). “Fast graph matrix partitioning algorithm for solving the water distribution system equations.” J. Water Resour. Plann. Manage., .
Diao, K., Farmani, R., Fu, G., Astaraie-Imani, M., Ward, S., and Butler, D. (2014). “Clustering analysis of water distribution systems: Identifying critical components and community impacts.” Water Sci. Technol., 70(11), 1764–1776.
Diao, K., Fu, G., Farmani, R., Guidolin, M., and Butler, D. (2015). “Twin-hierarchy decomposition for optimal design of water distribution systems.” J. Water Resour. Plann. Manage., .
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.
Di Nardo, A., and Di Natale, M. (2011a). “A design support methodology for district metering of water supply networks.” Water Distribution Systems Analysis 2010: Proc., 12th Int. Conf., K. E. Lansey, C. Y. Choi, A. Ostfeld, and I. L. Pepper, eds., ASCE, Reston, VA.
Di Nardo, A., and Di Natale, M. (2011b). “A heuristic design support methodology based on graph theory for district metering of water supply networks.” Eng. Optim., 43(2), 193–211.
Engelhardt, M., Skipworth, P., Savić, D., Saul, A., and Walters, G. (2000). “Rehabilitation strategies for water distribution networks: A literature review with a UK perspective.” Urban Water, 2(2), 153–170.
Farmani, R., Savić, D. A., and Walters, G. A. (2005a). “Evolutionary multi-objective optimization in water distribution network design.” Eng. Optim., 37(2), 167–183.
Farmani, R., Walters, G. A., and Savić, D. A. (2005b). “Trade-off between total cost and reliability for Anytown water distribution network.” J. Water Resource. Plann. Manage., 161–171.
Ferrari, G., Savić, D., and Becciu, G. (2014). “A graph theoretic approach and sound engineering principles for design of district metered areas.” J. Water Resour. Plann. Manage., .
Fortunato, S. (2010). “Community detection in graphs.” Phys. Rep., 486(3), 75–174.
Fu, G., Kapelan, Z., and Reed, P. (2012). “Reducing the complexity of multi-objective water distribution system optimization through global sensitivity analysis.” J. Water Resour. Plann. Manage., 196–207.
Gephi.org. (2014). “Gephi, an open source graph visualization and manipulation software.” ⟨https://gephi.org/⟩ (Jun. 22, 2014).
Giustolisi, O., Laucelli, D., and Savić, D. A. (2006). “Development of rehabilitation plans for water mains replacement considering risk and cost-benefit assessment.” Civil Eng. Environ. Syst., 23(3), 175–190.
Giustolisi, O., and Ridolfi, L. (2014). “New modularity-based approach to segmentation of water distribution networks.” J. Hydraul. Eng., .
Herrera Fernandez, A. M. (2011). "Improving water network management by efficient division into supply clusters." ⟨http://riunet.upv.es/handle/10251/11233⟩ (Jun. 17, 2014).
Kadu, M. S., Gupta, R., and Bhave, P. R. (2008). “Optimal design of water networks using a modified genetic algorithm with reduction in search space.” J. Water Resour. Plann. Manage., 147–160.
Kessler, A., Ormsbee, L., and Shamir, U. (1990). “A methodology for least-cost design of invulnerable water distribution networks.” Civ. Eng. Syst., 7(1), 20–28.
Kim, J., and Mays, L. (1994). “Optimal rehabilitation model for water-distribution systems.” J. Water Resour. Plann. Manage., 674–692.
Mandel, P., Maurel, M., and Chenu, D. (2015). “Better understanding of water quality evolution in water distribution networks using data clustering.” Water Res., 87, 69–78.
Newman, M. E. J. (2006). “Modularity and community structure in networks.” PNAS, 103(23), 8577–8582.
Perelman, L., and Ostfeld, A. (2011). “Topological clustering for water distribution systems analysis.” Environ. Modell. Software, 26(7), 969–972.
Price, E., and Ostfeld, A. (2016). “Successive linear programming approach applied to BBLAWN.” J. Water Resour. Plann. Manage., .
Rahmani, F., Behzadian, K., and Ardeshir, A. (2016). “Rehabilitation of a water distribution system using sequential multiobjective optimization models.” J. Water Resour. Plann. Manage., .
Rossman, L. (1999). “Computer models/EPANET.” Water distribution systems handbook, L. Mays, ed., McGraw-Hill, New York.
Savić, D., and Banyard, J., eds. (2011). Water distribution systems, 1st Ed., ICE Publications, London.
Savić, D. A., Bicik, J., and Morley, M. S. (2011). “A DSS generator for multiobjective optimisation of spreadsheet-based models.” Environ. Modell. Software, 26(5), 551–561.
Scarpa, F., Lobba, A., and Becciu, G. (2016). “Elementary DMA design of looped water distribution networks with multiple sources.” J. Water Resour. Plann. Manage., .
Schaeffer, S. (2007). “Graph clustering.” Comput. Sci. Rev., 1(1), 27–64.
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.
Stokes, C., Maier, H., and Simpson, A. (2016). “Effect of storage tank size on the minimization of water distribution system cost and greenhouse gas emissions while considering time-dependent emissions factors.” J. Water Resour. Plann. Manage., .
Swamee, P. K., and Sharma, A. K. (1990). “Decomposition of large water distribution systems.” J. Environ. Eng., 116(2), 269–283.
Swamee, P. K., and Sharma, A. K. (2008). Design of water supply pipe networks, Wiley, NJ.
Tzatchkov, V., Alcocer-Yamanaka, V., and Ortiz, V. (2006). “Graph theory based algorithms for water distribution network sectorization projects.” 8th Annual Water Distribution Systems Analysis Symp., ASCE, Reston, VA.
Wang, Q., Guidolin, M., Savić, 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, .
Yazdani, A., and Jeffrey, P. (2010). “A complex network approach to robustness and vulnerability of spatially organized water distribution networks.” ⟨⟩ (Aug. 11, 2010).
Zecchin, A. C., Thum, P., Simpson, A. R., and Tischendorf, C. (2012). “Steady-state behavior of large water distribution systems: algebraic multigrid method for the fast solution of the linear step.” Water Resour. Plann. Manage., 639–650.
Zheng, F., Simpson, A., Zecchin, A., and Deuerlein, J. (2013). “A graph decomposition-based approach for water distribution network optimization.” Water Resour. Res., 49(4), 2093–2109.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 143 • Issue 7 • July 2017
Copyright
©2017 American Society of Civil Engineers.
History
Received: Jul 4, 2016
Accepted: Dec 21, 2016
Published online: Mar 20, 2017
Published in print: Jul 1, 2017
Discussion open until: Aug 20, 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.