Coupled Binary Linear Programming–Differential Evolution Algorithm Approach for Water Distribution System Optimization
Publication: Journal of Water Resources Planning and Management
Volume 140, Issue 5
Abstract
A coupled binary linear programming–differential evolution (BLP-DE) approach is proposed in this paper to optimize the design of water distribution systems (WDS). Three stages are involved in the proposed BLP-DE optimization method. In the first stage, the WDS that is being optimized is decomposed into trees and the core using a graph algorithm. Binary linear programming is then used to optimize the design of the trees during the second stage. In the third stage, a differential evolution (DE) algorithm is utilized to deal with the core design while incorporating the optimal solutions for the trees obtained in the second stage, thereby yielding near-optimal solutions for the original whole WDS. The proposed method takes advantage of both the BLP and DE algorithms: BLP is capable of providing a global optimal solution for the trees (no loops involved) with great efficiency, and a DE is able to efficiently generate good quality solutions for the core (loops involved) with a reduced search space compared to the original full network. Two benchmark WDS case studies and one real-world case study (with multiple demand loading cases) with a number of decision variables ranging from 21–96 are used to verify the effectiveness of the proposed BLP-DE optimization approach. Results show that the proposed BLP-DE algorithm significantly outperforms other optimization algorithms in terms of both solution quality and efficiency.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors are grateful to School Editor Barbara Brougham for improving the quality of this manuscript. The first author gratefully acknowledges the scholarship provided by the Australian government and the University of Adelaide.
References
Alperovits, E., and Shamir, U. (1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
Bolognesi, A., Bragalli, C., Marchi, A., and Artina, S. (2010). “Genetic heritage evolution by stochastic transmission in the optimal design of water distribution networks.” Adv. Eng. Software, 41(5), 792–801.
Cunha, M. d. C., and Sousa, J. (2001). “Hydraulic infrastructures design using simulated annealing.” J. Infrastruct. Syst., 32–39.
Dandy, G. C., Simpson, A. R., and Murphy, L. J. (1996). “An improved genetic algorithm for pipe network optimization.” Water Resour. Res., 32(2), 449–458.
Deo, N. (1974). Graph theory with applications to engineering and computer science, Prentice-Hall, Englewood Cliffs, NJ.
Deuerlein, J. W. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 822–832.
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., 210–225.
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.
Geem, Z. W., Kim, J. H., and Loganathan, G. V. (2002). “Harmony search optimization: Application to pipe network design.” Int. J. Model. Simul., 22(2), 125–133.
Gessler, J. (1985). “Pipe network optimization by enumeration.” Proc., Computer Application for Water Resources, ASCE, New York, 572–581.
Guercio, R., and Xu, Z. (1997). “Linearized optimization model for reliability-based design of water systems.” J. Hydraul. Eng., 1020–1026.
Haghighi, A., Samani, H., and Samani, Z. (2011). “GA-ILP method for optimization of water distribution networks.” Water Resour. Manage., 25(7), 1791–1808.
Kadu, M. S., Gupta, R., and Bhave, P. R. (2008). “Optimal design of water networks using a modified genetic algorithm with reduction in search space.” J. Water Resour. Plann. Manage., 147–160.
Krapivka, A., and Ostfeld, A. (2009). “Coupled genetic algorithm–linear programming scheme for least-cost pipe sizing of water-distribution systems.” J. Water Resour. Plann. Manage., 298–302.
Lansey, K. E., and Mays, L. W. (1989). “Optimization model for water distribution system design.” J. Hydraul. Eng., 1401–1418.
Lin, M.-D., Liu, Y.-H., Liu, G.-F., and Chu, C.-W. (2007). “Scatter search heuristic for least-cost design of water distribution networks.” Eng. Optim., 39(7), 857–876.
Maier, H. R., et al. (2003). “Ant colony optimization for design of water distribution systems.” J. Water Resour. Plann. Manage., 200–209.
Marchi, A., Dandy, G., Wilkins, A., and Rohrlach, H. (2014). “A methodology for comparing evolutionary algorithms for the optimization of water distribution systems.” J. Water Resour. Plann. Manage., 22–31.
Martínez, J. B. (2008). “Discussion of ‘Optimization of water distribution networks using integer linear programming’ by Hossein M. V. Samani and Alireza Mottaghi.” J. Hydraul. Eng., 1023–1024.
Montalvo, I., Izquierdo, J., Pérez, R., and Tung, M. M. (2008). “Particle swarm optimization applied to the design of water supply systems.” Comput. Math. Appl., 56(3), 769–776.
Perelman, L., and Ostfeld, A. (2007). “An adaptive heuristic cross-entropy algorithm for optimal design of water distribution systems.” Eng. Optim., 39(4), 413–428.
Reca, J., and Martínez, J. (2006). “Genetic algorithms for the design of looped irrigation water distribution networks.” Water Resour. Res., 42(5), W05416.
Rossman, L. A. (2000). EPANET 2-user manual, National Risk Management Research Laboratory, Office of Research and Development, U.S. Environmental Protection Agency, Cincinnati.
Samani, H. M. V., and Mottaghi, A. (2006). “Optimization of water distribution networks using integer linear programming.” J. Hydraul. Eng., 501–509.
Savic, D., and Cunha, M. d. C. (2008). “Discussion of ‘Optimization of water distribution networks using integer linear programming’ by Hossein M. V. Samani and Alireza Mottaghi.” J. Hydraul. Eng., 1024–1025.
Schaake, J., and Lai, D. (1969). “Linear programming and dynamic programming applications to water distribution network design.”, Dept. of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MA.
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., 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.
Suribabu, C. R. (2010). “Differential evolution algorithm for optimal design of water distribution networks.” J. Hydroinf., 12(1), 66–82.
Suribabu, C. R., and Neelakantan, T. R. (2006). “Design of water distribution networks using particle swarm optimization.” Urban Water J., 3(2), 111–120.
Tolson, B. A., Asadzadeh, M., Maier, H. R., and Zecchin, A. (2009). “Hybrid discrete dynamically dimensioned search (HD-DDS) algorithm for water distribution system design optimization.” Water Resour. Res., 45(12), W12416.
Vairavamoorthy, K., and Ali, M. (2005). “Pipe index vector: A method to improve genetic-algorithm-based pipe optimization.” J. Hydraul. Eng., 1117–1125.
Vasan, A., and Simonovic, S. P. (2010). “Optimization of water distribution network design using differential evolution.” J. Water Resour. Plann. Manage., 279–287.
Zecchin, A. C., Maier, H. R., Simpson, A. R., Leonard, M., and Nixon, J. B. (2007). “Ant colony optimization applied to water distribution system design: Comparative study of five algorithms.” J. Water Resour. Plann. Manage., 87–92.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2011a). “A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems.” Water Resour. Res., 47(8), W08531.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2011b). “Optimal rehabilitation for large water distribution systems using genetic algorithms.” Proc., Australia Water Association (AWA) 2011 OzWater, Adelaide, SA, Australia.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 140 • Issue 5 • May 2014
Pages: 585 - 597
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Jun 4, 2012
Accepted: Mar 8, 2013
Published online: Mar 11, 2013
Discussion open until: Aug 11, 2013
Published in print: May 1, 2014
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.