Water Distribution Network Design Optimization: Simulated Annealing Approach
Publication: Journal of Water Resources Planning and Management
Volume 125, Issue 4
Abstract
A simulated annealing-based heuristic has been developed to obtain the least-cost design of a looped water distribution network. A Newton search method was used to solve the hydraulic network equations. Simulated annealing is a stochastic optimization method that can work well for large-scale optimization problems that are cast in discrete or combinatorial form, as with the problem proposed. The results obtained with this approach for networks currently appearing in the literature as case studies in this field (whose solution by other optimization methods was known) have proved the ability of the heuristic to handle this kind of problem.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Aarts, E., and Korts, J. (1989). Simulated annealing and Boltzman machines: A stochastic approach to combinatorial optimization and neural computing. Wiley, Chichester.
2.
Aarts, E., Korts, J., and Van Laarhoven, P. J. M. ( 1997). “Simulated annealing.” Local search in combinatorial optimization, E. Aarts and J. K. Lenstra, eds., Wiley, Chichester, 91–120.
3.
Aarts, E. H. L., and Van Laarhoven, P. J. M. (1985). “Statistical cooling: A general approach to combinatorial optimization problems.” Philips J. Res., 40(4), 193–226.
4.
Alperovits, E., and Shamir, U. (1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
5.
Cerny, V. (1985). “A thermodynamical approach to the travelling salesman problem.” J. Optimization Theory and Applications, 45, 41–51.
6.
Eiger, G., Shamir, U., and Ben-Tal, A. (1994). “Optimal design of water distribution networks.” Water Resour. Res., 30(9), 2637–2646.
7.
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.
8.
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.
9.
Fujiwara, O., and Khang, D. B. (1991). “Correction to a two-phase decomposition method for optimal design of looped water distribution networks.” Water Resour. Res., 27(5), 985–986.
10.
Goldberg, D. E., and Kuo, C. H. (1987). “Genetic algorithms in pipeline optimization.”J. Comp. in Civ. Engrg., ASCE, 1(2), 128–141.
11.
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.
12.
Goulter, I. C., and Morgan, D. R. (1985). “An integrated approach to the layout and design of water distribution networks.” Civ. Engrg. Sys., 2(2), 104–113.
13.
Hadji, G., and Murphy, L. J. (1990). “Genetic algorithms for pipe network optimization.” 4th Year Student Civ. Engrg. Res. Rep., University of Adelaide, Adelaide, Australia.
14.
Huang, M. D., Romeo, F., and Sangiovanni-Vincentelli, A. (1986). “An efficient general cooling schedule for simulated annealing.” IEEE Trans. Comp. Aided Des., CAD-5(1), 381–384.
15.
Johnson, D., Aragon, C., McGeoch, L., and Schevon, C. (1989). “Optimization by simulated annealing: An experimental evaluation; Part I, Graph partitioning.” Operation Res., 37, 865–892.
16.
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.
17.
Kessler, A., and Shamir, U. (1991). “Decomposition technique for optimal design of water supply networks.” Engrg. Optimization, 17(1), 1–19.
18.
Kirkpatrick, S. (1984). “Optimization by simulated annealing: Quantitative studies.” Stat. Phys., 34(5/6), 975–986.
19.
Kirkpatrick, S., Gelatt, C., and Vecchi, M. (1983). “Optimization by simulated annealing.” Sci., 220(4598), 671–680.
20.
Lansey, K. E., and Mays, L. W. (1989). “Optimization model for design of water distribution systems.” Reliability analysis of water distribution systems, L. R. Mays, ed., ASCE, Reston, Va.
21.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. (1953). “Equations of state calculations by fast computing machines.” J. Chemical Phys., 21, 1087–1092.
22.
Murphy, L. J., and Simpson, A. R. (1992). “Genetic algorithms in pipe network optimization.” Res. Rep. No. R93, Dept. of Civ. and Envir. Engrg., University of Adelaide, Adelaide, Australia.
23.
Quindry, G. E., Brill, E. D., and Liebman, J. C. (1981). “Optimization of looped water distribution systems.”J. Envir. Engrg., ASCE, 107(4), 664–679.
24.
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least-cost design of water distribution networks.”J. Water Resour. Plng., and Mgmt., ASCE, 123(2), 67–77.
25.
Schaake, J., and Lai, D. (1969). “Linear programming and dynamic programming applications to water distribution network design.” Rep. No. 116, Dept. of Civ. Engrg., Massachusetts Institute of Technology, Cambridge, Mass.
26.
Simpson, A. R., Dandy, G. C., and Murphy, L. J. (1994). “Genetic algorithms compared to other techniques for pipe optimization.”J. Water Resour. Plng. and Mgmt., ASCE, 120(4), 423–443.
27.
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.
28.
Varma, K. V. K., Narasimhan, S., and Bhallamudi, S. M. (1997). “Optimal design of water distribution systems using an NLP method.”J. Envir. Engrg., ASCE, 123(4), 381–388.
29.
Walski, T. M. (1985). “State-of-the-art: Pipe network optimization.” Computer applications in water resources, H. C. Toeno, ed., ASCE, New York, 559–568.
30.
Walski, T. M. (1996). “Discussion of `Design heuristic for globally minimum cost water distribution systems,' by G. V. Loganathan, J. J. Greene, and T. J. Ahn.”J. Water Resour. Plng. and Mgmt., ASCE, 122(4), 313–314.
31.
Walters, G. A., and Cembrowicz, R. G. ( 1993). “Optimal design of water distribution networks.” Water supply systems, state-of-the-art and future trends, E. Cabrera and F. Martinez, eds., Computational Mechanics Inc., Southampton, England, 91–117.
Information & Authors
Information
Published In
History
Received: Feb 10, 1998
Published online: Jul 1, 1999
Published in print: Jul 1999
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.