Abstract
The problems involved in the optimal design of water distribution networks belong to a class of large combinatorial optimization problems. Various heuristic and deterministic algorithms have been developed in the past two decades for solving optimization problems and applied to the design of water distribution systems. Nevertheless, there is still some uncertainty about finding a generally trustworthy method that can consistently find solutions which are really close to the global optimum of this problem. The paper proposes a combined genetic algorithm (GA) and linear programming (LP) method, named GALP for solving water distribution system design problems. It was investigated that the proposed method provides results that are more stable in terms of closeness to a global minimum. The main idea is that linear programming is more dependable than heuristic methods in finding the global optimum, but because it is suitable only for solving branched networks, the GA method is used in the proposed algorithm for decomposing a complex looped network into a group of branched networks. Linear programming is then applied for optimizing every branch network produced by GA from the original looped network. The proposed method was tested on three benchmark least-cost design problems and compared with other methods; the results suggest that the GALP consistently provides better solutions. The method is intended for use in the design and rehabilitation of drinking water systems and pressurized irrigation systems as well.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alperovits E, Shamir U (1977) Design of optimal water distribution systems. Water Resour Res AGU 13(6):885–900. doi:10.1029/WR013i006p00885
Cisty M (2002) Rehabilitation of irrigation pressurised pipe systems using optimisation techniques. J Land Water Dev, Pol Acad Sci 6(6):117–128
Cisty M, Savic DA, Walters GA (1999) Rehabilitation of pressurized pipe networks using genetic algorithms. In: Proc., water for agriculture in the next millennium. 17th congress on irrigation and drainage. International Commission on Irrigation and Drainage, Granada, pp 13–27
Cunha MC, Sousa J (2001) Hydraulic infrastructures design using simulated annealing. J Infrastruct Syst 7(1):32–39. doi:10.1061/(ASCE)1076-0342(2001)7:1(32)
Dandy GC, Simpson AR, Murphy LJ (1996) An improved genetic algorithm for pipe network optimization. Water Resour Res 32(2):449. doi:10.1029/95WR02917
Eiger G, Shamir U, Ben-Tal A (1994) Optimal design of water distribution networks. Water Resour Res 30(9):2637–2646. doi:10.1029/94WR00623
Ekinci O, Konak H (2009) An optimization strategy for water distribution networks. Water Resour Manage 23:169–185. doi:10.1007/s11269-008-9270-8
Eusuff MM, Lansey KE (2003) Optimization of water distribution network design using the shuffled frog leaping algorithm. J Water Resour Plan Manage 129(3):210–225. doi:10.1061/(ASCE)0733-9496(2003)129:3(210)
Fujiwara O, Khang DB (1990) A two-phase decomposition method for optimal design of looped water distribution networks. Water Resour Res 26(4):539–549
Geem ZW, Kim JH, Loganathan GV (2002) Harmony search optimization: application to pipe network design. Int J Model Simul 22(2):125–133
Goldberg DE (1989) Genetic algorithms in search, optimisation and machine learning. Addison-Wesley, New York
Kessler A, Shamir U (1989) Analysis of the linear programming gradient method for optimal design of water supply networks. Water Resour Res 25(7):1469–1480. doi:10.1029/WR025i007p01469
Loganathan GV, Greene JJ, Ahn TJ (1995) Design heuristic for globally minimum cost water-distribution systems. J Water Resour Plan Manage 121(2):182–192. doi:10.1061/(ASCE)0733-9496(1995)121:2(182)
Maier HR, Simpson AR, Foong WK, Phang KY, Seah HY, Tan CL (2001) Ant colony optimization for the design of water distribution systems. In: Proceedings of the world water and environmental resources congress, Orlando, FL
Olsson RJ, Kapelan Z, Savic DA (2008) Probabilistic building block identification for the multi-objective design and rehabilitation of water distribution systems. In: Proc., 10th annual water distribution systems analysis conference (WDSA 2008), Kruger National Park, South Africa
Raad D, Vuuren JV (2008) A multi-objective evolutionary meta-algorithmic approach towards water distribution system design. IFORS News, December 2008, pp 7–10
Reca J, Martinez J, Gil C, Banos R (2008) Application of several meta-heuristic techniques to the optimization of real looped water distribution networks. Water Resour Manage 22(10):1367–1379. doi:10.1007/s11269-007-9230-8
Savic DA, Walters GA (1997) Genetic Algorithms for least-cost design of water distribution networks. J Water Resour Plan Manage 123(2):67–77. doi:10.1061/(ASCE)0733-9496(1997)123:2(67)
Simpson AR, Dandy GC, Murphy LJ (1994) Genetic algorithms compared to other techniques for pipe optimization. J Water Resour Plan Manage 120(4):423–443. doi:10.1061/(ASCE)0733-9496(1994)120:4(423)
Vrugt JA, Robinson BA (2007) Improved evolutionary optimization from genetically adaptive multimethod search. Proc Natl Acad Sci U S A 104(3):708–711. doi:10.1073/pnas.0610471104
Zecchin AC, Maier HR, Simpson AR, Leonard M, Nixon JB (2007) Ant colony optimization applied to water distribution system design: comparative study of five algorithms. J Water Resour Plan Manage 133(1):87–92. doi:10.1061/(ASCE)0733-9496(2007)133:1(87)
Zitzler E, Laumanns M, Bleuler S (2003) A tutorial on evolutionary multi-objective optimization. (Unpublished) Technical Report, Computer Engineering and Network Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cisty, M. Hybrid Genetic Algorithm and Linear Programming Method for Least-Cost Design of Water Distribution Systems. Water Resour Manage 24, 1–24 (2010). https://doi.org/10.1007/s11269-009-9434-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11269-009-9434-1