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.
[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.
[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.
@article{"International Journal of Earth, Energy and Environmental Sciences:62889", author = "J. Tospornsampan and I. Kita and M. Ishii and Y. Kitamura", title = "Split-Pipe Design of Water Distribution Networks Using a Combination of Tabu Search and Genetic Algorithm ", 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", volume = "1", number = "4", pages = "44-11", }
