Coupled Genetic Algorithm—Linear Programming Scheme for Least-Cost Pipe Sizing of Water-Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 135, Issue 4
Abstract
Water-distribution systems least-cost pipe sizing/design is probably the most explored problem in water-distribution systems optimization. Attracted numerous studies over the last 4 decades, two main approaches were employed: decomposition in which an “inner” linear programming problem is solved for a fixed set of flows/heads, while the flows/heads are altered at an “outer” problem using a gradient or a subgradient type technique; and the employment of a general evolutionary optimization algorithm. In 1995 Loganathan and his colleagues proposed to couple these two approaches into one framework, thus overcoming the limitations of each. This study employs this framework with two modifications: (1) application of a genetic algorithm for the “outer” optimization search instead of simulated annealing; and (2) constraining the sought solution to the lowest cost spanning tree layout with the spanning tree chords kept at their minimum permissible pipe diameters. A comparison of the methodology to a genetic algorithm application without the refinement of using a spanning tree with minimal chord diameters was explored, showing the proposed methodology dominance. The suggested method is limited to one loading gravitational systems, and is demonstrated using a simple example application.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This study was supported by the Grand Water Research Institute (GWRI) at the Technion—Israel Institute of Technology.
References
Alperovits, E., and Shamir, U. (1977). “Design of optimal water-distribution systems.” Water Resour. Res., 13(6), 885–900.
Bhave, P. R., and Sonak, V. V. (1992). “A critical study of the linear programming gradient method for optimal design of water supply networks.” Water Resour. Res., 28(6), 1577–1584.
Deo, N. (1989). Graph theory with applications to engineering and computer science, Prentice-Hall, Englewood Cliffs, N.J.
Eiger, G., Shamir, U., and Ben-Tal, A. (1994). “Optimal design of water-distribution networks.” Water Resour. Res., 30(9), 2637–2646.
Eusuff, M. M., and Lansey, K. E. (2003). “Optimization of water-distribution network design using the shuffled frog leaping algorithm.” J. Water Resour. Plann. Manage., 129(3), 210–225.
Fujiwara, O., Jenchaimahakoon, B., and Edirisinghe, N. C. P. (1987). “A modified linear programming gradient method for optimal design of looped water-distribution networks.” Water Resour. Res., 23(6), 977–982.
Fujiwara, O., and Khang, D. B. (1990). “A two-phase decomposition method for optimal design of looped water-distribution networks.” Water Resour. Res., 26(4), 539–549.
Fujiwara, O., and Khang, D. B. (1991). “Correction to ‘A two-phase decomposition method for optimal design of looped water-distribution networks’ by Okitsugu Fujiwara and Do Ba Khang.” Water Resour. Res., 27(5), 985–986.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, New York.
Goulter, I. C., Lussier, B. M., and Morgan, D. R. (1986). “Implications of head loss path choice in the optimization of water-distribution networks.” Water Resour. Res., 22(5), 819–822.
Haupt, L. R., and Haupt, S. E. (1998). Practical genetic algorithms, Wiley, New York.
Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, Mich.
Kessler, A., and Shamir, U. (1989). “Analysis of the linear programming gradient method for optimal design of water supply networks.” Water Resour. Res., 25(7), 1469–1480.
Kessler, A., and Shamir, U. (1991). “Decomposition technique for optimal design of water supply networks.” Eng. Optimiz., 17, 1–19.
Loganathan, G. V., Greene, J. J., and Ahn, T. J. (1995). “Design heuristic for globally minimum cost water-distribution systems.” J. Water Resour. Plann. Manage., 121(2), 182–192.
Loganathan, G. V., Sherali, H. D., and Shah, M. P. (1990). “A two-phase network design heuristic for minimum cost water-distribution systems under a reliability constraint.” Eng. Optimiz., 15, 311–336.
Maier, H. R., et al. (2003). “Ant colony optimization for design of water- distribution systems.” J. Water Resour. Plann. Manage., 129(3), 200–209.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. (1953). “Equation of state calculations by fast computing machines.” J. Chem. Phys., 21(6), 1087–1092.
Ostfeld, A., and Shamir, U. (1996). “Design of optimal reliable multiquality water supply systems.” J. Water Resour. Plann. Manage., 122(5), 322–333.
Quindry, G. E., Brill, E. D., and Liebman, J. C. (1981). “Optimization of looped water-distribution systems.” J. Envir. Engrg. Div., 107(4), 665–679.
Quindry, G. E., Brill, E. D., Liebman, J. C., and Robinson, A. R. (1979). “Comment on ‘Design of optimal water-distribution systems’ by E. Alperovits, and U. Shamir.” Water Resour. Res., 15(6), 1651–1654.
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least-cost design of water-distribution networks.” J. Water Resour. Plann. Manage., 123(2), 67–77.
Sherali, H. D., and Smith, E. P. (1997). “A global optimization approach to a water-distribution network design problem.” J. Global Optim., 11, 107–132.
Simpson, A. R., Dandy, G. C., and Murphy, L. J. (1994). “Genetic algorithms compared to other techniques for pipe optimization.” J. Water Resour. Plann. Manage., 120(4), 423–443.
Sonak, V. V., and Bhave, P. R. (1993). “Global optimum tree solution for single-source looped water-distribution networks subjected to a single loading pattern.” Water Resour. Res., 29(7), 2437–2443.
USEPA. (2007). “EPANET 2.00 11.” ⟨www.epa.gov/ORD/NRMRL/wswrd/epanet.html⟩ (March 22, 2008).
Information & Authors
Information
Published In
Copyright
© 2009 ASCE.
History
Received: Nov 27, 2007
Accepted: Apr 22, 2008
Published online: Jun 15, 2009
Published in print: Jul 2009
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.