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

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.