# Using a Genetic Algorithm with a Mathematical Programming Solver to Optimize a Real Water Distribution System

^{1}

^{2}

^{3}

^{*}

## Abstract

**:**

## 1. Introduction

## 2. Water Distribution Problem (Case Study)

## 3. Solution Methodology

#### 3.1. Optimization Model

#### 3.2. Constraint Satisfaction Model

#### 3.3. Solution Strategy

- Add new storage tanks with appropriate characteristics at points in the network where the minimum pressure is not reached. The benefit of implementing storage tanks with gravity water distribution is that it reduces or eliminates the number of necessary pumps, thus reducing the energy costs. The main purpose of this work is to increase the pressure in the water distribution system. In order to do this, the coordinates of the possible tank locations are determined according to the topography of the network. It would not be possible to add a tank where there is an existing building, or to install a pipe in an area considered risky. The process of choosing the candidate positions for inserting an element (tank, pipe, PRV) includes first checking points where pressure is not reached and then verifying the feasibility of adding the element. For proper system operation, it is necessary to establish the required characteristics for the new storage tanks such as diameter, volume (m
^{3}), maximum level, minimum level, and initial level. Figure 3 shows the results obtained from the simulation performed during a 72-h period in EPANET solver. Three storage tanks with different characteristics were added (Figure 3a). Pressure increased at nodes that did not reach the required minimum pressure (Figure 3b). For the solution to be feasible, the maximum pressure requirements must be considered. The graph shows high pressures at several points in the network (red vertices, Figure 3a); therefore, the solution is unfeasible [35]. - Add a pressure-reducing valve (PRV), which allows the pressure to be reduced if it is very high. This ensures balanced service to the community and avoids constant pipe breaks. The problem of finding the optimal valve location in a system has been studied for years by different authors [24,25,26,27,28,40,41] in order to improve water distribution while minimizing operation costs. When a valve is added, an economic cost is generated. As more valves are added to the system, the cost increases. This work adopts the idea of [42], which suggests adding valves only in the pipes that connect nodes with pressures greater than the maximum limit. It is important to mention that each pipe is considered as a candidate for valve insertion. However, inserting a valve into the pipes that connect nodes without high pressure can decrease the pressure too much, or even create negative pressure. The solution would no longer reach the minimum pressure required, and it would therefore be unfeasible. To insert the valves, a few points are considered [43]. The direction of the valve must be the same as the direction of the original water flow in the selected pipe. In addition, the diameter of the valve must be the same as the diameter (22.7–101.6) of the chosen pipe. The pressure setting in the range of 10–60 mca is determined to perform the most realistic simulation possible. Figure 4 shows the results of adding pressure-regulating valves. Twenty-two valves were added (Figure 4a). As a result, the nodes met the maximum pressure requirements (Figure 4b). Therefore, the solution is feasible because it satisfies the constraints of the model.The proposed solution strategy obtains feasible solutions according to the constraint satisfaction model. It is also necessary to employ the optimization model in order to reduce the costs of modifications made to the FRM network. In this work, a genetic algorithm is implemented, since good results have been obtained with genetic algorithms in other investigations of water distribution systems [25,26,27,32].

#### 3.4. Genetic Algorithm

Algorithm 1. Genetic algorithm |

1: Parameters (P_{c}, P_{mut}, T_{pob}, N_{g}, P_{s}, P_{m}); // Initialize input parameters2: DataLoad(); // Load instance data 3: InitialConfiguration(); // Generate initial configuration 4: G = 0; // Number of steps 5: PopulationGenerate (P); // Initial population 6: Feasibility Evaluation (P); // Evaluation with EPANET 7: FitnessEvaluate (P); // Population evaluation (fitness = (P, T, V)) 8: while G < N_{g} do9: P′ = 0; // Initialize population P′ 10: Individual_best (Best _{IND}, P); // Save the best individual11: while N_{inds}<<T_{pob} do12: Selection (P, p _{1}, p_{2}); // Select parents p1, p2 of population P13: {h _{1}, h_{2}} = crossover (p_{1}, p_{2}, P_{c}); // crossover of the parents p1, p214: FeasibilityEvaluation (h _{1}, h_{2}); // Evaluation with EPANET15: Mutation (h _{1}, h_{2}, P_{mut}); // Mutation of descendants h1, h216: FeasibilityEvaluation (h _{1}, h_{2}); // Evaluation with EPANET17: IndividualsAdd (P′, h _{1}, h_{2}); // Insert the descendants h1, h2 into the population P′18: N _{inds}+ = 2;19: end while20: FitnessEvaluate (P); // Population evaluation (fitness = (P, T, V)) 21: PopulationReplacement (P, P′); 22: G+ = 1; //Increase of generation number 23: end while |

## 4. Experimental Results

#### Crossing Probability

## 5. Conclusions

## Author Contributions

## Funding

## Data Availability

## Conflicts of Interest

## References

- Rossman, L.A. EPANET 2 Use’s Manual; National Risk Management Research Laboratory Office of Research and Development, U.S. Environmental Protection: Cincinnati, OH, USA, 2000.
- National Water Comission. Manual of Drinking Water, Sewerage and Sanitation, 2007th ed.; National Water Comission: Mexico City, Mexico, 2007. [Google Scholar]
- Gupta, I.; Bassin, J.K.; Gupta, A.; Khanna, P. Optimization of water distribution system. Environ. Softw.
**2000**, 8, 101–113. [Google Scholar] [CrossRef] - Papadimitriou, C.H.; Steiglitz, K. Combinatorial Optimization. Algorithms and Complexity; Dover Publications, Inc.: New York, NY, USA, 1998. [Google Scholar]
- Osman, I.H.; Kelly, J.P. Meta-Heuristics: Theory and Applications; Kluwer Academic Publishers: New York, NY, USA, 1996. [Google Scholar]
- Alperovits, E.; Shamir, U. Design of optimal water distribution systems. Water Resour. Res.
**1977**, 13, 885–900. [Google Scholar] [CrossRef] - Shamir, U. Optimal Design and Operation of Water Distribution Systems. Water Resour. Res.
**1974**, 10, 27–36. [Google Scholar] [CrossRef] - Savic, D.A.; Walters, G.A. Genetic Algorithms for Least-Cost Design of Water. J. Water Resour. Plan. Manag.
**1997**, 123, 67–77. [Google Scholar] [CrossRef] - Montesinos, P.; Garcia Guzman, A.; Ayuso, J.L. Water Distribution Network Optimization Using a Modified Genetic Algorithm. Water Resour. Res.
**1999**, 35, 3467–3473. [Google Scholar] [CrossRef] - Reca, J.; Martínez, J.; Gil, C.; Baños, R. Application of Several Meta-Heuristic Techniques to the Optimization of Real Looped Water Distribution Networks. Water Resour. Manag.
**2008**, 22, 1367–1379. [Google Scholar] [CrossRef] - Kurek, W.; Ostfeld, A. Multi-objective optimization of water quality, pumps operation, and storage sizing of water distribution systems. J. Environ. Manag.
**2013**, 115, 189–197. [Google Scholar] [CrossRef] [PubMed] - Ostfeld, A.; Oliker, N.; Salomons, E. Multiobjective Optimization for Least Cost Design and Resiliency of Water Distribution Systems. J. Water Resour. Plan. Manag.
**2014**, 140, 401–437. [Google Scholar] [CrossRef] - Liu, Y.; Duan, H.; Feng, X. The Design of Water-reusing Network with a Hybrid Structure Through Mathematical Programming. Chin. J. Chem. Eng.
**2008**, 16, 1–10. [Google Scholar] [CrossRef] - D’Ambrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C. Mathematical programming techniques in water network optimization. Eur. J. Oper. Res.
**2015**, 243, 774–788. [Google Scholar] [CrossRef] - Pecci, F.; Abraham, E.; Stoianov, I. Mathematical Programming Methods for Pressure Management in Water Distribution Systems. Procedia Eng.
**2015**, 119, 937–946. [Google Scholar] [CrossRef] - Weickgenannt, M.; Kapelan, Z.; Blokker, M.; Savic, D.A. Risk-Based Sensor Placement for Contaminant Detection in Water Distribution Systems. J. Water Resour. Plan. Manag.
**2010**, 136, 629–636. [Google Scholar] [CrossRef] - Artina, S.; Bragalli, C.; Erbacci, G.; Marchi, A.; Rivi, M. Contribution of parallel NSGA-II in optimal design of water distribution networks. J. Hydroinformat.
**2014**, 14, 310–323. [Google Scholar] [CrossRef] - Van Dijk, M.; Van Vuuren, S.; Van Zyl, J. Optimising water distribution systems using a weighted penalty in a genetic algorithm. Water SA
**2008**, 34, 537–548. [Google Scholar] - Zhang, H.; Huang, T.-L.; He, W.-J. Application of Heuristic Genetic Algorithm for Optimal Layout of Flow Measurement Stations in Water Distribution Networks. In Proceedings of the Fifth International Conference on Natural Computation, Tianjin, China, 14–16 August 2009; Volume 4, pp. 140–143. [Google Scholar] [CrossRef]
- Shu, S.; Zhang, D. Calibrating water distribution system model automatically by genetic algorithms. In Proceedings of the International Conference on Intelligent Computing and Integrated Systems, Guilin, China, 22–24 October 2010; Volume 1, pp. 16–19. [Google Scholar] [CrossRef]
- Vasan, A.; Simonovic, S.P. Optimization of Water Distribution Network Design Using Differential Evolution. J. Water Resour. Plan. Manag.
**2010**, 136, 279–287. [Google Scholar] [CrossRef] - Chang, J.; Bai, T.; Huang, Q.; Yang, D. Optimization of Water Resources Utilization by PSO-GA. Water Resour. Manag.
**2013**, 27, 3525–3540. [Google Scholar] [CrossRef] - Tong, L.; Han, G.; Qiao, J. Design of Water Distribution Network via Ant Colony Optimization. In Proceedings of the 2nd International Conference on Intelligent Control and Information, Harbin, China, 25–28 July 2011; pp. 366–370. [Google Scholar]
- Reis, L.F.R.; Porto, R.M.; Chaudhrf, F.H. Optimal location of control valves in pipe networks by genetic algorithm. J. Water Resour. Plan. Manag.
**1997**, 123, 317–326. [Google Scholar] [CrossRef] - Araujo, L.S.; Ramos, H.; Coelho, S.T. Pressure Control for Leakage Minimisation in Water Distribution Systems Management. Water Resour. Manag.
**2006**, 20, 133–149. [Google Scholar] [CrossRef] - Cattafi, M.; Gavanelli, M.; Nonato, M.; Alvisi, S.; Franchini, M. Optimal placement of valves in a water distribution network with CLP(FD). Theory Pract. Log. Program.
**2011**, 11, 731–747. [Google Scholar] [CrossRef] [Green Version] - Dai, P.D.; Li, P. Optimal Localization of Pressure Reducing Valves in Water Distribution Systems by a Reformulation Approach. Water Resour. Manag.
**2014**, 28, 3057–3074. [Google Scholar] [CrossRef] - Ali, M.E. Knowledge-Based Optimization Model for Control Valve Locations in Water Distribution Networks. J. Water Resour. Plan. Manag.
**2015**, 141, 1–7. [Google Scholar] [CrossRef] - Ávila-Melgar, E.Y.; Cruz-Chávez, M.A.; Martínez-Bahena, B. General Methodology for Using EPANET as an Optimization Element in Evolutionary Algorithms in a Grid Computing Environment to Water Distribution Network Design. J. Water Sci. Technol. Water Supply
**2016**, 17, 1–13. [Google Scholar] [CrossRef] - Holland, J.H. Adaptation in Natural and Artificial Systems; MIT Press: Cambridge, MA, USA, 1975. [Google Scholar]
- Darwin, C. On the Origins of Species by Means of Natural Selection; Murray: London, UK, 1859; p. 247. [Google Scholar]
- Sonaje, N.P. A review of modeling and application of water distribution networks (WDN) softwares. Int. J. Tech. Res. Appl.
**2015**, 3, 174–178. [Google Scholar] - Adedoja, O.S.; Hamam, Y.; Khalaf, B.; Sadiku, R. Towards Development of an Optimization Model to Identify Contamination Source in a Water Distribution Network. Water
**2018**, 10, 579. [Google Scholar] [CrossRef] - Cruz-Chávez, M.A.; Ávila-Melgar, É.Y.; Cruz-Rosales, M.H.; Martínez-Bahena, B.; Flores-Sánchez, G. Search Space Analysis for the Combined Mathematical Model (Linear and Nonlinear) of the Water Distribution Network Design Problem. In Artificial Intelligence and Soft Computing; Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M., Eds.; ICAISC 2014; Lecture Notes in Computer Science; Springer International Publishing: Zug, Switzerland, 2014; Volume 8467, pp. 347–359. [Google Scholar]
- Martínez-Bahena, B.; Cruz-Chávez, M.A.; Peralta-Abarca, J.C.; Juárez-Chávez, J.Y.; Ortíz-Huerta, A.; Moreno-Bernal, P. Analysis of a Town’s Water Distribution System. In Proceedings of the 2014 International Conference on Mechatronics, Electronics and Automotive Engieering, Cuernavaca, Mexico, 18–21 November 2014; pp. 206–211. [Google Scholar]
- Korte, B.; Vygen, J. Combinatorial Optimization Theory and Algorithms. In Series Algorithms and Combinatorics, 4th ed.; Springer: Berlin/Heidelberg, Germany, 2008; Volume 21. [Google Scholar]
- Mariappan, V.E.N. Water Demand Analysis of Municipal Water Supply Using EPANET Software. Int. J. Appl. Bioeng.
**2011**, 5, 9–19. [Google Scholar] - Sotelo, G. Hidráulica de Canales. Primera Edición; Depertamento de Publicaciones de la Facultad de Ingeniería, UNAM: Ciudad de Mexico, Mexico, 2002. [Google Scholar]
- URREA Tecnología para Vivir el Agua. Available online: http://gruposar.com.mx/wp-content/uploads/2015/06/LP_Valvulas_2015.pdf (accessed on 15 June 2015).
- Nicolini, M.; Zovatto, L. Optimal Location and Control of Pressure Reducing Valves in Water Networks. J. Water Resour. Plan. Manag.
**2009**, 135, 178–187. [Google Scholar] [CrossRef] - Wright, R.; Abraham, E.; Parpas, P.; Stoianov, I. Optimized Control of Pressure Reducing Valves in Water Distribution Networks with Dynamic Topology. Procedia Eng.
**2015**, 119, 1003–1011. [Google Scholar] [CrossRef] - Liberatore, S.; Sechi, G.M. Location and calibration of valves in water distribution networks using a scatter-search meta-heuristic approach. Water Resour. Manag.
**2009**, 23, 1479–1495. [Google Scholar] [CrossRef] - Hurtado-Guzmán, V.H. Genetic Algorithms and EPANET 2.0 for Optimum Location of Pressure Reducing Valves in Potable Water Distribution Networks. Bachelor’s Thesis, UNAM, Mexico City, Mexico, 2009. Available online: http://www.ptolomeo.unam.mx:8080/xmlui/bitstream/handle/132.248.52.100/1153/Tesis.pdf?sequence=1 (accessed on 20 August 2018).
- Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning; Addison Wesley Longman Publishing Co., Inc.: Boston, MA, USA, 1989; ISBN 0201157675. [Google Scholar]
- Candelieri, A.; Perego, R.; Archetti, F. Bayesian optimization of pump operations in water distribution systems. J. Glob. Optim.
**2018**, 71, 213–235. [Google Scholar] [CrossRef] [Green Version]

**Figure 1.**Graphical representation of the Fraccionamiento Real Montecasino (FRM) hydraulic network [35].

**Figure 2.**Pressures at the FRM network nodes [35].

**Figure 3.**Pressures for each node after adding new tanks (unfeasible solution). (

**a**) New storage tanks added (

**b**) Pressure distribution.

**Figure 4.**Pressures for each node after adding new tanks and PRVs (feasible solution). (

**a**) New PRVs added (

**b**) Pressure distribution.

Symbol | Representation |
---|---|

Storage tank | |

Reservoir (river, lake, well, etc.) | |

Point of consumption (housing, shops, industries, etc.) | |

Valve | |

Pump | |

Pipe |

Pipes | Nodes | Tanks | Reservoirs | Standard Demand (LPS) | Minimum Pressure (mca) | Maximum Pressure (mca) | Pipe Diameters (mm) |
---|---|---|---|---|---|---|---|

364 | 350 | 6 | 1 | 0.003 | 10 | 60 | 22.7–101.6 |

Parameter | Cost (Currency Units) |
---|---|

Worst | 295,975 |

Mean | 281,618 |

Best | 251,850 |

Mean ± Standard deviation | 281,618 ± 7883 |

Median | 279,987 |

Pipes | Nodes | Tanks | Reservoirs | Valves | Standard Demand (LPS) | Minimum Pressure (mca) | Maximum Pressure (mca) | Pipe Diameters (mm) |
---|---|---|---|---|---|---|---|---|

367 | 350 | 9 | 1 | 7 | 0.003 | 10 | 60 | 22.7–101.6 |

ID_Tank | Elevation (m) | Initial Level (m) | Minimum Level (m) | Maximum Level (m) | Diameter (m) |
---|---|---|---|---|---|

1006 | 2412 | 6.50 | 1.50 | 13.00 | 14.09 |

1007 | 2425 | 4.00 | 1.00 | 8.00 | 7.90 |

1008 | 2329 | 4.50 | 1.00 | 9.00 | 12.66 |

ID_Pipe | Start Node | End Node | Length (m) | Diameter (mm) |
---|---|---|---|---|

365 | 1006 | 120 | 250.00 | 101.00 |

366 | 1007 | 279 | 260.00 | 76.00 |

367 | 1008 | 168 | 180.00 | 50.00 |

ID_Valve | Start Node | End Node | Diameter (mm) | Valve Setting |
---|---|---|---|---|

1 | 21 | 22 | 38.10 | 30.00 |

2 | 44 | 45 | 38.10 | 26.22 |

3 | 48 | 49 | 50.80 | 28.28 |

4 | 63 | 64 | 19.05 | 18.84 |

5 | 164 | 165 | 50.80 | 27.86 |

6 | 222 | 223 | 76.20 | 27.49 |

7 | 339 | 340 | 31.70 | 26.22 |

© 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

## Share and Cite

**MDPI and ACS Style**

Martínez-Bahena, B.; Cruz-Chávez, M.A.; Ávila-Melgar, E.Y.; Cruz-Rosales, M.H.; Rivera-Lopez, R.
Using a Genetic Algorithm with a Mathematical Programming Solver to Optimize a Real Water Distribution System. *Water* **2018**, *10*, 1318.
https://doi.org/10.3390/w10101318

**AMA Style**

Martínez-Bahena B, Cruz-Chávez MA, Ávila-Melgar EY, Cruz-Rosales MH, Rivera-Lopez R.
Using a Genetic Algorithm with a Mathematical Programming Solver to Optimize a Real Water Distribution System. *Water*. 2018; 10(10):1318.
https://doi.org/10.3390/w10101318

**Chicago/Turabian Style**

Martínez-Bahena, Beatriz, Marco Antonio Cruz-Chávez, Erika Yesenia Ávila-Melgar, Martín H. Cruz-Rosales, and Rafael Rivera-Lopez.
2018. "Using a Genetic Algorithm with a Mathematical Programming Solver to Optimize a Real Water Distribution System" *Water* 10, no. 10: 1318.
https://doi.org/10.3390/w10101318