Multi-objective optimization of water distribution networks based on non-dominated sequencing genetic algorithm

Abstract

Due to the conflict between reducing cost and improving water supply performance, how to select the appropriate pipe diameter is a current challenge. In this paper, the problem is transformed into a multi-objective optimization problem, and the evolutionary genetic optimization algorithm is used to solve the problem to determine the optimal selection of pipe diameter in the pipe network. To solve this problem, the evolutionary genetic algorithm was coupled with EPANET hydraulic simulation software in Python environment. The results show that NSGA-II and NSGA-III perform better in two typical case tests. Moreover, the increase of the objective functions will lead to an increase in the amount of data in the optimal solution set, and will affect the optimal value of each objective function. That shows that the balance between the economy and reliability of water supply can be successfully found by coupling the hydraulic model and the multi-objective optimization algorithm, which can provide an auxiliary decision for enterprises.

Introduction

Urban water supply system is an important basis for rapid urban construction and steady development, which plays an important role in ensuring sustained, rapid and sustainable economic development and ensuring people’s livelihood [1, 2]. However, with the continuous development of the society, the contradiction of water supply system is facing increasingly prominent, and gradually exposed problems [3]. Urban water supply industry development is relatively lags behind, seriously affect the healthy development of water supply and water supply safety [4], these also hinder economy high speed development, and build a well-off society in an all-round way of the target does not adapt [5].

Water distribution network (WDN) is composed of pipes, junctions, hydraulic devices and water sources, which is an important part of water supply system [6]. It is built to meet the demands of water nodes. The huge cost of building, maintaining and operating water systems means that a balance must be struck between technology and economics [7]. However, it is difficult to determine the optimal design. To get close to reality, the problem must be defined as an NP-hard problem in combinatorial form [8], which is generally impossible solved if under realistic conditions by classical optimization techniques.

In practical engineering, there are many complex problems such as nonlinear, multi dimension and so on in multi-objective optimization applications, which lead to the inability to obtain accurate optimal solution by traversing all situations. Therefore, finding an approximate optimal heuristic algorithm in a reasonable time can be used as a solution to this problem. The inspiration source of heuristic algorithm can be divided into many kinds, including (1) The swarm intelligence algorithms that imitates the behavior of animals in nature. The classical algorithm includes particle swarm optimization (PSO) [9], quantum-based avian navigation optimizer algorithm (QANA) [10], dragonfly algorithm (DA) [11]; (2) Simulating physical process, classical algorithms include simulated annealing (SA) [12]; (3) Inspired biological evolution, including non-dominated sequencing genetic algorithm (NSGA-II) [13].

At present, many scholars at home and abroad have carried out multi-objective optimization research on WDN [14]. Surco et al. constructed a multi-objective optimization model by minimizing the installation cost of WDN and the energy cost of water supply system as the objective function, the improved PSO algorithm was used to solve the problem. The results show that the results obtained by this algorithm are the same or better than those obtained in previous literature [15]. Zhang et al. constructed an optimization model of water distribution network by considering multiple factors such as hydraulic power, water quality and economy, and NSGA-II was used to solve the problem. The result shows that this method can provide good decision-making suggestions for water supply network zoning [16]. Monsef et al. compared the performance of various algorithms in solving multi-objective optimization problems. The result shows that MODE algorithm has better performance [17].

There have been many achievements in the optimization of WDN [18], but there are still some deficiencies. The optimization of the pipe network mainly considers the economy and reliability. The economic index represents the cost generated by the construction, updating and operation of the pipe network, and the reliability represents whether the demand of each junction can be met during the operation of the water distribution networks [19]. Many literature only consider the cost of pipeline updating and the requirement of nods, which is quite different from the actual situation. Water demand not only refers to the demand for water, but also needs to consider whether the pressure layout is reasonable and whether the water quality is up to standard. Therefore, this paper will consider multiple indicators to build a three-objective optimization model to meet the actual needs of WDN optimization. By considering more objective functions and solving them, it can provide enterprises with auxiliary decisions that meet the actual business needs.

Therefore, the main purpose of this study is to study the use of evolutionary genetic algorithm to determine the selection of pipe diameter during pipe network reconstruction, and to find a balance between the economy and reliability of water supply. Therefore, the organizational structure of the manuscript is as follows: "Introduction", which introduces the research background, research significance and research progress of the paper; "Method", including the explanation of simulation model, optimization algorithm and optimization model; "Results and discussion" expresses and discusses the results of the model; Finally, "Conclusion" summarizes the work of this paper and discusses possible future research directions.

Materials and methods

Optimization algorithms

NSGA-II is a landmark algorithm in the field of multi-objective optimization [13]. NSGA-II uses the method of calculating the crowding distance to replace the sharing function to improve NSGA, which ultimately significantly reduces the time complexity of the algorithm [20]. Meanwhile, as NSGA-II adopts the strategy of retaining excellent solutions, the algorithm performance increases. The NSGA-II algorithm flow chart is shown in Fig 1.

[Figure omitted. See PDF.]

The fundamental difference between NSGA-III and NSGA-II lies in the different selection methods when facing individuals of the same non-dominant rank. When NSGA-II is faced with individuals of the same non-dominant rank, it preferentially selects individuals with larger crowding distance. On the other hand, NSGA-III selects individuals based on reference points and has better convergence and distribution in the face of multiple targets [21].

Simulation model

EPANET is an open source software which can be used to simulate the operation of WDN. Simulation of hydraulic and water quality characteristics is the basic basis and important tool for design, operation and management of WDN. As a set of excellent free software with complete functions, friendly interface and easy to use, EPANET has been widely used, becoming the core of many commercial software, and also providing convenience for scientific research of water distribution system. The software can be downloaded at https://www.epa.gov/water-research/epanet..

Optimization problem

Selecting a larger pipe diameter can reduce the water head loss and increase the pressure of each node, but the cost is high. Selecting a smaller pipe diameter can save costs, but may cause insufficient water pressure at the water point. Therefore, the optimization problem of pipe network reconstruction is transformed into a multi-objective optimization problem with pipe diameter as an independent variable, which is solved by combining EPANET and evolutionary genetic algorithm. The Fig 2 shows the structures of the NSGA coupled with the EPANET hydraulic simulation and their connections.

[Figure omitted. See PDF.]

The design problem of WDN is transformed into an optimization problem taking pipe diameter as decision variable. The objective function is divided into economic index and reliability index, the economic index is the minimum total cost of the project [22], while the reliability index includes meeting the requirements of the head of each node [23], the sum of the surplus head of each node, and the variance of the surplus head of each node. At the same time, the hydraulic model also needs to consider the continuity equation of nodes, the energy balance equation of pipe network and the pressure drop equation of pipe segment. The constraint conditions include consistent flow in and out of pipe nodes, no negative pressure at each node, and pipeline energy balance.

The first objective function is to minimize the total cost of WDN reconstruction, the equation can be written as(1)where D_i and L_i represent the diameter and length of pipe i, and C_i represents the construction cost of pipe i.

The second objective function is to minimize the sum of surplus water heads at each node of the WDN, the more obvious it is, the less energy is wasted due to water supply pressure. The equation can be written as(2)(3)where SH_i represents the surplus water head of the node i. H_act and H_demand represent the actual water pressure and demand water pressure of the node respectively.

The third objective function is the lowest variance of the surplus head at each node. In this way, the uneven distribution of water pressure can be avoided, which will lead to excessive pressure at some nodes and pipe explosion. The equation can be written as(4)where Var(SH_i) represents the variance of the surplus water head.

The constraint equation includes the continuity of each node and the energy balance of the WDN. The equation can be written as(5)(6)(7)where h_ij represents the head difference between nodes i and j, and Q_in and Q_out represent the flow into and out of the node, Q_d represents the demand at the node.

All experiments were fairly executed under the same conditions on a personal computer with Intel Core i-9700, 3.0 GHz CPU, and 16 GB memory in the windows 10 operating system using Python3.6. The integrated development environment is PyCharm, and the hydraulic model calls the secondary development interface of EPANET.

Results and discussion

In order to verify the effectiveness of the optimization algorithms in examples, the New York Tunnels network (NYN) and the Hanoi network (HN) were selected for testing. The results can be compared with those of many literature. These cases can be downloaded at http://emps.exeter.ac.uk/engineering/research/cws/resources/benchmarks/.

Test results of optimization algorithm in NYN

The NYN was a gravity water supply system, the water distribution network consists of 1 reservoir, 20 junction nodes and 21 pipes. The network topology is shown in Fig 3.

[Figure omitted. See PDF.]

Table 1 shows the detailed information of water requirement, minimum head requirement, length and diameter of each pipe of NYN.

[Figure omitted. See PDF.]

It is worth mentioning that this case is not to replace the pipe directly, but to add the pipe beside the original pipe and lay it in parallel. A total of 15 pipe diameters are available for selection in the optimization scheme. The available pipe diameters and unit cost of the pipe diameters are shown in Table 2.

[Figure omitted. See PDF.]

The optimal solution set is shown in Fig 4. The result shows that the lowest total cost, the average and variance of surplus water head of all nodes obtained by RVEA algorithm are $40462400, 6.03 m and 7.09 m, respectively. Those obtained by awGA algorithm are $38637600, 6.01 m and 3.63 m, respectively. Those obtained by NSGA-II algorithm are $39204000, 6.01 m and 2.04 m, respectively. Those obtained by NSGA-III algorithm are $41776400, 5.96 m and 2.32 m, respectively. If only the cost of the WDN reconstruction is considered, the result of awGA algorithm is the best, and that of NSGA-III algorithm is the worst. At the same time, the number of solution sets obtained by RVEA algorithm is far less than other algorithms.

[Figure omitted. See PDF.]

Test results of optimization algorithm in HN

HN was proposed by Fujiawara and Khang [24]. It is a network that consists of 1 reservoir, 31 junction nodes and 34 pipes. The optimization goal is to determine the diameter of 34 pipes, so that the reconstruction of the network can not only meet the minimum cost, but also meet the pressure requirement that each node has 30 m surplus water head. Fig 5 shows the topology of the Hanoi network. In previous single objective optimization studies, the minimum total cost of the Haoni network is $6.081 × 10⁶. In this scheme, the average and variance of surplus water head are 41.59 m and 179.85 m.

[Figure omitted. See PDF.]

Table 3 shows the detailed information of water requirement, minimum head requirement, length and diameter of each pipe in each node of HN.

[Figure omitted. See PDF.]

In the pipe network reconstruction scheme, a total of 6 pipe diameters can be selected. The available pipe diameters and unit cost of the pipe diameters are shown in Table 4.

[Figure omitted. See PDF.]

The optimal solution set is shown in Fig 6. The result shows that the lowest total cost, the average and variance of surplus water head of all nodes obtained by RVEA algorithm are $7396154.77, 46.96 m and 121.19 m, respectively. Those obtained by awGA algorithm are $6205277.15, 40.21 m and 126.34 m, respectively. Those obtained by NSGA-II algorithm are $6488309.01, 36.05 m and 72.33 m, respectively. Those obtained by NSGA-III algorithm are $6444111.47, 36.16 m and 73.7 m, respectively. If only the cost of the WDN reconstruction is considered, the result of awGA algorithm is the best, and that of RVEA algorithm is the worst. At the same time, the number of solution sets obtained by RVEA algorithm is far less than other algorithms. Although the minimum WDN reconstruction cost of algorithm awGA is lower than that of NSGA-II and NSGA-III, the lowest value of the other two objective functions is much higher than that of NSGA-II and NSGA-III.

[Figure omitted. See PDF.]

The comparison of four algorithms in the two cases is shown in Fig 7. Six parameters of Object1 (Reconstruction cost), Object2 (Surplus head), Object3 (Variance of surplus head), HV, Spacing and execute time are selected for comparison, and the four algorithms are sorted. Object1, Object2 and Object3 refer to the minimum value of the objective function. It can be seen that the RVEA algorithm is superior to other algorithms in terms of operation efficiency and other indicators. NSGA-II algorithm performs well in other indicators except for long operation time. NSGA-III seems to be relatively balanced, with no particularly dominant indicators or particularly backward indicators.

[Figure omitted. See PDF.]

Statistical analysis between the pair’s algorithms

Due to the existence of multiple objective functions in multi-objective optimization problems, it is difficult to give the weight of each objective function to determine the optimal solution in solving practical problems, so it is difficult to compare the results of each algorithm intuitively. Therefore, we use the overall effectiveness analysis to compare and analyze each algorithm, run each algorithm 30 times under the same operating conditions, select the HV (Hypervolume) index and Spacing index of each algorithm in the optimal solution set, and use the and use Wilcoxon rank sum test to compare each algorithm. It is worth noting that in order to save the running time of the program, the population number and the maximum evolutionary algebra in the optimization algorithm are reduced from 300 to 100.

The Wilcoxon rank sum test results are shown in Table 5. In the case of Haoni, as the number of iterations and population decreases, the RVEA algorithm does not get the optimal solution set in the Haoni case. In terms of HV and Spacing indexes, awGA is inferior to NSGA-II and NSGA-III, but it is worth noting that the difference between awGA and NSGA-II in S does not pass the significance test. In the case of NY, it can be seen that the RVEA algorithm is inferior to other algorithms, which is also reflected in the previous solution set, possibly because RVEA has less solution sets. The performance of awGA algorithm is not as good as that of NSGA-II and NSGA-III. In comparison between NSGA-II and NSGA-III algorithms, NSGA-II is better than NSGA-III in HV index, but the result is opposite in the Spacing index.

[Figure omitted. See PDF.]

Compared with existing literature, this paper considers three-objective optimization, and considers the lowest variance of surplus head more than other literature. In the original two-objective optimization, there may be extreme cases where one head node is extremely high and the other nodes are extremely low, which will lead to leakage and pipe explosion events. After considering the variance of the remaining head, not only the average of the remaining head of each node is low, but also the difference of the remaining head of each node is small. The water head of a node will not be too high to lead to pipe explosion and other events.

At the same time, most of the previous literature carried out hydraulic simulation based on EPANET 2.0 or earlier version, which supported demand-driven, and the pressure in the system depended on the demands of nodes. In the case that the demands of nodes were known and met, the hydraulic equation was solved. This assumption is reasonable under the conditions of normal operation, can also be applied to network design, but in actual engineering, there are many factors can cause and generate low pressure phenomenon, such as fire water, power and leakage, etc., so the pressure driven simulation more reasonable, existing paper confirmed in pipeline leakage pressure drive than demand drive more real and effective.

In the test comparison of several typical WDN cases, the performance of NSGA-II and NSGA-III is better than that of other algorithms, and the comparison between NSGA-II and NSGA-III cannot clearly find which algorithm is better. HV and Spacing are selected as indicators for algorithm performance comparison, and Wilcoxon signed-rank test method is used to test the significance. The results show that NSGA-II is better in HV and NSGA-III is better in Spacing. This should be because NSGA-III has a different mechanism from NSGA-II in sorting and can obtain more decentralized results, which can also be seen in Fig 4 and Fig 6.

In the multi-objective optimization of water distribution network reconstruction, the selection of objective functions, constraint conditions and variables are particularly important, and different selection results may be quite different. In this paper, the selection of two typical water distribution networks cases are relatively simple, only consider the pipe diameter change and the choice of replication of the pipe diameter. In practical engineering, the switch of the valve, pump station of power are significantly influence the network running status, such as when need to consider these factors, the variables will increase a lot, model also become more complex. In the future, more complex pipe network close to the actual project will be selected for testing to verify the effectiveness of the algorithm. At the same time, the multi-objective optimization algorithm is not only suitable for water distribution networks reconstruction, but also for the layout of pressure monitoring points, water supply networks model parameter calibration, pump station operation optimization scheduling and other business requirements. These will be further studied and verified by examples.

Conclusions

The reconstruction of the old water supply pipe network is one of the most common projects in cities. The head loss in the water supply system is closely related to the size of the pipe diameter., the improvement of the water supply performance will inevitably lead to an increase in the cost. Therefore, how to find a balance between the economy and the reliability of the water supply system is one of the current challenges. In this study, we developed an optimization simulation model by coupling the evolutionary genetic algorithm and EPANET simulation model, defined the objective function, constraint conditions, and variable selection, and finally found the best pipe diameter selection scheme that meets the economy and reliability of water supply. The results show that the balance between economy and reliability of water supply can be found in the results obtained by the model. As two classic algorithms, NSGA-II and NSGA-III perform well in optimization performance

Future research should focus on how to select the size of pipe diameter when the demand for the water supply system is uncertain. At the same time, the selection of pipe materials is also worth considering. This is a challenging problem because if the demand in the water supply system is not clear, it is difficult to determine the pressure demand and water demand of the nodes.

Citation: Tao Y, Yan D, Yang H, Ma L, Kou C (2022) Multi-objective optimization of water distribution networks based on non-dominated sequencing genetic algorithm. PLoS ONE 17(11): e0277954. https://doi.org/10.1371/journal.pone.0277954

About the Authors:

Yi Tao

Roles: Conceptualization, Data curation, Methodology, Resources, Validation, Writing – original draft

Affiliation: Xi’an Aerospace Automation Co., Ltd., The 6th Academy of China Aerospace Science and Industry Corporation, Xi’an, Shaanxi, China

Dongfei Yan

Roles: Conceptualization, Formal analysis, Methodology, Resources, Software, Supervision, Writing – original draft

E-mail: [email protected]

Affiliation: Xi’an Aerospace Automation Co., Ltd., The 6th Academy of China Aerospace Science and Industry Corporation, Xi’an, Shaanxi, China

https://orcid.org/0000-0002-3495-0704

Huijia Yang

Roles: Formal analysis, Investigation, Validation, Writing – review & editing

Affiliation: Xi’an Aerospace Automation Co., Ltd., The 6th Academy of China Aerospace Science and Industry Corporation, Xi’an, Shaanxi, China

Lingna Ma

Roles: Conceptualization, Project administration, Resources, Validation

Affiliation: Xi’an Aerospace Automation Co., Ltd., The 6th Academy of China Aerospace Science and Industry Corporation, Xi’an, Shaanxi, China

Chen Kou

Roles: Project administration, Resources, Validation, Writing – review & editing

Affiliation: Xi’an Aerospace Automation Co., Ltd., The 6th Academy of China Aerospace Science and Industry Corporation, Xi’an, Shaanxi, China

References

1. Marchi A, Dandy G, Wilkins A, Rohrlach H. Methodology for Comparing Evolutionary Algorithms for Optimization of Water Distribution Systems. J Water Res Plan Man. 2014;140(1):22–31.

2. Jain P, Khare R. Multi-objective Rao algorithm in resilience-based optimal design of water distribution networks. Water Supply. 2022;22(4):4346–60.

3. Creaco E, Pezzinga G. Multiobjective Optimization of Pipe Replacements and Control Valve Installations for Leakage Attenuation in Water Distribution Networks. J Water Res Plan Man. 2015;141(3).

4. Walters GA, Halhal D, Savic D, Ouazar D. Improved design of "Anytown" distribution network using structured messy genetic algorithms. 1999;1(1):23–38.

5. Farmani R, Walters G, Savic D. Evolutionary multi-objective optimization of the design and operation of water distribution network: total cost vs. reliability vs. water quality: J Hydroinform. 2006; 8. 165–179.

6. Giustolisi O, Berardi L. Water distribution network calibration using enhanced GGA and topological analysis. J Hydroinform. 2011;13(4):621–41.

7. Choi YH. Development of optimal water distribution system design and operation approach considering hydraulic and water quality criteria in many-objective optimization framework. J Comput Des Eng. 2022;9(2):507–18.

8. Sedki A, Ouazar D. Hybrid particle swarm optimization and differential evolution for optimal design of water distribution systems. Adv Eng Inform. 2012;26(3):582–91.

9. Jafari-Asl J, Sami Kashkooli B., Bahrami M. Using particle swarm optimization algorithm to optimally locating and controlling of pressure reducing valves for leakage minimization in water distribution systems. Water Resour Manag. 2020; 6:64.

10. Zamani H, Nadimi-Shahraki MH, Gandomi AH. QANA: Quantum-based avian navigation optimizer algorithm. Eng Appl Artif Intel. 2021; 104(989):104314.

11. Jafari-Asl J, Azizyan G, Monfared S, Rashki K, Andrade A. An enhanced binary dragonfly algorithm based on a V-shaped transfer function for optimization of pump scheduling program in water supply systems (case study of Iran). Eng Fail Anal. 2021; 123:105323.

12. Hwang CR. Simulated annealing: Theory and applications. Acta Appl Math. 1988; 12(1):108–111.

13. Deb. K.; Pratap. A.; Agarwal. S.; Meyarivan. T. “A fast and elitist multiobjective genetic algorithm NSGA-II”. IEEE Trans. Evol. Comput. 2002; 6, 182–197.

14. Xia W, Wang S, Shi MJ, Xia Q, Jin WT. Research on partition strategy of urban water supply network based on optimized hierarchical clustering algorithm. Water Supply. 2022;22(4):4387–99.

15. Surco DF, Macowski DH, Cardoso FAR, Vecchi TPB, Ravagnani MASS. Multi-objective optimization of water distribution networks using particle swarm optimization. Desalin Water Treat. 2021;218:18–31.

16. Zhang K, Yan HX, Zeng H, Xin KL, Tao T. A practical multi-objective optimization sectorization method for water distribution network. Sci Total Environ. 2019;656:1401–12. pmid:30625668

17. Monsef H, Naghashzadegan M, Jamali A, Farmani R. Comparison of evolutionary multi objective optimization algorithms in optimum design of water distribution network. Ain Shams Eng J. 2019;10(1):103–11.

18. Palod N, Prasad V, Khare R. Reliability-based optimization of water distribution networks. Water Supply. 2022;22(2):2133–47.

19. Zarei N, Azari A, Heidari MM. Improvement of the performance of NSGA-II and MOPSO algorithms in multi-objective optimization of urban water distribution networks based on modification of decision space. Appl Water Sci. 2022;12(6).

20. Candelieri A, Ponti A, Giordani I, Archetti F. Lost in Optimization of Water Distribution Systems: Better Call Bayes. Water-Sui. 2022;14(5).

21. Sambito M, Piazza S, Freni G. Stochastic Approach for Optimal Positioning of Pumps As Turbines (PATs). Sustainability-Basel. 2021;13(21).

22. Bi WW, Chen MJ, Shen SW, Huang ZY, Chen J. A Many-Objective Analysis Framework for Large Real-World Water Distribution System Design Problems. Water-Sui. 2022;14(4).

23. Mangalekar RD, Gumaste KS. Residential water demand modelling and hydraulic reliability in design of building water supply systems: a review. Water Supply. 2021;21(4):1385–97.

24. Fujiwara O, Khang DBJWRR. A two-phase decomposition method for optimal design of looped water distribution networks. Water Resour Res. 1990;26(4):539–49.