Split-Pipe Design of Water Distribution Network Using Simulated Annealing

Authors: J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura

Abstract:

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.

Keywords: Combinatorial problem, Heuristics, Least-cost design, Looped network, Pipe network, Optimization

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057909

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.