1 Introduction
Water distribution networks consist of various components such as pipes, pumps, valves and tanks. The networks need to satisfy current and future water demands (Spiliotis and Tsakiris
2012; Korteling et al.
2013; Tsakiris and Spiliotis
2017). The main objective considered when designing water distribution networks is cost minimization subject to adequate water supply and pressure at the demand nodes. However, inevitably some network elements will be unavailable occasionally, for example, due to pipe breakage and pump failure. Therefore, some spare capacity needs to be included to enable the network to perform reasonably well under both normal and abnormal operating conditions. Thus, network resilience is important also (Harrison and Williams
2016; Herrera et al.
2016; Agathokleous et al.
2017). Resilience is characterised by redundancy, failure tolerance and reliability.
Optimizing the design of water distribution networks is an extremely complex problem that is classed as NP-hard (Yates et al.
1984). de Neufville et al. (
1971) were among the first researchers who recognised that water system design involved at least two conflicting objectives related to cost minimization and network performance. For many years, conflicting objectives were often aggregated into a scalar function and solved as a single-objective optimization problem.
More recently, evolutionary algorithms have been preferred. Evolutionary algorithms are stochastic search techniques well suited to identifying the Pareto optimal sets in complex multi-objective optimization problems. Many population-based optimization techniques have been employed in the design of water distribution networks. Some examples are genetic algorithms (Holland
1975), differential evolution (Storn and Price
1997)
, particle swarm (Kennedy and Eberhart
1995), ant colony (Dorigo et al.
1999) and harmony search (Geem et al.
2001).
Elitism is an extremely important feature in evolutionary algorithms that ensures the best solutions in a population are retained for inclusion in the next generation. This ensures that the fittest candidates will be preserved to improve the convergence characteristics (Zitzler et al.
2000). Vector Evaluated Genetic Algorithm (Schaffer
1985), Vector-Optimized Evolution Strategy (Kursawe
1990), Multi-Objective Genetic Algorithm (Fonseca and Fleming
1993), Weight-Based Genetic Algorithm (Hajela and Lin
1992) and Non-Dominated Sorting Genetic Algorithm (Srinivas and Deb
1994) are some examples of non-elitist evolutionary algorithms. Examples of elitist evolutionary algorithms include the Non-Dominated Sorting Genetic Algorithm (NSGA) II (Deb et al.
2002), Distance-Based Pareto Genetic Algorithm (Osyczka and Kundu
1995), Strength Pareto Evolutionary Algorithm (Zitzler and Thiele
1998) and Pareto-Archive Evolution Strategy (Knowles and Corne
2000).
Genetic algorithms are widely employed in the design of water distribution networks (Wu and Simpson
2001; Vairavamoorthy and Ali
2005; Rao and Salomons
2007; Haghighi et al.
2011; Creaco and Pezzinga
2015). Examples include design and rehabilitation (Jayaram and Srinivasan
2008), pump operation scheduling (Goldberg and Kuo
1987), tank siting and sizing (Prasad
2010) and water quality optimization (Munavalli and Kumar
2003).
Many researchers in various disciplines including water distribution employed the nondominated sorting genetic algorithm NSGA II (Yan et al.
2016). The majority of the applications of NSGA II in the area of water distribution considered design optimization through pipe sizing. Different measures of reliability were included in some cases, for example, Prasad and Park (
2004), Farmani et al. (
2006) and Saleh and Tanyimboh (
2016). Some other applications of NSGA II included Farmani et al. (
2006) and Prasad (
2010) who designed the benchmark network called “Anytown”. Jayaram and Srinivasan (
2008) and Siew et al. (
2014) investigated design and rehabilitation based on the life cycle cost. In the area of drinking water safety, Preis and Ostfeld (
2008) and Weickgenannt et al. (
2010) considered contamination detection whilst Jeong and Abraham (
2006) focused on the consequences of external attacks.
Due to the high computational burden associated with the reliability calculations, surrogate measures (Forrester et al.
2008; Díaz et al.
2016) have been proposed, for example, flow entropy and resilience index (Awumah et al.
1990,
1991; Tanyimboh
1993; Tanyimboh and Templeman
1993a,
b; Todini
2000). The advantage of using such measures is that they are relatively simple functions that do not require repetitive time-consuming hydraulic simulations and can be incorporated in optimization algorithms relatively easily.
The idea of incorporating Shannon’s informational entropy measure of uncertainty in the design of water distribution networks was introduced by Awumah et al. (
1990). Tanyimboh and Templeman (
1993a,
b) formalised the definition of the entropy function for flow networks using the conditional entropy concept (Khinchin
1953,
1957) and multiple probability spaces. Czajkowska and Tanyimboh (
2013) demonstrated that the entropy-based solutions derived from multiple operating conditions outperformed those from a single operating condition.
It has been shown that networks designed to carry the maximum entropy flows are more reliable than the traditional minimum cost solution and the relationship between reliability and entropy is strong (Tanyimboh and Templeman
1993b,
2000; Tanyimboh and Kalungi
2008; Tanyimboh and Setiadi
2008). The evidence in the literature shows that higher entropy values increase the uniformity of the pipe diameters (Awumah et al.
1991; Tanyimboh and Templeman
1993b) which, therefore, increases the reliability by increasing the opportunities for flow re-routing (Prasad and Park
2004). Investigations by Gheisi and Naser (
2015) and Tanyimboh et al. (
2016) demonstrated that flow entropy correlated well with hydraulic reliability and failure tolerance while other surrogate measures were mostly inconsistent.
This article is concerned with the formulation of the maximum entropy model for water distribution networks with multiple operating conditions. The primary aim is to develop and demonstrate a rigorous approach using empirical results. Research on flow entropy hitherto has focused on the peak demands. However, different loading conditions may be critical at various points during the typical 24-h operating cycle and there is a clear need to develop more realistic maximum entropy models applicable to real rather than small hypothetical networks.
2 Entropy Maximizing Design Optimization Approach
Steady state simulation is widely used in the design of water distribution networks. However, there are some important situations in which steady state modelling has weaknesses, e.g. valve operation and analysing energy consumption. Extended period simulation is more realistic. It leads to a better understanding of the characteristics e.g. due to time-varying water demands, and tank water level variations. Moreover, the optimization of pump scheduling or tank sizing and siting require extended period simulations.
Previously it was thought that if the peak daily demands were satisfied then the other operating conditions would be satisfied as well (Vamvakeridou-Lyroudia et al.
2005). However, Prasad (
2010) demonstrated that the node pressure constraints have to be considered for all loading conditions. Alperovits and Shamir (
1977) observed that the minimum demand periods have to be considered in addition to the maximum daily demand and fire flows. In addition to the fire-fighting and other emergency flows, the loading patterns that are frequently considered include:
(a).
The maximum daily demand, i.e. the peak demand over a 24-h period.
(b).
The peak hour demand that usually occurs in the evening of the maximum day.
(c).
The average daily demand, i.e. the average demand for the average day’s consumption.
(d).
The minimum daily demand, i.e. the loading pattern when water consumption is at its lowest level and the tanks refill.
Alternative hypotheses for maximizing the entropy when there are multiple operating conditions include: (a) maximizing the largest entropy value across all the operating conditions; (b) maximizing the smallest entropy value across all the operating conditions, to alleviate the worst-case performance; and (c) maximizing the sum of the separate entropies from all the operating conditions.
Collectively, the entropy values for the various operating conditions constitute an entropy vector. Maximizing the largest entropy value implies maximizing the largest element in the entropy vector. On its own, the largest entropy element provides only a partial characterization and thus may not represent the overall performance adequately. It has the potential to overestimate the resilience and, if used in design optimization, could lead to suboptimal results (Czajkowska
2016). This option yields the following objective function.
$$ \operatorname{Maximize}\;f=\mathit{\operatorname{Max}}\left({S}_k,\kern0.5em \forall k\right) $$
(1)
where
S
k
is the entropy of the
kth operating condition. Additional details on
S
k
are in the supplementary data.
On the other hand, maximizing the minimum element of the entropy vector would undoubtedly alleviate the worst-case scenario. However, it could underestimate the overall performance and, consequently, yield suboptimal or inconsistent results when used in optimization algorithms (Czajkowska
2016). The objective function based on the minimum entropy element is as follows.
$$ \operatorname{Maximize}\;f=\mathit{\operatorname{Min}}\left({S}_k,\kern0.5em \forall k\right) $$
(2)
where
S
k
is the entropy of the
kth operating condition.
Maximizing the sum of the separate entropies aims to achieve a good performance for all the operating conditions collectively.
$$ \operatorname{Maximize}\;f=\sum \limits_k{S}_k $$
(3)
where
S
k
is the entropy of the
kth operating condition.
A basic property of entropy as a measure of uncertainty is that the joint entropy of two or more independent probabilistic schemes is the sum of their separate entropies (Shannon
1948, Tanyimboh
1993: 73-77). Accordingly, for independent operating conditions, the joint entropy is the sum of the separate entropies. The appeal of this interpretation lies in the fact that it accounts for all the operating conditions. Furthermore, it does not require any additional assumptions or criteria. Therefore, viewed as a basic property of the network, the logical conclusion is that the sum of the entropies should be maximized.
This was the fundamental hypothesis of the research.
2.2 Network Design Optimization Model
Flow entropy may be included in the design optimization of a water distribution network to minimize the cost without sacrificing resilience completely. In this way, redundancy is safeguarded and deployed to the best possible advantage, to help address any unanticipated flow re-routing and short-term increases in demand. The objectives were thus cost minimization and entropy maximization. Only the initial construction cost was considered in this research. Other costs and additional factors may be incorporated relatively easily (Siew et al.
2014). Though relevant, these wider considerations were not the main focus of the investigation.
The constraints were the constitutive equations (i.e. conservation of mass and energy) and the minimum node pressure constraints. The equations for the conservation of mass and energy were satisfied by embedding the EPANET 2 hydraulic simulation model (Rossman
2000) in the evolutionary algorithm. The minimum node pressure constraints were addressed by introducing an additional objective that considers the feasibility of the solutions.
Michalewicz (
1995) classified the approaches for addressing constraints in evolutionary algorithms as: (a) repairing, (b) modifying, (c) rejecting and (d) penalizing strategies. The most common practice is to degrade infeasible solutions by applying penalties, with greater constraint violations incurring higher penalties. Excessively high penalties may confine the search to the feasible region of the solution space. However, searching through the feasible and infeasible regions improves the efficiency and yields better solutions than searching in the feasible regions only (Glover and Greenberg
1989). Designing penalty functions and calibrating the associated parameters is a complex task and requires extensive fine-tuning (Dridi et al.
2008). A penalty-free formulation was developed to obviate the difficulties.
According to the maximum entropy formalism, the entropy should be maximized subject to the relevant constraints without introducing any arbitrary assumptions (Jaynes
1957). Hence, the optimization problem may be summarized briefly as follows.
$$ \operatorname{Minimize}\ \mathrm{the}\ \mathrm{cost}\;{f}_1=\sum \limits_i^{np}{C}_i\left({d}_i,{L}_i\right) $$
(4)
$$ \operatorname{Minimize}\ \mathrm{the}\ \mathrm{node}\ \mathrm{pressure}\ \mathrm{deficits}\;{f}_2=\mathit{\operatorname{Max}}\left\langle \max \left[0,\left({H}_n^{req}-{H}_n\right)\right];\kern1em \forall n\right\rangle $$
(5)
$$ \operatorname{Maximize}\ \mathrm{the}\ \mathrm{flow}\ \mathrm{entropy}\;{f}_3=S $$
(6)
$$ \mathrm{Subject}\ \mathrm{to}:{d}_i\in D;\kern1em \forall i $$
(7)
C
i
(d
i
, L
i
) is the cost of pipe i with diameter d
i
and length L
i
while np is the number of pipes. The set D comprises the available discrete pipe diameter options. S is the flow entropy. H
n
and \( {H}_n^{req} \) are, respectively, the available and required residual heads at node n. The required head corresponds to the pressure above which the demand is satisfied in full. The decision variables are the pipe diameters. The hydraulic simulation model EAPANET 2, that ensures energy and flow conservation, also provides the nodal heads.
5 Conclusions
A methodology for flow entropy maximization in the design optimization of water distribution networks under multiple loading conditions was developed and assessed. The empirical results achieved demonstrated that the joint entropy of two or more independent loading conditions is the sum of the separate entropies. It was revealed also that no single loading condition was consistently dominant from the perspective of the flow entropy. The reason is that the critical loading conditions varied from one solution to the next and thus could not be ascertained beforehand. Maximizing the sum of the entropies was, therefore, the most logical approach. These observations are consistent with both the maximum entropy formalism (Jaynes
1957) and the formal definition of the joint entropy of independent probability schemes (Shannon
1948).
A large increase in the number of feasible solutions was achieved compared to previous investigations. It is possible, however, that in the network considered, the total number of feasible solutions is relatively small compared to the size of the solution space. It is also possible that the optimization performed mainly an exterior rather than an interior search within the feasible solution space. Thus some important challenges remain notably the effective incorporation and exploitation of infeasible solutions. Demand-driven hydraulic simulations were used in the optimization. Consequently, the flow entropy values of the infeasible solutions were misleading. Therefore, additional investigations are required. Alternative formulations of the optimization model based on pressure-driven simulation may be worth considering also.