Applying tabu search and simulated annealing to the optimal design of sewer networks

Abstract

Optimizations of sewer network designs create complicated and highly nonlinear problems wherein conventional optimization techniques often get easily bogged down in local optima and cannot successfully address such problems. In the past decades, heuristic algorithms possessing robust and efficient global search capabilities have helped to solve continuous and discrete optimization problems and have demonstrated considerable promise. This study applied tabu search (TS) and simulated annealing (SA) to the optimization of sewer network designs. For a case study, this article used the sewer network design of a central Taiwan township, which contains significantly varied elevations, and the optimal designs from TS and SA were compared with the original official design. The results show that, in contrast with the original design's failure to satisfy the minimum flow-velocity requirements, both TS and SA achieved least-cost solutions that also fulfilled all the constraints of the design criteria. According to the average performance of 200 trials, SA outperformed TS in both robustness and efficiency for solving sewer network optimization problems.

Keywords:

• sewer network
• optimization
• tabu search
• simulated annealing

Acknowledgements

This research was funded by a grant from the National Science Council of the Republic of China (NSC 96-2628-E-005-001-MY3). The authors gratefully appreciate this support.