To optimize the design of a water distribution network (WDN), a large number of possible solutions need to be examined; hence computation efficiency is an important issue. To accelerate the computation, one can use more powerful computers, parallel computing systems with adapted hydraulic solvers, hybrid algorithms, more efficient hydraulic methods or any combination of these techniques. This paper explores the possibility to speed up optimization using variations of the ΔQ method to solve the network hydraulics. First, the ΔQ method was used inside the evaluation function where each tested alternative was hydraulically solved and ranked. Then, the convergence criterion was relived in order to reduce the computation time. Although the accuracy of the obtained hydraulic results was reduced, these were feasible and interesting solutions. Another modification was tested, where the ΔQ method was used just once to solve the hydraulics of the initial network, and the unknown flow corrections were added to the list of other unknown variables subject to optimization. Two case networks were used for testing and were compared to the results obtained using EPANET2. The obtained results have shown that the use of the ΔQ method in hydraulic computations can significantly accelerate the optimization of WDN.

## NOMENCLATURE

• Qij(0)

initial flow distribution (m3/s)

•
• ΔQ

flow correction (m3/s)

•
• Rij

pipe flow resistance

•
• n

flow exponent (-)

•
• Lij

pipe length (m)

•
• Dij

pipe inside diameter (m)

•
• Λ

friction factor (-)

•
• g

gravity acceleration (≅9.81 m s−2)

•
• C

Hazen–Williams roughness coefficient (-)

•
• ΔHij

•
• ΔHres

•
• vk

flow velocity (m/s)

•
• pj

•
• f

fitness function ($),(€) • • I investment in the network ($),(€)

•
• Ip

pressure head condition penalty ($),(€) • • Iv flow velocity condition penaly ($),(€)

•
• Cp

#### FOS network

With the NYT reconstruction issue being classified as a medium sized optimization problem (Wang et al. 2015b), a step forward was to test an intermediate size optimization problem. The FOS network, another benchmark example from the literature, was chosen. The starting network topography was defined from the EPANET2's inp file (http://emps.exeter.ac.uk/media/universityofexeter/emps/research/cws/downloads/data/3-epanet/FOS.inp).

The FOS network, as well as the NYT network, is a gravitational WDN. Pipe diameters are unknown and have to be optimized to meet the given conditions. The network includes nn = 36 nodes with nr = 1 source node or reservoir, interconnected with np = 58 pipes forming nl = 22 loops. The minimum pressure head of all the demand nodes is 40 m, while the maximum pressure head of each node is given in Table 1. Besides pressure head condition, flow velocity condition needs to be satisfied, where in each pipe it has to be less than 1 m/s. For the network pipes, 22 different diameters are available in catalogue. This means that the search space has the size of 7.25 × 1077. The fitness function is made of three parts: investment in the distribution network I, penalty Ip for unfulfilled pressure head conditions and Iv penalty for failing to meet maximum velocity condition.
7
Table 1

The maximum pressure heads of each demand node of FOS

NiPmax (m)NiPmax (m)NiPmax (m)NiPmax (m)NiPmax (m)NiPmax (m)
55.85 53.10 13 59.10 19 58.10 25 56.6 31 56.60
56.60 54.50 14 58.40 20 58.17 26 57.6 32 56.80
57.65 55.00 15 57.50 21 58.20 27 57.1 33 56.40
58.50 10 56.83 16 56.70 22 57.10 28 55.35 34 56.30
59.76 11 57.30 17 55.50 23 56.80 29 56.5 35 55.57
55.60 12 58.36 18 56.90 24 53.50 30 56.9 36 55.10
NiPmax (m)NiPmax (m)NiPmax (m)NiPmax (m)NiPmax (m)NiPmax (m)
55.85 53.10 13 59.10 19 58.10 25 56.6 31 56.60
56.60 54.50 14 58.40 20 58.17 26 57.6 32 56.80
57.65 55.00 15 57.50 21 58.20 27 57.1 33 56.40
58.50 10 56.83 16 56.70 22 57.10 28 55.35 34 56.30
59.76 11 57.30 17 55.50 23 56.80 29 56.5 35 55.57
55.60 12 58.36 18 56.90 24 53.50 30 56.9 36 55.10

The pressure head penalty function has an expanded form compared to Equation (6), with a maximal pressure head condition introduced, where pjmax is the maximal pressure head for j-th node. In the velocity penalty function vk is the flow velocity in k-th pipe, vkmax is the maximal velocity for k-th pipe. The specific values of penalty functions for pressure and velocity are Cp = 15,000,000 €/m and Cv = 50,000,000 €/m, respectively.

## RESULTS AND DISCUSSION

The results of all presented ΔQ methods (A, B, C and D) are compared to the results obtained using the EPANET2 hydraulic solver (R). The first tests of the ΔQ method implementation, including all variations (A, B, C and D) were run on the NYT network. These different approaches share the same modified FBN (Figure 5(b)). There are two loops in the network: the larger loop 1 contains a reservoir along with the nodes numbered from 2 to 15, while loop 2 has nodes 11, 9, 16 and 20. The location of the split is arbitrary and inconsequential. Loop 1 was split in the proximity of node 6 where a new node 6′ is introduced as a start node for the downstream pipe. Loop 2 was split close to node 20, with the new node 20′ being generated. Flow corrections for loops 1 and 2, ΔQ1 and ΔQ2, respectively, are introduced as demands in the nodes 6 and 20, and in the nodes 6′ and 20′ as negative demands or inflows. A comparison of obtained results, for 1,000 generations and population of 100, is given in Table 2.

Table 2

A comparison of the optimization algorithms performance indicators for NYT

GA optimization algorithmFitness function f [106 $]CPU time t [s]Speedup factor [-] EPANET2 DLL (R) 38.6 390 Upgraded ΔQ (A) 38.6 18.5 21.1 Fixed ΔQ (B) 40.2 78.0 Variable ΔQ (C) 39.8 5.5 70.9 Fixed iteration ΔQ (D) 39.0 18.4 21.2 GA optimization algorithmFitness function f [106$]CPU time t [s]Speedup factor [-]
EPANET2 DLL (R) 38.6 390
Upgraded ΔQ (A) 38.6 18.5 21.1
Fixed ΔQ (B) 40.2 78.0
Variable ΔQ (C) 39.8 5.5 70.9
Fixed iteration ΔQ (D) 39.0 18.4 21.2

For the FOS network 22 minimum basis loops were obtained. Loops are also geometrically minimal. The InitSet had a total of 175 pipes, the STSet 143 and the FSet 101 pipes. Optimization algorithms A and D were tested for four different GA settings (Table 3). Comparisons of computed performance indicators are shown in Figures 6 and 7, respectively.
Table 3

GA evaluation function settings for FOS network tests

No. test1234
GA generations 1,000 1,000 2,000 2,000
GA population 100 200 100 200
No. test1234
GA generations 1,000 1,000 2,000 2,000
GA population 100 200 100 200
Figure 6

Comparison of suboptimal solutions obtained for different optimization algorithm runs with FOS.

Figure 6

Comparison of suboptimal solutions obtained for different optimization algorithm runs with FOS.

Figure 7

Comparison of speedup factors (Equation (5)) for different optimization algorithm runs with FOS.

Figure 7

Comparison of speedup factors (Equation (5)) for different optimization algorithm runs with FOS.

The computer used for testing was an Intel i7-2630QM CPU with 6 GB of RAM memory. The obtained optimal solution using the EPANET2 DLL, for the NYT problem, is the same as one taken from the literature fopt = 38.6 × 106 \$ (Dandy et al. 1996), proving it as a valid reference for this investigation.

The computed performance indicators for the NYT network (Table 2) showed significant reduction of the computation time for the optimization algorithm in all of the examined variations (A, B, C and D). In terms of the speedup factor, best results were derived with the variation B, with the value of 78.0. This was expected since no iterative computation was performed inside the evaluation function. Approach C had a slightly smaller speedup factor of 70.9, probably due to the fact that an extra penalty function had to be computed for every examined alternative. It is to be expected to have a further reduction of this factor in real applications, since we have knowledge from the previous tests that the correct values of ΔQ1 and ΔQ2 deviate not more than 25% from the first iteration (Ivetić et al. 2014), and we could make the search space rather narrow. This is due to the fact that it is a case of an existing, simple network with just two loops. It is obvious that this approach needs to be adjusted in order to allow the GA to perform a successful search for the suboptimal values of flow corrections, in the rather broad search space. Methods A and D had shown a similar computational burden, with the speedup factors of 21.1 and 21.2, respectively. The similar computational burden is probably due to the fact that for the NYT example, a prefixed number of iterations (10) for variation D was sufficient to compute the ‘exact’ or at least near to the ‘exact’ values of flow corrections. Furthermore, approach A produced the best-known solution, while approach D was the second best with almost the same solution as the previous. Methods B and C produced slightly worse solutions. The suboptimal solution degradation occurs mostly due to the hydraulic results' inaccuracy, which resulted in higher penalty function value. The acceleration in algorithms using ΔQ methods is owed to the fact that less equations need to be solved, as well as the way the network is processed. The pre-processing stage, called just once, performs a large proportion of the necessary analysis, therefore later calls for the evaluation function take much less computation time than in reference algorithm.

In the case of the FOS network, tests with four different GA evaluation function settings using two variations A and D were done. Methods B and C could not be used in the presented manner since none of the pipe diameters was known at the beginning. From Figure 6, it is clear that in all tests, the values of the fitness function were similar for reference algorithm R and the two examined variations of the ΔQ method implementation A and D. For this example, none of the used algorithms reached the best known solution, and it can be concluded that in terms of the suboptimal solution, algorithms A, D and R do not outperform each other. In case of A and D, finding these solutions took much less computation time (Figure 7). The speedup factor for algorithm A ranged from 39.3 to 62.6 and for algorithm D from 57.6 to 105.6. Between approaches A and D, roughly the same value of the fitness function was achieved, with algorithm D taking significantly less time. It is appropriate to point out the benefits of the current iteration flow correction update. For a single test run of evaluation function in approach A for the FOS network, it took 23 iterations to reach the desired accuracy for the pipe flows of 10−6 m3 s−1, as opposed to 39 iterations for solution without this modification (about 40% reduction in number of iterations). Similar numbers were obtained for different test runs but this percentage clearly depends on the loops; configuration and pipe diameters.

## CONCLUSIONS

During the optimization of the WDN, hydraulic computation of a network inside an evaluation function consumes most of the computation time. In this paper, use of the ΔQ method for hydraulic computation inside an optimization algorithm is presented through several different approaches. Each of these approaches requires a pre-processing stage, in which the loops in the original water network are detected through minimal basis loop detection algorithm, and network split into the FBN. If a prebuilt network exists, as in the NYT case, initial values of the flow corrections are assumed through hydraulic computation of this branch network.

The upgraded ΔQ method (A) approach computes the correct values of the flow corrections inside each evaluation function, the fixed ΔQ method (B) omits the iterative computation of the flow corrections by using the initial values throughout the optimization run, while the variable ΔQ method (C) includes the values of the flow corrections, through multiplicative factors, as additional variables for optimization. Finally, the fixed iteration ΔQ method (D) is actually the approach A used with a fixed number of iterations of Equation (3). Only methods A and D use the hydraulic solver programmed as a DLL, as well as the reference algorithm (R) which uses EPANET2 in a DLL form. The first tests of the presented variations were done on the NYT problem. In all of the cases, significant computation time reduction was achieved, primarily due to the fact that the ΔQ method solves fewer equations than the GGA integrated in EPANET2. These type of results are expected for real size networks in which the number of loops is rarely higher than 20% of the number of nodes (e.g., BWSN2) (Ostfeld et al. 2008). This implies 80% less equations to be solved with the ΔQ method.

On top of this, in the variations B and C, the network hydraulics is solved only once in the pre-processing stage which makes them even faster. In terms of the quality of the suboptimal solutions obtained, only algorithm A managed to compute a global optimum. The others, B, C and D, have shown a slight degradation in this performance indicator, which is caused by the hydraulic inaccuracy.

Further testing was undertaken on the benchmark example of the FOS network, where approaches A and D were compared with the reference EPANET2 based algorithm R. The tests, with four different GA configurations, have shown a major speedup, with the speedup factor reaching the value of over 100. Since method D had a fixed number of iterations it was the fastest method tested. In terms of finding the suboptimal solutions, both A and D found similar solutions as algorithm R.

The obtained results have shown that the ΔQ method is remarkably faster than EPANET2 when used in medium and intermediate optimization problems. Further investigation will be undertaken on real size water distribution networks. Apart from just changing the hydraulic solver, this approach can be utilized combined with other ways to reduce computation time, such as parallelization, network decomposition, etc.

## ACKNOWLEDGEMENTS

The authors express their gratitude to the Serbian Ministry of Education and Science for support through the project TR37010: ‘Rain water drainage systems as part of the urban and transport infrastructure’.

## REFERENCES

REFERENCES
Agullo
E.
Demmel
J.
Dongarra
J.
B.
Kurzak
J.
Langou
J.
Ltaief
H.
Luszczek
P.
Tomov
S.
2009
.
J. Physics Conf. Ser.
180
,
IOP Publishing
,
012037
.
Alonso
J. M.
Alvarruiz
F.
Guerrero
D.
Hernández
V.
Ruiz
P. A.
Vidal
A. M.
Martínez
F.
Vercher
J.
Ulanicki
B.
2000
.
J. Water Resour. Plann. Manage.
126
(
4
),
251
260
.
Artina
S.
Bragalli
C.
Erbacci
G.
Marchi
A.
Rivi
M.
2012
.
J. Hydroinform.
14
(
2
),
310
323
.
Bragalli
C.
D'Ambrosio
C.
Lee
J.
Lodi
A.
Toth
P.
2012
.
Optim. Eng.
13
,
219
246
.
Burger
G.
2014
Parallel computing in urban water management: A Model-Based Parallel Computing Approach to Reduce the Runtime of Applications in Urban Water Management
.
Doctoral dissertation
,
University of Innsbruck
,
Austria
.
Burger
G.
Sitzenfrei
R.
Kleidorfer
M.
Rauch
W.
2013
.
Environ. Modell. Softw.
53
,
27
34
.
Craeco
E.
Franchini
M.
2012
.
Urban Water J.
9
,
385
399
.
Craeco
E.
Franchini
M.
2014
.
J. Hydraul. Eng.
140
,
313
321
.
Cross
H.
1936
Analysis of flow in networks of conduits or conductors. Bulletin University of Illinois No. 286
.
Crous
P.
van Zyl
J.
Roodt
Y.
2012
.
J. Hydroinform.
14
,
603
.
Dandy
G. C.
Simpson
A. R.
Murphy
L. J.
1996
.
Water Resour. Res.
32
,
449
458
.
Di
P.
Berardi
L.
Khu
S. T.
Savic
D.
2009
.
Environ. Modell. Softw.
24
,
202
213
.
Diao
K.
Rauch
W.
2013
.
Water Res.
47
(
16
),
6097
6108
.
Diao
K.
Wang
Z.
Burger
G.
Chen
C.-H.
Rauch
W.
Zhou
Y.
2013
.
Environ. Modell. Softw.
52
,
253
263
.
Hoffman
J. D.
2001
Numerical Methods for Engineers and Scientists
, 2nd edn.
Marcel Dekker
,
New York
,
USA
.
Holland
J. H.
1992
.
Scientific American
267
,
66
72
.
Ivetić
D.
Vasilić
Ž.
Prodanović
D.
Stanić
M.
2014
Implementing ΔQ method to accelerate the optimization of pressurized pipe networks
. In:
Proceedings of the 16th Annual Water Distribution Systems Analysis Conference, WDSA
,
14–17 July
,
Bari
,
Italy, Procedia Engineering, Elsevier
.
Jha
K.
2007
Automatic minimal loop extraction and initialisation for water pipe network analysis
.
Int. J. Simul. Syst. Sci. Technol.
8
,
8
19
.
Jungnickel
D.
2005
Graphs, Networks and Algorithms
, 2nd edn.
Springer-Verlag
,
Berlin
,
Heidelberg
,
Germany
.
Larock
B. E.
Jeppson
R. W.
Watters
G. Z.
2000
Hydraulics of Pipeline Systems
.
CRC Press LLC
,
Boca Raton, Florida
,
USA
.
Marques
J.
Cunha
M. C.
Sousa
J.
Savić
D.
2012
.
Drinking Water Eng. Sci.
5
,
31
37
.
Montesinos
P.
Guzman
A. G.
Ayuso
J. L.
1999
.
Water Resour. Res.
35
(
11
),
3467
3473
.
Neelakantan
T. R.
Suribabu
C. R.
2005
Optimal design of water distribution networks by a modified genetic algorithm
.
J. Civil Environ. Eng.
1
(
1
),
20
34
.
Ostfeld
A.
Uber
J. G.
Salomons
E.
Berry
J. W.
Hart
W. E.
Philips
C. A.
Watson
J.
Dorini
G.
Jonkergouw
P.
Kapelan
Z.
di Pierro
F.
Khu
S.
Savic
D.
D.
Polycarpou
M.
Ghimire
S. R.
Barkdoll
B. D.
Gueli
R.
Huang
J. J.
McBean
E. A.
James
W.
Krause
A.
Leskovec
J.
Isovitsch
S.
Xu
J.
Guestrin
C.
Van Briesen
J.
Small
M.
Fischbeck
P.
Preis
A.
Propato
M.
Piller
O.
Trachtman
G.
Wu
Z. Y.
Walski
T.
2008
.
J. Water Resour. Plann. Manage.
134
(
6
),
556
568
.
Rossman
L. A.
2007
.
J. Water Resour. Plann. Manage.
133
(
6
),
566
567
.
Savic
D. A.
Walters
G. A.
1997
.
J. Water Resour. Plann. Manage.
123
(
2
),
67
77
.
Smith
L.
Liang
Q.
Quinn
P.
2013
A flexible hydrodynamic modelling framework for GPUs and CPUs: Application to the Carlisle 2005 floods
. In:
Proc. International Conference on Flood Resilience: Experiences in Asia and Europe
,
5–7 September
,
Centre for Water Systems, Exeter
,
UK
.
Stanić
M.
Avakumović
D.
Kapelan
Z.
1998
Evolutionary algorithm for determining optimal tree layout of water distribution networks
. In:
Hydroinformatics 98
(
Babovic
V.
Larsen
L. C.
, eds).
Balkema
,
Rotterdam
,
The Netherlands
, pp.
901
910
.
Stanić
M.
Ivetić
D.
Vasilić
Ž.
Prodanović
D.
2012
Improvement of application of genetic algorithms in optimization of pressurized pipe networks
. In:
Proc. 16th Conference of Society of Serbian Hydraulic Engineers
,
Donji Milanovac
,
Serbia
,
University of Belgrade – Faculty of Civil Engineering (In Serbian)
.
Suribabu
C. R.
2010
.
J. Hydroinform.
12
(
1
),
66
82
.
Todini
E.
Pilati
S.
1987
A gradient method for the analysis of pipe networks
. In:
International Conference on Computer Applications for Water Supply and Distribution
.
Leicester Polytechnic
,
Leicester
,
UK
.
Todini
E.
Rossman
L. A.
2013
.
J. Hydraul. Eng.
139
,
511
526
.
Van de Geijn
R. A.
1997
Using PLAPACK: Parallel Linear Algebra Package
.
MIT Press
,
Cambridge, MA
,
USA
.
von zur Gathen
J.
1993
Parallel linear algebra
. In:
Synthesis of parallel algorithms
(
Reif
J. H.
, ed.).
Morgan and Kaufmann
,
Los Altos, CA
,
USA
, pp.
574
617
.
Wang
Q.
Craeco
E.
Franchini
M.
Savić
D.
Kapelan
Z.
2015a
.
Water Resour. Manage.
29
(
1
),
1
16
.
Wang
Q.
Guidolin
M.
Savic
D.
Kapelan
Z.
2015b
.
J. Water Resour. Plann. Manage.
141
(
3
).
doi:10.1061/(ASCE)WR.1943-5452.0000460
.
Zecchin
A.
Thum
P.
Simpson
A.
Tischendorf
C.
2012
.
J. Water Resour. Plann. Manage.
138
(
6
),
639
650
.