Optimal Layout of Sewer Systems: A Deterministic versus a Stochastic Model
Publication: Journal of Hydraulic Engineering
Volume 132, Issue 9
Abstract
The optimization of a new or partially existing urban drainage system may be modeled as a subproblems sequence of layout and optimal design within the discrete search space. The design optimization, incorporating the optimal selection of the pumping stations, intermediate manholes, pipe sections, and installation depths, for a general system fixed layout in plan, is a high level sequential decision problem which may be efficiently solved deterministically through a multilevel dynamic programming model. The optimal general layout may be selected in a deterministic way by means of a simple economical comparison of all plan solutions having optimized designs, for small to medium sized systems (if the specific restrictions of the applications are appropriately exploited) in practicable computer time. For larger dimension networks, where it is clearly impossible to achieve plan optimization with full enumeration (which is a NP complete), stochastic search models can be used. For the subproblem layout, an effective enumeration model is presented; the results of a stochastic model proposed previously, using simulated annealing for an application example, are compared and discussed in detail.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgment
The writers are grateful to Professor Luis Miguel Simões for his review and suggestions.
References
Aarts, E. H. L., Korst, J. H. M., and Laarhoven, P. J. M. (1988). “A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem.” J. Stat. Phys., 50(1/2), 187–206.
Argaman, Y., Shamir, U., and Spivak, E. (1973). “Design of optimal sewerage systems.” J. Environ. Eng. Div. (Am. Soc. Civ. Eng.), 99(5), 703–716.
Berge, C. (1982). The theory of graphs and its applications, Greenwood, Westport, Conn.
Cerny, V. (1985). “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm.” J. Optim. Theory Appl., 45(1), 41–51.
Cunha, M. C., and Sousa, J. (1999). “Water distribution network design optimization: Simulated annealing approach.” J. Water Resour. Plan. Manage., 125(4), 215–221.
Davis, L., and Steenstrup, M. (1987). “Genetic algorithms and simulated annealing: An overview.” Genetic algorithms and simulated annealing (Research notes in artificial intelligence), Morgan Kaufmann, Los Altos, Calif., 1–11.
Deininger, R. A. (1966). “Computer aided design of waste collection and treatment systems.” Proc., 2nd American Water Resource Conf., Univ. of Chicago, Chicago.
Diogo, A. F. (1996). “Optimização tridimensional de sistemas urbanos de drenagem.” Ph.D. thesis, FCTUC, Univ. of Coimbra, Coimbra, Portugal.
Diogo, A. F., Walters, G. A., Sousa, E. R., and Graveto, V. M. (2000). “Three-dimensional optimization of urban drainage systems.” Comput. Aided Civ. Infrastruct. Eng., 15(6), 409–426.
Dolan, W. B., Cummings, P. T., and Le Van, M. D. (1989). “Process optimization via simulated annealing: Application to network design.” AIChE J., 35(5), 725–736.
Dowsland, K. A. (1991). “Hill-climbing, simulated annealing, and the Steiner problem in graphs.” Eng. Optimiz., 17, 91–107.
Even, S. (1979). Graph algorithms, Computer Science, Inc., Md.
Froise, S., and Burges, S. J. (1978). “Least-cost design of urban-drainage networks.” J. Water Resour. Plan. Manage. Div., Am. Soc. Civ. Eng., 104(1), 75–92.
Garey, M. R., and Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP completeness, Freeman, San Francisco.
Geman, S., and Geman, D. (1984). “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.” IEEE Trans. Pattern Anal. Mach. Intell., 6(6), 721–741.
Gibbons, A. (1985). Algorithmic graph theory, Cambridge University Press, Cambridge, U.K.
Gidas, B. (1985). “Nonstationary Markov chains and the convergence of the annealing algorithm.” J. Stat. Phys., 39(1/2), 73–131.
Haestad. (2004). Wastewater collection system modeling and design, Haestad methods, Waterbury, Conn.
Hajek, B. (1988). “Cooling schedules for optimal annealing.” Math. Op. Res., 13(2), 311–329.
Kirkpatrick, S. (1984). “Optimization by simulated annealing: Quantitative studies.” J. Stat. Phys., 34(5/6), 975–986.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). “Optimization by simulated annealing.” Science, 220, 671–680.
Laarhoven, P. J. M., and Aarts, E. H. L. (1988). Simulated annealing: Theory and applications, Reidel, Dordrecht, Holland.
Liebman, J. C. (1967). “A heuristic aid for the design of sewer networks.” J. Sanit. Eng. Div., Am. Soc. Civ. Eng., 93(4), 81–90.
Lundy, M., and Mees, A. (1986). “Convergence of an annealing algorithm.” Math. Program., 34, 111–124.
Mai, S. W., and Evans, D. J. (1984). “A parallel algorithm for the enumeration of the spanning trees of a graph.” Parallel Comput., 1, 275–286.
Merritt, L. B., and Bogan, R. H. (1973). “Computer-based optimal design of sewer systems.” J. Environ. Eng. Div. (Am. Soc. Civ. Eng.), 99(1), 35–53.
Pereira, D. J. (1988). “Redes Urbanas de drenagem—Projecto assistido por computador com optimização tridimensional.” Ph.D. thesis, Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa, Lisboa, Portugal.
Simpson, A. R., Dandy, G. C., and Murphy, L. J. (1994). “Genetic algorithms compared to other techniques for pipe optimization.” J. Water Resour. Plan. Manage., 120(4), 423–443.
SMASC. (1993). Interceptor do Loreto e ligação à estrada Adémia Eiras, Projecto, Coimbra.
SMASC. (1995). Bacia da Ribeira de Eiras Vol. II—Estação elevatória de esgotos da Estação Velha, REEP, SMASC, Coimbra.
Walters, G. A. (1992). “A review of pipe network optimization techniques.” Pipeline systems, Kluwer Academic, Dordrecht, Holland, 3–13.
Walters, G. A., and Lohbeck, T. (1993). “Optimal layout of tree networks using genetic algorithms.” Eng. Optimiz., 22, 27–48.
Walters, G. A., and Smith, D. K. (1995). “Evolutionary design algorithm for optimal layout of tree networks.” Eng. Optimiz., 24, 261–281.
Walters, G. A., and Templeman, A. B. (1979). “Nonoptimal dynamic programming algorithms in the design of minimum cost drainage systems.” Eng. Optimiz., 4, 139–148.
Information & Authors
Information
Published In
Journal of Hydraulic Engineering
Volume 132 • Issue 9 • September 2006
Pages: 927 - 943
Copyright
© 2006 ASCE.
History
Received: Dec 30, 2003
Accepted: Jul 14, 2005
Published online: Sep 1, 2006
Published in print: Sep 2006
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.