## Abstract

This paper explores the relationship between the minimum cost design of water distribution networks (WDNs) and the minimum water path criterion (MWPC), according to which the water entering the network through the source nodes should cover the shortest possible paths before being delivered to users. To this end, a three-step linear algorithm for WDN design based on the MWPC and set up in the 1980s was applied to many benchmark case studies. The results of the linear three-step algorithm were almost coincident with, and in some cases superior to, those produced by more complex and burdensome algorithms. This represents a solid proof of the strong implications of the MWPC for WDN design.

## INTRODUCTION

The design of water distribution networks (WDNs) has been one of the most explored topics in the WDN scientific literature, starting from the end of the 1960s (Shaake & Lai 1969) up to nowadays (e.g., see Creaco et al. 2014, 2016; Wang et al. 2015; Liu et al. 2016). In particular, the minimum cost design (MCD) is generally carried out considering a single loading condition and referring to lowest source node heads and highest nodal demands. Under these conditions, the objective of MCD is to assign suitable diameters to WDN pipes, which minimize the network cost while respecting constraints on nodal heads and flow velocities. Since the full enumeration of all the possible solutions is almost always impossible due to the large size of the search space, numerous authors have proposed methods of various kinds through the years to tackle this problem. In this context, algorithms based on linear programming (LP) (e.g., Alperovits & Shamir 1977; Ciaponi & Papiri 1983, 1985; Stephenson 1984; Suribabu & Neelakantan 2005) have been proposed. Other algorithms of heuristic or metaheuristic kinds have also been proposed, including local search algorithms, such as the Tabu Search (e.g., Sung et al. 2007) and the gradient method (Fujiwara & Khang 1990; Gomes et al. 2009), and global search algorithms, such as the genetic algorithms (GAs) (e.g., Savic & Walters 1997; Shau et al. 2005), the Ant Colony (e.g., Maier et al. 2003), the Cross Entropy (e.g., Perelman & Ostfeld 2007), the Harmony Search (Geem 2006), the particle swarm (Montalvo et al. 2008), the Differential Evolution (Vasan & Simonovic 2010), the nonlinear programming (NLP) (Kim et al. 1994), the mixed integer nonlinear programming (MINLP) (Bragalli et al. 2012) and the simulated annealing (Cunha & Sousa 1999). Finally, hybrid algorithms have also been proposed as the combination of algorithms of various kinds, such as those proposed by Krapivka & Ostfeld (2009) and Kadu et al. (2008), made up of GA + LP, that proposed by Haghighi et al. (2011), made up of GA + integer LP, and that proposed by Eusuff & Lansey (2003), made up of the combination of a global optimization algorithm with a local search method.

Despite being interesting contributions to the field, the nonlinear heuristic and metaheuristic algorithms mentioned above are often applicable only to oversimplified design problems. Therefore, they have seldom been implemented in freeware or licensed pieces of software, which, instead, make use of various network resolution algorithms coming from the research world (e.g., Todini & Pilati 1988). The idea of this work is to use, for analysis and comparison purposes, an algorithm proposed in the 1980s at the same time by Ciaponi & Papiri (1983, 1985) and by Stephenson (1984). This algorithm simplifies the non-linear network design problem by transforming it into the sequence of two LP applications, followed by a third simple corrective step. Since LP can be easily applied to networks of whatever size, the aim of this work is to show that the algorithm mentioned above can bridge the gap between the complex methodologies of limited applicability that exist in the scientific literature and the fully empirical approaches used by practitioners to design WDNs. The analysis and comparison of the results of the algorithm proposed by Ciaponi & Papiri (1983, 1985) and Stephenson (1984) can now be carried out trustworthily, thanks to the large availability of detailed case studies tackled with various methodologies in the scientific literature.

In detail, the algorithm proposed by Ciaponi & Papiri (1983, 1985) is based on the criterion of defining the pipe water discharges in such a way that the water supplied by the source node(s) reaches the demanding nodes covering the shortest path length (minimum water path criterion – MWPC). A positive effect of the application of the MWPC lies in the fact that the minimization of the total water path length entails a reduction in the water detention time in the network as well as the better preservation of the water's organoleptic and thermic characteristics. Furthermore, the MWPC has evident implications of economical optimality, in that the reduction in the total water path length facilitates selection of small pipe diameters, while respecting the constraints of maximum head loss between source and demanding nodes.

Following Ciaponi & Papiri (1983, 1985), the MWPC is enforced by searching for the pipe water discharges that minimize a linear objective function, while respecting nodal continuity and path head loss constraints, which are linear as well. Similar formulations were proposed by Stephenson (1984) and Suribabu & Neelakantan (2005). In detail, the formulation of Stephenson (1984) leads to identical mathematical expressions to those of Ciaponi & Papiri (1983, 1985), though the objective function of Stephenson (1984) has a different meaning with network unitary costs being proportional to pipe water discharges. Suribabu & Neelakantan (2005), instead, proposed that further constraints should be used, related to the maximum and minimum water discharge values at each pipe.

After the design configuration of pipe water discharges has been obtained, the pipes' optimal diameters are assessed using LP, in a similar way to Alperovits & Shamir (1977).

Being based on two LP applications in a row, the algorithm is conceptually flawed by the fact that the results of the former LP application, for the estimation of the design pipe water discharges, affect the results of the latter, aimed at pipe sizing. Therefore, it can be reasonably expected that the solution obtained by this algorithm is different and features higher costs compared with those obtainable by applying other algorithms which minimize the cost function in a single step, as a function of all the decision variables at stake. This is one of the reasons why this work was aimed at exploring the extent to which the solutions obtainable through the MWPC-based algorithm differ in terms of cost from the solutions obtainable through optimization algorithms minimizing directly the WDN cost. Furthermore, the work was aimed at verifying if the MWPC is implicitly taken into account by the other optimization algorithms for the WDN design, through the hydraulic analysis of the minimum cost solutions obtained in various benchmark case studies.

In the following subsections, first the MWPC-based algorithm (Ciaponi & Papiri 1983, 1985) is described, followed by the applications and comparisons with the other optimization algorithms.

## THE MWPC-BASED ALGORITHM

The MWPC-based algorithm (Ciaponi & Papiri 1983, 1985) is based on the following three steps:

1. calculation of the design water discharges minimizing the sum of water path lengths, transforming de facto a generic looped network into a system of branched networks, each of which is fed by a single source;

2. calculation of the pipe diameters minimizing the total cost of the system of branched networks;

3. re-closure of network loops through minimum diameter pipes.

In the following subsections, each step is thoroughly described.

### Step 1 – Calculation of the design water discharges (loop opening)

Let us consider a generic network featuring np pipes, n1 nodes with unknown head and n0 nodes with fixed head. The number of elementary network loops nl will be equal to:
(1)
For the network it is possible to define a topological incidence matrix A (Todini & Pilati 1988), in which the element A (i, j) can take on the values 0, −1 and 1. In particular, A (i, j) = 0 if the i-th pipe does not have the j-th node at one end; if the i-th pipe has the j-th node at one end, A (i, j) = 1 or A (i, j) = −1 depending on whether the (arbitrarily) assumed flow in the i-th pipe enters or exits the j-th node. Matrix A can be partitioned into two sub-matrixes, A10 and A12, associated with the nodes of fixed head and the nodes of unknown head, respectively (Todini & Pilati 1988). Continuity equations at demanding nodes of unknown head take on the following vector form:
(2)
where A21 is the transpose matrix of A12, and Q and q are the vectors of pipe water discharges Q and nodal demands q respectively. In this context, it should be underlined that q in Equation (2) can also be negative, therefore indicating a water discharge input into the WDN.

In the case of a looped network, the system of Equation (2) is indeterminate when considered standing alone, given that A21 is not of full rank. In fact, the number of rows (equal to the number of demanding nodes n1) is lower than the number of columns (equal to the number of pipes). This means that an infinite number of water discharge configurations satisfy the system of Equation (2).

The flow distribution corresponding to the MWPC can be obtained by solving an optimization problem featuring the constraints coded in the continuity equations of Equation (2) and the following objective function f to be minimized:
(3)
where LT is the transpose vector of L (containing the pipe lengths) and is a vector containing the absolute values of Q. Minimizing function f in Equation (3) is equivalent to applying MWPC in the network.
The previous optimization problem can be transformed into an LP problem by duplicating the network pipes, in such a way that opposite flow directions are allowed in the two arcs associated with the generic network pipe. In the network with duplicated pipes, vector Ld of arc lengths, vector Qd of arc flows and matrix can be obtained as:
(4)

(5)

(6)
where symbols ‘T’ and ‘’ indicate the transpose vector/matrix and the vector/matrix vertical concatenation, respectively.
Through the previous matrix operations, the optimization problem in Equations (2) and (3) takes on the new form of function fd in Equation (7) to be minimized, subject to the linear constraints in Equations (8) and (9), with Qd as the vector of decisional variables:
(7)

(8)

(9)
If required, further constraints can be added concerning the maximum water discharges that can leave the source nodes. In detail, these eventual constraints take on the following form:
(10)
where q0,max is the vector of maximum water discharges leaving the source nodes and can be obtained as:
(11)
if the pipes leaving the sources have the sources themselves as upstream nodes, from the topological point of view.

The constraint in Equation (10) can also be a strict equality.

In the solution of the optimization problem, only one of the two arcs associated with the generic pipe can have Qd greater than 0. In fact, the condition of Qd greater than 0 in both the arcs would prevent minimization of function fd. Furthermore, in light of the adopted schematization with outflows allocated only to network nodes, the optimal solution is a configuration of pipe water discharges, in which there are nl pipes in which Qd = 0 in both arcs. (In some (sporadic) cases, the number of pipes with Qd = 0 in both arcs can be larger or smaller than nl, though this does not affect the application of step 2, for which the main requirement is to have a pre-assigned distribution of pipe water discharges.) The removal of these pipes transforms the looped network into a group of branched networks (one for each source node), the pipe diameters of which can be sized as explained in the following subsection. This procedure is powerful since it enables fast identification of branched structures with a well-defined characteristic (minimum water path length) even in very complex and huge looped networks with several source nodes.

### Step 2 – Design of the pipes with Qd ≠ 0 (branched network(s))

The optimal design of the branched network(s), obtained by removing the pipes with Qd = 0 in both associated arcs, can be carried out for pre-fixed values of minimum pressure head (hdes,k) constraints. In this problem, given a set of nD diameters Di for each pipe of the branched network(s), the unknown variables are, with reference to the j-th network pipe, the lengths lj,i of the sub-pipes fitted with diameter Di. The objective of this design is to minimize the overall cost of the branched network while respecting the minimum acceptable pressure hdes,k constraints for the pre-selected configuration of nodal demands. The design entails solving an LP problem, with the following cost function to be minimized:
(12)
where ci is the unit cost associated with diameter Di and npb is the number of pipes in the branched network(s).
For each network pipe j, the constraint that the sum of sub-pipe lengths lj,i is equal to the length Lj of the whole pipe needs to be considered:
(13)
For the path leading from the reservoir (with head Hres) supplying the k-th node (with elevation zk) to the k-th node itself, the sum of the head losses in the nk pipes belonging to the path has to be so low as to allow the minimum acceptable pressure hdes b,k constraint to be respected at node k. This can be expressed as:
(14)
where Jj,i is the energy friction slope relative to sub-pipe lj,i of pipe Lj; Hdes,k is the desired total head at node k for full demand satisfaction, being the sum of node elevation and pre-fixed minimum pressure hdes,k of the branched network.

Although all the diameters Di in the set are simultaneously considered for each pipe in the LP problem, the solution generally yields sub-lengths greater than 0 only for one or two diameters.

Other constraints such as those related to minimum and maximum pipe flow velocities can be easily taken into account, since pipe water discharges are pre-assigned in the branched network(s). Actually, pipe sub-lengths lj,i in which these constraints are not respected due to too small or large diameters (and then too large or small flow velocities) can be set to 0 as a further constraint of LP. The formulation described above can also be extended to include other decision variables, such as the pressure head at the source nodes.

### Step 3 – Loop re-closure

After the design of the pipes in the branched network(s), a diameter needs to be assigned to the pipes that were removed in step 1 during loop opening. In this step, Ciaponi & Papiri (1983, 1985) recommended that the minimum diameter in the list of WDN design diameters be adopted. As for the distribution of pipe flows obtained in steps 1 and 2, the use of the minimum diameter generally prevents large variations from taking place, after network loops have been re-closed. This ensures good preservation of the MWPC prescribed in step 1. Nevertheless, the pipe flow variations due to the loop re-closure may cause minimum pressure head (hdes,k) or maximum velocity constraints to be violated at some nodes. In this case, the WDN designer can make some adjustments to the pipe design to re-obtain constraint preservation. In order to detect the pipes that need adjustments, step 2 can be tentatively repeated with different constraints from before.

Of course, the cost C3 of the total network is obtained as the sum of the cost of the branched network(s) plus the cost of the pipes used for loop re-closure, following the designer's adjustments.

In the context of step 3, it must be noted that the use of the minimum diameter in the list for loop re-closure is here considered only to pursue the minimum cost. However, in real WDN design applications, other choices could be made, such as the minimum diameter used in step 2 over all the branched network or for the pipes belonging to the same loop as the generic removed pipe. This would yield benefits of increased reliability, at the expense of a larger investment.

## APPLICATIONS

The applications of this work concerned the 13 WDNs reported in Table 1, in ascending order of number np of pipes to be sized. For each network, Table 1 also reports the literature source of the case study, the numbers n0 and n1 of source and demanding nodes, the number nD of available pipe sizes in the design, and the source and kind of the optimization algorithm of the reference minimum cost solution used for the analyses and comparisons of this work. In particular, the reference case studies were chosen among those available in the scientific literature based on the full availability of design data and reference solutions obtained by the paper authors.

Table 1

The various case studies and literature sources

NetworkSourcenpn0n1nDReference solutionOptimization algorithm
Two loop Alperovits & Shamir (1977)  14 Krapivka & Ostfeld (2009)  GA + LP
Ruey Fang Shau et al. (2005)  16 20 16 Shau et al. (2005)  GA
Blacksburg Sherali et al. (2001), Bragalli et al. (2012)  30 23 14 Bragalli et al. (2012)  MINLP
GoYang Kim et al. (1994)  30 22 Geem (2006)  Harmony Search
Taichung Sung et al. (2007)  31 19 13 Sung et al. (2007)  Tabu search
Hanoi Fujiwara & Khang (1990)  34 32 Perelman & Ostfeld (2007)  Cross entropy
Kadu Kadu et al. (2008)  34 24 14 Haghighi et al. (2011)  GA + ILP
Fossolo P0 Bragalli et al. (2012)  58 37 Bragalli et al. (2012)  MINLP
Fossolo Ir Bragalli et al. (2012)  58 37 13 Bragalli et al. (2012)  MINLP
Fossolo P1 Bragalli et al. (2012)  58 37 22 Bragalli et al. (2012)  MINLP
R9 Gomes et al. (2009)  71 61 10 Gomes et al. (2009)  Gradient method
Pescara Bragalli et al. (2012)  99 71 13 Bragalli et al. (2012)  MINLP
Modena Bragalli et al. (2012)  336 268 13 Bragalli et al. (2012)  MINLP
NetworkSourcenpn0n1nDReference solutionOptimization algorithm
Two loop Alperovits & Shamir (1977)  14 Krapivka & Ostfeld (2009)  GA + LP
Ruey Fang Shau et al. (2005)  16 20 16 Shau et al. (2005)  GA
Blacksburg Sherali et al. (2001), Bragalli et al. (2012)  30 23 14 Bragalli et al. (2012)  MINLP
GoYang Kim et al. (1994)  30 22 Geem (2006)  Harmony Search
Taichung Sung et al. (2007)  31 19 13 Sung et al. (2007)  Tabu search
Hanoi Fujiwara & Khang (1990)  34 32 Perelman & Ostfeld (2007)  Cross entropy
Kadu Kadu et al. (2008)  34 24 14 Haghighi et al. (2011)  GA + ILP
Fossolo P0 Bragalli et al. (2012)  58 37 Bragalli et al. (2012)  MINLP
Fossolo Ir Bragalli et al. (2012)  58 37 13 Bragalli et al. (2012)  MINLP
Fossolo P1 Bragalli et al. (2012)  58 37 22 Bragalli et al. (2012)  MINLP
R9 Gomes et al. (2009)  71 61 10 Gomes et al. (2009)  Gradient method
Pescara Bragalli et al. (2012)  99 71 13 Bragalli et al. (2012)  MINLP
Modena Bragalli et al. (2012)  336 268 13 Bragalli et al. (2012)  MINLP

Number of pipes (np), source nodes (n0) and demanding nodes (n1), available pipe sizes for the design (nD) and reference solution considered for comparison.

The simplest case study considered in this work is the two-loop network of Alperovits & Shamir (1977), the layout of which is reported in the following Figure 1.

Figure 1

Network layout of Alperovits & Shamir (1977). Node numbers are close to nodes and pipe numbers are close to pipes inside brackets ‘[ ]’. Dashed pipes are the pipes removed following step 1 of Ciaponi & Papiri (1983, 1985).

Figure 1

Network layout of Alperovits & Shamir (1977). Node numbers are close to nodes and pipe numbers are close to pipes inside brackets ‘[ ]’. Dashed pipes are the pipes removed following step 1 of Ciaponi & Papiri (1983, 1985).

The network is fed by a single source with head of 210 m and the minimum pressure constraint (hdes,k) is set to 30 m for all the network nodes. More information about the network can be found in the referenced work. The application of step 1 of the MWPC-based algorithm (Ciaponi & Papiri 1983, 1985) led to removal of pipes 4 and 8, one for each network loop. The minimized value of the path objective function f is 872,218 (m L)/s. The application of step 2 of the algorithm led to the pipe design reported in Table 2, which costs 399,473 $. Following loop re-closure with the pipe diameter of 25.4 mm, some adjustments were necessary to eliminate some pressure constraint violations, resulting in the other pipe design reported in Table 2 (step 3). In fact, these small adjustments are required because, by modifying the flows defined in step 1 and taken as granted in step 2, loop re-closure (step 3) can cause slight violations of nodal head constraints. Table 2 Diameters [mm] assigned to the network pipes of the network of Alperovits & Shamir (1977) PipeCiaponi & Papiri (1983, 1985) Krapivka & Ostfeld (2009) Step 2Step 3 457.2 457.2 457.2 304.8 (L = 219.22 m) 304.8(L = 207.08 m) 304.8 (L = 207.00 m) 254.0 (L = 780.78 m) 254.0(L = 792.92 m) 254.0 (L = 793.00 m) 406.4 406.4 406.4 – 25.4 25.4 406.4 (L = 682.29 m) 406.4(L = 693.61 m) 406.4 (L = 693.24 m) 355.6 (L = 317.71 m) 355.6(L = 306.39 m) 355.6 (L = 306.76 m) 254.0 (L = 986.13 m) 254.0(L = 989.52 m) 254.0 (L = 989.46 m) 203.2 (L = 13.87 m) 203.2(L = 10.48 m) 203.2 (L = 10.54 m) 254.0 (L = 909.18 m) 254.0(L = 902.31 m) 254.0 (L = 902.27 m) 203.2 (L = 90.82 m) 203.2(L = 97.69 m) 203.2 (L = 97.73 m) – 25.4 25.4 PipeCiaponi & Papiri (1983, 1985) Krapivka & Ostfeld (2009) Step 2Step 3 457.2 457.2 457.2 304.8 (L = 219.22 m) 304.8(L = 207.08 m) 304.8 (L = 207.00 m) 254.0 (L = 780.78 m) 254.0(L = 792.92 m) 254.0 (L = 793.00 m) 406.4 406.4 406.4 – 25.4 25.4 406.4 (L = 682.29 m) 406.4(L = 693.61 m) 406.4 (L = 693.24 m) 355.6 (L = 317.71 m) 355.6(L = 306.39 m) 355.6 (L = 306.76 m) 254.0 (L = 986.13 m) 254.0(L = 989.52 m) 254.0 (L = 989.46 m) 203.2 (L = 13.87 m) 203.2(L = 10.48 m) 203.2 (L = 10.54 m) 254.0 (L = 909.18 m) 254.0(L = 902.31 m) 254.0 (L = 902.27 m) 203.2 (L = 90.82 m) 203.2(L = 97.69 m) 203.2 (L = 97.73 m) – 25.4 25.4 Solution at the end of steps 2 and 3 of the algorithm of Ciaponi & Papiri (1983, 1985) and reference solution of Krapivka & Ostfeld (2009). In bold, adjustments following loop re-closure. The cost of the network with re-closed loops is C3 =$403,561. The value of f for the network with re-closed loops is 872,602 (m L)/s, which is very close to the f value obtained for the network with open loops. In particular, the percentage difference PD1 can be calculated between the value of f3 obtained at the end of step 3 and the value of f2 associated with the network configuration with open loops in step 2. The value of PD1 = 100 (f3f2)/f2 is equal to 0.04%, attesting to the small flow distribution variations that take place due to loop re-closure.

For the network of Alperovits & Shamir (1977), the reference solution considered in this work is the design configuration obtained by Krapivka & Ostfeld (2009) (see Table 2) by applying a hybrid algorithm made up of GA + LP. The value of the path function fr for the reference solution is 872,611 (m L)/s, which is very close to f2. In particular, the percentage difference PD2 = 100 (frf2)/f2 is equal to 0.04%, highlighting the fact that the reference solution also respects the MWPC, though being obtained without considering explicitly this criterion inside the optimization process. The total cost Cr of the reference solution is $403,572, which is slightly superior to that obtained through the algorithm of Ciaponi & Papiri (1983, 1985). In particular, the percentage difference PD3 = 100 (CrC3)/C3 is equal to 0.003%. Table 3 reports, for the networks of the various case studies, the values of function f and cost obtained by the algorithm of Ciaponi & Papiri (1983, 1985) at the end of steps 2 and 3 and those associated with the reference solutions. Table 3 For the various networks, values of the path f and cost objective functions obtained by Ciaponi & Papiri (1983, 1985) at the end of steps 2 and 3, and in the reference solution Networkf [L m/s] Network cost Ciaponi and PapiriCiaponi and PapiriReferenceCiaponi and PapiriCiaponi and PapiriReference Step 2Step 3SolutionStep 2Step 3Solution Two loop 872,218 872,602 872,611 399,473$ 403,561 $403,572$
Ruey Fang 294,887 298,107 312,223 8,497 × 10310,334 × 10311,593 × 103
Blacksburg 99,185 99,293 99,528 119,714 $120,142$ 118,251 $GoYang 15,702 16,765 16,726 112,758 × 103 won 177,382 × 103 won 177,136 × 103 won Taichung 205,691 209,481 213,687 5,629 × 1037,255 × 1038,775 × 103 Hanoi 34,108 × 103 34,304 × 103 35,100 × 103 6,027 × 1036,215 × 1036,080 × 103 Kadu 6,591,526 6,660,273 6,698 × 103 106,810 × 103 rupie 124,189 × 103 rupie 131,313 × 103 rupie Fossolo P0 16,766 18,071 17,055 50,755 × 103 £ 78,359 × 103 £ 70,681 × 103 £ Fossolo Ir 16,766 17,997 17,904 98,547 € 181,856 € 178,494 € Fossolo P1 16,766 16,891 17,049 29,460 € 30,398 € 29,117 € R9 2,660 × 103 2,666 × 103 2,741 × 103 191,865 × 103 Cr$ 198,185 × 103 Cr$199,390 × 103 Cr$
Pescara 900,212 937,902 944,282 1,228,663 € 1,856,557 € 1,820,263 €
Modena 786,210 810,230 821,564 2,161 × 103 € 2,537 × 103 € 2,577 × 103 €
Networkf [L m/s]
Network cost
Ciaponi and PapiriCiaponi and PapiriReferenceCiaponi and PapiriCiaponi and PapiriReference
Step 2Step 3SolutionStep 2Step 3Solution
Two loop 872,218 872,602 872,611 399,473 $403,561$ 403,572 $Ruey Fang 294,887 298,107 312,223 8,497 × 10310,334 × 10311,593 × 103 Blacksburg 99,185 99,293 99,528 119,714$ 120,142 $118,251$
GoYang 15,702 16,765 16,726 112,758 × 103 won 177,382 × 103 won 177,136 × 103 won
Taichung 205,691 209,481 213,687 5,629 × 1037,255 × 1038,775 × 103
Hanoi 34,108 × 103 34,304 × 103 35,100 × 103 6,027 × 1036,215 × 1036,080 × 103
Kadu 6,591,526 6,660,273 6,698 × 103 106,810 × 103 rupie 124,189 × 103 rupie 131,313 × 103 rupie
Fossolo P0 16,766 18,071 17,055 50,755 × 103 £ 78,359 × 103 £ 70,681 × 103 £
Fossolo Ir 16,766 17,997 17,904 98,547 € 181,856 € 178,494 €
Fossolo P1 16,766 16,891 17,049 29,460 € 30,398 € 29,117 €
R9 2,660 × 103 2,666 × 103 2,741 × 103 191,865 × 103 Cr$198,185 × 103 Cr$ 199,390 × 103 Cr\$
Pescara 900,212 937,902 944,282 1,228,663 € 1,856,557 € 1,820,263 €
Modena 786,210 810,230 821,564 2,161 × 103 € 2,537 × 103 € 2,577 × 103 €

First, it must be remarked that, except for Blacksburg and Fossolo P1, all the branched networks sized on the basis of the MWPC have a lower cost than the looped networks sized by means of other optimization algorithms. However, this result has no application since networks must deliver water to users connected along the pipes. Therefore, no pipes can be removed from the designed layout. The loop re-closure through pipes of minimum diameters (step 3 in the algorithm of Ciaponi and Papiri), indispensable for restoring the pipes removed in step 1, does not alter significantly the pipe flow distribution and the minimized flow path length f obtained for the network with open loops (Figure 2). In fact, PD1 is always quite small, below 4% in all but three case studies (GoYang, Fossolo P0 and Fossolo Ir) in which PD1 is around 7%. The higher PD1 values in these case studies take place because, in correspondence with some of the pipes removed in step 1, there are non-negligible ground elevation differences between the end nodes. These differences cause some non-negligible flow distribution variations when the loops are reclosed. This unpleasant effect in the Fossolo network is attenuated in the Fossolo P1 case study, where loops are re-closed with 16 mm diameter pipes, rather than 60 mm diameter pipes (as in Fossolo P0 and Fossolo Ir).

Figure 2

Values of PD1 for the various networks.

Figure 2

Values of PD1 for the various networks.

PD2 has the same order of magnitude as PD1 (Figure 3), pointing out that the search for the minimum cost solution leads to network configurations with low values of f, even when the MWPC is not explicitly taken into account inside the optimization process. In fact, the reference solutions in the various case studies were obtained through algorithms that do not take account of the MWPC in network design.

Figure 3

Values of PD2 for the various networks.

Figure 3

Values of PD2 for the various networks.

Finally, the closeness of PD3 to 0 (Figure 4) attests to the good performance of the algorithm based on MWPC. This algorithm is able to provide solutions with close (and in some cases even inferior) network cost to those obtained through more complex and burdensome optimization algorithms. The only network configuration in which the algorithm of Ciaponi & Papiri (1983, 1985) does not provide a cost-effective solution is the Fossolo network with the P0 set of available pipe diameters. The poor performance in this case study may be ascribed to the issue highlighted above, related to the higher flow distribution variations taking place after loop re-closure. Another reason for the poor performance could be the presence of stringent maximum flow velocity constraints in this case study. This could have led to an oversizing of the pipes where water discharges are concentrated in the branched network in step 2 of the algorithm, compared to solutions obtained by minimizing directly the network cost.

Figure 4

Values of PD3 for the various networks.

Figure 4

Values of PD3 for the various networks.

A final remark can be made about the cost increase that takes place during loop closure (step 3), due to the re-introduction of pipes that were removed during step 1. This increase strongly depends on the total lengths of the removed pipes compared to the total length of the original layout with closed loops. For instance, in the case of the Fossolo network, the total length of the removed pipes is equal to 5,408 m, which is almost half of the total length of the original layout (11,145 m). However, despite the influence of loop closure on network cost, it must be acknowledged that loop closure does not alter flow distribution much, which stays close to that obtained by applying the MWPC (step 1).

## CONCLUSIONS

This work has confirmed that, in WDN design, imposing the minimum path length on the water flowing from the source nodes to the demanding nodes has strong economic consistency, besides representing a valid design criterion for the conservation of the water's qualitative properties.

In a looped network model with demands allocated to the nodes, the application of the MWPC causes a number of pipes equal to the number of elementary loops to be removed in the network layout. Therefore, the looped network layout is transformed into a system of branched networks. The application of the MCD to branched networks yields the absolute minimum cost in almost all the case studies considered, thus proving the existence of a strong relationship between MCD and the MWPC. The strong relationship between the MCD and the MWPC is only slightly affected by the need to assign a hydraulic function to the pipes that should theoretically be excluded from the network based on a criterion of pure economic optimization (but that cannot be removed for obvious reasons). In fact, the total flow path length (function f) varies only slightly due to loop re-closure. Furthermore, the WDN design carried out with various optimization methodologies always leads to network configurations featuring f values close to the lowest value obtained applying the MWPC, even when the methodologies do not take account of the MWPC inside the optimization process.

It entails that MCD, which strictly speaking should be tackled by means of algorithms aimed at minimizing in a single step the network cost as a function of the whole set of decision variables at stake, can be faced through two optimization steps:

1. assessment of the design pipe water discharges that minimize the water path length;

2. calculation of the diameters that minimize the network cost.

Both the steps can be solved by means of LP, following well-established formulations (Ciaponi & Papiri 1983, 1985; Stephenson 1984; Suribabu & Neelakantan 2005), and completed by a third step for network loop re-closure.

The calculations reported in this work confirmed that the three-step linear algorithm described above is very effective. In fact, it yields solutions comparable (and in some cases superior) to those obtainable through nonlinear and heuristic algorithms, which are more burdensome from the computational viewpoint.

The three-step algorithm described above enabled solving the nonlinear WDN design problem through LP, which can be successfully applied to networks of whatever size, thanks to its lightness, robustness and effectiveness. Therefore, algorithms like that used in this work can bridge the gap between the complex methodologies of limited applicability that exist in the scientific literature and the fully empirical approaches used by practitioners to design WDNs.

The strong economic consistency of the MWPC and its major role in WDN design was highlighted here in case studies characterized by regular ground elevations (the maximum difference in the ground elevation ranges from 0 to 27 m). The application of the MWPC needs further investigation in the cases of strong ground elevation gradients, where flow distributions between nodes with very different ground elevations are affected by available heads rather than flow lengths. In fact, nodal ground elevations are actually neglected in the first step of the algorithm. Hence, if these variables vary significantly over the network, then the loop re-closure (step 3) can alter significantly the flow paths obtained in steps 1 and 2, thus worsening the performance of the algorithm in its current version.

A development of this work will also concern the extension of the MWPC to networks operating under multiple loading conditions.

## ACKNOWLEDGEMENTS

The Authors are grateful to Daniele De Stefani, who carried out the numerical simulations reported in this paper as a part of his Master's thesis in Civil Engineering.

## REFERENCES

REFERENCES
Alperovits
,
E.
&
Shamir
,
U.
1977
Design of optimal water distribution systems
.
Water Resources Research
13
(
6
),
885
900
.
Bragalli
,
C.
,
D'Ambrosio
,
C.
,
Lee
,
J.
,
Lodi
,
A.
&
Toth
,
P.
2012
On the optimal design of water distribution networks: a practical MINLP approach
.
Optim. Eng.
13
,
219
246
.
Ciaponi
,
C.
&
Papiri
,
S.
1983
Contributo al dimensionamento ottimale delle reti di condotte in pressione a maglie chiuse
.
Ed.
SEAG
,
Pavia, Italy
(in Italian)
.
Ciaponi
,
C.
&
Papiri
,
S.
1985
Contributo al dimensionamento ottimale delle reti di condotte in pressione a maglie chiuse
.
Ingegneria Sanitaria
4
,
209
217
(in Italian)
.
Creaco
,
E.
,
Franchini
,
M.
&
Walski
,
T. M.
2014
Accounting for phasing of construction within the design of water distribution networks
.
J. Water Resour. Plann. Manage.
140
(
5
),
598
606
.
Creaco
,
E.
,
Alvisi
,
S.
&
Franchini
,
M.
2016
Multi-step approach for optimizing design and operation of the C-Town pipe network model
.
J. Water Resour. Plann. Manage.
142
(
5
),
C4015005
.
Cunha
,
M. C.
&
Sousa
,
J. J. O.
1999
Water distribution network design optimization: simulated annealing approach
.
J. Water Resour. Plann. Manage.
125
(
4
),
215
221
.
Eusuff
,
M. M.
&
Lansey
,
K. E.
2003
Optimization of water distribution network design using the shuffled frog leaping algorithm
.
J. Water Resour. Plann. Manage.
129
(
3
),
210
225
.
Fujiwara
,
O.
&
Khang
,
D. B.
1990
A two-phase decomposition method for optimal design of looped water distribution networks
.
Water Resources Research
26
(
4
),
539
549
.
Geem
,
Z. W.
2006
Optimal cost design of water distribution networks using harmony search
.
Engineering Optimization
38
(
3
),
259
277
.
Gomes
,
H. P.
,
Marques Bezerra
,
S. d. T.
,
Oliveira de Carvalho
,
P. S.
&
Menezes Salvino
,
M.
2009
Optimal dimensioning model of water distribution systems
.
Water SA
35
(
4
),
421
432
.
Haghighi
,
A.
,
Samani
,
H. M. V.
&
Samani
,
Z. M. V.
2011
GA-ILP method for optimization of water distribution networks
.
Water Resources Management
25
,
1791
1808
.
Kadu
,
M.
,
Gupta
,
R.
&
Bhave
,
P.
2008
Optimal design of water networks using a modified genetic algorithm with reduction in search space
.
J. Water Resour. Plann. Manage.
134
(
2
),
147
160
.
Kim
,
J. H.
,
Kim
,
T. G.
,
Kim
,
J. H.
&
Yoon
,
Y. N.
1994
A study on the pipe network system design using non-linear programming
.
J. Korean Water Resour. Assoc.
27
(
4
),
59
67
.
Krapivka
,
A.
&
Ostfeld
,
A.
2009
Coupled genetic algorithm–linear programming scheme for least-cost pipe sizing of water-distribution systems
.
J. Water Resour. Plann. Manage.
135
(
4
),
98
302
.
Liu
,
H.
,
Savic
,
D. A.
,
Kapelan
,
Z.
,
Creaco
,
E.
&
Yuan
,
Y.
2016
Reliability surrogate measures for water distribution system design: comparative analysis
.
J. Water Resour. Plann. Manage.
143
(
2
),
doi:10.1061/(ASCE)WR.1943-5452.0000728
.
Maier
,
H. R.
,
Simpson
,
A. R.
,
Zecchin
,
A. C.
,
Foong
,
W. K.
,
Phang
,
K. Y.
,
Seah
,
H. Y.
&
Tan
,
C. L.
2003
Ant colony optimization for design of water distribution systems
.
J. Water Resour. Plann. Manage.
129
(
3
),
200
209
.
Montalvo
,
I.
,
Izquierdo
,
J.
,
Péreza
,
R.
&
Tung
,
M. M.
2008
Particle swarm optimization applied to the design of water supply systems
.
Computers & Mathematics with Applications
56
(
3
),
769
776
.
Perelman
,
L.
&
Ostfeld
,
A.
2007
An adaptive heuristic cross-entropy algorithm for optimal design of water distribution systems
.
Engineering Optimization
39
(
4
),
413
428
.
Savic
,
D.
&
Walters
,
G.
1997
Genetic algorithms for least-cost design of water distribution networks
.
J. Water Resour. Plann. Manage.
123
(
2
),
67
77
.
Shaake
,
J. C.
&
Lai
,
D.
1969
Linear Programming and Dynamic Programming Application to Water Distribution Network Design
.
Rep. No. 116
,
Dept. of Civil Engineering, Massachusetts Institute of Technology
,
Cambridge, MA, USA
.
Shau
,
H. M.
,
Lin
,
B. L.
&
Huang
,
W. C.
2005
Genetic algorithms for design of pipe network systems
.
Journal of Marine Science and Technology
13
(
2
),
116
124
.
Sherali
,
H. D.
,
Subramanian
,
S.
&
Loganathan
,
G. V.
2001
Effective relaxations and partitioning schemes for solving water distribution network design problems to global optimality
.
Journal of Global Optimization
19
(
1
),
1
26
.
Stephenson
,
D.
1984
Pipeflow Analysis
.
Elsevier
,
Amsterdam, The Netherlands and New York, USA
.
Sung
,
Y. H.
,
Lin
,
M.-D.
,
Lin
,
Y. H.
&
Liu
,
Y. L.
2007
Tabu search solution of water distribution network optimization
.
Journal of Environmental Engineering Management
17
(
3
),
177
187
.
Suribabu
,
C. R.
&
Neelakantan
,
T. R.
2005
Design of water distribution network by a non-iterative two-stage optimization
.
ISH Journal of Hydraulic Engineering
11
(
2
),
18
40
.
Todini
,
E.
,
Pilati
,
S.
1988
A gradient algorithm for the analysis of pipe networks
. In:
Computer Application in Water Supply, System Analysis and Simulation
,
Vol. I
(
Coulbeck
,
B.
&
Choun-Hou
,
O.
, eds),
John Wiley & Sons
,
London, UK
, pp.
1
20
.
Vasan
,
A.
&
Simonovic
,
S. P.
2010
Optimization of water distribution network design using differential evolution
.
J. Water Resour. Plann. Manage.
136
(
2
),
279
287
.
Wang
,
Q.
,
Creaco
,
E.
,
Franchini
,
M.
,
Savic
,
D.
&
Kapelan
,
Z.
2015
Comparing low and high-level hybrid algorithms on the two-objective optimal design of water distribution systems
.
Water Resources Management
29
(
1
),
1
16
.