Efficient partitioning of water distribution networks using a graph-theoretical approach
Učinkovita particija vodovodnih omrežij na merilna območja z uporabo teorije grafov
- Avtorji: Jure Zevnik, Marjeta Kramar Fijavž, Daniel Kozelj
- Citat: Acta hydrotechnica, vol. 31, no. 54, pp. 35-50, 2018. https://doi.org/10.15292/acta.hydro.2018.03
- Povzetek: V prispevku je predstavljena učinkovita metoda za particijo vodovodnih omrežjih (VO) na merilna območja (MO), ki temelji na teoriji grafov. Algoritem sestoji iz dveh glavnih delov: razbitja VO na MO in njihovega vpetja nazaj v celotno VO. Preizkusili smo ga na primeru realnega VO in med seboj primerjali več različnih utežnih primerov. Učinkovitost predlaganega algoritma za vpetje MO v primerjavi s tradicionalnim kombinatoričnim pristopom smo prikazali za različna števila vzpostavljenih MO. Končno rešitev smo izbrali z uporabo večkriterijskega evalvacijskega modela, ki upošteva hidravlične, stroškovne ter topološke metrike ter izloči subjektivni vpliv na izbiro. Rezultati so pokazali, da je novo predlagana metoda spektralnega razbitja, tj. posplošeni normirani prerez, ustrezna za particijo VO in da lahko z upoštevanjem ustreznih topoloških in cenovnih informacij o VO v fazi razbitja pozitivno vplivamo na dobljeno rešitev.
- Ključne besede: vodovodno omrežje, merilna območja, teorija grafov, spektralno razbitje grafov, transportni vodi, večkriterijski evalvacijski model
- Polno besedilo: a31jz.pdf
- Viri:
- 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.