Application of Primary Network Analysis in Real Water Distribution Systems †
1
Department of Civil, Chemical, Environmental and Materials Engineering—DICAM, University of Bologna, 40136 Bologna, Italy
2
Department of Electrical, Electronic and Information Engineering “Guglielmo Marconi”—DEI, University of Bologna, 40136 Bologna, Italy
*
Authors to whom correspondence should be addressed.
†
Presented at the 3rd International Joint Conference on Water Distribution Systems Analysis & Computing and Control for the Water Industry (WDSA/CCWI 2024), Ferrara, Italy, 1–4 July 2024.
Eng. Proc. 2024, 69(1), 181; https://doi.org/10.3390/engproc2024069181
Published: 8 October 2024
(This article belongs to the Proceedings of The 3rd International Joint Conference on Water Distribution Systems Analysis & Computing and Control for the Water Industry (WDSA/CCWI 2024))
Abstract
:Water distribution systems (WDSs) play a vital rule in communities, ensuring well-being and supporting social and economic growth. Consequently, they are recognized as critical infrastructures for which identifying priorities in design and maintenance interventions is a fundamental step. This work applies a methodology founded on graph theory based algorithmic approach to identify a connected subgraph named the Primary Network (PN) in complex WDSs by focusing on the potentially most suitable paths for transferring water resources in a perspective of interconnection of water sources. Furthermore, the PN can constitute the supporting infrastructure on which to set up a possible WDS sectorization. An efficient implementation is discussed, and the results are presented for a real WDS.
1. Introduction
Water distribution systems (WDSs), ensuring well-being and supporting social and economic growth, are recognized as critical infrastructures. WDSs are complex graphs in which the identification of the most relevant linear elements is extremely challenging [1]. Although the concept of a subset of main pipes transporting water from the water resources to supply users is consolidated in the literature, a univocal definition of the primary network and the identification of this subset present a challenging task [2,3]. Graph theory for connectivity and betweenness centrality metrics were applied to develop different approaches for the ability to read the most important edges [4]. Furthermore, a pipeline criticality assessment was used to determine the importance of the pipes; this type of approach can be further refined if the hydraulic model is available [1]. Transmission mains are identified in [5] as a series of connected pipes whose diameter is at least equal to a properly defined threshold. An approach to determine the pipes mainly dedicated to transport water is presented in [6], where the trunk mains are defined through a process based on the concept of shortest path on a graph weighted according to the flow in each pipe. In [3], the concept of Primary Network was proposed with the meaning of a subset of pipes that guarantee the hydraulic performance and maximum topological redundancy with the strictly necessary reduction in the length of the infrastructure. The application of different algorithmic approaches to real WDSs must deal with the inevitable inconsistencies in the choice of diameters that have occurred over decades of network growth, while the digitization process produces a graph in which the length of the edges can vary significantly. Starting from [7], the focus of this work is on the identification of the fundamental assets in terms of the main pipelines from an infrastructural point of view. The proposed methodology is founded on a graph theory based algorithmic approach to analyze the connected subgraphs, defined as Primary Network (PN), in complex WDSs by focusing on the potentially most suitable infrastructural paths for transferring water resources within WDSs in a perspective of higher interconnection of water sources. Furthermore, the PN can constitute the supporting infrastructure on which to set up an eventual sectorization of the distribution network. In fact, if the distinction between pipes that are mainly dedicated to transport water and pipes that are dedicated to supply users can have less relevance in a completely open WDS, it becomes a fundamental aspect in the sectorization design [2].
2. Materials and Methods
A WDS is assumed to be described by means of an undirected weighted graph G = (N, E), where N is the set of nodes and E is the set of edges. Each edge is associated with a nonnegative weight we. The graph G can comprehend multiple edges between the same pair of nodes. The node set N includes a subset NP ⊂ N of primary nodes, which correspond to water resource inlet nodes, storage volumes as reservoirs or tanks, and nodes for providing water to other WDSs or users of particular strategic importance (such as hospitals, schools, and military zones). In the next subsection, some criteria to identify a connected subgraph PN are presented. The weight we associated with each edge of E is assumed an infrastructural weight, computed as where is the length and the internal diameter. The value assigned to this weight coefficient signifies that, in order to minimize energy dissipation during the transfer of a specified flow, pipes with larger diameters should be prioritized. This aspect is relevant both for the interconnection of primary nodes and for WDS sectorization.
2.1. Criteria for the Definition of Primary Network
Given the undirected weighted graph G = (N, E), PN is defined as a connected subgraph which meets the following criteria: (i) given the strategic relevance of primary nodes, a PN is required to connect the subset NP ⊂ N by means of a minimum weighted path; (ii) a PN is a non-tree subgraph to guarantee a certain degree of redundancy; and (iii) a PN must transport a proper fraction of the water consumption within its edges. The criteria (i) and (ii) are mainly directed to the interconnection of primary nodes; all the criteria (i), (ii), and (iii) are mostly applied to sustain an eventual WDS sectorization.
2.2. Algorithic Approach
The algorithm proceeds with the following exploration tools developed in the Python environment:
T0—Bridge identification. A bridge is an edge of G whose deletion increases the number of connected components. By means of the Tarjan’s algorithm [8], the subset of bridges EB ⊆ E is identified with the relative subset of the nodes NB ⊆ N using a subtended percentage of the network length.
T1—Steiner Tree algorithm. Given a weighted undirected graph G = (N, E) and a subset NS ⊆ N, the Steiner Tree problem finds a minimum cost tree ST = (NS, ES) that contains all the terminals nodes NS. In this approach, the Steiner Tree problem is solved by the algorithm [9], which allows us to obtain a global optimal solution. The criteria (i) of the minimum weighted path that connects the primary nodes NP ⊂ N can be equivalent to the Steiner tree problem [9], where NS = NP. According to an infrastructural approach, an extension of this minimum cost tree problem can also include the set of bridges EB ⊆ E, assuming NS = NP ∪ NB.
T2—k-shortest paths algorithm. The concept of a PN associated with WDS sectorization requires a layout with loops (ii). The exploration tools used is the algorithm k—shortest path that identifies a connected sub-graph K = (NK, EK) by means of the local exploration for each pair of NS [10]. Initially, the optimal shortest path for each pair of nodes of NS corresponding to k = 1 is performed using Dijkstra’s algorithm [8]. Subsequently, the algorithm evaluates k-shortest paths (where k > 1) [10] for each node pair. The inclusion of additional paths is terminated when the percentage increase in path cost compared to the optimal solution for k = 1 exceeds a predefined threshold.
T3—Consumption approach algorithm. A water consumption-oriented approach is developed to identify a subgraph C = (NC, EC), taking into account the spatial distribution of water consumption associated to each node of N. The problem is solved by calculating the edge betweenness among each node of G and the set of water resources that are a sub-set of NP ⊂ N (therefore, not between node and node). Among the shortest paths from each node to the sources, the closest resource is identified. All the edges that are part of this path are identified and the start node demand value is added to the edge counter (that starts from 0 for all edges). This operation is repeated for each node of G.
3. Results
3.1. Case Study
In this section, the algorithmic approach is applied to a large real WDS, called Emilia Network, is a real WDS composed of 3395 nodes (of which 7 are reservoirs and 3 are tanks) and 4400 edges with a total length of 60.313 km and a maximum water demand equal to 1206 L/s.
3.2. Results and Discussion
The obtained PNs (Figure 1a,b) meet the criteria indicated in paragraph 2.1 differently. In Figure 1b, the 1% threshold represents, for each pair of nodes, the maximum allowable increase in weight in the k-shortest path solutions compared to the optimal solution (first shortest path). If, globally, the Steiner Tree (Figure 1a) provides the optimal least cost tree then, locally, the shortest path for k = 1 by T2 (Figure 1b) can identify the minimum cost path between the pairs of nodes. Table 1 presents the lengths of the distinct diameter classes constituting the three identified subgraphs relative to the corresponding diameter class lengths present in the entire WDS. As can be observed, the algorithms select almost all large diameter pipes to connect the chosen nodes. The presence of smaller diameter classes identified by tools T1 and T2 could highlight the limited connectivity between some sources. This should be analyzed for the different potentiality of each of them; if the water resources have comparable contribution capacities instead, these smaller diameter sections could form a bottleneck. The sub-graph in Figure 1c is oriented to the water consumption of the nodes. The identification of the most important edges requires a filter on the edge counter Q. The results presented in Table 1 consider a solution with 2% of the maximum value of the edge counter Qmax. Multiple approaches based on the edge centrality were proposed in the literature [3,4] and could be applied for an extensive analysis.
4. Conclusions
In the planning, design, and management decisions necessary to fill the infrastructure gap relating the water distribution networks, the identification of the main connections of each water sources with storages, and the water distribution and interchanges with other WDSs is strategic in a context of future uncertainty regarding the availability of water resources. The results obtained considering the analysis of the PN can support the understanding of the WDS infrastructure. In addition, in case a numerical model is available, the outcomes can be utilized to integrate the assessment.
Author Contributions
Conceptualization, L.C.Z., M.M. and C.B.; methodology, L.C.Z., M.M. and C.B.; software, L.C.Z.; validation, L.C.Z.; formal analysis, L.C.Z., M.M. and C.B.; investigation, L.C.Z.; data curation, L.C.Z. and C.B.; writing, L.C.Z., M.M. and C.B.; visualization, L.C.Z.; supervision, M.M. and C.B. All authors have read and agreed to the published version of the manuscript.
Funding
This research received no external funding.
Institutional Review Board Statement
Not applicable.
Informed Consent Statement
Not applicable.
Data Availability Statement
The raw data supporting the conclusions of this article, except for the EPANET model, will be made available by the authors on request.
Conflicts of Interest
The authors declare no conflicts of interest.
References
- Meijer, D.; Post, J.; van der Hoek, J.P.; Korvinga, H.; Langeveld, J.; Clemens, F. Identifying critical elements in drinking water distribution networks using graph theory. Struct. Infrastruct. Eng. 2021, 17, 347–360. [Google Scholar] [CrossRef]
- Hajebi, S.; Roshani, E.; Cardozo, N.; Barrett, S.; Clarke, A.; Clarke, S. Water distribution network sectorisation using graph theory and many-objective optimization. J. Hydroinformatics 2016, 18, 77–95. [Google Scholar] [CrossRef]
- Di Nardo, A.; Di Natale, M.; Giudicianni, C.; Santonastaso, G.F.; Savic, D. Simplified Approach to Water Distribution System Management via Identification of a Primary Network. J. Water Resour. Plan. Manag. 2017, 144, 04017089. [Google Scholar] [CrossRef]
- Giustolisi, O.; Ridolfi, L.; Simone, A. Tailoring Centrality Metrics for Water Distribution Networks. Wat. Res. Res. 2019, 55, 2348–2369. [Google Scholar] [CrossRef]
- Ferrari, G.; Savic, D.; Becciu, G. Graph-theoretic approach and sound engineering principles for design of district metered areas. J. Water Resour. Plann. Manag. 2014, 140, 04014036. [Google Scholar] [CrossRef]
- Brentan, B.; Campbell, E.; Goulart, T.; Manzi, D.; Meirelles, G.; Herrera, M.; Izquierdo, J.; Luvizotto, E. Social network community detection and hybrid optimization for dividing water supply into district metered areas. J. Water Resour. Plann. Manag. 2018, 144, 04018020. [Google Scholar] [CrossRef]
- Fortini, M.; Bragalli, C.; Artina, S. Identifying the high-level flow model of water distribution networks using graph theory. Procedia Eng. 2014, 89, 1192–1199. [Google Scholar] [CrossRef]
- Hagberg, A.A.; Schult, D.A.; Swart, P.J. Exploring network structure, dynamics, and function using network. In Proceedings of the 7th Python in Science Conference, Austin, TX, USA, 28–30 June 2008; Varoquaux, G., Vaught, T., Millman, J., Eds.; Proc. SciPy 2008: Pasadena, CA, USA, 2008; pp. 11–15. [Google Scholar]
- Leitner, M.; Ljubić, I.; Luipersbeck, M.; Sinnl, M. A Dual Ascent-Based Branch and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems. INFORMS J. Comput. 2018, 30, 402–420. [Google Scholar] [CrossRef]
- Yen, J.Y. Finding the K Shortest Loopless Paths in a Network. Manag. Sci. Theory Ser. 1971, 17, 712–716. [Google Scholar] [CrossRef]
Figure 1.
Primary Networks for Emilia Network—(a) in blue the Steiner tree by T1, in magenta the added shortest paths edges by T2 (k = 1) (b) in teal the added k-shortest paths edges T2 (k > 1); (c) in dark red Consumption approach results by T3 as presented in Table 1.
Figure 1.
Primary Networks for Emilia Network—(a) in blue the Steiner tree by T1, in magenta the added shortest paths edges by T2 (k = 1) (b) in teal the added k-shortest paths edges T2 (k > 1); (c) in dark red Consumption approach results by T3 as presented in Table 1.
Table 1.
The fraction of the lengths of the identified PN, categorized by diameter class, in relation to the total network length, which is also categorized by diameter class.
Table 1.
The fraction of the lengths of the identified PN, categorized by diameter class, in relation to the total network length, which is also categorized by diameter class.
| Primary Networks | L/Ltot | 100 < D | 100 ≤ D < 200 | 200 ≤ D < 300 | 300 ≤ D < 400 | 400 ≤ D < 500 | D ≥ 500 |
|---|---|---|---|---|---|---|---|
| T1 − ST | 0.104 | 0 | 0.049 | 0.370 | 0.352 | 0.277 | 0.705 |
| T2 − kSP (k = 1) | 0.127 | 0 | 0.077 | 0.410 | 0.440 | 0.465 | 0.809 |
| T2 − kSP (k > 1) | 0.170 | 0 | 0.082 | 0.558 | 0.816 | 0.783 | 0.900 |
| T3 − CA(Q/Qmax ≥ 0.02) | 0.123 | 0 | 0.039 | 0.415 | 0.485 | 0.720 | 0.855 |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
MDPI and ACS Style
Zingali, L.C.; Monaci, M.; Bragalli, C. Application of Primary Network Analysis in Real Water Distribution Systems. Eng. Proc. 2024, 69, 181. https://doi.org/10.3390/engproc2024069181
AMA Style
Zingali LC, Monaci M, Bragalli C. Application of Primary Network Analysis in Real Water Distribution Systems. Engineering Proceedings. 2024; 69(1):181. https://doi.org/10.3390/engproc2024069181
Chicago/Turabian StyleZingali, Lorenzo Carmelo, Michele Monaci, and Cristiana Bragalli. 2024. "Application of Primary Network Analysis in Real Water Distribution Systems" Engineering Proceedings 69, no. 1: 181. https://doi.org/10.3390/engproc2024069181
APA StyleZingali, L. C., Monaci, M., & Bragalli, C. (2024). Application of Primary Network Analysis in Real Water Distribution Systems. Engineering Proceedings, 69(1), 181. https://doi.org/10.3390/engproc2024069181