Efficient partitioning of water distribution networks using a graph-theoretical approach
- Authors: Jure Zevnik, Marjeta Kramar Fijavž, Daniel Kozelj
- Citation: Acta hydrotechnica, vol. 31, no. 54, pp. 35-50, 2018. https://doi.org/10.15292/acta.hydro.2018.03
- Abstract: We present an efficient graph-theoretical method for partitioning water distribution networks (WDNs) into district metered areas (DMAs). The proposed algorithm consists of two main parts, namely WDN partitioning and DMA connection, and is tested on a real-life WDN, for which different weight cases are compared. The efficiency of the proposed DMA connection algorithm, in regard to the traditional combinatorics approach, is shown for various numbers of established DMAs. The final solution is selected according to the multi-criteria evaluation model, which was developed in order to reduce the subjective influence in the selection process and considers hydraulic, cost, and topological criteria. The results show that the newly proposed spectral partitioning method, namely generalized normalized cut, is appropriate for WDN partitioning and that we can further improve the quality of the obtained solutions by considering appropriate topological and cost-based WDN information in the partitioning process.
- Keywords: Water Distribution Network, District Metered Areas, Graph Theory, Spectral Graph Partitioning, Water Mains, Multi-Objective Evaluation Model.
- Full text: a31jz.pdf
- References:
- Alvisi, S., Franchini M. (2014). Heuristic procedure for the automatic creation of district metered areas in water distribution systems, Urban Water Journal 11.2, 137‒159. https://doi.org/10.1080/1573062X.2013.768681.
- Alvisi, S. (2015). A New Procedure for Optimal Design of District Metered Areas Based on the Multilevel Balancing and Refinement Algorithm, Water Resources Management 29, 4397‒4409. https://doi.org/10.1007/s11269-015-1066-z.
- Arthur, D., Vassilvitskii, S. (2007). K-means++: The Advantages of Careful Seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, 1027–1035.
- Campbell, E., Izquierdo, J., Montalvo, I., Pérez-García, R. (2016). A Novel Water Supply Network Sectorization Methodology Based on a Complete Economic Analysis, Including Uncertainties, Water 8(5), 179. https://doi.org/10.3390/w8050179.
- Creaco, E., Franchini, M., Todini, E. (2016). Generalized resilience and failure indices for use with pressure-driven modeling and leakage, Journal of Water Resources Planning and Management 142(8), 04016019. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000656.
- De Paola, F., Fontana, N., Galdiero, E., Giugni, M., Savic, D., Sorgenti degli Uberti, G. (2014). Automatic Multi-Objective Sectorization of a water distribution network, Procedia Engineering 89, 1200‒1207. https://doi.org/10.1016/j.proeng.2014.11.250.
- Diao, K., Zhou, Y., Rauch, W. (2013). Automated creation of district metered areas boundaries in water distribution systems, Journal of Water Resources Planning and Management 139(2), 184‒190. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000247.
- Di Nardo, A., Di Natale, M. (2010). A heuristic design support methodology based on graph theory for district metering of water supply networks, Engineering Optimization 43(2), 193‒211. https://doi.org/10.1080/03052151003789858.
- Di Nardo, A., Di Natale, M., Santonastaso, G. F., Venticinque, S. (2013). An Automated Tool for Smart Water Network Partitioning, Water Resources Management 27(13), 4493‒4508. https://doi.org/10.1007/s11269-013-0421-1.
- Di Nardo, A., Di Natale, M., Greco, R., Santonastaso, G. F. (2014). Ant Algorithm for Smart Water Network Partitioning, Procedia Engineering 70, 525‒534. https://doi.org/10.1016/j.proeng.2014.02.058.
- Di Nardo, A., Di Natale, M., Giudicianni, C., Musmarra, D., Santonastaso, G. F., Simone, A. (2015). Water distribution system clustering and partitioning based on social network algorithms, Procedia Engineering 119, 196‒205. https://doi.org/10.1016/j.proeng.2015.08.876.
- Di Nardo, A., Di Natale, M., Chianese, S., Musmarra, D., Santonastaso, G. F. (2016). Combined Recursive Clustering and Partitioning to Define Optimal DMAs of Water Distribution Networks. Proceedings of the 8th International Congress on Environmental Modelling and Software, Toulouse, France, 63.
- Di Nardo, A., Di Natale, Giudicianni, C., Santonastaso, G. F., Tzatchkov, V., Rodriguez Varela, J. M. (2017a). Economic and Energy Criteria for District Meter Areas Design of Water Distribution Networks, Water 9(7), 463. https://doi.org/10.3390/w9070463.
- Di Nardo, A., Di Natale, Giudicianni, C., Greco, R., Santonastaso, G. F. (2017b). Weighted spectral clustering for water distribution network partitioning, Applied Network Science 2, 19. https://doi.org/10.1007/s41109-017-0033-4.
- Di Nardo, A., Di Natale, Giudicianni, C., Greco, R., Santonastaso, G. F. (2018). Water Distribution Network Clustering: Graph Partitioning or Spectral Algorithms?. Proceedings of the 6th International Conference on Complex Networks and Their Applications: COMPLEX NETWORKS 2017, Lyon, France. Studies in Computational Intelligence, vol 689, 1197‒1209.
- Eliades, D. G., Kyriakou, M., Stelios Vrachimis, S., Polycarpou, M. M. (2016). EPANET-MATLAB Toolkit: An Open-Source Software for Interfacing EPANET with MATLAB. Proceedings of the 14th International Conference on Computing and Control for the Water Industry, CCWI 2016, Amsterdam, Netherlands.
- Ferrari, G. (2012). Hybrid graph partitioning approach for dividing a water distribution network into district metered areas. Proceedings of WDSA 2012: 14th Water Distribution Systems Analysis Conference, 24‒27 September 2012, Adelaide, Australia, 569–578.
- Ferrari, G., Savić, D. A., Becciu, G. (2014). Graph-Theoretic Approach and Sound Engineering Principles for Design of District Metered Areas, Journal of Water Resources Planning and Management 140(12), 04014036. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000424.
- Hajebi, S., Barrett, S., Clarke, A., Clarke, S. (2013). Multi-agent simulation to support water distribution network partitioning. In proceeding of the 27th European Simulation and Modelling Conference ‒ ESM’2013, Lancaster, UK.
- Hajebi, S., Ehsan, R., Cardozo, N., Barrett, S., Clarke, A., Clarke, S. (2016). Water distribution network sectorisation using graph theory and many-objective optimisation, Journal of Hydroinformatics 18(1), 77‒95. https://doi.org/10.2166/hydro.2015.144.
- Hotz, M (2017). generateSpanningTrees(A), MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/53787-generatespanningtrees-a- (Pridobljeno 1. 10. 2017.)
- Karypis, G., Kumar, V. (1999). A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing 20(1), 359–392. https://doi.org/10.1137/S1064827595287997.
- Kozelj, D., Kapelan, Z., Novak, G., Steinman, F. (2014). Investigating prior parameter distributions in the inverse modelling of water distribution hydraulic models, Strojniški vestnik – Journal of Mechanical Engineering 60(11), 725‒734. https://doi.org/10.5545/sv-jme.2014.1741.
- Kozelj, D., Gorjup, M., Kramar Fijavž, M. (2017). Uporaba metode spektralnega razbitja grafov za zasnovo merilnih območij v vodovodnem omrežju, Acta hydrotechnica 30(53), 81‒96.
- Lambert, A. (2003). Assessing non-revenue water and its components: A practical approach, Water 21 5(4), 50‒51.
- Liu, J., Han, R. (2018). Spectral Clustering and Multicriteria Decision for Design of District Metered Areas, Journal of Water Resources Planning and Management 144(5), 04018013. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000916.
- Lloyd, S. P. (1982). Least Squares Quantization in PCM, IEEE Transactions on Information Theory 28(2), 129–137. https://doi.org/10.1109/TIT.1982.1056489.
- Von Luxburg, U. (2007). A tutorial on spectral clustering, Statistics and Computing 17(4), 395‒416. https://doi.org/10.1007/s11222-007-9033-z.
- MATLAB 2015b (2015). The MathWorks, Inc., Natick, Massachusetts, United States.
- Mohar, B., Alavi, Y., Chartrand, G., Oellermann, O., Schwenk, A. (1991). The Laplacian spectrum of graphs. Graph Theory, Combinatorics and Applications 2, 871–898.
- Morrison, J., Rogers, D., Tooms, S. (2007). District Metered Areas Guidance Notes, Water Loss Task Force, IWA Publication, 2007.
- QGIS Development Team (2018). QGIS Geographic Information System. Open Source Geospatial Foundation Project. http://qgis.osgeo.org
- Rossman, L. A. (2000). Epanet2 Users Manual. U. S. Environmental Protection Agency, National Risk Management Research Laboratory, Cincinnati, Ohio, USA.
- Sela Perelman, L., Allen, M., Preis, A., Iqbal, M., Whittle, A. J. (2015). Automated sub-zoning of water distribution systems, Environmental Modelling & Software 65, 1‒14. https://doi.org/10.1016/j.envsoft.2014.11.025.
- Sempewo, J., Pathirana, A., Vairavamoorthy, K. (2008). Spatial analysis tool for development of leakage control zones from the analogy of distributed computing. Proceedings of the 10th Annual Water Distribution Systems Analysis Conference (WDSA 2008), Kruger National Park, South Africa.
- Shi, J., Malik, J. (2000). Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888‒905. https://doi.org/10.1109/34.868688.
- Tarjan, R. E. (1974). A note of finding the bridges of a graph, Information Processing Letters 2(6), 160–161. https://doi.org/10.1016/0020-0190(74)90003-9.
- Wilson, R.J., Watkins, J.J. (1997). Uvod v teorijo grafov. DMFA Slovenije.
- Yen, J. Y. (1971). Finding the k Shortest Loopless Paths in a Network, Management Science 17(11), 712–716. http://dx.doi.org/10.1287/mnsc.17.11.712.