Split-Pipe Design of Water Distribution Network Using Simulated Annealing

In this paper a procedure for the split-pipe design of looped water distribution network based on the use of simulated annealing is proposed. Simulated annealing is a heuristic-based search algorithm, motivated by an analogy of physical annealing in solids. It is capable for solving the combinatorial optimization problem. In contrast to the split-pipe design that is derived from a continuous diameter design that has been implemented in conventional optimization techniques, the split-pipe design proposed in this paper is derived from a discrete diameter design where a set of pipe diameters is chosen directly from a specified set of commercial pipes. The optimality and feasibility of the solutions are found to be guaranteed by using the proposed method. The performance of the proposed procedure is demonstrated through solving the three well-known problems of water distribution network taken from the literature. Simulated annealing provides very promising solutions and the lowest-cost solutions are found for all of these test problems. The results obtained from these applications show that simulated annealing is able to handle a combinatorial optimization problem of the least cost design of water distribution network. The technique can be considered as an alternative tool for similar areas of research. Further applications and improvements of the technique are expected as well.

Authors:

• J. Tospornsampan
• I. Kita
• M. Ishii
• Y. Kitamura

Keywords:

• Combinatorial problem
• Heuristics
• Least-cost design
• Looped network
• Pipe network
• Optimization

References:

[1] E. Alperovits and U. Shamir, Design of optimal water distribution
systems, Water Resources Research, vol. 13, no. 6, pp. 885-900, 1997.
[2] A. Bárdossy, Generating precipitation time series using simulated
annealing, Water Resources Research, vol. 34, no. 7, pp. 1737-1744,
1998.
[3] P.R. Bhave and V.V. Sonak, A critical study of the linear programming
gradient method for optimal design of water supply networks, Water
Resources Research, vol. 28, no. 6, pp. 1577-1584, 1992.
[4] M.D.C. Cunha, On Solving Aquifer Management Problems with
Simulated Annealing Algorithms, Water Resources Management, vol.
13, pp. 153-169, 1999.
[5] M.D.C. Cunha and J. Sousa, Water Distribution Network Design
Optimization: Simulated Annealing Approach, Journal of Water
Resources Planning and Management ASCE, vol. 125, no. 4, pp. 215-
221, 1999.
[6] M.D.C. Cunha and L. Ribeiro, Tabu search algorithms for water network
optimization, European Journal of Operational Research, vol. 157, pp.
746-758, 2004.
[7] G.C. Dandy, A.R. Simpson, and L.J. Murphy, An improved genetic
algorithm for pipe network optimization, Water Resources Research,
vol. 32, no. 2, pp. 449-458, 1996.
[8] D.E. Dougherty and B.A. Marryott, Optimal groundwater management,
1. simulated annealing, Water Resources Research, vol. 27, no. 10, pp.
2493-2508, 1991.
[9] G. Eiger, U. Shamir, and A.B. Tal, Optimal design of water distribution
networks, Water Resources Research, vol. 30, no. 9, pp. 2637-2646, 1994.
[10] O. Fujiwara, B. Jenchaimahakoon, and N.C.P. Edirisinghe, A modified
linear programming gradient method for optimal design of looped water
distribution networks, Water Resources Research, vol. 23, no. 6, pp.
977-982, 1987.
[11] O. Fujiwara and D.B. Khang, A two-phase decomposition method for
optimal design of looped water distribution networks, Water Resources
Research, vol. 26, no. 4, pp. 539-549, 1990.
[12] O. Fujiwara and D.B. Khang, Correction to "A two-phase decomposition
method for optimal design of looped water distribution networks" by
Okitsugu Fujiwara and Do Ba Khang, Water Resources Research, vol.
27, no. 5, pp. 985-986, 1991.
[13] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and
Machine Learning, 2nd edn. Addison-Wesley, Reading, Mass, 1989.
[14] I.C. Goulter, B.M. Lussier, and D.R. Morgan, Implications of head loss
path choice in the optimization of water distribution networks, Water
Resources Research, vol. 22, no. 5, pp. 819-822, 1986.
[15] A. Kessler and U. Shamir, Analysis of the linear programming gradient
method for optimal design of water supply networks, Water Resources
Research, vol. 25, no. 7, pp. 1469-1480, 1989.
[16] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, Optimization by Simulated
Annealing, Science, vol. 220, no. 4598, pp. 671-680, 1983.
[17] S.F. Kuo, C.W. Liu, and G.P. Markley, Application of the Simulated
Annealing Method to Agricultural Water Resoures Management, J.
agric. Engng. Res., vol. 80, no. 1, pp. 109-124, 2001.
[18] G.V. Loganathan, J.J. Greene, and T.J. Ahn, Design heuristic for
globally minimum cost water-distribution systems, Journal of Water
Resources Planning and Management ASCE, vol. 121, no. 2, pp. 182-
192, 1995.
[19] A.H. Mantawy, S.A. Soliman, and M.E. El-Hawary, The long-term
hydro-scheduling problem - a new algorithm, Electric Power Systems
Research, vol. 64, pp. 67-72, 2003.
[20] R.A. Marryott, D.E. Dougherty, and R.T. Stollar, Optimal Groundwater
Management; 2. Application of Simulated Annealing to a Field-Scale
Contamination Site, Water Resources Research, vol. 29, no. 4, pp. 847-
860, 1993.
[21] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolutionary
Programs, 3rd edn. Springer-Verlag, New York, 1996.
[22] P. Montesinos, A.G. Guzman, and J.L. Ayuso, Water distribution
network optimization using a modified genetic algorithm, Water
Resources Research, vol. 35, no. 11, pp. 3467-3473, 1999.
[23] D.R. Morgan and I.D. Goulter, Optimal urban water distribution design,
Water Resources Research, vol. 21, no. 5, pp. 642-652, 1985.
[24] S.G. Ponnambalam and M.M. Reddy, A GA-SA Multiobjective Hybrid
Search Algorithm for Integrating Lot Sizing and Sequencing in Flow-
Line Scheduling, Int. J. Adv. Manuf. Technol, vol.. 21, pp. 126-137,
2003.
[25] G.E. Quindry, E.D. Brill, and J.C. Liebman, Optimization of looped
water distribution systems, Journal of the Environmental Engineering
Division ASCE, vol. 107, no. 4, pp. 665-679, 1981.
[26] G.E. Quindry, E.D. Brill, J.C. Liebman, and A.R. Robinson, Comment
on ÔÇÿDesign of optimal water distribution systems- by E. Alperovits and
U. Shamir, Water Resources Research, vol.15, no. 6, pp. 1651-1654,
1979.
[27] D.M. Rizzo and D.E. Dougherty, Design Optimization for Multiple
Management Period Groundwater Remediation, Water Resources
Research, vol. 32, no. 8, pp. 2549-2561, 1996.
[28] D.A. Savic and G.A. Walters, Genetic algorithms for least-cost design of
water distribution networks, Journal of Water Resources Planning and
Management ASCE, vol. 123, no. 2, pp. 67-77, 1997.
[29] A.R. Simpson, G.C. Dandy, and L.J. Murphy, Genetic algorithms
compared to other techniques for pipe optimization, Journal of Water
Resources Planning and Management ASCE, vol. 120, no. 4, pp. 423-
443, 1994.
[30] R.S.V. Teegavarapu and S.P. Simonovic, Optimal Operation of
Reservoir System Using Simulated Annealing, Water Resources
Management, vol. 16, pp. 401-428, 2002.
[31] J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura, Optimization of
multiple reservoir system using simulated annealing: a case study in the
Mae Klong system, Thailand, Paddy and Water Environment, Vol. 3,
No. 3, pp.137-147, September, 2005.
[32] K.V.K. Varma, S. Narasimhan, and M. Bhallamudi, Optimal design of
water distribution systems using an NLP method, Journal of
Environmental Engineering ASCE, vol. 123, no. 4, pp. 381-388, 1997.