{'fraction_non_alphanumeric': 0.026625206491108735, 'fraction_numerical': 0.006947818482168885, 'mean_word_length': 4.807844243792325, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal design of district metered areas in water distribution networks

The paper presents a multi-objective approach for the automatic partitioning of a water distribution network into District Metering Areas (DMAs). In the proposed methodology, both technical and economic issues are considered, including reduction of water leakages due to pressure management and energy production achievable through the use of turbines. The optimization approach is based on a clear explanation of the objective functions, whose structures are defined with the aim of providing full control to the decision-maker. Concepts from graph theory and cluster analysis methods are combined in a three-step algorithm, which can be easily implemented for software use. © 2013 The Authors. Published by Elsevier Ltd. Selection and peer-review under responsibility of the CCWI2013 Committee.


Introduction
Pressure management is commonly used for the reduction of leakages in water distribution networks (WDNs). The impact on both the amount of losses and the occurrence of new damages has been strongly highlighted in the past (Lambert 2002).
Most of the literature has been focused on the issue of optimal localization and setting of Pressure Reducing Valves (PRVs). In other works, the replacement PRVs with turbines or Pumps As Turbines (PATs) for energy production has been addressed. Different models have been proposed, based on classic optimization methodologies or on meta-heuristic approaches (Vairavamoorthy and Lumbers 1998;Araujo et al. 2006;Giugni et al. 2009;Liberatore and Sechi 2009;Fontana et al. 2012).
Among the available approaches for pressure management, the use of District Metered Areas (DMAs) also allows for a more accurate localization of the leakages in the water distribution network, which is achieved by monitoring the input and the output discharges for each district. Nowadays, this approach is widely used in practice, but its application is still largely entrusted to the experience of technicians.
The optimal design of DMAs as part of a Decision Support System (DSS) for reducing the water losses has been addressed only recently in the literature. Some authors have proposed hybrid approaches for the automatic partitioning of a water distribution network, based on both meta-heuristic algorithms and on applications from the graph theory (Di Nardo and Di Natale 2011; Alvisi and Franchini 2012). The proposed models mainly focus on the preservation of the hydraulic reliability of the network, while less control is allowed on the costs of the provided solutions. Sempewo et al. (2009) developed a spatial analysis zoning approach based on the METIS graph partitioning tool (Karypis and Kumar 1995). The proposed technique follows the analogy with the distributed computing methodology of equally distributing workloads among processors. However, as stated by the same authors, although the method results effective in the demarcation of contiguous districts, the quality of the provided solution degrades when considering multi-objective partitioning, and uncertainties are produced when increasing the number of DMAs. Herrera et al. (2012) proposed a semi-supervised method named multi-agent adaptive boost clustering. This complex technique considers both the WDN features (e.g. node elevations and demands) and the economic issues (edge cut = number of pipes to be intercepted) for the partitioning of the network. Nevertheless, the procedure is only applied to cases in which the number of DMAs is lower than the number of supply nodes.
More recently, Diao et al. (2013) have introduced an approach for automatic creation of DMAs based on the hierarchical community structure of the WDN. In this study, the selection of the feeding lines for the DMAs is made through an iterative selection method based on a sensitivity analysis. The methodology was tested on a very large network with reasonable computing times, but the results showed high sensitivity towards the assignment of the input parameters.
A comprehensive description of the possible objective functions for the problem can be found in Gomes et al. (2012). The two-step approach proposed by the authors consists of a preliminary partitioning of the WDN into suitable DMAs through the application of the design criteria and graph theory concepts, i.e. the Floyd-Warshall Algorithm (FWA). Next, Simulated Annealing (SA) is used for the localization of entry points and of boundary valves, but also for planning the reinforcement/replacement of pipes in the network. Although the results have resulted satisfactory, the global optimality of the solution is not ensured by the SA.
Hence, despite the newest contributions, further developments seem required about this topic. Therefore, in the present paper a multi-objective methodological approach for the automatic partitioning of a WDN is presented, in which both technical and economic issues are taken into account, and user control is allowed on the results through dynamic blending of the objective functions.

Objective functions
The proposed methodology is based on a detailed explanation of the objective functions for the optimization problem. In order to provide the best solutions under a multi-objective approach, different criteria are taken into account, mainly related to the costs of the intervention scenarios.
However, following the classical approach for the design of the DMAs, the homogenization of the supplied water demand in each district is firstly considered. While not being strictly required for the optimal partitioning of the WDN, this goal is usually pursued by dividing the network in districts with equal number of served customers.
In this case, the sum of the water demand supplied by the pipes belonging to each DMA is computed (see section 3.1).
Also the minimization of the difference between the required heads at nodes within the DMAs is taken into account. This criterion allows to establish a unique target pressure value in each DMA, and consequently, to achieve an efficient pressure regulation also in WDNs with strong variations in ground elevation or in height of the buildings within the same area. To this aim, the sum of the elevation difference covered by the pipes within the same DMAs must be minimized.
The two objectives described so far are considered in the first stage of the optimization algorithm, as described in section 3.1.
As regards the economic evaluation of the provided solutions, different costs and benefits are taken into account. The costs of the partitioning of the network are basically due to the shut-off valves necessary for setting of district boundaries and to the required equipment for discharge measurement and pressure regulation at entry point of each DMA. These costs are obviously linked to each other: the larger the number of intercepted pipes for the delimitation of the DMAs, the smaller the number of accesses to the districts.
Therefore, in the proposed methodology, an objective function is explicitly defined only for the former, while the latter is properly taken into account in the second stage of the optimization algorithm (see section 3). Considering the total number of pipes intercepted with shut-off valves (N GV ) and the number of accesses to the DMAs (N CV ), the objective function can be expressed as follows: Where r is an annual discounting rate, while C GV and C CV are the unit costs of the shut-off valves and of the monitoring/regulating devices, respectively. Among the potential benefits achievable through the design of DMAs, two main aspects are considered, namely the reduction of water leakages due to a more efficient control of the pressure in the network and the economic return deriving from the possible use of turbines for the production of energy.
Following the classical approach from literature (Sterling and Bargiela 1995;Vairavamoorthy and Lumbers 1998;Giugni et al. 2009;Fontana et al. 2012), the reduction of leakages is usually sought through the minimization of the sum of squared differences between actual (P i ) and target (P t,i ) pressures at every node of the network: where N n is the number of demand nodes. In order to make comparisons between the objectives and to combine all of them in a single cost function, equation (2) must be rearranged according to the results of studies on leakagepressure relationship De Paola and Giugni 2012), which is usually structured as follows: Then, assuming a daily time pattern for the water demand (with duration T), the objective function for the reduction of annual costs due to leakages can be expressed as in equation (4), in which C WL is the unit cost of lost water: Obviously, in case of pressure regulation performed through the use of PRVs or turbines, the evaluation of this term is subjected to the definition of the optimal settings for these devices.
Moreover, as stated before, the use of turbines involves further benefits consisting of the earnings from energy production, that can be accounted as negative costs. The corresponding cost function is built in the same way of the previous (4): Where N T is the number of turbines, C EN the current cost of produced energy, and Q i , ΔH i , η i are the discharge, the available head jump and the efficiency of the single turbine, respectively. In previous works, the hydraulic reliability of the network has also been taken into account. The closure of several links for setting of the DMAs boundaries may cause an excessive reduction of the water system redundancy, which can result particularly vulnerable against unintended disconnections caused by pipe failures or in case of emergency conditions (e.g. fire fighting).
The conservation of the hydraulic reliability, which is obviously dual to the goal of pressure regulation for the reduction of water losses, could be achieved by minimizing the resilience deviation index of the network (I rd ) , as defined by Di Nardo and Di Natale (2011) In equation (6), q i is the water demand at node i, H t,i is the minimum required head, while H i,ND and H i are the actual heads before and after the partitioning of the WDN, respectively. However, in the proposed approach, this term is not used as part of the objective function, but it can only be computed as a performance indicator for postevaluation of the provided solutions.

Optimization approach
The proposed algorithm develops in three phases, as sketched in Figure 1. The process starts with an initialization phase, in which the assignment of the input parameters is checked and first elaborations are performed. In addition to the network geometry, the required data are the elevation (z i ), the water demand (q i ) and the minimum service pressure (P t,i ) for each of the N n demand node. Subsequently, the minimum hydraulic heads (H t,i ) are calculated: , , 1,...,

Generation of topologically optimized solutions
Variants of the K-Means Clustering Algorithm (KMCA) (Mc Queen 1967) can provide solutions meeting the criteria of "topological optimization", namely the homogenization of water demands and of node elevations explained in section 2.
The application of the KMCA requires the computation of the distances between domain elements. The Euclidean distance between two nodes or the length of the connecting pipe are not directly relevant for a WDN. Instead, the node elevations and demands provide the input for defining useful network metrics.
To this aim, once defined the desired number of DMAs (N DMA ), the KMCA starts by the random selection of an equal number of nodes to be the initial positions of centroids. The method then proceeds by a series of cycles, each cycle consisting of two steps. The first step assigns each node to the closest centroid, while the second step moves each centroid to the one among its controlled nodes optimizing a given objective function. In both the first and the second step one needs to compute the shortest paths between pairs of nodes in a graph given the assigned length of its edges, using by the well-known algorithms of Dijkstra or Floyd-Warshall.
In order to meet the criteria of topological optimization, for every edge of the graph (i.e. every pipe of the WDN), the following quantities are calculated: and the corresponding edge weight (l ij ) is computed: In equations (8), q i and z i are the water demand and elevation at node i, while n i is the number of edges linked to the same node. The value of φ in equation (9) can range between 0 and 1. However, since the homogenization of water demands is not crucial for the design of the DMAs (see section 2), low values of φ should be used.
The objective function minimized in the centroid-move step can be the sum over nodes of their distance from the associated centroid. Alternatively, one may minimize the maximum over centroids of their distance from the farthest controlled node.
The KMCA rapidly converges to a local minimum. Starting the process several times with different initial picks of the centroids generates multiple solutions, the latter possibly ranked by corresponding values of the objective function. Further criteria can be introduced for discarding solutions (e.g. max unbalance for sum of node weights between different DMAs), and different values of N DMA should be considered.
The KMCA works well for computing the optimal placement of a number of sensors over the WDN using a proper metric for the network edges (Fontana et al., 2013). In that case, one is interested in the solution corresponding to the minimum of the objective function. With the KMCA, one cannot establish whether the process attained the global minimum: if this is important, one can use the KMCA solution as the starting point in solving a Mixed Integer Linear programming (MILP) formulation of the same optimum problem, for which library solvers exist (IBM ILOG CPLEX) that provide this information.
In the problem at hand, there is no guarantee that a solution meeting the stated optimization criteria would be also sound from a hydraulic perspective otherwise one should resort to a well-established graph partitioning tool like METIS 5 (Karypis, 2013). The approach presented here follows an alternative route: the KMCA is used to generate not just one but many solutions, all well behaved with respect to optimization criteria that are expressed through an objective function which depends on the lengths of network edges in a properly chosen metric. In this framework the optimal partition is searched among the ones generated by KMCA (or possibly by alternative heuristics) that can also lead with minimum cost to a hydraulically feasible implementation.

Setting of boundaries and selection of feeding lines for DMAs
At the end of the first stage of the optimization algorithm, a number of solutions for the partitioning of the WDN is obtained, each one consisting of the assignment of every node to a single DMA. Preliminary operation for the development of the next phases is the setting of boundaries of the designed DMAs.
This could be easily achieved by changing the status of the pipes (from "open" to "closed") or by operating on the adjacency matrix (A) of the WDN graph: for each couple of nodes j and k belonging to different DMAs, the correspondent term in matrix A should be substituted with 0.
Then, it must be pointed out that, in the most of cases, the topological optimization can lead to the design of districts without supply nodes (named "inner districts"). Furthermore, it might result that, within the same DMA, the supply node is not able to meet the total demand, which must be supplied by opening the connection with another DMA (see figure 2). The selection of the most appropriate connections between different DMAs must be made according to the criteria mentioned in section 2. However, since this operation has great influence on the hydraulic response of the partitioned WDN, the cost function defined in equation (1) is not completely useful to this aim, but its contribution is properly taken into account in the next step.
Then, for each of the obtained solutions, the procedure sketched in figure 3 must be applied. At first, all DMAs are grouped in the set D 0 . Then, for each d in the set D 0 , the presence of a supply node (nodes belonging to the set of supply nodes, S) is checked: if the condition is verified, and the total demand at nodes is available at supply node, the DMA is removed from D 0 , and next d is evaluated.
If it is not directly supplied, or the total demand is not met, and there are no adjacent supplied DMAs, district d is skipped and put in queue. Otherwise, the set of nearby supplied DMAs (not already linked to d) is considered: 0 : ; , where N δ is the set of nodes belonging to district δ, L 0 is the set of closed pipes, while B d and B δ are the sets of boundary nodes of districts d and δ, respectively. Then, the lengths of shortest-paths from supply nodes of districts in A d to nodes in B d are computed with FWA. However, in order to ensure the compliance with the hydraulic constraints, in this case the edge weights should be set equal to the hydraulic resistances of the corresponding pipes: l l l l R L w D ( 11) in which D i , L i , R i , are the pipe diameter, length and roughness, respectively. After the calculations, the following operations should be made: i) opening the connection belonging to the minimum shortest-path; ii) adding the entry node of d (s d ) to the set of supply nodes (S); iii) storing the length of the shortest-path in the variable sp d ; iv) removing d from D 0 .
The sequence must be repeated until set 0 D is emptied. Moreover, when calculating the shortest-paths from DMAs indirectly supplied, the sum of edge costs must be increased of quantities sp d .
At the end of the procedure, the number of closed pipes (i.e. the number of substituted elements in the adjacency matrix) correspond to the shut-off valves required for setting of district boundaries (N GV ), while the number of selected connections is equal to N CV .
Finally, it is worth noting that the proposed approach significantly reduces the combinatorial explosion of the number of solutions to be investigated when the number of districts and the extension of the WDN increase.

Verification of constraints and selection of the best solution
In the last step of the optimization algorithm, hydraulic simulations are carried out in order to evaluate the hydraulic response of the partitioned network. Demand Driven Analysis (DDA) or Pressure Driven Analysis (PDA) can be performed; obviously, in the latter case, further input parameters are required (Giustolisi et al. 2008). It is worth noting that the reduction of the number of hydraulic simulations to be run may ensure considerable savings in computation time.
For each solution detected in the previous steps, pressures at demand nodes (P i ) and output discharges (q s,d ) from supply nodes are obtained from the hydraulic simulation model. Then, the compliance of the hydraulic constraints in equation (12) Another constraint can be introduced in case of limited budget for the investment: The solutions not satisfying the previous conditions are discarded, while the remaining are ranked for decreasing values of the total cost function, obtained by linear combination of equations (1), (4) and (5): in which the weights can be suitably modulated in order to meet the decision-maker preferences, in accordance with the following conditions: , , 0;1 ; 1 The best design of DMAs must be intended as the one with the lowest value of (12), even though other evaluations (i.e. performance indicators like the one proposed in equation (6)) can bring to the adoption of a different solution in the ranking.

Conclusions
This study was focused on the presentation of a multi-objective approach for the automatic partitioning of a water distribution network into suitable DMAs.
A three-step procedure has been introduced, based on the definition of explicit and adjustable target functions, with the aim of providing full control on the optimization algorithm and for improving the readability and the interpretation of the results.
Further developments will be studied for the improvement of the provided solutions through unsupervised machine learning.
The proposed methodology will be applied to case tests from literature, in order to make comparisons with the other developed approaches. The effectiveness of the solutions will also be evaluated by analyzing a real case represented by a subsystem of the WDN of the city of Naples (Italy).