Journal of Environmental
1684-8799 / Print ISSN 1726-2135
© 2005 ISEIS.
All rights reserved.
Establishing an Optimization Model for Sewer System Layout with Applied Genetic Algorithm
H. T. Weng* and S. L. Liaw
Graduate Institute of Environmental Engineering, National Central University, Chungli 32054, Taiwan
*Corresponding author. Email: firstname.lastname@example.org
In this study, a genetic algorithm (GA) is first used to establish a combinatorial optimization model, called the Sewer System Optimization Model for Layout & Hydraulics (GA/SSOM/LH), to find an optimal design for a real urban sewer system. The problems of "network layout" and "hydraulic design" optimization are considered simultaneously. The modeling concept is to combine the fundamental principles of the GA, to the generation of possible network layouts as well as to develop a "hydraulic design" optimization module, the Sewerage System Optimization model (SSOM), which can find the best sewer system layout by checking the overall least-cost hydraulic design of several possible alternate network layouts. SSOM is a 0-1 Mixed Integer Programming (MIP) in which a traditional algorithm, the Bounded Implicit Enumeration (BIE) is applied to determine the optimal size and slope for each. Unlike the BIE algorithm, 'one chromosome' in the GA evolution is coded to represent 'one system layout' parameter. Specific coding strings on 'parameters' are operated directly and are more robust when combined with the SSOM module. Hence the GA can evolve quickly generating an optimized system layout and ensuring a solution closer to the global optimum in a 'fast' manner. Finally, a case study was conducted on a 73-node project to verify the optimal system layout as generated by the GA/SSOM/LH model.
Keywords: Bounded Implicit Enumeration, Genetic Algorithm, hydraulic design, N-P Complete problem, system layout, 0-1 Mixed Integer Programming
Full Text (PDF) | Export citation to: EndNote RefMan
Cite this paper as: H. T. Weng and S. L. Liaw, 2005. Establishing an Optimization Model for Sewer System Layout with Applied Genetic Algorithm. Journal of Environmental Informatics, 5(1), 26-35. http://dx.doi.org/10.3808/jei.200500043
- Benson, R.E., (1985). Self-cleaning slope for partially full sewers. J. Environ. Eng. Div., ASCE, 111(6), 925-928.
- Chang, S.Y. and Liaw, S.L. (1987). An efficient implicit enumeration algorithm for multistage systems, presentated at the TIMS/ORSA Joint National Meeting, New Orleans, LA, May 4-6.
- Dandy, G.C. and Engelhardt, M. (2001). Optimal scheduling of pipe replacement using genetic algorithms. J. Water Resour. Plann. Manage., ASCE, 127(4), 214-223.
- Goldberg, D.E. and The University of Alabama (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, 1st Edition, Addison-Wesley Publishing Company, Inc., USA.
- Gupta, A., Mehndiratta, S.L. and Khanna, P. (1983). Gravity waste water collection systems optimization, J. Environ. Eng. Div., ASCE, 109(5), 1195-1208.
- Halhal, D., Walters G.A. and Savic, D.A. (1997). Water network rehabilitation with structured messy genetic algorithms. J. Water Resour. Plann. Manage., ASCE, 123(3), 137-146.
- Hsu, C.L. (1984). Computer Aided Design for Large Sewerage Systems, A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering, AIT.
- Liaw, S.L. (1991). Optimization of Sewer System: System Layout, International Conference on Ccomputer Application in Water Resources, Tamkang University, 2, pp. 157-164.
- Liaw, S.L. and Lin, B.L. (1991). Optimization of Sewer System: Hydraulic Design, International Conference on Computer Application in Water Resources, Tamkang University, 2, pp. 77-84.
- Lin, B.L. (1990). An Optimization Model for Sewer System Layout and Design, A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering, Tamkang University, Taiwan.
- Mays, L.W. and Yen, B.C. (1975). Optimal cost design of branched sewer systems. Water Resour. Res., 11(1), 37-47.
- McKinney, D.C. and Lin, M.D. (1994). Genetic algorithm solution of groundwater management models. Water Resour. Res., 30(6), 1897-1906.
- Orth, H.M. (1986), Model-Based Design of Water Distribution and Sewage Systems, 1st Edition, John Wiley & Sons, New York, USA.
- Pilar, M., Adela, G.G. and Jose, L.A. (1999). Water distribution network optimization using a modified genetic algorithms. Water Resour. Res., 35(11), 3467-3473.
- Savic, D.A. and Walters, G.A. (1997). Genetic algorithms for Least-cost design of water distribution networks. J. Water Resour. Plann. Manage., ASCE, 123(2), 67-77.
- Shih, C.S. (1983). Application of DDDP in Routing of Sewer System and Selecting of Pipe Size and Excavation Depth, A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering, Cheng-Kung University, Taiwan.
- Simpson, A.R., Dandy, G.C. and Murphy, L.J. (1994). Genetic algorithms compared to other techniques for pipe optimization. J. Water Resour. Plann. Manage., ASCE, 120(4), 423-443.
- Swamee, P.K. (2001). Design of sewer line. J. Environ. Eng., 127(9), 776-781.
- Tekeli, T. and Belkaya, H. (1986). Computerized layout generation for sanitary sewers. J. Environ. Eng. Div., ASCE, 112(4), 500-515.
- Weng, H.T. and Liaw, S.L. (2003). An optimization model for sewer hydraulic design (SSOM) base on novel trenchless technology, in Proc. IWA Asia-Pacific Regional Conference, Bangkok, Thailand, Oct. 19-23.
- Weng, H.T. and Liaw, S.L. (2003). The study of applying enumeration algorithm to a sewer system layout optimization model (SSOM/LH), in Proc. 16th Environmental Planning and Management Conference of CIEnvE, Taiwan, Nov. 28-29.
- Wolfram Research (2005). MathWorldTM the web's most complete mathematical resource created and maintained by Eric W. Weisstein, http://mathworld.wolfram.com/ (accessed Feb. 18, 2005).