Hydraulic Infrastructures Design Using Simulated Annealing
Publication: Journal of Infrastructure Systems
Volume 7, Issue 1
Abstract
Because the provision of an adequate and reliable water supply system involves a very high level of investment, it is essential that the layout and design of such systems are very carefully planned and the operation of their hydraulic infrastructures is properly managed. This paper describes a simulated annealing method that can be used to find the least-cost design for a gravitational looped water distribution network. Simulated annealing heuristics have proved to be extremely efficient in solving classic combinatorial problems such as the “traveling salesmen” problem. To assess its performance, this heuristic method has been applied to well-known networks in the literature. The results compare very favorably with those obtained by other optimization methods, confirming that simulated annealing is capable of handling nonlinear mixed-integer problems such as this. This encourages further research in this area.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Aarts, E. H. L., Korst, J. H. M., and Van Laarhoven, P. J. M. ( 1997). “Simulated annealing.” Local search in combinatorial optimization, E. Aarts and J. K. Lenstra, eds., Wiley, New York, 91–120.
2.
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.
3.
Alperovits, E., and Shamir, U. ( 1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
4.
Cunha, M. C. ( 1999). “On solving aquifer management problems with simulated annealing algorithms.” Water. Resour. Mgmt., 13(3), 153–169.
5.
Cunha, M. C. M. O., and Sousa, J. O. ( 1997). “Simulated annealing algorithms for water distribution systems optimization.” EURO XV-INFORMS XXXIV Joint Int. Meeting, The Association of European Operational Research Societies and Institute for Operational Research and the Management Sciences, Barcelona, Spain [mimeo].
6.
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.
7.
DIGITAL Fortran—Language manual reference. (1997). Digital Equipment Corp. Maynard, Mass.
8.
Eiger, G., Shamir, U., and Ben-Tal, A. ( 1994). “Optimal design of water distribution networks.” Water Resour. Res., 30(9), 2637–2646.
9.
Feller, W. ( 1950). An introduction to probability theory and its applications, Vol. 1, Wiley, New York.
10.
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.
11.
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.
12.
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.
13.
Gessler, J. ( 1982). “Optimization of pipe networks.” Proc., Inst. on Urban Hydr. and Sediment Control, University of Kentucky, Lexington, Ky., 165–171.
14.
Goldberg, D. E., and Kuo, C. H. (1987). “Genetic algorithms in pipeline optimization.”J. Comp. in Civ. Engrg., ASCE, 1(2), 128–141.
15.
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.
16.
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.
17.
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.
18.
Huang, M. D., Romeo, F., and Sangiovanni-Vincentelli, A. ( 1986). “An efficient general cooling schedule for simulated annealing.” IEEE Trans. Comp. Aided Des., 5(1), 381–384.
19.
Isaacson, D., and Madsen, R. ( 1976). Markov chains, Wiley, New York.
20.
Johnson, D., Aragon, C., McGeoch, L., and Schevon, C. ( 1989). “Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning.” Operations Res., 37, 865–892.
21.
Kessler, A. ( 1988). “Optimal design of water supply networks using graph theory.” DSc thesis, Technion—Israel Institute of Technology Haifa, Israel (in Hebrew).
22.
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.
23.
Kessler, A., and Shamir, U. ( 1991). “Decomposition technique for optimal design of water supply networks.” Engrg. Optimization, 17(1), 1–19.
24.
Kirkpatrick, S. ( 1984). “Optimization by simulated annealing: Quantitative studies.” J. Stat. Phys., 34(5/6), 975–986.
25.
Kirkpatrick, S., Gelatt, C., and Vecchi, M. ( 1983). “Optimization by simulated annealing.” Sci., 220(4598), 671–680.
26.
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, New York.
27.
Lin, S. ( 1965). “Computer solutions of the traveling-salesman problem.” Bell Sys. Tech. J., 44, 2245–2269.
28.
Loganathan, G. V., Greene, J. J., and Ahn, T. J. (1995). “Design heuristic for globally minimum cost water-distribution systems.”J. Water Resour. Plng. and Mgmt., ASCE, 121(2), 182–192.
29.
Loganathan, G. V., and Sherali, H. D. ( 1990). “A two-phase network design heuristic for minimum cost water distribution systems under reliability constraint.” Engrg. Optimization, 15, 311–336.
30.
Loubser, B. F., and Gessler, J. ( 1990). “Computer-aided optimization of water distribution networks.” The Civ. Engr. in South Africa, (Oct.), 413–422.
31.
Metropolis, N., Rosenbluth, M., Rosenbluth, A., Teller, A., and Teller, E. ( 1953). “Equation of state calculations by fast computing machines.” J. Chemical Phys., 21, 1087–1092.
32.
Morgan, D. R., and Goulter, I. C. ( 1985). “Optimal urbanwater distribution design.” Water Resour. Res., 21(5), 642–652.
33.
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.
34.
Murphy, L. J., Simpson, A. R., and Dandy, G. C. ( 1993). “Design of a network using genetic algorithms.” Water, 20, 40–42.
35.
Quindry, G. E., Liebman, J. C., and Brill, E. D. (1981). “Optimization of looped water distribution systems.”J. Envir. Engrg. Div., ASCE, 107(4), 665–679.
36.
Rowell, W. F. ( 1979). “A methodology of optimal design of water distribution systems.” PhD thesis, University of Texas, Austin, Tex.
37.
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.
38.
Sherali, H. D., Totlani, R., and Loganathan, G. V. ( 1998). “Enhanced lower bounds for the global optimization of water distribution networks.” Water Resour. Res., 34(7), 1831–1841.
39.
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.
40.
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.
41.
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.
42.
Walski, T. M. ( 1985). “State-of-the-art: Pipe network optimization.” Computer applications in water resources, H. C. Torno, ed., ASCE, New York, 559–568.
43.
Walski, T. M. ( 1990). Water distribution systems: Simulation and sizing, T. M. Walski, J. Gessler, J. W. Sjostrom, eds., Lewis, Boca Raton, Fla.
44.
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 Publications, Southampton, U.K., 91–117.
45.
Yates, D. F., Templeman, A. B., and Boffey, T. B. ( 1984). “The computational complexity of the problem of determining least capital cost designs for water supply networks.” Engrg. Optimization, 7, 143–155.
Information & Authors
Information
Published In
Journal of Infrastructure Systems
Volume 7 • Issue 1 • March 2001
Pages: 32 - 39
History
Received: Jul 27, 1998
Published online: Mar 1, 2001
Published in print: Mar 2001
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.