Sewer Layout Design in Flat Areas Using Growing Spanning Tree Method and Tabu Search Optimization

Document Type : Research Article


Assistant Professor, Department of Civil Engineering, Shahid Chamran University of Ahvaz


In order to optimize sewer networks layout in flat areas, this paper aims at introducing an optimization
model based on the growing spanning tree and Tabu search methods. In the beginning, an undirected
loop graph named as the base graph is prepared for the network at hand. For extracting a feasible treelike
sewer layout from the base graph, one pipe from each loop must be cut. For this purpose, the
method of growing spanning tree from the graphs theory is adopted. Through this method, by defining
a root (sewer system’s outlet), it is possible to develop a spanning tree from downstream to upstream
of the network. Herein, some modifications are added to the method to be used for sewer networks. In
flat areas, the number of possible trees exponentially increases with the network size. For finding the
optimum layout among too many alternatives, an objective function is defined in terms of sewers
length and discharge. The decision variables are the pipes to be cut for opening the base graph’s loops
plus the cut locations which can be either at the upstream or downstream of the chosen pipes. A Tabu
search optimization model is developed for solving the problem. The proposed scheme is then applied
against a hypothetical example and a part of Hendijan sewer network. The results manifest that the
method is computationally efficient, reliable and capable of solving large-scale problems.