Development of a Hybrid Algorithm for the Optimal Design of Sewer Networks
Publication: Journal of Water Resources Planning and Management
Volume 144, Issue 8
Abstract
In this paper, a particle swarm optimization (PSO) algorithm augmented by fly-back and harmony memory features—referred to as the heuristic particle swarm optimization (HPSO) algorithm—is used for solving the sewer network optimization problem. The fly-back and harmony memory mechanisms are meant to avoid ineffective particle flights and to increase the efficiency and computational stability of the PSO algorithm. Problem constraints are checked and observed at two levels through a mechanism that enhances the convergence of the PSO algorithm as compared with those of conventional penalizing methods used in other evolutionary methods. The HPSO algorithm is then combined with dynamic programming (DP) to yield a hybrid algorithm called dynamic programming with heuristic particle swarm optimization (DPHPSO). Eliminating the inadequacies associated with either component method, this hybrid algorithm does not rely on the discretization of elevations, thereby reducing the complexity of the problem and the time required for solving it when compared with the rival DP method. Moreover, compared with the situation in which an evolutionary algorithm is used alone, the DP partitioning employed in HPSO leads to a reduced number of decision variables in the metaheuristic algorithm and also decreases the changes in ultimate objective function. The proposed methods are validated by applying them to three benchmark sewer network problems. Comparison of the results with those obtained from other optimization methods indicates the superiority of these algorithms over those reported in the literature.
Get full access to this article
View all available purchase options and get full access to this article.
References
Afshar, M. H. 2006a. “Application of a genetic algorithm to storm sewer network optimization.” Sci. Iran. 13 (3): 234–244.
Afshar, M. H. 2006b. “Improving the efficiency of ant algorithms using adaptive refinement: Application to storm water network design.” Adv. Water. Resour. 29 (9): 1371–1382. https://doi.org/10.1016/j.advwatres.2005.10.013.
Afshar, M. H. 2007. “Partially constrained ant colony optimization algorithm for the solution of constrained optimization problems: Application to storm water network design.” Adv. Water. Resour. 30 (4): 954–965. https://doi.org/10.1016/j.advwatres.2006.08.004.
Afshar, M. H. 2008. “Rebirthing particle swarm optimization algorithm: Application to storm water network design.” Can. J. Civ. Eng. 35 (10): 1120–1127. https://doi.org/10.1139/L08-056.
Afshar, M. H. 2010. “A parameter free continuous ant colony optimization algorithm for the optimal design of storm sewer networks: Constrained and unconstrained approach.” Adv. Eng. Software 41 (2): 188–195. https://doi.org/10.1016/j.advengsoft.2009.09.009.
Afshar, M. H., A. Afshar, M. A. Mariño, and A. A. S. Darbandi. 2006. “Hydrograph-based storm sewer design optimization by genetic algorithm.” Can. J. Civ. Eng. 33 (3): 319–325. https://doi.org/10.1139/l05-121.
Afshar, M. H., and M. A. Mariño. 2006. “Application of an ant algorithm for layout optimization of tree networks.” Eng. Optim. 38 (3): 353–369. https://doi.org/10.1080/03052150600557783.
Afshar, M. H., and M. Rohani. 2012. “Optimal design of sewer networks using cellular automata-based hybrid methods: Discrete and continuous approaches.” Eng. Optim. 44 (1): 1–22. https://doi.org/10.1080/0305215X.2011.557071.
Afshar, M. H., and M. Rohani. 2014. “Optimal design of gravitational sewer networks with general cellular automata.” [In Persian.] J. Water Wastewater 25 (2): 12–25.
Afshar, M. H., M. Shahidi, M. Rohani, and M. Sargolzaei. 2011. “Application of cellular automata to sewer network optimization problems.” Sci. Iran. 18 (3): 304–312. https://doi.org/10.1016/j.scient.2011.05.037.
Afshar, M. H., and M. H. Sotoodeh. 2008. “Optimal design of the sewer networks with the genetic algorithm.” J. Eng. Sci. Iran Univ. Sci. Technol 2 (19): 37–48.
Argaman, Y., U. Shamir, and E. Spivak. 1973. “Design of optimal sewerage systems.” J. Environ. Eng. 99 (5): 703–716.
Barlow, J. F. 1972. “Cost optimization of pipe sewerage systems.” Proc. Inst. Civ. Eng. 53 (3): 639–646. https://doi.org/10.1680/iicep.1972.5385.
Botrous, A., I. El-Hattab, and M. Dahab. 2000. “Design of wastewater collection networks using dynamic programming optimization technique.” In Proc., ASCE Nat. Conf., Environmental and Pipeline Engineering, 503–512. Reston, VA: ASCE.
Cembrowicz, R. G., and G. E. Krauter. 1987. “Design of cost optimal sewer networks” In Proc., 4th Int. Conf. on Urban Storm Drainage, edited by W. Gujer et al., 367–372. Lausanne, Switzerland: Ecole Poly Fed.
Dajani, J. S., R. S. Gemmell, and E. K. Morlok. 1972. “Optimal design of urban wastewater collection networks.” J. Sanitary. Eng. Div. 98 (6): 853–867.
Dajani, J. S., and Y. Hasit. 1974. “Capital cost minimization of drainage networks.” J. Environ. Eng. 100 (2): 325–337.
Deininger, R. A. 1966. “Computer aided design of waste collection and treatment systems.” In Proc., 2nd Annual Conf. of American Water Resources, 247–258. Chicago, IL: University of Chicago.
Deininger, R. A. 1970. “Systems analysis for water supply and pollution control.” In Natural resource systems models in decision making, edited by G. H. Toebes. Lafayette, IN: Water Resources Center, Purdue Univ.
Diogo, A. F., and V. M. Graveto. 2006. “Optimal layout of sewer systems: A deterministic versus a stochastic model.” J. Hydr. Eng. 132 (9): 927–943. https://doi.org/10.1061/(ASCE)0733-9429(2006)132:9(927).
Eberhart, R. C., and J. Kennedy. 1995. “A new optimizer using particle swarm theory.” In Proc., 6th Int. Symp. on Micro Machine and Human Science, 39–43. New York, NY: IEEE.
Elimam, A. A., C. Charalambous, and F. H. Ghobrial. 1989. “Optimum design of large sewer networks.” J. Environ. Eng. 115 (6): 1171–1190. https://doi.org/10.1061/(ASCE)0733-9372(1989)115:6(1171).
Gen, M., and R. Cheng. 1997. Genetic algorithms and engineering design. Hoboken, NJ: Wiley.
Gidley, J. S. 1986. “Optimal design of sanitary sewers.” In Proc., 4th ASCE Conf. on Computing in Civil Engineering, 162–177. Boston, MA.
Guo, Y., G. A. Walters, S. T. Khu, and E. C. Keedwell. 2007. “A novel cellular automata based approach to storm sewer design.” Eng. Optim. 39 (3): 345–364. https://doi.org/10.1080/03052150601128261.
Guo, Y., G. A. Walters, and D. Savic. 2008. “Optimal design of storm sewer networks: Past, present and future.” In Proc., 11th Int Conf. on Urban Drainage. Edinburgh.
Gupta, A., S. Mehndiratta, and P. Khanna. 1983. “Gravity wastewater collection systems optimization.” J. Environ. Eng. 109 (5): 1195–1209. https://doi.org/10.1061/(ASCE)0733-9372(1983)109:5(1195).
Haghighi, A. 2013. “Loop-by-loop cutting algorithm to generate layouts for urban drainage systems.” J. Water. Resour. Plan. Manag. 139 (6): 693–703. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000294.
Haghighi, A. 2017. “Intelligent optimization of wastewater collection networks.” In Intelligence systems in environmental management: Theory and applications, edited by C. Kahraman and I. U. Sari. 41–65. Cham: Springer.
Haghighi, A., and A. E. Bakhshipour. 2012. “Optimization of sewer networks using an adaptive genetic algorithm.” Water. Resour. Manage. 26 (12): 3441–3456. https://doi.org/10.1007/s11269-012-0084-3.
Haghighi, A., and A. E. Bakhshipour. 2015a. “Deterministic integrated optimization model for sewage collection networks using tabu search.” J. Water. Resour. Plan. Manage. 141 (1): 04014045. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000435.
Haghighi, A., and A. E. Bakhshipour. 2015b. “Reliability-based layout design of sewage collection systems in flat areas.” Urban Water. J. 13 (8): 790–802. https://doi.org/10.1080/1573062X.2015.1036085.
Heaney, J. P., R. Pitt, and R. Field. 2000. Innovative urban wet-weather flow management systems. Cincinnati, OH: US Environmental Protection Agency.
Holland, M. E. 1966. “Computer models of wastewater collection systems.” Ph.D. thesis, Harvard Univ.
Izquierdo, J., I. Montalvo, R. Pérez, and V. S. Fuertes. 2008. “Design optimization of wastewater collection networks by PSO.” Comput. Math. Appl. 56 (3): 777–784. https://doi.org/10.1016/j.camwa.2008.02.007.
Karovic, O., and L. W. Mays. 2014. “Sewer system design using simulated annealing in excel.” Water. Resour. Manage. 28 (13): 4551–4565. https://doi.org/10.1007/s11269-014-0750-8.
Kulkarni, V. S., and P. Khanna. 1985. “Pumped wastewater collection systems optimization.” J. Environ. Eng. 111 (5): 589–601. https://doi.org/10.1061/(ASCE)0733-9372(1985)111:5(589).
Li, G. Y., and R. G. S. Matthew. 1990. “New approach for optimization of urban drainage systems.” J. Environ. Eng. 116 (5): 927–944. https://doi.org/10.1061/(ASCE)0733-9372(1990)116:5(927).
Li, L., Z. Huang, F. Liu, and Q. Wu. 2007. “A heuristic particle swarm optimizer for optimization of pin connected structures.” Comput. Struct. 85 (7–8): 340–349. https://doi.org/10.1016/j.compstruc.2006.11.020.
Liang, L. Y., R. G. Thompson, and D. M. Young. 2004. “Optimizing the design of sewer networks using genetic algorithms and tabu search.” J. Eng. Constr. Archit. Manage. 11 (2): 101–112. https://doi.org/10.1108/09699980410527849.
Liebman, J. C. 1967. “A heuristic aid for the design of sewer networks.” J. Sanit. Eng. Div. 93 (4): 81–90.
Lowsley, I. H. 1973. “An implicit enumeration algorithm for optimal sewer layout.” Ph.D. thesis, Johns Hopkins Univ.
Mansouri, M., and M. J. Khanjani. 1999. “Optimization of wastewater collection systems using nonlinear programming method.” J. Water Wastewater. 30: 20–30.
Mansouri, M. R., and M. J. Khanjani. 1999. “Optimization of sewer system by the nonlinear programming.” [In Persian.] J. Water and Wastewater 30: 20–30.
Mays, L. W. 1976. “Optimal layout and design of storm sewer systems.” Ph.D. thesis, Univ. of Illinois at Urbana-Champaign.
Mays, L. W., and H. G. Wenzel. 1976. “Optimal design of multi-level branching sewer systems.” Water. Resour. Res. 12 (5): 913–917. https://doi.org/10.1029/WR012i005p00913.
Mays, L. W., H. G. Wenzel, and J. C. Liebman. 1976. “Model for layout and design of sewer systems.” J. Water. Resour. Plan. Manage. Div. 102 (2): 385–405.
Mays, L. W., and B. C. Yen. 1975. “Optimal cost design of branched sewer systems.” Water. Resour. Res. 11 (1): 37–47. https://doi.org/10.1029/WR011i001p00037.
Meredith, D. D. 1971. “Dynamic programming with case study on planning and design of urban water facilities.” In SEC. IX, Treatise on Urban Water Systems, 590–652. Fort Collins, CO: Colorado State Univ.
Merritt, L. B., and R. H. Bogan. 1973. “Computer-based optimal design of sewer systems.” J. Environ. Eng. Div. 99 (1): 35–53.
Moeini, R., and M. H. Afshar. 2012. “Layout and size optimization of sanitary sewer network using intelligent ants.” Adv. Eng. Software 51: 49–62. https://doi.org/10.1016/j.advengsoft.2012.05.003.
Moeini, R., and M. H. Afshar. 2013. “Constrained ant colony optimisation algorithm for the layout and size optimisation of sanitary sewer networks.” Urban Water. J. 10 (3): 154–173. https://doi.org/10.1080/1573062X.2012.716445.
Moeini, R., and M. H. Afshar. 2017. “Arc based ant colony optimization algorithm for optimal design of gravitational sewer networks.” Ain Shams Engineering J. 8 (2): 207–223. https://doi.org/10.1016/j.asej.2016.03.003.
Nafisi, M., and A. Ahmadi. 2014. “Sewer networks optimization by particle swarm optimization with abilities of fly-back mechanism and harmony memory.” [in Persian.] J. Water Wastewater 25 (4): 76–87.
Navin, P. K., and Y. P. Mathur. 2016. “Layout and component size optimization of sewer network using spanning tree and modified PSO algorithm.” Water. Resour. Manage. 30 (10): 3627–3643. https://doi.org/10.1007/s11269-016-1378-7.
Nzewi, E. U., D. D. Gray, and M. H. Houck. 1985. “Optimal design program for gravity sanitary sewers.” Civ. Eng. Syst. 2 (3): 132–141. https://doi.org/10.1080/02630258508970397.
Pan, T. C., and J. J. Kao. 2009. “GA-QP model to optimize sewer system design.” J. Environ. Eng. 135 (1): 17–24. https://doi.org/10.1061/(ASCE)0733-9372(2009)135:1(17).
Papalexandri, K. P., E. N. Pistikopoules, and C. A. Floudas. 1994. “Synthesis of mass exchanger networks for the waste minimization: An MINLP approach.” In Vol. 133 of Proc., IChemE Symp. Series, 351–358. Rugby, UK: IChemE.
Price, R. K. 1978. “Design of storm water sewers for minimum construction cost.” In Proc., 1st Int. Conf. on Urban Strom Drainage, 636–647. Southampton, UK.
Rohani, M., M. H. Afshar, and R. Moeini. 2015. “Layout and size optimization of sewer networks by hybridizing the GHCA model with heuristic algorithms.” Sci. Iran. 22 (5): 1742–1754.
Safavi, H. R., and M. A. Geranmehr. 2017. “Optimization of sewer networks using the mixed-integer linear programming.” Urban Water. J. 14 (5): 452–459. https://doi.org/10.1080/1573062X.2016.1176222.
Sotoodeh, M. H. 2003. “Optimal design of sewer networks.” M.Sc. thesis, Iran Univ. of Science and Technology.
Steele, J. C., K. Mahoney, O. Karovic, and L. W. Mays. 2016. “Heuristic optimization model for the optimal layout and pipe design of sewer systems.” Water. Resour. Manage. 30 (5): 1605–1620. https://doi.org/10.1007/s11269-015-1191-8.
Strategic Planning and Control Deputy of Iran Presidential Organization. 2013. List price for base unit to collect and transfer sewer network. Tehran, Iran: Iran Presidential Organization.
Swamee, P. K. 2001. “Design of sewer line.” J. Environ. Eng. 127 (9): 776–781. https://doi.org/10.1061/(ASCE)0733-9372(2001)127:9(776).
Swamee, P. K., and A. K. Sharma. 2013. “Optimal design of a sewer line using linear programming.” Appl. Math. Model 37 (6): 4430–4439. https://doi.org/10.1016/j.apm.2012.09.041.
Tang, W. H., L. W. Mays, and B. C. Yen. 1975. “Optimal risk-based design of storm sewer networks.” J. Environ. Eng. Div. 101 (3): 381–398.
Tekeli, S., and H. Belkaya. 1986. “Computerized layout generation for sanitary sewers.” J. Water. Resour. Plan. Manage. 112 (4): 500–515. https://doi.org/10.1061/(ASCE)0733-9496(1986)112:4(500).
Walsh, S., and L. C. Brown. 1973. “Least cost method for sewer design.” J. Environ. Eng. Div. 99 (3): 333–345.
Walters, G. A., and T. Lohbeck. 1993. “Optimal layout of tree networks using genetic algorithms.” Eng. Optim. 22 (1): 27–48. https://doi.org/10.1080/03052159308941324.
Walters, G. A., and D. K. Smith. 1995. “Evolutionary design algorithm for optimal layout of tree networks.” Eng. Optim. 24 (4): 261–281. https://doi.org/10.1080/03052159508941193.
Walters, G. A., and A. B. Templeman. 1979. “Non-optimal dynamic programming algorithms in the design of minimum cost drainage systems.” Eng. Optim. 4 (3): 139–148. https://doi.org/10.1080/03052157908902416.
Yen, B. C., H. G. Wenzel, L. W. Mays, and W. H. Tang. 1976. “Advanced methodologies for design of storm sewer systems.”. Urbana, IL: Water Resources Center, Univ. of Illinois.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 144 • Issue 8 • August 2018
Copyright
©2018 American Society of Civil Engineers.
History
Received: Jan 28, 2017
Accepted: Jan 3, 2018
Published online: Jun 5, 2018
Published in print: Aug 1, 2018
Discussion open until: Nov 5, 2018
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.