Optimal Design of Gravitational Sewer Networks with General Cellular Automata

Document Type : Research Paper


1 Assoc. Prof., Dept. of Civil Eng., Iran University of Science and Tech., Tehran

2 Ph.D. Student of Water Eng., Iran University of Science and Tech., Tehran


In this paper, a Cellular Automata method is applied for the optimal design of sewer networks. The solution of sewer network optimization problems requires the determination of pipe diameters and average pipe cover depths, minimizing the total cost of the sewer network subject to operational constraints. In this paper, the network nodes and upstream and downstream pipe cover depths are considered as CA cells and cell states, respectively, and the links around each cell are taken into account as neighborhood. The proposed method is a general and flexible method for the optimization of sewer networks as it can be used to optimally design both gravity and pumped network due to the use of pipe nodal cover depths as the decision variables. The proposed method is tested against two  gravitational sewer networks and the  comparison of results with other methods such as  Genetic algorithm, Cellular Automata, Ant Colony Optimization Algorithm and Particle Swarm Optimization show the efficiency and effectiveness of the proposed method.


1. Dajani, J. S., Gemmell, R. S., and Morlok, E.K. (1972). “Optimal design of urban wastewater collection networks.” J. of the Sanitary Engineering Division, 98(6), 853-867.
2. Price, R. K. (1978). “Design of storm water sewers for minimum construction cost.” In Proc. 1st International Conference on Urban Strom Drainage, Southampton, United Kingdom, 636-647.
3. Robinson, D. K., and Labadie, J. W. (1981). “Optimal design of urban storm water drainage system.” Int. Symposium on Urban Hydrology, Hydraulics, and Sediment Control, University of Kentucky, Lexington, KY, USA, 145-156.
4. Li, G., and Matthew, R. G. S. (1990). “New approach for optimization of urban drainage systems.” J. of Environmental Engineering, 116(5), 927-944.
5. Elimam, A. A., Charalambous, C., and Ghobrial, F. H. (1989). “Optimum design of large sewer networks.” J. Envire. Engrg., 115(6), 1171-1190.
6. Papalexandri, K. P., Pistikopoules, E. N., and Floudas, C. A. (1994). “Synthesis of mass exchanger networks for the waste minimization: An MINLP approach.” In Proceedings of the IChemE Symposium Series, 133, 351-358.
7. Merritt, L. B., and Bogan R. H. (1973). “Computer-based optimal design of sewer system.” J. Envire. Engrg. Div., 99(1), 35-53.
8. Mays, L. W., and Wenzel, H. G. (1976). “Optimal design of multilevel branching sewer systems.” Water Resour. Res., 12(5), 913-917.
9. Kulkarni, V. S., and Khanna, P. (1985). “Pumped wastewater collection system optimization.” J. Envire. Engrg., 111(5), 589-601.
10. Afshar, M. H. (2006a). “Improving the efficiency of ant algorithms using adaptive refinement: Application to storm water network design.” Advances in Water Resources, 29(9), 1371-1382.
11. Afshar, M. H. (2006b). “Application of a genetic algorithm to storm sewer network optimization.” Scientia Iranica, Sharif University of Technology, 13 (3), 234-244.
12. Izquierdo, J., Montalvo, I., Perez, R., and Fuertes, V. S. (2008). “Design optimization of wastewater collection networks by PSO.” Computers and Mathematics with Applications, 56 (3), 777-784.
13. Afshar, M. H. (2008). “Rebirthing particle swarm optimization algorithm: Application to storm sewer network design.” NRC Research Press website at cjce.nrc.ca, 234-244.
14. Heaney, J. P., Wright, L. T., Sample, D., Field, R., and Fan, C. Y. (1999). “Innovative methods for the optimization of gravity storm sewer design.” In Proceedings the 8th International Conference on Urban Storm Drainage, Sydney, Australia, 1896-1903.
15. Sotoodeh, M. H. (2003). “Optimal design of sewer networks.” M.Sc. Thesis, Department of Civil Eng., Iran University of Science and Technology, Iran. (In Persian)
16. Liang, L. Y., Thompson, R. G., and Young, D. M. (2004). “Optimising the design of sewer networks using genetic algorithms and tabu search.” Eng. Constr. Archit. Manage, 11(2), 101-112.
17. Afshar, M. H., Afshar, A., Marino, M. A., and Darbandi, A.A.S. (2006). “Hydrograph-based storm sewer design optimization by genetic algorithm.” Can. J. Civil Engineering, 33(3), 310-325.
18. Afshar, M. H. (2007). “Partially constrained ant colony optimization algorithm for the solution of constrained optimization problems: Application to storm water network design.” Advances in Water Resources, 30(4), 954-965.
19. Pan, T. C., and Kao, J. J. (2009). “GA-QP model to optimize sewer system design.” J. of Environmental Engineering, 135(1), 17-24.
20. Afshar, M. H., and Rohani, M. (2012). “Optimal design of sewer networks using cellular automata-based hybrid methods: Discrete and continuous approaches.” Engineering Optimization, 44(1), 1-22.
21. Neumann, J. V. (1966). Theory of self-reproduction automata, Burks, A. (Ed.), University of Illinois Press, Urbana.
22. Ulam, S. M. (1952) “Random processes and transformations.” Proceedings of the International Congress of Mathematicians, 2, 264-275.
23. Guo, Y., Walters, G. A., Khu, S. T., and Keedwell, E. (2007a). “A novel cellular automata based approach to optimal storm sewer design.” Engineering Optimization, 39(3), 345-364.
24. Thatcher, J. (1964). Universality in the von Neumann cellular model, Technical Report 03105-30-T, University of Michigan.
25. Codd, E.F. (1968). Cellular automata, Academic Press, New York.
26. Burks, E. (1972). Essays on cellular automata, University of Illinois Press, Champaign, IL.
27. Packard, N. H. (1986). “Lattice models for solidification and Aggregation.” First International Symosium for Science on Form. Tsukuba, Japan.
28. Smith, M. A. (1994). “Cellular automata methods in mathematical physics”.
29. Provota, A., Niocolis, C. (1994). “A microscopic aggregation model of droplet dynamics in warm clouds.” J. Stat. Phys., 74, 75-89.
30. Chopard, B., and Droz, M. (1998). Cellular automata modeling of physical systems, Cambridge University Press, UK.
31. Nagel, K. (2002). “Cellular automata models for transportation applications.” Lect. Notes Comput. Sc., 2493, 20-31.
32. Droz, M., and Pakalski, A. (2002). “Dynamics of populations in extended systems.” Lect.Notes Comput. Sc., 2493, 190-201.
33. Kita, E., and Toyoda, T. (2000). “Structural design using cellular automata.” J. Structural and Multidisciplinary Optimization, 19, 64-73.
34. Missoum, S., Gürdal, Z., and Setoodeh, S. (2005). “Study of a new local update scheme for cellular automata in structural design.” J. Struct. Multidisciplinary Optimization, 29, 103-112.
35. Setoodeh, S., Gürdalb, Z., and Watson, L.T. (2006), “Design of variable-stiffness composite layers using cellular automata.” Computer Methods in Applied Mechanics and Engineering, 195(9-12), 836-851.
36. Shuai, D., and Zhao, H. (2004). “A new generalized cellular automata approach to optimization of fast packet switching.” Computer Networks, 45, 399-419.
37. Keedwell, E., and Khu, S. T. (2005). “A hybrid genetic algorithm for the water distribution networks.” J. of Engineering Application of Artificial Intelligence, 18, 461-472.
38. Guo, Y. (2005). “Sewer network optimal design base on cellular automata principles.” In Proc. XXXI IAHR Congress, Seoul, South Korea, 6582-6593.
39. Guo, Y., Walters, G. A., Khu, S-T., and Keedwell, E. (2006). Optimal design of sewer networks using hybrid cellular automata and genetic algorithm, IWA Pub. London, UK.
40. Keedwell, E., and Khu, S. T. (2006). “Novel cellular automata approach to optimal water distribution network design.” J. of Computing in Civil Engineering, 20(1), 49-56.
41. Guo, Y., Keedwell, E. C., Walters, G. A., and Khu, S. T. (2007b). “Hybridizing cellular automata principles and NSGAΠ for multi-objective design of urban water networks.” Computer Science and Mathematics, 4403,
42. Afshar, M. H., and Shahidi, M. (2009). “Optimal solution of large scale reservoir operation problems: Cellular automata versus heuristic-search methods.” J. of Engineering Optimization, 41(3), 275-293.
43. Afshar, M. H., Shahidi, M., Rohani, M., and Sargolzaei, M. (2011). “Application of cellular automata to sewer network optimization problems.” Scientia Iranica A, 18 (3), 304-312.
44.Miles, S. W., and Heaney, J. P. (1988). “Better than optimal method for designing drainage systems.” J. of Wat. Resour. Plng. and Mgmt., 114(5), 477-499.
45. Meredith, D. D. (1972). “Dynamic programming with case study on planning and design of urban water facilities.” Treaties on Urban Water Systems, Colorado State Univ., fort Collins, Colo., 47-47.
46. Mansouri, M.R. and Khanjani, M.J. (1989). “Optimization of the sewer networks with the nonlinear programming.” J. of Water and Wastewater, 30, 20-30. (In Persian)
47. Afshar, M. H., and Sotoodeh, M. H. (2008). “Optimal design of the sewer networks with the genethic algorithm.” J. of Engineering Science, Iran University of Science and Technology, 2(19), 37-48. (In Persian)