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

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.
{"references":["E. Alperovits and U. Shamir, Design of optimal water distribution\nsystems, Water Resources Research, vol. 13, no. 6, pp. 885-900, 1997.","P.R. Bhave and V.V. Sonak, A critical study of the linear programming\ngradient method for optimal design of water supply networks, Water\nResources Research, vol. 28, no. 6, pp. 1577-1584, 1992.","M.D.C. Cunha and J. Sousa, Water Distribution Network Design\nOptimization: Simulated Annealing Approach, Journal of Water\nResources Planning and Management ASCE, vol. 125, no. 4, pp. 215-\n221, 1999.","M.D.C. Cunha and L. Ribeiro, Tabu search algorithms for water network\noptimization, European Journal of Operational Research, vol. 157, pp.\n746-758, 2004.","G.C. Dandy, A.R. Simpson, and L.J. Murphy, An improved genetic\nalgorithm for pipe network optimization, Water Resources Research,\nvol. 32, no. 2, pp. 449-458, 1996.","G. Eiger, U. Shamir, and A.B. Tal, Optimal design of water distribution\nnetworks, Water Resources Research, vol. 30, no. 9, pp. 2637-2646,\n1994.","O. Fujiwara, B. Jenchaimahakoon, and N.C.P. Edirisinghe, A modified\nlinear programming gradient method for optimal design of looped water\ndistribution networks, Water Resources Research, vol. 23, no. 6, pp.\n977-982, 1987.","O. Fujiwara and D.B. Khang, A two-phase decomposition method for\noptimal design of looped water distribution networks, Water Resources\nResearch, vol. 26, no. 4, pp. 539-549, 1990.","O. Fujiwara and D.B. Khang, Correction to \"A two-phase decomposition\nmethod for optimal design of looped water distribution networks\" by\nOkitsugu Fujiwara and Do Ba Khang, Water Resources Research, vol.\n27, no. 5, pp. 985-986, 1991.\n[10] F. Glover, J.P. Kelly, M. Laguna, Genetic algorithms and tabu search:\nhybrids for optimization, Computers Operations Research 22(1) (1995)\n111-134.\n[11] F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers,\nDordrecht, 1997.\n[12] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and\nMachine Learning, 2nd edn. Addison-Wesley, Reading, Mass, 1989.\n[13] I.C. Goulter, B.M. Lussier, and D.R. Morgan, Implications of head loss\npath choice in the optimization of water distribution networks, Water\nResources Research, vol. 22, no. 5, pp. 819-822, 1986.\n[14] A. Kessler and U. Shamir, Analysis of the linear programming gradient\nmethod for optimal design of water supply networks, Water Resources\nResearch, vol. 25, no. 7, pp. 1469-1480, 1989.\n[15] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, Optimization by Simulated\nAnnealing, Science, vol. 220, no. 4598, pp. 671-680, 1983.\n[16] G.V. Loganathan, J.J. Greene, and T.J. Ahn, Design heuristic for\nglobally minimum cost water-distribution systems, Journal of Water\nResources Planning and Management ASCE, vol. 121, no. 2, pp. 182-\n192, 1995.\n[17] A.H. Mantawy, S.A. Soliman, and M.E. El-Hawary, The long-term\nhydro-scheduling problem - a new algorithm, Electric Power Systems\nResearch, vol. 64, pp. 67-72, 2003.\n[18] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolutionary\nPrograms, 3rd edn. Springer-Verlag, New York, 1996.\n[19] P. Montesinos, A.G. Guzman, and J.L. Ayuso, Water distribution\nnetwork optimization using a modified genetic algorithm, Water\nResources Research, vol. 35, no. 11, pp. 3467-3473, 1999.\n[20] D.R. Morgan and I.D. Goulter, Optimal urban water distribution design,\nWater Resources Research, vol. 21, no. 5, pp. 642-652, 1985.\n[21] G.E. Quindry, E.D. Brill, and J.C. Liebman, Optimization of looped\nwater distribution systems, Journal of the Environmental Engineering\nDivision ASCE, vol. 107, no. 4, pp. 665-679, 1981.\n[22] G.E. Quindry, E.D. Brill, J.C. Liebman, and A.R. Robinson, Comment\non ÔÇÿDesign of optimal water distribution systems- by E. Alperovits and\nU. Shamir, Water Resources Research, vol.15, no. 6, pp. 1651-1654,\n1979.\n[23] D.A. Savic and G.A. Walters, Genetic algorithms for least-cost design of\nwater distribution networks, Journal of Water Resources Planning and\nManagement ASCE, vol. 123, no. 2, pp. 67-77, 1997.\n[24] A.R. Simpson, G.C. Dandy, and L.J. Murphy, Genetic algorithms\ncompared to other techniques for pipe optimization, Journal of Water\nResources Planning and Management ASCE, vol. 120, no. 4, pp. 423-\n443, 1994.\n[25] A. Thesen, Design and evaluation of tabu search algorithms for\nmultiprocessor scheduling, Journal of Heuristics, vol. 4, pp. 141-160,\n1998.\n[26] J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura, Optimization of\nMultiple Reservoir System Operation Using Combination of Genetic\nAlgorithm and Discrete Differential Dynamic Programming, A Case\nStudy in Mae Klong System, Thailand, Journal of the International\nSociety of Paddy and Water Environment Engineering 3(1) (2005) 29-\n38.\n[27] J. Tospornsampan, I. Kita, M. Ishii, Y. Kitamura, Split-Pipe Design of\nWater Distribution Networks Using Simulated Annealing, (Submitted\nfor publication to WASET together with this manuscript).\n[28] K.V.K. Varma, S. Narasimhan, and M. Bhallamudi, Optimal design of\nwater distribution systems using an NLP method, Journal of\nEnvironmental Engineering ASCE, vol. 123, no. 4, pp. 381-388, 1997.\n[29] C. Zheng, P. Wang, Parameter structure identification using tabu search\nand simulated annealing, Advances in Water Resources, vol. 19, no. 4,\npp. 215-224, 1996."]}