Optimal pipe-sizing design of water distribution networks using modified Rao-II algorithm

EA

evolutionary algorithm

WDN

water distribution network

GA

genetic algorithm

ACO

ant colony optimization

PSO

particle-swarm optimization

DDA

demand-driven analysis

PDA

pressure-driven analysis

HDB-SA-DDA

head deficit-based self-adaptive demand-driven analysis

HDB-SA-PDA

head deficit-based self-adaptive pressure-driven analysis

HFDB-SA-PDA

head and flow deficit-based self-adaptive pressure-driven analysis

DN

demand nodes

N

pipes

Y

loops

C_T

cost of network in monetary unit

Π_j

set of pipes connected to node j

Λ_y

pipes in loop y

J

number of nodes

c (⁠⁠)

is unit cost of pipe n having diameter

length of pipe n

discharge of pipe n

required nodal demand

available nodal demand

head loss in pipe n

E_pmp

head developed by a pump

Λ_p

pumps in loop y

available head at node j

minimum desirable head at node j

D_min and D_max

minimum and maximum diameter of available pipes, respectively

Z

total cost of network including penalty cost

C_P

penalty cost

PM or p

penalty coefficient

cost of network with all pipes as largest available commercial diameter

cost of pipe n with added penalty cost due to minimum pressure constraint at node j

cost per unit length of pipe n

flow in pipe n

total flow into node

PWF

present worth factor

cu_e

unit cost of the energy in monetary units per kWh

w

specific weight of water (9,810 N/m³)

η

overall efficiency

t_p

total time of the pump operation in a year in hours

X_m,best,i

best values for any iteration i, for a variable m

X_m,worst,i

worst values for any iteration i, for a variable m

X′_m,k,i and X_m,k,i

updated and old value for any variable m

r_1,m,i, r_2,m,i

random numbers

k and l

any randomly picked solution from the population set

FSS

full search space

RSS

reduced search space

DSSR

dynamic search space reduction

NFE

number of function evaluations

DNA

data not available

GA-ILP

genetic algorithm–integer linear programming

NSGA-II

non-dominated sorting genetic algorithm

MA

memetic algorithm

CFO

central force optimization

CSA

crow search algorithm

ICSA

improved crow search algorithm

A water distribution network (WDN) is one of the costliest components of any water supply project (Walski et al. 2003); therefore, the cost optimization of a WDN design is required. The simplest WDN optimization problem consists of selecting the most appropriate diameter for each pipe of the network from the set of available discrete pipe-diameters to minimize the network cost. The constraints of satisfying the pressure requirements along with the satisfaction of continuity equations at all the nodes and energy equations for all loops are imposed (Alperovits & Shamir 1977; Wu & Walski 2005; Kadu et al. 2008; Jain & Khare 2021; Palod et al. 2021; Gangwani et al. 2023, 2024). Researchers have suggested using various mathematical programming-based techniques to obtain the least-cost design of WDNs from the 1960s to 1990s. These techniques, called ‘deterministic search techniques’, begin the search with a solution in the search space and progress to a better solution in an iterative manner using some mathematical expressions. Such searches frequently result in a local optimal solution (Bhave 2003).

Several EAs based on different metaphors have been developed over the last three decades for the least-cost design of networks. The search in an evolutionary algorithm (EA) starts from many randomly chosen points in the search space, which move towards better solutions by mimicking the metaphor, and terminates when the search is complete. The EAs are observed to have a global search capacity to achieve global optimal and several near-optimal solutions. The main disadvantage of EAs is the high computational effort, as shown by Coelho & Andrade-Campos (2012). Mostly, the EA uses certain constants besides the population size and the number of generations to mimic the metaphor; for example, the genetic algorithm (GA) uses cross-over and mutation probabilities (Savic & Walters 1997; Wu & Simpson 2001; Deb et al. 2002; Kadu et al. 2008; Siew & Tanyimboh 2012; Abdy Sayyed et al. 2019); ant colony optimization (ACO) uses the rate of pheromone evaporation and the pheromone reward factor (Maier et al. 2003; Zecchin et al. 2006; Zecchin et al. 2007; Ostfeld & Tubaltzev 2008); and particle-swarm optimization (PSO) uses inertia weight, cognition rate, and social learning rate (Suribabu & Neelakantan 2006; Rao et al. 2017). These constants must be fine-tuned for case-specific problems, which increases computational efforts and is also sometimes tedious. Recent advancements are, therefore, towards the development of parameter-less EA that either adjusts required algorithm-specific constants internally or uses their fixed values.

Gajghate & Mirajkar (2021) used a parameter-less Jaya algorithm (Rao 2016) for the optimal design of irrigation pipe networks. The diameters are initially obtained using the critical path method and then this is optimized using both linear programming (LP) and the Jaya algorithm, and it was concluded that the Jaya algorithm can reach a better-optimized solution than LP. Palod et al. (2020) used the same Jaya algorithm for the design of WDNs and observed that this parameter-less algorithm reduces the computational effort and is efficient. Palod et al. (2021) compared two parameter-less EAs – Rao-I and Rao-II (Rao 2020) – for the optimal design of WDNs and found that Rao-II is better compared with Rao-I. Jain & Khare (2021) also used the Rao-II algorithm for the design of WDNs.

The WDN optimization problem has constraints related to the satisfaction of flow continuity at nodes, energy equations for loops, and minimum pressure availability at nodes. The first two conditions are tackled in EA by involving a hydraulic solver. However, the third constraint, i.e., minimum pressure availability at nodes, is to be externally satisfied in the EA-based optimization models. Penalty approaches are mostly used to overcome this situation. The penalty is applied proportionately to the constraint violation amount using a penalty coefficient to make infeasible solutions inferior to feasible solutions. The selection of a proper penalty coefficient for the penalty function is a key to improving the efficiency of EA-based optimization models. A larger coefficient imposes a larger penalty and may quickly eliminate infeasible solutions from the population; thus, these solutions may not be given enough opportunity to improve further. Conversely, a smaller penalty may allow the infeasible solutions to remain in the population for a longer duration, thereby delaying the convergence or converging at an infeasible solution. This renders the penalty an external parameter that requires fine-tuning for proper convergence of the objective function as suggested by Abebe & Solomatine (1998) and van Dijk et al. (2008). On the other hand, a self-adaptive penalty does not require fine-tuning of the penalty coefficient as suggested by Kadu et al. (2008), Abdy Sayyed et al. (2019), Jain & Khare (2021), and Gangwani et al. (2023, 2024).

The penalty cost is thus dependent on the penalty coefficient and the amount of pressure deficit. The maximum pressure deficit among all nodes in the network is determined and multiplied by the penalty coefficient to obtain the penalty cost (Palod et al. 2020, 2021), or a penalty due to the pressure deficit at all nodes can be added (Abdy Sayyed et al. 2019) to obtain the final penalty. Kadu et al. (2008) recommended that for a pressure deficit node, the penalty multiplier must be proportional to the capitalized energy cost required at that node to lift the unit quantity of water through a unit head. Further, the pressure deficit can be calculated using demand-driven analysis (DDA) or pressure-driven analysis (PDA). Abdy Sayyed et al. (2019) showed that DDA overestimates the penalty as in this case it is assumed that the demands are fully satisfied, and pressure is determined accordingly. This leads to a larger pressure deficiency than required at the nodes. In contrast to this, PDA determines the pressure deficit according to the partial flow conditions and hence may result in lower pressure deficit values. Further, they recommend using a combined flow and pressure deficit-based penalty. Jain & Khare (2021) also showed the superiority of PDA over DDA by comparing the optimal costs obtained using the Rao-II algorithm for some benchmark problems. Recently, Gangwani et al. (2024) also used a combined flow and pressure deficit-based penalty in GA to obtain a better solution for a two-source network from Kadu et al. (2008). Although parameter-less EAs avoid the fine-tuning of a large number of problem-specific constants as required in other EAs, the penalty multiplier needs to be fine-tuned for faster convergence.

The main objective of this paper is to explore the application of Rao-II with self-adaptive penalty approaches. Three approaches are considered herein: (1) a self-adaptive penalty approach (Kadu et al. 2008) in which head deficit is obtained using DDA, abbreviated as head deficit-based self-adaptive demand-driven analysis (HDB-SA-DDA); (2) a self-adaptive penalty approach (Abdy Sayyed et al. 2019) in which head deficit is obtained using PDA, abbreviated as head deficit-based self-adaptive pressure-driven analysis (HDB-SA-PDA); and (3) a self-adaptive combined flow and head deficit penalty approach (Abdy Sayyed et al. 2019) in which deficit is obtained using PDA, abbreviated as head and flow deficit-based self-adaptive pressure-driven analysis (HFDB-SA-PDA). The application of the methodology is demonstrated with a two-source network from Kadu et al. (2008) and a Ramnagar network of Nagpur city from Gangwani et al. (2024).

The remainder of the paper consists of the description of the general WDN optimization problem to be solved by EA, a brief literature on constraint-handling through different types of penalties, the Rao-II algorithm and proposed modifications, application to benchmark problems, comparison of solutions, and conclusions of the study.

Martínez-Bahena et al. (2018) used the death-penalty approach in GA in which infeasible solutions are discarded. While applying the GA operators to the initial population, a tournament selection method was used in which only feasible solutions were selected. Further, after the cross-over and mutation, a feasibility check was applied, and infeasible solutions were discarded. Only feasible solutions were added to the new population until the population size was obtained.

Sangroula et al. (2022) suggested applying a penalty at all the nodes. Two different penalty coefficients, PM1 for nodes with pressure above the required pressure and PM2 for nodes with deficiency in pressure, are used to calculate the penalty cost. The values of PM1 and PM2 are case-specific and were obtained by trial and error as 0.02 and 1.9.

Montesinos et al. (1999) considered a penalty based on the number of nodes having constraint violations instead of degree of constraint violation. The severity of failure is better indicated by the degree of constraint violation. In fact, DDA overpredicts the number of nodes with pressure deficiency as compared with PDA (Abdy Sayyed et al. 2019). Deb & Agrawal (1999) suggested a niched penalty based on the comparison in tournament selection in which two feasible solutions are compared based on the cost, the two infeasible solutions are compared based on their constraint violation, and the feasible solution is considered better than infeasible solution in the tournament.

In Equation (19), the best and worst values for any iteration i, for a variable j, are represented by X_m,best,i and X_m,worst,i, respectively. X′_m,k,i and X_m,k,i represent the updated and old values for any variable m; r_1,m,i and r_2,m,i are random numbers distributed uniformly, and the range of r_1,m,i and r_2,m,i is (0,1); l is any randomly picked solution from the population set, and X_m,l,i represents its value for variable m at the ith iteration. Solutions k and l are compared based on the total cost. Suppose solution l is better than k (total cost of solution l < total cost of solution k). In that case, information must be exchanged from l to k, and hence, the term X_m,k,i or X_m,l,i is simplified to X_m,l,i and the term X_m,l,i or X_m,k,i is simplified to X_m,k,i. This delineates the transfer of information from a superior solution to an inferior solution. In contrast to this, if the total cost of solution k < solution l, the term X_m,k,i or X_m,l,i is simplified to X_m,k,i and the term X_m,l,i or X_m,k,i is simplified to X_m,l,i . Once the updated values of all solutions in the population are determined, a completely fresh population set is created. The updated values are compared with the previous values of the solution, and a better-performing solution (solution with minimum total cost) is directed to the next iteration. This process of updating and comparing the solutions is continued until the termination criterion is reached, which is generally a fixed number of iterations or when, over a larger number of iterations, no improvement is observed in the fitness value of the solutions. For the present case, the former serves as the termination criterion.

The Rao-II algorithm is a two-step methodology that identifies the best and worst solution from the entire population. Further, it evolves the solution to move towards the best solution and away from the worst solution. In the second step, a comparison is made between the old and updated, i.e., the evolved solution. The better-performing solution is sent to the next iteration. It is essential to remember that for the optimal design of WDN, performance in the Rao-II algorithm solely depends on the total cost (total cost = network cost + penalty). While applying the self-adaptive penalty, care must be taken to keep the infeasible solutions near the feasible–infeasible front more active by applying just enough penalty (Wu & Walski 2005). It was observed that the penalty cost may be significantly less if the constraint violation is very low. Therefore, some solutions, though infeasible, may have lesser total cost than feasible solutions. This leads to the selection of an infeasible solution over a feasible solution. Once an infeasible best is identified, the entire population starts moving towards this infeasible best and ultimately becomes infeasible. Such situations can be avoided by selecting a higher penalty coefficient or varying the penalty coefficient as iteration progresses. Herein, a different approach is suggested to overcome the aforementioned drawback. Two modifications are suggested for the Rao-II algorithm.

• 1. The entire population is segregated into two groups: the feasible (penalty = 0) and infeasible group (penalty ≠ 0). It is suggested that the minimum cost solution be selected as the best solution from the group of feasible solutions. This approach ensures that the best solution consistently results in a feasible solution. It is important to note that the entire population may be initially infeasible with larger penalty values. This may be due to the random generation of solutions. In such a case, a minimum total cost solution from the group of infeasible cost solutions is selected. Penalty decreases and feasible solutions appear with the progress of the algorithm.

• 2. The Rao-II algorithm compares the updated solution with the original one based on the total cost value only to pass it on to the next iteration. Hence, an infeasible solution with a lower total cost is selected over a feasible solution with a higher total cost during the comparison process. To rectify this, the following changes are made:

• • a. Between two infeasible solutions, the least total cost solution is selected and sent to the next iteration.

  • b. Between an infeasible (penalty ≠ 0) and feasible solution (penalty = 0), a feasible solution is selected and sent to the next iteration.

  • c. Between two feasible solutions, the least total cost solution is selected and sent to the next iteration.

• This step guarantees the alignment of feasible solutions with the advancement of the algorithm.

The platform used for the coding of the Rao-II algorithm for optimization of WDN is Python, and it is integrated with EPANET 2.0 with the help of a toolkit for hydraulic simulation. As EPANET 2.0 does not have a PDA facility, a separate C code proposed by Gupta et al. (2018) is used to modify the input file to be used in PDA. The capacity of the computer used for running the code is Intel(R) Core (TM) i7-10510 U, 8 GB RAM, CPU @ 2.30 GHz.

Initially, the Rao-II algorithm was used with different penalty approaches. The three approaches HDB-SA-DDA, HDB-SA-PDA, and HFDB-SA-PDA as given in Equations (14) and (15) were applied for the optimal design of the Kadu network. Initially, a few runs were performed to fix the population size and the number of generations. A population size of 75 and 1,000 iterations as the termination criteria were fixed to compare the convergence characteristics. Fifteen trial runs were performed, and the best obtained in one of the 15 trials was considered. With Rao-II, HDB-SA-DDA and HDB-SA-PDA converged to feasible solutions; however, HFDB-SA-PDA converged to a non-feasible solution. The head deficit was noted at six nodes in the best solution. The head deficit was 0.18 m at node 6, 0.19 m at node 12, 0.28 m at node 16, 0.21 m at node 18, 0.79 m at node 23, and 0.49 m at node 26. The cost of the network was Rs. 123,499,991 and the penalty cost was Rs. 956,552. The total cost was Rs. 124,456,543. Moreover, none of the solutions from the final population was found feasible. This indicated the necessity of modifying the Rao-II algorithm as all the solutions were observed to move towards the infeasible solution. Considering this possibility in other penalty-based approaches, the modified Rao-II algorithm was applied. However, for the Kadu network, modified Rao-II is used with HFDB-SA-PDA, and it resulted in improved convergence.

Pipe diameters obtained in the best solution with three different penalties are shown in Table 1.

The Ramnagar network shown in Figure 2(b) was first used by Gangwani et al. (2024) to illustrate their design methodology. The network consists of 375 pipes, 292 junctions, and a ground service reservoir with a lowest supply level of 327.205 m. The design diameters for the network must be selected from 16 commercially available diameters, as shown in Table S3, which leads to a total search space of 16,375. The pipe and node details of the network are shown in Tables S4 and S5, respectively. The penalty multiplier, p, for the Ramnagar network is calculated as 145,220 using Equations (12) and (13), based on the prevailing unit energy charges of Rs. 5.4/kWh.

Five trial-runs were performed with a population size of 500 and 4,000 iterations as the termination criteria to obtain the convergence curve of the modified Rao-II algorithm. Pipe diameters obtained from three different penalties are shown in Table S6. A comparison of results as obtained by GA (Gangwani et al. 2024) and modified Rao-II for the Ramnagar network is shown in Table 4. GA, using the HFDB-SA-PDA penalty approach, provided the optimal cost of the network as Rs. 37,837,223 and Rs. 34,289,227 with FSS and DSSR, respectively. The modified Rao-II algorithm with FSS resulted in better solutions than that obtained by GA using FSS and DSSR for the HDB-SA-DDA and HFDB-SA-PDA penalty approaches as shown in Table 4. The minimum cost solution is obtained as Rs. 34,166,161 by modified Rao-II with HFDB-SA-PDA. Modified Rao-II with HDB-SA-PDA obtained a 8.98% cheaper solution than GA with FSS. When compared with GA-DSSR, modified Rao-II obtained a solution with only 0.438% higher cost. However, it cannot be overlooked that only five trial runs are performed in the present work, and hence, there might be a possibility to obtain a cheaper solution than reported here if a greater number of trial runs are performed. The NFEs required by modified Rao-II are on the higher side when compared with GA. Figure 3(b) shows the convergence curve obtained for the Ramnagar network.

Thus, it can be stated that penalty approaches play an important factor in determining the efficiency of an EA in terms of both network cost and computational time. The network cost could be further reduced by increasing the number of iterations or trials, subsequently increasing the computational time. However, for a large-size network, incorporating search-space reduction methodology could be more beneficial to obtain the optimal solution with reasonable computational efforts.

The self-adaptive penalty approaches as suggested by many researchers for constraint handling do not require fine-tuning of penalty coefficients. Three different self-adaptive penalty approaches used earlier by researchers are proposed herein to improve the performance of the parameter-less Rao-II algorithm. The Rao-II algorithm is improved herein to avoid convergence to the infeasible solutions. The modified Rao-II algorithm prioritizes the feasible solutions over infeasible solutions during both the evolution and the selection process. The modified Rao-II algorithm was then tested on a real-life network consisting of 375 pipes. For this network, the modified Rao-II algorithm was observed to be a better performer when compared with GA. Further, when the number of trials is increased to 100 for the Kadu network, the Rao-II algorithm obtained the minimum cost solution of Rs. 124,963,610, which does not feature in the literature so far. The modified Rao-II algorithm also converges to a lesser optimal cost than given in the literature. This highlights the potential that the modified Rao-II algorithm holds in obtaining the optimal solution. The modified Rao-II algorithm can be further improved by amalgamating it with search-space reduction techniques.

All relevant data are included in the paper or its Supplementary Information.

The authors declare there is no conflict.