Split-Pipe Design of Water Distribution Networks Using a Combination of Tabu Search and Genetic Algorithm

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

Abstract:

In this paper a combination approach of two heuristic-based algorithms: genetic algorithm and tabu search is proposed. It has been developed to obtain the least cost based on the split-pipe design of looped water distribution network. The proposed combination algorithm has been applied to solve the three well-known water distribution networks taken from the literature. The development of the combination of these two heuristic-based algorithms for optimization is aimed at enhancing their strengths and compensating their weaknesses. Tabu search is rather systematic and deterministic that uses adaptive memory in search process, while genetic algorithm is probabilistic and stochastic optimization technique in which the solution space is explored by generating candidate solutions. Split-pipe design may not be realistic in practice but in optimization purpose, optimal solutions are always achieved with split-pipe design. The solutions obtained in this study have proved that the least cost solutions obtained from the split-pipe design are always better than those obtained from the single pipe design. The results obtained from the combination approach show its ability and effectiveness to solve combinatorial optimization problems. The solutions obtained are very satisfactory and high quality in which the solutions of two networks are found to be the lowest-cost solutions yet presented in the literature. The concept of combination approach proposed in this study is expected to contribute some useful benefits in diverse problems.

Keywords: GAs, Heuristics, Looped network, Least-cost design, Pipe network, Optimization, TS

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

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] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] F. Glover, J.P. Kelly, M. Laguna, Genetic algorithms and tabu search: hybrids for optimization, Computers Operations Research 22(1) (1995) 111-134.
[11] F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, Dordrecht, 1997.
[12] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, 2nd edn. Addison-Wesley, Reading, Mass, 1989.
[13] 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.
[14] 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.
[15] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, Optimization by Simulated Annealing, Science, vol. 220, no. 4598, pp. 671-680, 1983.
[16] 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.
[17] 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.
[18] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolutionary Programs, 3rd edn. Springer-Verlag, New York, 1996.
[19] 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.
[20] D.R. Morgan and I.D. Goulter, Optimal urban water distribution design, Water Resources Research, vol. 21, no. 5, pp. 642-652, 1985.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] A. Thesen, Design and evaluation of tabu search algorithms for multiprocessor scheduling, Journal of Heuristics, vol. 4, pp. 141-160, 1998.
[26] J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura, Optimization of Multiple Reservoir System Operation Using Combination of Genetic Algorithm and Discrete Differential Dynamic Programming, A Case Study in Mae Klong System, Thailand, Journal of the International Society of Paddy and Water Environment Engineering 3(1) (2005) 29- 38.
[27] J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura, Split-Pipe Design of Water Distribution Networks Using Simulated Annealing, (Submitted for publication to WASET together with this manuscript).
[28] 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.
[29] C. Zheng, P. Wang, Parameter structure identification using tabu search and simulated annealing, Advances in Water Resources, vol. 19, no. 4, pp. 215-224, 1996.