Topological and hydraulic metrics-based search space reduction for optimal re-sizing of water distribution networks

The increase of population in urban areas causes the rise of water demand in water distribution networks (WDNs) while the ageing of a pipeline is responsible for the reduction of its hydraulic capacity. The joint effects of these factors progressively increase the risk of insufficient water supply and motivate water companies to increase WDN performance. Since the complete re-building of the system is economically and technically infeasible, effective plans should select only a subset of pipes for rehabilitation, accounting for economic and technical constraints. The rehabilitation commonly focuses on replacement of aged pipes, pipe re-sizing and pipe duplications. As there are a number of discrete sizes to select for each pipe to rehabilitate, the pipe re-sizing for WDN is a challenging task in water engineering. The task becomes more difficult when considering the need to identify only the most critical pipes from the enormous number of combinations of interacting pipes. The search for optimal solutions (i.e., set of pipes to be re-sized and the diameters to use) can be formulated as an optimization problem aimed at minimizing the cost of intervention while providing adequate pressure at all demand nodes.

The most widely used current methods for solving the optimization problem in technical literature are Evolutionary Algorithms (EAs) (e.g., Lansey & Mays 1989; Kim & Mays 1994; Halhal et al. 1997; Savic & Walters 1997; Farmani et al. 2005; Giustolisi et al. 2006; Jin et al. 2008; Roshani & Filion 2015). The key advantage of using optimization models is their ability to consider many decision variables and automatically search potential combinations of re-sizing solutions (Savic & Banyard 2011).

Although EAs are designed to solve classically NP-Hard problems quite efficiently, they are not computationally efficient especially when applied to real-world large WDNs. Indeed, finding optimal Pareto front for a WDN with many potential pipes to be re-sized is a major challenge due to the large size of the search space (Kadu et al. 2008). For example, the Exnet WDN (Farmani et al. 2005), which is used as a case study in this paper, has 2,465 pipes. If 11 diameter sizes are available as well as a ‘do nothing’ option for pipe replacement, the search space considering all possible pipe size combinations will be as large as 12²⁴⁶⁵ discrete combinations. Such a huge search space makes many solutions equally good in terms of objective functions, although very different in terms of selected pipes and diameters. Therefore, improving the computational efficiency and quality of solutions, even using EAs, for such optimization problems is needed (Maier et al. 2014).

An emerging way to improve EAs in such kinds of problems is to reduce the search space as much as possible. Mala-Jetmarova et al. (2018) classified techniques for search space reduction into algorithm-based and network-based methods. The algorithm-based methods focus on refining the process of searching optimal solutions within the search space, e.g., better strategy of updating some parameters (e.g., the penalty factor) that guides the optimization process. The network-based methods use information resulting from network analysis to directly reduce the size of the search space. Dandy & Engelhardt (2001) placed an upper bound on the number of pipes considered for replacement and/or re-sizing, thus reducing the search space. Kadu et al. (2008) used the critical path method (Bhave 1978) to simplify looped WDNs into a branched system and set lower and upper bounds on the number of candidate sizes for a pipe. However, this may result in a suboptimal solution if candidate pipe sizes are not selected properly. Vairavamoorthy & Ali (2005) used a pipe index vector to measure the relative importance of pipes in a WDN in terms of their impact on the hydraulic performance of the network, and thus excluding regions of the search space where impractical and infeasible solutions exist. Diao et al. (2015) developed a twin hierarchical decomposition technique that simplified a whole complex WDN to that of smaller subsystems formed by either backbone mains or community feeders. The method enables optimal rehabilitation of all communities independently, without physical division of the WDN. Muhammed et al. (2017) proposed a clustering-based method for selection of a subset of pipes within the clusters with the lowest pressure and the feeding pipelines between these clusters and the source(s).

This paper proposes a search space reduction method to identify a subset of critical pipes for optimal pipe re-sizing of a WDN based on topological and hydraulic metrics. Topological metrics are based on latest advancements in application of complex network theory (CNT) to WDN analysis (Giustolisi et al. 2019). The purpose of the proposed methodology is to provide suboptimal solutions almost as good as full search solutions (considering all pipes as candidates for sizing) but much more efficiently. The reduced size of the search space also minimizes the risk of selecting multiple solutions, which are equally good in terms of objective functions in different runs of the EA that would put decision-makers in a quandary. From such a perspective, the methodology also improves the technical effectiveness in using EAs for supporting decisions. Specifically, the topological metrics that are used are based on the WDN-tailored edge-betweenness and the hydraulic metrics are based on the unit head loss of pipes and the flow rate. Moreover, the proposed strategy implicitly drives the search towards solutions that select contiguous pipes for re-sizing. This is of practical relevance to planning works since it reduces the number of construction sites and the relevant indirect socio-economic costs.

Therefore, this study aims at introducing a novel strategy to reduce the search space, enabling faster optimization runs, and allowing the comparison of re-sizing solutions coming from using different metrics. Indeed, the most effective metric to inform such a process depends on hydraulic and topological features of the specific WDN.

The next section of the paper summarizes the main formulation of the pipe re-sizing problem as an optimization problem, and the methodology of using metrics (e.g., the WDN-tailored edge-betweenness indicators) for search space reduction. The following case study section describes the application of the proposed approach to optimal pipe re-sizing of the Exnet WDN (Centre for Water Systems 2004; Farmani et al. 2005). Discussion and conclusions summarize rationales of the proposed procedures, findings and perspectives for future applications.

The optimal WDN re-sizing considered in this study aims to meet pressure requirements (i.e., no pressure deficiencies) by replacing some pipes at minimal capital cost. It is formulated as a two-objective optimization model as shown in Equations (1)–(5), which takes the minimization of the capital cost, Equation (1) and the number of demand nodes with pressure deficits into account, Equations (2) and (3). Equations (4) and (5) represent mass balance and energy conservation in the WDN (implicit constraints), which are automatically fulfilled by simulating the WDN hydraulic model for each candidate solution. It is worth noting that including the minimization of number of demand nodes with pressure deficits as an objective function, rather than a constraint, allows for a more effective exploration of the search space, avoiding losing promising solutions during the search.

As mentioned before, assuming n_D decision alternatives, including the do-nothing option, the complete search space of the problem includes n_D^np candidate solutions, which means that even in a small WDN with np=100 pipes and 10 commercial diameters, i.e., n_D=11 including the ‘do nothing’ option, the search space encompasses 1.3781×10¹⁰⁴ alternative solutions.

Giustolisi et al. (2019) demonstrated that all such modifications enable an effective analysis of the key features of the physical domain of the WDN (i.e., the network), which captures the emerging hydraulic behaviours of the system, even before running the hydraulic simulation. Indeed, domain analysis through WDN-tailored CNT metrics helps to understand in advance the role of pipes in determining the system hydraulics independently of the specific set of boundary conditions (e.g., demands, water level in tanks, etc.). Nonetheless, the same authors discussed the usage of different edge weights to pipes for different purposes of analysis.

The present work exploits the idea of using the WDN-tailored edge-betweenness to inform the identification of a subset of pipes that are more effective than others for the re-sizing. It consists of the two steps that need to be performed before running the optimization routine (e.g., using EAs):

• (1)

  WDN-tailored edge-betweenness of every pipe element is computed by accounting for weights representing features of the pipes.

• (2)

  A subset of pipes with the highest values of the WDN-tailored edge-betweenness is selected as a candidate for re-sizing.

Since this strategy aims at supporting pipe re-sizing, three kinds of weights are analysed in the present work:

• (1)

  ‘connectivity’: all pipes are unweighted in order to account for information on connectivity only, meaning that the information on topological connectivity described by the edge-betweenness in Equation (6) identifies the most relevant pipes.

• (2)

  ‘resistance’: each pipe is assigned a weight equal to L_k·D_k⁻⁵, which is proportional to the hydraulic resistance per unit flow through the pipe, according to Darcy–Weisbach equation, meaning that the pipes with higher hydraulic resistance are the most effective for re-sizing.

• (3)

  ‘length’: each pipe is assigned a weight equal to L_k, meaning that longer pipes affect more WDN hydraulics and background leakages.

It is worth noting that the weight representing ‘resistance’ is formulated to use pipe features that are commonly available (i.e., pipe length L_k and diameter D_k) and do not depend on uncertain internal roughness conditions and hydraulic variables (i.e., flow regime).

For the sake of discussion in this paper, the WDN-tailored edge-betweenness in each of the previous weighting strategies is computed accounting (‘direct’) or not accounting (‘indirect’) for the information on flow direction (i.e., flow from reservoirs, unidirectional devices). This means that six possible rankings of pipes are obtained by using various WDN-tailored edge-betweenness metrics: ‘connectivity-direct’; ‘connectivity-indirect’; ‘resistance-direct’; ‘resistance-indirect’; ‘length-direct’; and ‘length-indirect’.

The information on WDN hydraulics is already available from the analysis of the system as is, possibly with pressure deficit at some nodes. Such observation motivated the idea to inform the reduction of the search space by ranking pipes according to the two main hydraulic features, retrieved from hydraulic simulation, as described below:

• (1)

  ‘Pipe flow’: it comes from the assumption that pipes carrying the largest flow are the main ‘arteries’ of the system, which drive the main WDN hydraulic behaviour and are supposed to be the most effective for re-sizing.

• (2)

  ‘Unit head loss’: the pipes with the highest head losses per unit length can be seen as responsible for insufficient pressure at water demand nodes; therefore, their replacement is potentially effective to solve local pressure deficit conditions.

Also, in the present work, a fixed percentage of pipes (30% of pipes with the highest hydraulic metrics) is identified as a subset of candidate pipes for re-sizing, although such selection can be performed using different criteria.

To facilitate the search space reduction (i.e., select a subset of pipes as candidates for re-sizing), the WDN is first divided into clusters by using the modularity-based clustering. Details of the method are available in Diao et al. (2012, 2014). Pipes in all clusters are ranked in descending order of the metric used (e.g., pipe flow). Next, a percentage of pipes (e.g., 30%) with the highest values of the metric are selected as candidate pipes (this work assumes a fixed percentage of pipes over all metrics although this can be performed in various ways, e.g., based on total maximum length). In the same way, the selection is made for pipes connecting clusters. From an optimization perspective, this aims to reduce the size of the search space from n_D^p to n_D^(0.3×p); assuming n_D=11 and n_p=100, the search space reduces to about 1.74×10³¹, about 73 orders of magnitude smaller that the full search space. Therefore, the complete set of candidate pipes includes both selected inner-cluster and inter-cluster pipes.

Note that the decision on the percentage of the selected pipes depends on the WDN and might follow various approaches. Using a large percentage will make the constraints easier to satisfy but it also means a larger search space and vice versa. The methodology used herein to identify the percentage is defined using the following procedure: (1) the mean of the values of each metric are calculated; (2) the percentage of pipes that have their metric values higher than or equal to the mean is calculated for each metric; (3) the largest value of these percentages among all the metrics is identified (e.g., 24%); (4) a value slightly higher than the largest percentage identified in step 3 is used (e.g., 30%) for every metric-informed optimization to make the analyses comparable.

The Exnet WDN model was set up by the Centre for Water Systems (CWS) at the University of Exeter as a realistic and challenging rehabilitation problem (Farmani et al. 2005). The use of the Exnet WDN enables us to focus on the proposed methodology to reduce the search space, while ignoring some other aspects related to real systems such as background leakages and pressure-driven demands.

The network serves a population of approximately 400,000 and was supposed to be reinforced to meet the projected demand in 2020. It consists of a great number of pipes with a wide head loss range. The layout of Exnet is shown in Figure 1, with 16 highlighted clusters obtained by using the modularity method proposed in the section above. It contains 2,465 pipes, 5 valves, 1,891 junction nodes and 7 water sources. Two major reservoirs (node 3001 and 3002) supply water to the system at fixed heads of 58.4 and 62.4 m, respectively. The system is also fed by its neighbouring systems via nodes 3003 to 3007 at fixed rates. Three non-return valves (also known as check valves) are connected to node 3001 and 3002 to control the flow direction into and out of the system. One pressure reducing valve is in the downstream of node 3004 to maintain the downstream pressure below 58.4 m. One throttle control valve is also in the link downstream of node 3004 to control the flow and pressure of the system. The minimum pressure requirement for demand nodes is set to 15 m according to Muhammed et al. (2017).

The re-sizing options for Exnet are restricted to 11 discrete pipe sizes available for replacement (Table 1) and one extra option of ‘do nothing’. Therefore, from the mathematical perspective, the complete search space is equal to 12²⁴⁶⁵ discrete combinations, which makes it an extremely large and complex combinatorial optimization problem. Note that a few changes were made in the original EPANET2 input file of Exnet. All the changes are listed in Table 2 and the new input file for this case study is provided in the Supplementary material. The changes were made to neglect those devices that would bias the hydraulic functioning of the re-sized WDN. In addition, replacing the inflows (i.e., negative water demands at five junctions) with reservoirs at the same nodes aims at keeping the direction of inflow pipes consistent with the original network feeding scheme (Table 3).

The EA adopted in this work is the NSGAII (Deb et al. 2002) algorithm, although any other optimization method can be used without influencing the effectiveness of the proposed strategy. For optimal re-sizing, the NSGAII was independently run five times to alleviate the impact of randomness on the solutions obtained. Each re-sizing solution was evaluated by invoking the EPANET2 solver (Rossman 2000), which implements classical demand-driven analysis. On the one hand, this choice was due to the lack of information on water losses, which prevented us from calibrating an advanced pressure-driven model (see the last equation of Equation (3)). At the same time, using a classical model keeps the main focus of this work on the proposed strategy for reducing the search space, avoiding possible bias due to pressure-driven formulation of demands and leakages.

The total number of function evaluations (NFEs) was set to 10 million for all the optimization runs, in order to make results independent of the number of iterations. The population size was fixed at 50, with 200,000 generations evolving during the optimization process. For each pipes selection strategy, the 30% of pipes with the highest values of each metric was selected as candidate pipes. This is because the percentage of pipes with their metric values higher than or equal to the mean is between 20 and 25%. The optimization was repeated five times; for each time and each pipes selection strategy, only the optimal solutions with NNPD=0 are considered as feasible. The average cost of the solutions among the five runs is selected for numerical comparison (Figure 2), while the minimum cost solution is selected for topological evaluation (Figure 3).

Figure 2 compares the average cost (i.e., computed in the five-optimization runs as above-mentioned) of each re-sizing solution for the Exnet WDN based on the eight different strategies described, while Figure 3 details each of the minimum cost solution's topology showing the candidate pipes for re-sizing in red.

In the far right of Figure 2, in the dark-blue bar, the mean cost (20.9 M€) of re-sizing plans using full search is displayed. This kind of strategy has highly variable solution costs, ranging from 7.4 to 32.5 M€, obtained over multiple runs of the full space search. This high variability is probably due to the dependence on the initial conditions of the NSGAII optimizer (Deb et al. 2002) and on the size of the search space, so it can be said that as the size and the complexity of a WDN increases, the variability can get wider.

Figure 3(a) shows the topology of the cheapest solution (7.4 M€) obtained from the full space search. It can be noted that the EA selected pipes are quite spread over the entire WDN, with many small pipes separated from the others. This observation means that, although such a solution would solve pressure deficit conditions, it requires several construction sites to carry on works, which is not effective from a practical standpoint.

The ‘pipe flow’ case (Figure 3(b)) shows many pipes on the same water path that are connected with each other for re-sizing, thus providing a plan to be more easily implemented in practice. However, the pipes selected are those with the highest flow rate; therefore, those pipes have larger diameters and replacing them is expected to be more expensive. Results are consistent with the fact that the solution cost is about 9.6 M€. As for the topological metrics informed solutions (Figure 3(c) and 3(d)), it can be noted that the ‘direct’ cases are more expensive (10.2 M€) than their ‘indirect’ counterparts (8.1 M€). In fact, ‘direct’ metrics account for directional devices and for known pipe flow directions (i.e., from reservoirs to the network), allowing shortest paths in one direction only. This, in turn, results in a reduced value of the centrality metrics, i.e., the edge betweenness in the ‘direct’ case, it only applies to the pipes where only one direction is allowed. Therefore, some pipes in the highest 30% of edge betweenness that are in the ‘indirect’ case are not in the ‘direct’ case and cannot be selected as candidate for re-sizing. Such pipes are usually not that long (e.g., pipes close to reservoirs); this means that their re-sizing potentially allows considerable improvement in pressure with lower cost.

It is worth noting that the selection of pipes based on the highest edge betweenness, without using any weights, results in the cheapest solution among all search space reduction strategies used in this study. This is likely due to the circumstance that, in the case of the Exnet WDN, the connectivity information is quite useful to determine the most effective water paths. As such, the topological informed search drives the EA to explore solutions into a subset of pipes whose re-sizing has an effective impact on WDN hydraulic behaviour.

The cases of ‘resistance-indirect’ and ‘length-direct’ are shown in Figure 3(f) and 3(g), which are those with the lowest dispersed pipes in the WDN, and many contiguous pipes (i.e., pipes on the same path). Many pipes also coincide with those selected in the ‘pipe flow’ case, demonstrating that a close relationship exists between WDN topology domain and hydraulics (Giustolisi et al. 2019).

The outcome that using the tailored edge betweenness with the weights of ‘length’ provides better results than those with ‘resistance’ can be explained considering that longer pipes usually carry water from different regions of a WDN, thus having more impact on WDN hydraulic behaviour (i.e., sufficient pressure at nodes). Vice versa, the hydraulic resistance increases as diameter decreases, and smaller diameters are usually in the looped (distribution) part of the WDN, which have only local impact on pressure; therefore, getting sufficient pressure at all nodes may require the replacement of a larger number of pipes providing more expensive solutions.

Such observation hints that the results of various optimization runs based on different metrics to reduce the search space may provide a ranking of pipes that are the most effective to solve pressure deficit conditions due to their topological position and hydraulic asset features. Such pipes can be included as a priori in further optimization runs.

This work proposes a strategy to reduce the search space for the optimal re-sizing problem, informed by hydraulic and topological metrics. The latter ones come from the latest advancements in centrality metrics tailored for WDN from CNT. Specifically, the pipe re-sizing optimization uses a subset of pipes selected based on the highest values of metrics entailing topological and hydraulic features rather than all pipes. The strategy described above was proposed as a support to the planning of the re-sizing of a real WDN in the presence of insufficiencies of the user supply service.

In particular, the analyses of the different metrics aimed at evaluating their effectiveness within the proposed strategy, with the final purpose of making its application flexible with respect to the specificities of existing real networks. The goodness of the previously described results allows us to foresee its potential application in the ‘real life’ of a municipality which, based on the information and knowledge available, will be able to adapt the search to the characteristics of the considered WDN.

The procedure was tested on a large WDN, a known benchmark in the literature, and the results show that the strategy is performing well, providing cheaper solutions if compared with the average cost from multiple runs of the same optimization algorithm on the complete search space (i.e., taking all pipes as candidate for re-sizing). It is notable that most of the re-sizing plans obtained from applying the search space reduction strategy report contiguous pipes. This is a positive aspect for an effective support to planning interventions on the WDN, because by reducing the number of construction sites if compared with the solutions found in the full search case, it reduces direct and indirect intervention costs (e.g., nuisance to traffic and to the city life in general). It must remark that having contiguous pipes in the reduced search space is a direct consequence of using topologically informed metrics, which is likely to return similar (high) values of edge betweenness in pipes close to each other.

Furthermore, the case study shows that not accounting for flow directions (i.e., ‘indirect’ case) in edge betweenness calculation performs better than other metrics. This is because the ‘direct’ metrics account for the shortest paths in one direction only, and thus ignored some pipes playing an important role in topological connectivity regardless of flow directions.

The idea of using WDN-tailored metrics from CNT that is presented in this work opens new directions for future research. Regarding optimization strategies, various topological metrics can be used in sequence during the same optimization run, e.g., progressively reducing the search space, or in conjunction, i.e., to select a subset of pipes with the highest values of different metrics. Future studies could also explore other metrics, not reported here, for reducing the search space, combining information on network topology and relevance of nodes (e.g., Giustolisi et al. 2020). Finally, the same approach could be tested on multiobjective optimization search, embedding additional objective functions related to different technical aspects (i.e., pipe deterioration, pipe material information, number of private connections, etc.).

There are two main limitations in the results presented. First, the simplified assumption on hydraulic model (i.e., EPANET2) used in the case study does not account for pressure-dependent leakages and users' demands. Although this makes the WDN re-sizing problem close to the classical WDN design problem, this assumption allows keeping the focus on the impact of the proposed strategy on optimization. Nonetheless, future works can explore the effectiveness of the approach proposed here on real complex WDNs employing an advanced hydraulic modelling. Secondly, for the pipes selection strategy, the decision on the percentage of the selected pipes depends on the analysed WDN and some techniques can be investigated to automatically decide the optimal percentage regardless of the metric applied for pipes selection.

All relevant data are available from https://www.researchgate.net/publication/359109267_exnet_EPS_mod.