Water distribution network sectorisation using graph theory and many-objective optimisation

A water distribution network (WDN) is the infrastructure that supplies drinking water to homes and businesses, and links water sources to consumers. Such networks are typically complex and dynamic, consisting of thousands of nodes (reservoirs, tanks and consumption nodes), interconnected by different types of links (pipes, pumps and valves).

Partitioning a WDN into smaller sub-networks is a strategy to manage its complexity, as advised by the International Water Association (IWA) (Morrison et al. 2007). Each sub-network, called a district metered area (DMA) (Burrows et al. 2000), is defined as a discrete area of a distribution system, in which the quantity of water entering and leaving an area is metered. DMAs are usually created by closure of valves or completely disconnecting pipes (Water Research Centre 1980; Morrison et al. 2007).

The main goal of WDN partitioning is to achieve better control over the distribution of water (Chambers et al. 2004). Some of the benefits of partitioning a water distribution network include: enhanced leakage and burst detection and management, establishment of a permanent pressure control system (pressure zones) by providing different pressure levels, improved contamination spread control (which is directly associated with water security) and enhanced rehabilitation and work planning (Herrara Fernández 2011). Partitioning a water network is also a major step towards a smart water grid (Hajebi et al. 2013a), which aims at the transformation of the existing water supply systems with ICT capabilities, to provide improved monitoring and control capacity over the network.

Recently, water security has gained a great deal of attention (National Research Council 2007; Porco 2010). Water security requires the division of the water distribution system into isolated sectors (also called isolated DMAs or iDMAs) ensuring no flow exchange between sectors. All water entering such a sector is consumed within it. In the event of a contamination incident, these sectors limit exposure to threat and minimise the number and the length of pipes that need to be decontaminated (Murray et al. 2009). Sector isolation implies that each sector must have direct access to at least one source (i.e., the path from the sector to a water source must not contain any nodes in other sectors), so that it can have access to water without having flow exchange with other sectors.

The process of partitioning a WDN into a set of isolated sectors is referred to as water network sectorisation (WNS) (Di Nardo et al. 2013b). This paper explores the WNS problem and proposes a novel WDN partitioning technique, called WDN-Partition, to solve this multifaceted partitioning problem. WDN-Partition applies a novel structural graph partitioning technique combined with a many-objective optimisation to find good sectorisation solutions. The key characteristics of the proposed method are as follows:

• Each sector has direct access to a water source, so the path from the sector to a source does not contain any nodes in other sectors.

• The identified sectors are isolated from each other, so there is no flow exchange between different sectors.

• The sizes of the identified sectors are within a predefined boundary.

• The candidate solutions are hydraulically analysed, and the best ones are chosen using a many-objective optimisation procedure.

• The criteria of optimisation and their priorities can be specified for each case.

• It works well for both small and large networks.

• It does sectorisation without adding any new component to the network.

This paper is organised as follows: first, the issues related to iDMA design are discussed and a set of WNS requirements are proposed. Then, based on the discussed requirements, the state of the art is reviewed briefly. Next, the WNS problem is formulated as a constrained many-objective optimisation problem. The next section explains how the proposed solution (i.e., WDN-Partition) addresses the requirements and challenges of the problem. The proposed method is evaluated in the next section. Finally, the last section concludes the paper and discusses future work.

Designing highly looped networks is the strategy applied in water distribution system design to guarantee high reliability of the network (Walski et al. 2003). In contrast, by cutting pipes or using isolation valves in the network re-design process to create DMAs (or iDMA), the loop structure of the network is reduced, which results in a decrease in network reliability. Additionally, water network partitioning causes more energy to be dissipated in the network, which may cause problems to ensure pressure requirements at some nodes, and therefore, may affect network efficiency (Alvisi & Franchini 2014). Furthermore, water may remain at dead-ends, which are created by disconnecting pipes and/or closing valves. This may cause water quality problems, especially water age issue, which is a surrogate for water quality (Walski et al. 2003).

Nonetheless, if partitioning is performed correctly, it can bring advantages in terms of water security and leakage detection, without highly compromising network reliability or water quality (Murray et al. 2009; Di Nardo et al. 2012, 2015). To perform partitioning correctly, the requirements of partitioning should be taken into account. In other words, a set of criteria and metrics should be defined in advance that reflect WNS requirements. These requirements should be considered in the sectorisation process, and the outcome of sectorisation should be evaluated using the defined metrics.

Despite the importance of defining WNS requirements, each of the existing approaches focuses on some particular requirements and does not consider the other ones. To have a basis for this study, a general set of requirements is needed. To come up with a general set of WNS requirements, the following methodology has been used:

• First, the IWA guidelines on DMA design (Morrison et al. 2007) are considered: size (geographical area and number of customer connections), elevation of nodes, pressure requirements, number of pipes to be cut, number of meters to be installed, infrastructure conditions and minimum number of mains crossed by sectors.

• Second, the initial list of criteria has been complemented with that discussed on the state of the art in WDN partitioning.

• Finally, the list of criteria has been discussed and modified with experts and practitioners in WDN partitioning.

The outcome of this process is the following set of WNS requirements, which are as comprehensive as possible within the scope of this work.

• Water security requirements.

• Isolation of sectors: i.e., no flow exchange between different sectors is allowed.

• Direct access to water source for each sector must be guaranteed: i.e., the path from a sector to at least one source must not contain any nodes in other sectors.

• Connectedness: i.e., the partitioned sectors in the WDN should be connected to guarantee that all the nodes have access to water. There must be a path from the source to all the nodes in an identified sector, and there should be no isolated node in the network after partitioning.

• Conservation of mass and conservation of energy. Two fundamental hydraulic constraints that govern the physics of hydraulic networks and should be considered in all water distribution network design and re-design problems. Conservation of mass can be regarded as continuity of flow constraint, which dictates that the fluid mass entering any pipe will be equal to the mass leaving the pipe (since fluid is typically neither created nor destroyed in hydraulic systems). Conservation of energy can be regarded as hydraulic equilibrium equations, which imposes that the difference in energy between two points in a network must be the same irrespective of flow path (Walski et al. 2003).

• Pressure requirements: i.e., the pressure at nodes should not exceed certain limits, i.e., a minimum of 28 (m) and a maximum of 100 (m) (US Army Corps of Engineers 2004). Additionally, minimum nodal pressure requirements should be guaranteed. Both of these requirements should consider the following scenarios (Walski et al. 2003; Morrison et al. 2007):

  • average day demand (ADD),

  • minimum hourly demand (MHD),

  • peak hourly demand (PHD),

  • maximum day demand (MDD),

  • fire demand (FD).

  It should be noted that from the hydraulic point of view, whenever a system is able to satisfy the MDD it will be able to satisfy MHD, PHD and ADD as well. For water quality modelling mainly ADD is used. Therefore, {MHD, PHD, MDD + FD} cover all the five scenarios, as FD is modelled with MDD to ensure the capability of the system to provide fire demand at the maximum day demand, and a system with such a capacity will definitely satisfy ADD.

• Sector sizes must be balanced and within a predefined boundary (Morrison et al. 2007). Boundaries like (300–2,500), (500–3,000) and (500–5,000) customer connections can be found in the literature (Morrison et al. 2007; Di Nardo & Di Natale 2011; Herrara Fernández 2011); however, (500–5,000) is the most common one.

• Customer demand satisfaction: i.e., enough water should be supplied to satisfy different customer demands at all times during the different consumption scenarios (Diao et al. 2013).

• Elevation of the nodes in a DMA should be within a specific range (Morrison et al. 2007).

• Limited water velocity: i.e., the minimum and maximum velocity of water in pipes should be within certain limits (Gomes et al. 2012). Typically, a minimum of 1 m/s (3 ft/s) for large zones and a maximum of 3 m/s (10 ft/s) are recommended (Walski et al. 2003).

• Minimum cut size: i.e., the number of pipes that must be cut (and equipped with flow meters and valves) should be minimised (Morrison et al. 2007).

• Minimum cut weight: i.e., sum of diameters of the pipes that must be cut should be minimised.

• Tank level limitations: i.e., the level of water in tanks should be within a boundary. The maximum allowable level is typically the top of the tank, and the minimum allowable water level is typically above the bottom of the tank to provide some residual storage for potential fire defeat events. Additionally, the difference between the water level at the start and the end of simulation period should be limited (usually less than 10% of the tank height).

• Maximum network reliability (Murray et al. 2009): i.e., the reliability of the network should be maximised. Resilience (Todini 2000) is a surrogate for network reliability, defined as the inherent capacity of a water network to manage unexpected failures. Network resilience is measured as ‘the ratio between the surplus of power delivered to users and the maximum power that can be dissipated in the network when meeting exactly the design criteria’ (Grayman et al. 2009).

• Maximum network efficiency: i.e., the energy efficiency of the network should be maximised. Dissipated power is a surrogate for energy efficiency (Di Nardo et al. 2013b), which is the power dissipated in the pipes during water flow from the source to the users; i.e., the total available power at the entrance of the distribution network minus the power that is delivered to the users. Dissipated power should be minimised to have the maximum energy efficiency in the network.

• Water quality considerations (Murray et al. 2009). Water age is usually considered as a replacement for water quality, which should be minimised.

• Minimum background leakage. Background leakage is characterised by small non-visible leaks that occur mostly at joints and fittings, not generating sufficient noise to be detected by existing equipment (Delgado 2008; WDSA 2014 team). It should be minimised in the network.

• Sectors should cross as few mains as possible (Morrison et al. 2007). The sector boundaries should follow the natural geographic and hydraulic boundaries. The final goal is to minimise the costs, both CAPEX and OPEX.

• Minimum costs. CAPEX (capital expenditure) is an expense incurred for WDN partitioning, e.g., expenditure on assets like pipes, valves, meters and installations. OPEX (operational expenditure) is the required day-to-day operation cost of the network, like valve operations, pump operations, maintenance and repairs. The total running cost of the sector creation and operation (CAPEX + OPEX) should be minimised.

The above list can be divided into three categories:

• Structural requirements, which are related to the structure of the network after partitioning, including sector isolation, direct access, connectedness, sector size, sector size balance, minimum cut-set size, minimum cut-set weight and, finally, sectors should cross as few mains as possible. Of these structural requirements, sector isolation and direct access are specific to WNS (i.e., to address water security); while the other ones are general in WDN partitioning, including sectorisation.

• Hydraulic requirements, which are hydraulic constraints and objectives that need to be maintained in water networks, including conservation of mass, conservation of energy, limited pressure at nodes, limited water velocity in pipes, limited tank level, customers demand satisfaction or guaranteeing nodal pressure requirements, network reliability, energy efficiency, minimum nodal elevation differences within the sectors, water quality, and background leakage. Violation of one of these requirements could result in damage to the network infrastructure or create problems in service provisioning. These requirements must be satisfied in all types of water distribution network design and re-design, including partitioning and sectorisation.

• Economic requirements, that deal with the total cost of sectorisation, i.e., CAPEX + OPEX.

Although some of the mentioned requirements are basic hydraulic requirements of a water distribution system, they should be taken into account for WDN partitioning and should be re-examined after the process. In some sources (Charalambous 2005; Murray et al. 2009; Grayman et al. 2009), the process of DMA design is referred to as network re-design. The structure of the network will be modified and some of the hydraulic requirements may not hold after partitioning. Therefore, it is important to assess all the requirements of network design again.

The priorities for these requirements may depend on the local situations, policies and legislations. However, as this work focuses on water network sectorisation, water security requirements (sector isolation and direct access) are highly prioritised.

Graph theory can be used to address the structural requirements of WNS. The WNS problem can be reduced to three different classic graph theory problems (Hajebi et al. 2014a): balanced graph partitioning (Andreev & Racke 2006), constraint graph clustering (Davidson 2005) and graph edge deletion (Yannakakis 1978). However, existing techniques are not suitable for handling water security related requirements in graph theory, i.e., sectors' isolation and direct access to sources for each sector.

On the other hand, existing solutions for WDN partitioning do not address all the requirements of water network sectorisation. In particular, water security is not addressed in most of the existing approaches; therefore, they cannot handle WNS. Three approaches address water security; however, they cannot handle large networks and/or do not address other WDN partitioning requirements. Herrara Fernández (2011) uses a multi-agent approach to divide a WDN into a collection of isolated sectors. It addresses sector isolation and direct access to water sources for each sector. However, no hydraulic requirement is considered in this work. Di Nardo et al. (2013a) identify isolated sectors and address direct access to water source for each sector; however, a number of hydraulic requirements are not addressed, including pressure requirements, minimum nodal elevation differences, sector size, limited water velocity in pipes, crossing few water mains, and water quality. More importantly, in both Herrara Fernández (2011) and Di Nardo et al. (2013a), as the number of sectors that can be created equals the number of main sources, for large networks, some of the resulting sectors may be larger than the maximum allowable size, especially if the size of the network divided by the number of sources is larger than the maximum allowable sector size. Ferrari et al. (2014) and Savic & Ferrari (2014) address sector isolation, direct access to a source for each sector, and sector size limitations to some extent; however, they do not address some WDN partitioning requirements. For example, pressure requirements for some scenarios, energy efficiency, limited water velocity in pipes, and minimum nodal elevation differences within the sectors are not considered in this work.

Water network sectorisation involves assigning all nodes in the network into different sectors, and deciding how many and which links should be closed to define the isolated sectors (Ferrari et al. 2014). This can be achieved by identifying and closing sector boundary links. In other words, the status of links (here, pipes or valves) being open or closed determines sector boundaries. Therefore, WNS can be formulated as a least-cost optimisation problem with a selection of link statuses as the decision variables. The links' layout and their connectivity, nodal demand, nodal elevation and minimum head requirements are assumed to be known.

In a general form, the WNS problem can be stated as: find the best combination of link statuses to partition a given WDN into a collection of isolated sectors, optimising the related objectives while satisfying the corresponding constraints. Objective functions reflect the metrics that are derived from WNS requirements and quantify them. Constraints are the conditions that must be held to have a feasible solution, also derived from the WNS requirements. There are three categories of objectives derived from WNS requirements: structural objectives, hydraulic objectives and economic objectives. Similarly, there are three categories of constraints in this problem: structural constraints, hydraulic constraints and explicit bound constraint that limits the domain of the decision variables: link statuses are binary variables, bounded to {0, 1}.

Mathematically, the problem can be formulated as:

• Given G = (nodes, links) a graph modelling a water distribution network, where nodes = {n₁, n₂, … , n_N}, ∀ n ∈ nodes, lable(n) ∈ {source, consumer} and links = {l₁, l₂, … , l_M}, ∀ l ∈ links, label (l) ∈ {pipe, valve, pump} such that l_j = 〈p, q〉 where p, q ∈ nodes, 1 ≤ j ≤ M. A partition of G into connected components is defined as DMAs = ⋃_{i = 1}^kdma_i where dma_i = (nodes_i, links_i), is a sub-graph of G, obtained by deleting links from G such that ∀ i ∈ {1, … , k} : nodes_i ⊂nodes, links_i ⊂links and also node s_i∩ nodes_j = ⁠, links_i ∩ links_j = ⁠.

The goal is to find the optimal partition of G considering the following objectives and constraints:

Objectives:
Minimise cut size:		(1)
Minimise cut weight:		(2)
Minimise sector size imbalance:		(3)
Minimise average customer exposure:		(4)
Minimise maximum customer exposure:		(5)
Minimise average pipe length exposure:		(6)
Minimise maximum pipe exposure:		(7)
Minimise pressure requirements violations (da Conceição Cunha & de Oliveira Sousa 2010):		(8)
Minimise dissipated power (Di Nardo et al. 2013b):		(9)
Minimise elevation difference within sectors:		(10)
Maximise resilience index (Todini 2000):		(11)
Minimise average of water age in the network in last 24 hours:		(12)
Minimise background leakage:		(13)
Subject to (constraints):
Connectedness of the partitioned network (PN):		(14)
Direct access to a source for each sector:		(15)
Isolation of sectors:		(16)
Sector size constraint:		(17)
Conservation of mass (Walski et al. 2003):		(18)
Conservation of energy (Walski et al. 2003):		(19)
Pressure constraints:		(20)
Water velocity constraint:		(21)
Tanks level constraints:		(22)
		(23)
Decision variables domain:		(24)

Objectives:
Minimise cut size:		(1)
Minimise cut weight:		(2)
Minimise sector size imbalance:		(3)
Minimise average customer exposure:		(4)
Minimise maximum customer exposure:		(5)
Minimise average pipe length exposure:		(6)
Minimise maximum pipe exposure:		(7)
Minimise pressure requirements violations (da Conceição Cunha & de Oliveira Sousa 2010):		(8)
Minimise dissipated power (Di Nardo et al. 2013b):		(9)
Minimise elevation difference within sectors:		(10)
Maximise resilience index (Todini 2000):		(11)
Minimise average of water age in the network in last 24 hours:		(12)
Minimise background leakage:		(13)
Subject to (constraints):
Connectedness of the partitioned network (PN):		(14)
Direct access to a source for each sector:		(15)
Isolation of sectors:		(16)
Sector size constraint:		(17)
Conservation of mass (Walski et al. 2003):		(18)
Conservation of energy (Walski et al. 2003):		(19)
Pressure constraints:		(20)
Water velocity constraint:		(21)
Tanks level constraints:		(22)
		(23)
Decision variables domain:		(24)

View Large

where in (1) and (2), such that ⁠, for with exactly one end-node in ⁠. In (2) and (17), or is the number of customer connections in ⁠. In (3), (4), (5), (6) and (7) ⁠. In (6) and (7), l is a link in which is in dma. In (8), s ∈ scen = ⁠, a set of possible demand scenarios; N = number of nodes; is the penalty cost of pressure deficit for node j in scenario s; is the minimum admissible pressure at node j in scenario s; and is the pressure for node j in scenario s obtained from simulations results. In (9), is the specific weight of water, where y is the number of boundary links and M is the total number of links in the network, = flow rate, =head loss for each link i in the network (Di Nardo et al. 2013a). In (10), k is the number of identified DMAs, n is the number of nodes in ⁠; is the standard deviation of elevations of nodes in DMA d, is the elevation of node ⁠; and is the mean of elevation of all nodes in ⁠. In (11), T is the operational time period (the mean is calculated over all the operational time period), N is the number of Nodes, is the demand at node i in (m³/sec), and are available and minimum required head at node i in (kPa), respectively; is the number of reservoirs; and are the discharge in (m³/sec) and head in (kPa) at reservoir r, respectively; is the number of pumps in the system, is the power introduced into the network by the j-th pump in (kW) and is the specific weight of water in (N/m³) (Todini 2000). In (12), i is the subscript of the i-th node in the network, LT is the last time step in the operational time period and is the water age at node i at time t. In (13), if then ⁠, and it is zero otherwise; l is the subscript of the l-th pipe; is the model mean pressure along the l-th pipe in (m); is background leakages outflow along the l-th pipe in (m³/sec), and are the model parameters, is unitless and is in (⁠⁠); and is the length of the l-th pipe in (m) (WDSA 2014 team).

In (14), Sources are the nodes in the network that supply water. In (16), a u-v path is a finite sequence of links which connect node u to node v. A flow path is defined as a path which respects flow directions in the network. In (17), or is the number of customer connections in ⁠. In (18), is the demand at demand node C at time t; and ⁠, are the flows entering and leaving the node at time t, respectively. In (19), Z₁ and Z₂ are elevations at points 1 and 2, respectively, in (m); P₁ and P₂ are pressures at points 1 and 2, respectively, in (N/m²); γ = fluid (water) specific weight, in (N/m³); V₁ and V₂ are flow velocities at points 1 and 2, respectively, in (m/s); g = acceleration due to gravity, in (m/sec²); h_P = pumping head gain, in (m); h_L = head loss in pipes, in (m); and h_M = head loss due to minor losses, in (m) (US EPA 2005). In (20), and are the maximum and minimum pressure requirements for each scenario s; is the service pressure in node i at time t in scenario s.

In (21), is the water velocity in pipe p at time t in scenario s in (m/s); is the maximum water velocity allowed in (m/s). In (22), is the level of tank i at time t in scenario s in (m). and are minimum and maximum admissible levels for tank i, respectively, in (m). In (23), and are the levels of the tank i at the end and the beginning of the simulation in the scenario s in (m), and is the maximum level difference for tank i in (m).

As discussed in the section ‘Problem statement’, WNS is a multifaceted problem embracing graph-theoretic, hydraulic and economic aspects. The graph-theoretic aspects of the problem may be handled using different algorithms for graph partitioning, clustering and community detection among others. However, as the goal is to partition a WDN into isolated sectors (iDMAs), the current methods are inadequate, and there is a need to develop an algorithm that takes the structural constraints of the problem into account. Additionally, besides the structural constraints, WNS has other objectives and constraints, therefore, it is a multi-objective optimisation problem.

There are four different approaches to deal with optimisation problems: mathematical approaches, brute force search, meta-heuristic techniques and heuristic techniques. As can be seen in ‘Problem statement’, objective functions and constraints are not functions of the decision variables. Therefore, it is not possible to use mathematical approaches in this context. Brute force search is not practical in this case, as the search space of the WNS problem is very large and increases exponentially by increasing the number of links. The possible combinations of link statuses that make the search space is 2ⁿ, for n being the number of links in the network. Three categories of meta-heuristic techniques have been used in different stages of this study (i.e., multi-agent systems (Hajebi et al. 2013b), Tabu search (Hajebi et al. 2014a) and genetic algorithms (NSGA-II) (Hajebi et al. 2014b)). However, the solutions generated by these techniques usually do not satisfy the structural requirements of the problem, as they are typically general search techniques and do not consider the specificities of the problem. This study develops a heuristic technique, which is problem-specific, adapted to the problem at hand, and takes full advantage of the particularities of the problem.

Based on valuable insights from existing solutions (Ferrari et al. 2014; Savic & Ferrari 2014), this paper proposes a novel heuristic WDN partitioning technique (WDN-Partition), to partition a water distribution network into (sub)-optimal isolated sectors, using a many-objective optimisation procedure. Optimisation ‘is the act of obtaining the best result under given circumstances’ (Rao 2009); in other words, it is ‘the process of determining the best design’ (Parkinson et al. 2013). To achieve the best results under the given circumstances explained in the problem statement (cf. the section ‘Problem statement’), WDN-Partition first satisfies water security related constraints and generates a collection of feasible solutions (i.e., solutions that address structural requirements of sectorisation, namely, isolation of sectors, direct access to at least one source for each sector, sector size limitations, and connectedness of the partitioned network) using a novel heuristic graph partitioning technique. Then, the best solutions are identified considering the values for their objective functions (i.e., the metrics for evaluation). Therefore, the efficiency of the optimisation method has been increased radically by first reducing the search space (by generating a collection of structurally feasible solutions), and then finding the best solutions among the feasible ones, which entails radically reduced number of hydraulic simulations.

After applying the structural graph partitioning technique, the structural, hydraulic and economic objectives and constraints should be considered. The challenge is that the objective functions of the problem are not formally defined based on the decision variables (as discussed in ‘Problem statement’, the decision variables are the statuses of the links with values either 0 or 1). The parameters of the objective functions and constraints are affected by the decision variables, however, their relationships are not trivial to formulate. A disaggregated methodology is used to solve this challenge. Although the decision variables do not appear in the objective functions and constraints, the results of changing them can be achieved indirectly using a network solver, i.e., a water distribution network hydraulic simulator, e.g., EPANET (Rossman 2000).

Each solution will be sent from the graph partitioning algorithm to the network solver to satisfy the hydraulic constraints. Once the network solver has solved the hydraulic equations and satisfied the hydraulic constraints, it will give the values for the parameters used in the objective functions and constraints (flow, head, pressure, etc.). Then, the values of these objective functions and constraints can be calculated and checked in the optimisation procedure.

Another issue is the optimisation method. WNS is a many-objective optimisation problem, so it might not be possible to have a single solution as the best one. The candidate solutions should be compared against each other in terms of different objectives, i.e., formulae (1) through (13). There are some multi-objective optimisation algorithms that perform well in dealing with two or three objectives (Coello et al. 2007); however, they cannot adequately handle more than three objectives (Jain & Deb 2013). The number of objective functions in this problem is 13, so these methods are not suitable to handle the WNS problem. Recently, some algorithms were proposed to deal with many (more than three) objectives (Jain & Deb 2013; Yuan et al. 2014; Liu et al. 2014). However, because of the structural constraints of the WNS problem (especially sector isolation and direct access), they are incapable of generating structurally feasible solutions and/or modify the solutions in such a way that the new solutions are also structurally feasible.

To demonstrate the different steps of the proposed method, the WDN for the city of Novato, California is used. This WDN is the most complex example included in EPANET 2 (Rossman 2000) which covers an area of about 150 km². It is a dual-source network, composed of 92 junctions, two reservoirs, three tanks, which are interconnected through 117 pipes and two pumps. This network is referred to as Novato network hereafter.

Step 1 (Initialisation): First of all, the network data are read from an EPANET (Rossman 2000) input file. An adjacency matrix A of the network is created using such data. The A(i,j) and A(j,i) entries in the matrix are set to the diameter of a link l if there is such a link l between two nodes i and j in the network; infinity if there is a pump or valve between i and j; 0 if there is no link between i and j.

The user is asked for the following parameters during the initialisation phase: (1) MainsSizeThreshold, which is the minimum threshold size for the main pipes, (2) dmaMinSize and (3) dmaMaxSize, which are the minimum and maximum size of a sector, (4) MaxIter, which is the maximum number of iterations in the loop in Step 5.1.2, and (5) a list of required criteria for the specific network at hand (objective functions) and their priorities (if more than one is chosen).

Then, two parameters are set based on the network data: LinkCount which is the number of links in the network, and a solution template (called position), which is a bit vector of length LinkCount and is used as a template for possible solutions. Each bit in the position vector uniquely represents a link in the network; 0 represents a closed link and 1 represents an open link. The position vector is initialised by 1 in all places.

Finally, two sets are defined during initialisation: Meters, which is the set of links that should be equipped with meters (the links that connect the DMAs to large water mains) and Valves, which is the set of links that should be closed off (i.e., the neighbouring links in the boundaries of different DMAs identified after partitioning).

Step 3 (Identifying Islands): In this step, the groups of nodes which are connected to each PotentialSources are identified and added to a list called Islands. To this end, each node in PotentialSources is selected and a breadth-first search (BFS) (Pohl 1969) algorithm is started to find all its reachable nodes. In the first step (for the first-level neighbours), the left-hand side nodes are separated from the right-hand side nodes (or the upper-side nodes are separated from the lower-side nodes), considering the large water mains as a reference line. This separation guarantees that the identified groups of nodes (and so, the identified sectors in the next steps) do not cross the large water mains. This is one of the advantages of WDN-Partition compared to the other approaches (Herrara Fernández 2011; Di Nardo et al. 2013a; Ferrari et al. 2014).

Step 4 (Checking the size of Islands): In this step, the sector size constraint is examined. For each group in the Islands list, the number of customer connections (or sum of nodal demands) is assessed. There are three possible situations:

• If size is in the range of the allowed size of a sector (between dmaMinSize and dmaMaxSize), the Island will be considered as an iDMA, and the first link from the corresponding potential source(s) will be added to the Meters set.

• If size is less than the minimum allowable size of a sector, it is considered as a MinorIsland. No meter is defined for MinorIslands as the cost is not justified (Ferrari et al. 2014). However, they cannot cause any water security risk for the rest of the network as there is no flow path from these islands to the other parts of the network.

• If size is greater than the maximum allowable size of a sector, it is considered as a MajorIsland, and must be partitioned into a set of isolated sectors all having direct access to the large water mains, and consequently, to a water source. Partitioning of major islands is done in Step 5.

It can be seen in Figure 3 that two MinorIslands and one MajorIsland are identified in the Novato network.

Step 5.1 (Partition a MajorIsland into K groups): First, it is examined to see whether there are enough nodes to serve the method as seeds to grow graphs from. Let us consider ptnSrcs4MI = PotentialSources ∩ MajorIsland, K_max = ⌊|MajorIsland|/dmaMinSize⌋ and K_min = ⌈|MajorIsland|/dmaMaxSize⌉. If the number of the nodes in PtnSrcs4MI is less than K_max, the number of seed nodes is not enough, so new nodes need to be found and used as seeds. In such a case, Step 5.1.1 should be taken, otherwise Step 5.1.2.

Step 5.1.1 (Find new potential sources): In this stage, the method finds new nodes in the MajorIsland that are connected to large water mains with large pipes (which are definitely smaller than the MainsSizeThreshold by some order, as all the nodes that are connected to large pipes with links of size MainsSizeThreshold or larger were previously identified and added to PotentialSources). To this end, for each node in PtnSrcs4MI a DFS algorithm is used to identify the neighbours in MajorIsland which are connected with links of size MainsSizeThreshold – ReductSteps. The identified nodes are added to the PtnSrcs4MI set. The method starts by ReductSteps = 1 and continues increasing it until at least K_max nodes are in PtnSrcs4MI.

Step 5.1.2 (Select seeds and grow graphs): Once there are enough seed nodes, K is set to be the number of partitions; starting from K = K_min and continuing to K_max (for example if size of MajorIsland is 10,000 and the proper sector size is between 500 and 5,000, any number between 2 and 20 partitions is acceptable; therefore, K starts from 2 and continues to increase up to 20). Then, in a loop of MaxIter (e.g., 100) times, K nodes are selected randomly from PtnSrcs4MI (selection by replacement) to serve as seeds. Then using a BFS algorithm, the method grows K graphs from the selected seeds.

The graph growing algorithm works as the following: starting from each K seed node in parallel, all the neighbouring nodes that are in MajorIsland are added to a group corresponding to the seed node and will be removed from MajorIsland. This process continues until all the nodes in MajorIsland are visited and removed from it and assigned to different groups. The resulting arrangement of nodes into identified groups could be a feasible solution for partitioning this MajorIsland, if sizes of all the resulting groups are within the limits of a proper sector size (larger than dmaMinSize and smaller than dmaMaxSize). If this condition holds, the resulting graphs are added to the sectors corresponding to the solution; the first link from the selected seed is added to Meters set; the neighbouring links are identified and added to the Valves set, and the corresponding bits are set to 0 in the position vector of the solution (the bit string representing the status of links in a solution). The neighbouring links are the links with exactly one end in a group. This process is repeated MaxIter times for each K, and all the feasible solutions are identified.

This is the end of Step 5.1 (Partition a MajorIsland into K groups). After that, the resulting solutions of partitioning different MajorIslands should be combined to create overall solutions, which cover all the network.

Step 5.2 (Combine solutions for different MajorIslands): As discussed, if there is more than one MajorIsland in the network, all the resulting components of partitioning different MajorIslands should be reflected in the overall solution which covers the entire network. Therefore, the solutions related to different MajorIslands should be combined into overall solutions. This is done by doing bitwise ‘and’ operations on positions of partial solutions and combining the corresponding DMAs. Note that the solutions related to each MajorIsland deal with a part of the network, so they are called partial solutions. Each partial solution corresponds to a specific set of links and represents the links that should be closed (the positions with 0) or remain open (the positions with 1), by doing bitwise ‘and’ the overall positions of the links that should be closed is identified. As there might be multiple solutions for partitioning each MajorIsland, all possible combinations of all solutions for different MajorIslands should be considered. Finally, the identified sectors in this step should be combined with the identified sectors from Step 4 to make the final candidate solutions.

After this stage, if there is at least one MajorIsland in the network, it is possible to end up having a couple of different solutions, as there might be more than one solution for partitioning each MajorIsland. Therefore, the best solution(s) should be identified. This is done in the next stage.

Step 6 (Selecting the best solutions): In this step, the solutions that do not have any advantage over the other solutions, with respect to their objective functions, are removed. As explained in the section ‘Problem statement’, WDN partitioning is a many-objective optimisation problem, so a single solution cannot be chosen as the best one. Thus, a set of Pareto optimal solutions should be identified, which make the Pareto front (Deb 2014). Pareto optimal solutions (in short, Pareto solutions) are the non-dominated ones. To compare candidate solutions, the dominance (Deb & Pratap 2002) concept is used. Solution A is said to dominate solution B if and only if A is no worse than B in terms of all the objective functions, and A is exactly better than B in terms of at least one objective function. All solutions are compared against each other, and if one solution dominates another one, the dominated solution will be removed. Therefore, all the non-dominated solutions will remain.

Each candidate solution's costs is calculated using the formulae (1) through (13). In order to obtain the values for the parameters involved in the objective functions (8) through (13) (e.g., flow, pressure, hydraulic head, tank level, water velocity in pipes and water age), an extended period simulation of the candidate solutions should be run. To do so, the resulting networks (the network in which statuses of links are set based on the position vector) are sent to the hydraulic solver (EPANET 2) to solve the network hydraulic equations and to satisfy constraints (18) and (19). Once the required information is returned from the hydraulic solver, the objective functions can be calculated, and the constraint violations can be examined for the candidate solutions.

The final results including the identified DMAs, Meters set, Valves set, and the related costs of each non-dominated solution will be reported at the end of the process. The domain experts should choose the best solution(s) based on other requirements of the problem (e.g., financial requirements, infrastructure constraints, etc.) and their experience.

WDN-Partition has been applied on some real-world water distribution networks including the two networks used for illustration of the method in the ‘Method’ section. However, as those two networks are small, they cannot sufficiently reflect the benefits of partitioning. Additionally, no other approach has used these networks for partitioning, so there is no baseline for evaluation on these two networks. Therefore, to evaluate WDN-Partition, a large network, which is used as a benchmark in other base line approaches (Murray et al. 2009; Diao et al. 2013; Ferrari et al. 2014; Savic & Ferrari 2014) was chosen, and the results are compared with the results of other approaches, based on the metrics defined in ‘Problem statement’ as objective functions.

The studied WDN comprises 12,523 nodes, two constant head sources, two tanks, 14,822 pipes, four pumps, five valves, and is subject to five variable demand patterns. It serves about 150,000 people and is a good example of a relatively large water distribution system. The system was simulated for a total period of 48 hours. This WDN is used as a test bed for a number of modelling exercises, including the Battle of the Water Sensor Networks competition (Ostfeld et al. 2008). The network is a real water distribution system, but it is modified to preserve its anonymity. However, these modifications do not affect the connectivity and the hydraulic behaviour of the network. The network's EPANET input file can be downloaded from the Exeter Centre for Water Systems. Hereafter, this network is referred to as BWSN_Network2. As there are no exact data for the number of customer connections per node in the BWSN_Network2, the average customer connection per node is used instead. The total number of customer connections is 77,916, so to have the boundary of (500–5,000) customer connections per DMA, 80–800 nodes per DMA on average are considered. Additionally, MainsSizeThreshold = 14 (inch) is considered for this network. MaxIter is set to 100 (as it proved to be a good trade-off between execution time and the probability of finding different solutions; however, if execution time is not an issue, larger numbers are preferred). As there is no detailed information for each node separately, is fixed to 28 (m) for all the demand nodes (Ferrari et al. 2014).

As mentioned in the ‘Method’ section, the method is designed and implemented in such a way that a list of requirements and their priorities (from the list of objective functions stated in ‘Problem statement’) are input, so for each network or each run, the user chooses what criteria are important and in what order. In running WDN-Partition on BWSN_Network2, the cost and background leakage are not chosen as criteria, as there are no exact data to calculate them. (It should be noted that to calculate background leakage, there should be data about the model parameters, i.e., and ⁠, for different sectors, which are not available for the current case. For costs, the exact costs of partitioning including the costs of cutting pipes and installing valves and meters and operating them is dependent on the exact situation of the network at hand, which are not also available for the current case.) Minimum pressure violation, maximum network reliability and water quality are chosen as high priority criteria, so the results are lexicographically ordered based on these requirements.

WDN-Partition identifies three MajorIslands. After partitioning them and combining the solutions, the method recognises 81 feasible candidate solutions. After removing the dominated ones, the method ended up with 78 non-dominated solutions, i.e., Pareto solutions. The Pareto solutions have between 28 and 48 sectors of sizes between 1,515 and 2,425 customer connections per sector. The total number of closed pipes vary from 66 to 161, and the total number of meters varies from 56 to 78 in different solutions.

The values of objective functions for 10 different Pareto solutions are reported in Table 1. These 10 solutions are selected from the set of 78 non-dominated solutions after sorting them based on the minimum pressure violations, maximum network reliability and minimum water age (as a surrogate measure for water quality).

Table 2 illustrates the results of partitioning BWSN_Network2 using WDN-Partition in comparison with other approaches.

Murray et al. (2009) manually partition BWSN_Network2 into 43 sectors using engineering principles with trial and error. They modified the network by adding 11 pipes to have at least two feed lines for each sector to ensure sufficient redundancy within the system. The average sector size is 1,996 connections. Three sectors are smaller than 500, and one is slightly larger than 5,000. Additionally, one sector is not directly connected to a source. Total number of closed pipes and meters are 163 and 53, respectively. The average water age during the last 24 hours of simulation is 31.51 hours. The other metrics are not reported in this work.

Diao et al. (2013) applied community detection for the automated identification of sector boundaries in BWSN_Network2. This approach identifies 41 sectors, but as the focus of the method is not on identifying iDMAs, a number of the identified sectors are not connected directly to a source. Two sectors are larger than the maximum allowable size, and one sector is smaller than the minimum allowable sector size. The average sector size is 2,044 customer connections, and the average water age during the last 24 hours of simulation is 32.01 hours. The other metrics are not reported in this work.

Ferrari et al. (2014) and Savic & Ferrari (2014) applied graph theory to partition BWSN_Network2 into isolated sectors. As this method applied a multi-objective optimisation method to find the sub-optimal solutions, a set of non-dominated solutions results, comprising solutions having 32 to 43 sectors. The reported sub-optimal solution identifies 36 sectors, of which, at least four sectors are not directly connected to a source (this can be seen in the arrangement illustrated in the paper). One sector is larger than the maximum acceptable size, and three sectors are smaller than the minimum acceptable sector size. The average sector size of the reported solution is 1,863 customer connections per sector, and the total number of closed pipes is between 53 and 132 for different Pareto solutions. The average reported resilience index is between 0.81 and 0.82 for different solutions, while the average reported water age during the last 24 hours of simulation is between 31.04 and 31.62 hours for different solutions. The other metrics are not reported in this work.

WDN-Partition identifies between 28 and 48 sectors in different Pareto solutions. All the identified sectors are isolated from each other and have direct access to a source. No sector has less than 500 or more than 5,000 customer connections. The average sector size varies from 1,515 to 2,425 customer connections for different solutions. The total number of closed pipes is between 66 and 161 for different solutions. The average resilience index is between 0.83 and 0.72, while the average water age during the last 24 hours of simulation is between 31.01 and 33.14 hours for different Pareto solutions. The total number of closed pipes varies from 66 to 161, and the total number of meters varies from 56 to 78 in different Pareto solutions.

WDN-Partition is implemented in MATLAB 2014b, and integrated with EPANET 2. The execution time for BWSN_Network2 on a laptop with an Intel Core i5 processor and 8 GB of memory is about 15 hours (the execution times for Novato network and BWSN_Network2 are 69 and 153 seconds, respectively).

WDN-Partition addresses water security requirements of water network sectorisation, i.e., isolation of sectors and direct access to at least one source for each sector, with minimum negative impact on the other structural (connectedness of the network and sector size limitations) and hydraulic requirements (customer demand satisfaction, pressure requirements, network reliability, energy efficiency, limited water velocity in pipes, minimum nodal elevation differences within the sectors and water quality). It partitions a water network into isolated sectors without adding any new component to the network, and works well for both small and large networks, as the number of sources is not a limiting factor for the number of sectors. The criteria of optimisation and their priorities can be specified for each case, which makes the method a general purpose one. Simulation-based results show WDN-Partition generally achieves its design objectives with a minimal decrease in the performance criteria of the network.

Despite its advantages, WDN-Partition has limitations. Similar to every heuristic method, finding the global optimal solution is not guaranteed. However, the results are structurally and hydraulically feasible. Moreover, WDN-Partition, like other methods, can only follow a predefined set of steps. There might be room for improving the results by experts. Finally, in WDN-Partition only closure of links (pipes and valves) is considered. It might be useful in some situations to add new components to the network; however, it is beyond the scope of this study.

Some improvements are planned for future work. For example, in the seed selection stage (Step 5.1.2), it is possible to consider some criteria to select better seeds (e.g., the diameter and/or flow of the connecting links, the demand of the seed nodes, and the distance of the seed nodes from each other and/or from the large water mains). Additionally, in Step 5.1.2, after graph growing, it is possible to optimise the boundaries of the identified sub-graphs considering sub-graph size, nodal elevation difference in each sub-graph, the number and the diameter of the pipes that should be cut, distances of the nodes in a group, nodal demands, etc. Finally, in some cases, it might be possible to merge nearby MinorIslands with each other to create a sector, or merge them with the neighbouring sectors.

This work was supported, in part, by Science Foundation Ireland grant 10/CE/I1855 to Lero – the Irish Software Research Centre (www.lero.ie). This paper is an extension to the paper entitled ‘Water distribution network sectorization using structural graph partitioning and multiobjective optimization’, presented at the 16th Conference on Water Distribution System Analysis, WDSA 2014, Bari, Italy.