Extension of the Hybrid Ant Colony Optimization Algorithm for Layout and Size Optimization of Sewer Networks

Abstract

In this paper, the incremental solution building capability of Ant Colony Optimization Algorithm (ACOA) is exploited using a Tree Growing Algorithm (TGA) augmented with the efficiency of Nonlinear Programming (NLP) methods leading to a hybrid ACOA-TGA-NLP algorithm for the effective layout and pipe size optimization of pumped/gravitational sewer networks. Solution of layout and pipe size optimization of sewer network requires the determination of pipe locations, pipe diameters, average pipe cover depths, drop and pump heights minimizing the total cost of the sewer network subject to operational constraints. The resulting problem is a highly constrained Mixed-Integer Nonlinear Programming (MINLP) problem presenting a challenge even to the modern heuristic search methods. In the proposed method, the TGA is used to construct feasible tree-like layouts out of the base layout defined for the sewer network, the ACOA is used to optimally determine the pipe diameters of the constructed layout, and finally NLP is used to determine the pipe slopes from which the remaining characteristics of the network such as pump/drop locations and heights are determined. In the NLP stage of the model, the velocity and flow depth constraints are expressed in terms of the slope constraints which are easily enforced as box constraint of the NLP solver leading to a considerable reduction of the search space size. The proposed hybrid ACOA-TGA-NLP has two significant advantages over other available methods. First, this method can be used for both pumped and gravitational sewer networks. Second, the computational effort is significantly reduced compared to alternative methods. Another method is also proposed here in which the layout of the network is determined by an ad-hoc method based on engineering judgment while the component design of the network is carried out by ACOA-NLP method as defined above. Proposed hybrid methods are used to solve a benchmark example from the literature and a hypothetical test example and the results are presented and compared with those produced by the existing methods such as SPST-DDDP, SDM-DDDP and GA-DDDP. The results indicate the efficiency and effectiveness of the proposed methods and in particular the ACOA-TGA-NLP method. In fact, the optimal solution of ACOA-TGA-NLP is 149, 64.1, 22.2 and 13.6% cheaper than those of ACOA-NLP, SPST-DDDP, SDM-DDDP and GA-DDDP methods, respectively, for the benchmark text example. Furthermore, ACOA-TGA-NLP yields a solution 80% cheaper than that of ACOA-NLP method for hypothetical test example.

Keywords: Ant Colony Optimization Algorithm, Tree Growing Algorithm, Nonlinear Programming, sewer network, layout and sizing