1 Introduction

Water supply reliability is a pressing concern due to urbanization, increasing water demands, spatio-temporal disruptions, cyber-physical threats, and climate change impacts (Ashraf et al. 2019; Özerol et al. 2020; Taormina et al. 2018). The World Economic Forum recognized water crises among top ten threats to global economic growth (McLennan 2021), prompting the United Nations to integrate clean water supply and sanitation into their sustainability initiatives and allocate funds (United Nations 2021; Källqvist 2021). Utilities are constantly challenged with managing water distribution networks (WDNs) (Al-Washali et al. 2020; Oviedo-Ocaña et al. 2020; Ávila et al. 2022; Bui et al. 2022) to ensure uninterrupted customer service and reliable water supply, especially during extreme conditions, necessitating proactive and protective measures (Kang and Lansey 2014). Specifically, risks and uncertainties associated with deteriorating pipeline infrastructure are not straightforward to deal with (Bui et al. 2022).

In recent years, substantial efforts have focused on enhancing the sustainability and management of large WDNs (Perelman and Ostfeld 2011; Bui et al. 2020), which are subdivided into District Metered Areas (DMAs) to facilitate operational management (Malcolm 2001; Walski et al. 2003; Bui et al. 2022). DMAs entail using gate valves (closed valves) strategically for isolation and flow meters for quantifying inflow and outflow (Bui et al. 2022), serving multiple objectives, including:

  1. (a)

    Cost minimization and energy conservation (Zhang et al. 2019; Giudicianni et al. 2020a, b),

  2. (b)

    Real loss management (Gomes et al. 2011; Creaco and Haidar 2019; Shekofteh et al. 2020b; Zhang et al. 2021; Moslehi et al. 2020),

  3. (c)

    Apparent loss control (Mix et al. 2020; Wu and Liu 2020; Ghamkhar et al. 2023),

  4. (d)

    Contamination prevention (Di Nardo et al. 2013a; Lifshitz and Ostfeld 2018),

  5. (e)

    Water quality monitoring (Ciaponi et al. 2019),

  6. (f)

    Sensor deployment (Raei et al. 2018; Ciaponi et al. 2019; Yousefi-Khoshqalb et al. 2023),

  7. (g)

    Risk reduction (Palleti et al. 2018),

  8. (h)

    Reliability achievement (Mu et al. 2021),

  9. (i)

    Transitioning from intermittent to continuous water supply (Burt et al. 2018; Mohammadi et al. 2020), and

  10. (j)

    Ensuring adequate quantity and quality of water supply (Rahmani et al. 2018; Brentan et al. 2021; Zeidan et al. 2021; Bianchotti et al. 2021).

Various methods have been proposed for establishing DMAs using two broader approaches: clustering and sectorization (Di Nardo et al. 2013b; Bui et al. 2020). These approaches can be configured permanently or adaptively to address network instabilities (Wright et al. 2014). The clustering approach defines DMA layouts by clustering adjacent nodes based on multiple design criteria:

  1. (a)

    Optimizing DMA number (Di Nardo et al. 2014; Liu and Han 2018; Bui et al. 2021),

  2. (b)

    Minimizing boundary pipes (Bianchotti et al. 2021),

  3. (c)

    Ensuring similar DMA sizes (Zhang et al. 2019; Vasilic et al. 2020), and

  4. (d)

    Balancing water demand and pressure consistency (Brentan et al. 2017; Bui et al. 2022).

However, many previous studies have employed graph theory-based algorithms for clustering (Tzatchkov et al. 2006; Di Nardo et al. 2014, 2018; Liu and Han 2018; Zhang et al. 2019; Vasilic et al. 2020; Shekofteh et al. 2020a, b; Bui et al. 2021; Mambretti et al. 2021). In the sectorization approach, strategic placement of flow meters and gate valves is vital for network decomposition and hydraulic modifications, aiming to optimize system performance, encompassing operational costs (Gomes et al. 2012), resilience (Di Nardo and Di Natale 2011), security (Grayman et al. 2009), and leakage (Laucelli et al. 2017). Multicriteria decision analysis assists in selecting the optimal DMA that meets multiple performance measures (Liu and Han 2018; Bui et al. 2021; Brentan et al. 2021).

Despite prior studies, WDNs face challenges impacting operational efficiency and reliable water supply, necessitating revised DMAs for system integrity and overall sustainability. These challenges include: (a) flow management, (b) leak control, (c) pressure optimization, (d) data insights, (e) infrastructure care, (f) regulatory compliance, (g) efficient design, (h) emergency plans, (i) community involvement, and (j) smart integration. In this context, dynamic DMA layouts offer practical solutions. Some examples from the literature include sequential convex programming for adjusting bidirectional flow and facilitating dynamic DMA aggregations (Wright et al. 2014, 2015), semi-supervised clustering for transforming multiscale network layouts into dynamic aggregation/disaggregation processes (Scarpa et al. 2016; Giudicianni et al. 2020a, b), and the integration of self-organization maps and community structure algorithms for permanent configurations that self-adapt to abnormalities (Bui et al. 2022).

Prior research on dynamic DMA layouts faced challenges adjusting boundary pipes' number and placement due to changing situations, like seasonal demands or evolving consumption patterns. These adjustments necessitated flow meter repositioning and adaptation for each scenario, which rendered them impractical in real-world applications due to financial implications. To address this, this study presents an innovative approach focusing on dynamic DMA configuration within WDNs, achieving the following key objectives: (1) developing a graph theory-based method for partitioning networks into desired DMAs with simplicity, efficiency, robustness, scalability, and visualization advantages; (2) optimizing DMA layouts by strategically installing flow meters and gate valves, using a multi-objective optimizer to minimize variable installation costs, enhancing monitoring and management; (3) considering critical hydraulic conditions to ensure adequate water supply, appropriate pressure, flow rates, and improved customer satisfaction; (4) reducing computational effort by integrating the multi-optimization algorithm with graph theory algorithms for diverse network sizes; and (5) determining an adaptable DMA layout that dynamically addresses critical situations without assumptions about various hydraulic scenarios. This approach maintains a constant number of boundary pipes, enabling seamless adjustments in response to unforeseen network changes, such as burst pipes or shifts in demand patterns, by simply substituting gate valves with flow meters, thereby supplying sufficient water to consumers without requiring a complete DMA layout overhaul.

2 Methodology

This paper introduces a simple yet comprehensive framework for partitioning WDNs into optimal DMAs. The framework consists of three sequential phases: (1) Characterizing a WDN as a simple graph and utilizing community detection algorithms in graph theory to cluster it into distinct sectors, i.e., DMAs; (2) Employing the hydraulic solver to identify WDN components and verify hydraulic criteria; and (3) Utilizing multi-objective optimization procedure to determine the boundary pipes between DMAs that can be closed by gate valves and those requiring flow meters to regulate inlet and outlet flows. Each of these phases is elaborated in the following sections.

2.1 Graph Characterization of WDNs

In graph theory, a graph is composed of two ordered pairs, V and E, where V represents vertices (or nodes) and E represents edges (or links) that indicate a relationship between two vertices. Complex networks have a community structure, with each community representing a group of nodes. The process of identifying these communities is called community detection. WDNs can be analyzed using graph theory, where vertices represent consumption nodes, tanks, and reservoirs, while edges represent pipes, pumps, and valves (Hajebi et al. 2015; Liu and Lansey 2020). Detecting communities in large graphs, such as WDNs with hundreds to thousands of nodes and pipes, can be a challenging task that requires computational algorithms to provide quick and accurate results. Clustering algorithms can be particularly useful for analyzing large and complex WDNs.

This paper employs the following three partitioning algorithms to divide WDNs into metered areas: Girvan-Newman, Fast Greedy, and Short Random Walks. Using different algorithms allows for comparing the resulting DMA layouts to identify the best suited for any given WDN. Partition algorithms have the notable advantage of being able to identify community structures in any WDN without requiring hydraulic criteria as an initial input. This enables rapid computational analysis and allows for incorporating hydraulic criteria in subsequent sections. The paper's novelty lies in decoupling DMA layouts from hydraulic criteria, making it adaptable for future changes based on the network's hydraulic requirements. This approach avoids the need for a complete DMA layout overhaul, with only adjustments to the number of flow meters and gate valves, as the number of boundary pipes remains constant.

2.2 Partitioning Algorithms

This paper utilizes various community detection algorithms. The Girvan-Newman algorithm, also known as the Edge Betweenness Community algorithm, is a widely used method for detecting community structures in a graph. This algorithm iteratively removes edges with the highest betweenness centrality, which measures the number of shortest paths passing through a given edge between pairs of nodes. As edges are removed, the graph is split into smaller components that correspond to communities until a stopping criterion is reached, such as identifying a certain number of communities or disconnection of the graph (Newman 2004).

The Fast Greedy algorithm is another promising approach that involves merging groups of vertices to create communities with higher modularity. Modularity measures the density of connections within a graph's community. The algorithm optimizes modularity in a greedy manner, where it selects links that improve the subnetwork's modularity and adds them iteratively. This process continues until the modularity stops increasing. The communities are obtained based on the connected components within the subnetwork (Fortunato 2010).

The last approach employed for partitioning a water network is the Short Random Walks algorithm (Leskovec et al. 2007). It detects community structures in graphs by simulating short random walks from each node and clustering nodes based on the similarity of their random walk paths. To achieve this, the algorithm calculates a transition probability matrix that reveals the likelihood of moving from one node to another in a single step. The matrix is then raised to a power to simulate random walks of a particular length, and the resulting matrix shows the probability of ending up at each node from any starting point after a given number of steps. By comparing the probability vectors for each pair of nodes, the algorithm identifies nodes that are likely to be visited together in short random walks and clusters them into communities.

All the mentioned algorithms have an inherent stopping condition to find the optimal community in the network. However, sometimes the partitioned network may not be suitable for DMAs in WDNs. This may lead to numerous small DMAs, requiring a higher number of flow meters and gate valves, or an imbalanced distribution of consumers among DMAs. To address this issue, this paper introduces an external stopping condition that interrupts the partitioning algorithms when they reach the desired DMA number. This enables the creation of DMA layouts in various numbers, allowing the comparison of these layouts to choose the best one based on the project requirements and budget constraints. The number of DMAs and the budget exhibit a direct correlation, as more DMAs offer improved network control and management but concurrently entail a higher cost due to the increased need for flow meters. This paper employs the EPANET toolkit in R programming language for hydraulic analysis (Arandia and Eck 2018) and utilizes the igraph package for network analysis (Csardi and Nepusz 2006). EPANET (Rossman 2000), a widely adopted water distribution system analysis software, was selected for its comprehensive toolkit and coding capabilities, aligning perfectly with our research objectives, thus enabling efficient analysis.

2.3 DMA Configuration

Following partitioning the WDN using community detection algorithms, the decomposed sections are established as initial DMAs. As hydraulic terms were absent in the network during the preceding step, the partitioned WDN is subsequently linked with EPANET to identify the location of assets in the water network, including reservoirs, tanks, pumps, and valves. Figure 1 illustrates a schematic of an arbitrarily partitioned WDN, forming 9 DMAs with two reservoirs, interconnected by 12 boundary pipes, potentially open or closed as needed.

Fig. 1
figure 1

A schematic view of DMAs in a WDN

Full size image

A partitioned network can form three types of DMAs. The first type consists of water sources supplying the entire network, such as DMA 1 and 7 in Fig. 1. The second type has no direct water source but is adjacent to DMAs that have direct connections to water sources. Within this type, certain DMAs, such as DMA 2 and 8, have only one pipe linked to their adjacent reservoir-connected DMAs, while others like DMA 5 and 6 have multiple connecting pipes. The final category, known as far DMAs, comprises DMA 3, 4, and 9, which do not belong to either of the previous two types.

After identifying the types of DMAs, the ones in type 2 with one linked pipe and type 3 (far DMAs) are vital for supplying water to their consumers. Therefore, the shortest path between them and the nearest water resource must be found, and the path must be kept open to provide water for consumers. These shortest paths must be opened under any circumstances, and flow meters must be installed on the pipes between DMAs to control inlet and outlet flow. For example, the shortest path for DMA 3 and DMA 4 to the nearest water source includes (P1, P2), and (P1, P4), respectively. However, P3, which is between two far DMAs, needs further investigation to decide whether it can be closed by a valve or requires a flow meter to be installed. In the cases where there are multiple pipes that interconnect two DMAs, such as P11 and P12 linking DMA 8 and 9, it is recommended to prioritize the closure of longer pipes over shorter ones, provided they fulfill the WDN hydraulic criteria. This decision is based on the higher probability of longer pipes experiencing leaks or breaks. Other pipes of the network between DMAs, such as P5, P6, P7, P8, and P9, along with pipes that needed further investigation, like P3, P11, and P12, are potential pipes that can be closed off by valves without any impact on the water supply. Thus, finding the optimal combination of their status (open or closed) is critical for final DMA implementation. Figure 2 depicts a visual representation of the proposed method.

Fig. 2
figure 2

Flowchart of the proposed method

Full size image

2.4 Hydraulic Criteria

Two crucial hydraulic terms must be considered when creating a practical DMA. The first is the minimum pressure at the junctions, which may drop if a gate valve is used to mark the boundary between DMAs by closing off one of the pipes. The second is the velocity constraint within the pipes, which corresponds to the volume of flow in the pipes. The closure of a pipe may lead to an increased flow velocity in other pipes responsible for supplying the network. Nevertheless, it is essential to ensure that this heightened velocity remains within allowable thresholds.

The study utilizes the Non-dominated Sorting Genetic Algorithm-II (NSGA-II; Deb et al. 2002) to address the multi-objective optimization problem of determining the optimal combination of pipes' status (open or closed) between DMAs. The decision variables are represented by the potential pipes for DMA configuration. To ensure that a network can provide adequate water supply and maintain sufficient pressure over time, the design of DMAs should be based on critical scenarios, with the maximum demand selected from demand patterns. The objective of the optimal DMA design is to minimize the budget for installing flow meters in open pipes while adhering to hydraulic constraints. This entails the minimization of the expected number of open pipes (NO) and the expected length of open pipes (LO), as outlined below:

$$Minimize\quad NO=\sum_{k=1}^{{N}_{pp}}{P}_{k}$$
(1)
$$Minimize\quad LO=\sum_{k=1}^{{N}_{pp}}L{P}_{k}\times {P}_{k}$$
(2)
$$\begin{aligned}Subject\, to\, {Pr}_{i}&\ge minimum\, allowable\, pressure\, \forall i\in {N}_{n}\\ {V}_{j}&\le maximum\, allowable\, velocity\, \forall j\in {N}_{p}\end{aligned}$$
(3)

where \({P}_{k}\) represent the expected values of the pipe status, which can either be 1 (open) or 0 (closed); \(L{P}_{k}\) is the length of the pipe in the kth potential pipe; \({N}_{pp}\) is the number of potential pipes; \({Pr}_{i}\) is the pressure of the ith node (up to \({N}_{n}=\) network nodes) and \({V}_{j}\) is the velocity of the jth pipe (up to \({N}_{p}=\) network pipes).

Following the determination of potential pipe status in each iteration, the EPANET solver verifies pressure and velocity constraints and stores them as potential solutions for NSGA-II. As previously mentioned, solutions that meet hydraulic constraints while utilizing the fewest open pipes (resulting in lower flow meter installation costs) are preferred.

It should be emphasized that the solution space for this problem grows exponentially as the network size increases, posing a challenge for real network applications. The search space (S) of the problem is typically of size \({\left|S\right|=2}^{{N}_{pp}}\), where \({N}_{pp}\) represents the number of potential pipes that can be either open or closed based on hydraulic constraints. This means that there are two possible states (open or closed) for each potential pipe in the network.

2.5 Multi-Objective Optimization

The NSGA-II is a multi-objective optimizer that employs the Pareto approach with elitism implementation. The optimization process begins with generating an initial population randomly, which is evaluated by all target functions. The population is then sorted based on the non-domination principle, assigning each chromosome a rank number equal to its non-domination level, and Pareto fronts are introduced for each level. The best solutions from non-dominant fronts are transferred to the mating pool to create the next generation, and diversity is maintained by utilizing a crowded comparison scheme. The crowded comparison operator is applied to the selection process to guide the algorithm to an optimal Pareto front at different stages. The hybrid mastery criterion of each chromosome on the Pareto front is characterized by its non-domination rank and crowding distance, ensuring optimal solutions are selected (Deb et al. 2002).

This study employs a specific encoding approach for decision variables in each individual—a potential solution to the optimization problem—by utilizing a generic gene associated with each potential pipe \({P}_{k}\). The gene takes a binary value of 1 if the pipe is open and 0 if closed. This encoding allows for scenarios where boundary pipes are either considered or not considered to transport water between DMAs. The number of open pipes in a scenario dictates the allocated budget for flow meter installation, while the length of the open pipes plays a role in determining the optimal DMA layout.

The NSGA-II was implemented using rmoo (Benitez and Pinto-Roa 2022), an R-based multi-objective optimization framework, with a population size of 400, a crossover probability of 0.9, a mutation probability of 0.2, and a maximum of 2000 generations, which were determined through sensitivity analysis. Additionally, for visualization purposes, two Python packages, VisWaterNet (Thomas et al. 2023) and WNTR (Klise et al. 2017), were utilized.

3 Results and Discussion

In this section, we assess our proposed method's efficacy by employing various benchmark models of WDNs. The first benchmark model, termed BIN WDN, comprises 443 nodes, 454 pipes, and four reservoirs (Reca and Martínez 2006). A uniform consumption of 5.55 liters per second (LPS) is assumed across all nodes within the network. The consumer nodes are expected to maintain a minimum allowable pressure head of 14 m, while the pipes are not allowed to exceed a maximum velocity of 3 m/s. Figure 3 illustrates the partitioning of WDN into 6 DMAs using the proposed method based on the three community detection algorithms: Girvan-Newman, Fast Greedy, and Short Random Walks. The number of potential pipes between DMAs utilizing these approaches is 7, 9, and 7, respectively. Additionally, Fig. 3 graphically presents the distribution of flow meters and gate valves in each DMA layout.

Fig. 3
figure 3

Arrangement of DMAs and boundary pipes' status for BIN model using: (a) Girvan-Newman algorithm, (b) Fast Greedy algorithm, and (c) Short Random Walks algorithm

Full size image

Based on the hydraulic criteria, four out of the seven pipes interconnecting the DMAs resulted from the Girvan-Newman method need to remain open to maintain acceptable levels of minimum pressure and maximum velocity and to ensure sufficient water supply. Conversely, the remaining three pipes can be closed using gate valves. As an example, DMA number 6 is connected to three pipes, but only one of them can be closed while the other two must remain open to satisfy the hydraulic criteria.

The DMA layouts obtained from alternative partitioning algorithms exhibit suboptimal outcomes for establishing multiple DMAs. Specifically, the Fast Greedy algorithm generates nine boundary pipes between DMAs, of which six must remain open, necessitating the use of two additional flow meters to regulate water flow compared to the Girvan-Newman layout. Similarly, the Short Random Walks algorithm entails seven pipes linking the DMAs, with one additional open pipe required to meet hydraulic criteria compared to the Girvan-Newman algorithm. Furthermore, this layout suffers from imbalanced DMA sizes, with one DMA being significantly larger (DMA 1) while another being relatively small (DMA 6), as shown in Fig. 3(c). This imbalance poses challenges in managing large DMAs, while a very small DMA requires flow meters to control a small part of the network, which is not cost-effective. Rigorous tests conducted on various benchmark WDNs, featuring varying numbers of DMAs, demonstrate that the Girvan-Newman algorithm yields the optimal DMA layout with the minimal number of potential pipes between DMAs.

Clustering a WDN into a random number of DMAs is not a suitable approach but partitioning it with different DMA layouts enables a comparison of each layout based on the allocated budget. Table 1 shows the number of boundary pipes between DMAs in the BIN WDN model, obtained through the Girvan-Newman algorithm, with varying numbers of DMAs. The number of consumers is more balanced when the network is divided into 7 DMAs, but more flow meters and gate valves are required. This table is useful for selecting the best scenario within the allocated budget. Any unforeseeable hydraulic changes in the future can be accommodated by re-running the NSGA-II section to redefine the status of the boundary pipes. This maintains unchanged DMA layouts by keeping the number of boundary pipes constant, although some gate valves may need be replaced with flow meters.

Table 1 Attributes of each partitioned DMA in the BIN model
Full size table

To assess the efficacy of our proposed method across a range of WDNs with varying assets and circumstances, we applied it to five additional benchmark networks and partitioned them into different numbers of DMAs using only the Girvan-Newman algorithm which performed best in the preliminary investigation. The characteristics of these models are as follows:

  1. 1.

    Modified EXNET model (Farmani et al. 2004): including 1891 nodes, 2465 pipes, 2 reservoirs, 1 PRV valve, and 1 TCV valve.

  2. 2.

    Modified Wolf-Cordera Ranch model (Lippai 2005): including 1782 nodes, 1995 pipes, 4 reservoirs, and 6 pumps.

  3. 3.

    C-Town model (Ostfeld et al. 2012): including 388 nodes, 429 pipes, 1 reservoir, 7 tanks, 11 pumps, 3 PRV valves, and 1 FCV valve.

  4. 4.

    D-Town model (Marchi et al. 2014): including 399 nodes, 443 pipes, 1 reservoir, 7 tanks, 11 pumps, 4 PRV valves, and 1 TCV valve.

  5. 5.

    Modena Network (MOD) model (Bragalli et al. 2012): including 268 demand nodes, 317 pipes, and 4 reservoirs.

Figure 4 depicts the DMA layout for each model, which shows the division of WDNs into DMAs using boundary pipes, as well as the location of flow meters and gate valves. Table 2 provides a comprehensive evaluation of hydraulic criteria and partitioning results for each network with the selected number of DMAs. It includes essential hydraulic thresholds, such as minimum allowable pressure head, maximum pipe velocity, and the number of boundary pipes eligible for closure using gate valves or requiring flow meters for inlet and outlet flow regulation.

Fig. 4
figure 4

The DMA layout for five benchmark networks: (a) EXNET with 10 DMAs, (b) Wolf-Cordera Ranch with 8 DMAs, (c) C-Town with 5 DMAs, (d) D-Town with 5 DMAs, and (e) Modena network with 4 DMAs

Full size image
Table 2 Comprehensive hydraulic criteria and partitioning results
Full size table

The modified EXNET model comprises 10 DMAs with 39 boundary pipes, out of which 25 must remain open according to hydraulic criteria. Conversely, the Modified Wolf-Cordera Ranch model consists of eight DMAs with 17 boundary pipes, six of which are eligible for closure. As C-Town and D-Town models have already been optimized with a 5-layout DMA network, it is not possible to close any more pipes to implement a new layout. However, to analyze these networks with our proposed method, a single-period analysis was conducted based on the maximum available demand pattern. Based on the hydraulic criteria outlined in Table 2, two and three boundary pipes can be shut off in C-Town and D-Town networks, respectively. The Modena Network, with 4 DMAs comprising 15 pipes, necessitates flow meters for seven pipes and allows eight to be closed safely. Compared to other networks, Modena has fewer junctions and pipes, but a significantly higher number of pipes linking DMAs, rendering it unsuitable for DMA implementation due to its structure and layout, which requires numerous flow meters to operate a relatively smaller network.

Partitioning DMAs in large and complex WDNs without community detection algorithms and multi-objective optimization poses a significant challenge, necessitating manual determination of DMA boundaries to create isolated areas. A crucial aspect involves identifying boundary pipes that can be closed without disrupting water supply to consumers, thereby reducing flow meter costs. This method presented in this paper enables rapid analysis of diverse WDNs as graphs and offers the advantage of creating various sustainable DMA layouts, particularly useful when project costs are constrained.

4 Conclusion

This paper presents a novel graph-based approach using multi-objective optimization to determine the optimal number of DMAs in WDNs. The proposed method ensures adequate water supply, appropriate pressure, and flow rates, thereby enhancing customer satisfaction and network operations and management. DMAs are isolated using gate valves and flow meters to regulate water inlet and outlet, ensuring compliance with critical hydraulic criteria throughout the network. The NSGA-II algorithm is then employed to find the optimal configuration of boundary pipes (closed or open) connected to the DMAs. Additionally, the proposed method requires only modifications to the number of flow meters and gate valves, rather than the DMA layout, to accommodate changes in network requirements. Evaluation on six complex benchmark models demonstrates the approach's effectiveness in partitioning vast and intricate WDNs into DMA layouts, providing a practical and efficient solution.