Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/5453
標題: 禁忌搜尋法及模擬退火法於污水管網最佳化設計之應用
The Application of Tabu Search and Simulated Annealing on the Optimal Design Of Sewer Networks
作者: 卓延穎
Cho, Yen-Ying
關鍵字: Tabu Search;禁忌搜尋法;Simulated Annealing;Sewer Networks;模擬退火法;污水管網;最佳化
出版社: 環境工程學系所
引用: 內政部營建署,「污水下水道設計指南」,臺北,2003。 內政部營建署,「苗栗縣南庄鄉污水下水道系統規劃報告」,2003。 內政部營建署,「雲林縣西螺鎮污水下水道系統規劃報告」,2003。 王聖丰,「禁忌搜尋法於污水下水水最佳化之應用」,國立中興大學環工系,碩士論文,2006。 李佩穎,「啟發式演算法在地下水復育優選問題之應用」,國立中興大學環工系,碩士論文,2006。 林禹豪,「平行禁忌搜尋法於最佳化配水管網設計之應用」,國立中興大學環工系,碩士論文,2003。 林師檀,「禁忌搜尋法與遺傳演算法混合模式在地下水復育問題之應用」,國立中興大學環境工程系,碩士論文,2002。 徐君豪,「全域工程最佳化之模擬退火法」,碩士論文,淡江大學機械工程研究所,1998。 翁煥廷、林碧亮、盧品仲、廖述良,「都市污水下水道管網最佳水力設計模式」,第十四屆環境規劃與管理研討會,2001。 翁煥廷、廖述良,「應用遺傳演算法於污水管網系統配置最佳化模式之研究」,環工年會論文集,2005。 張宏岳,「污水下水道管網系統最佳化水理設計之研究」,國立中興大學環境工程系,碩士論文,2003。 張嘉君,「應用模擬退火法求解營建工程專案多重資源排程最佳化之研究」,碩士論文,朝陽科技大學營建工程系研究所,2003。 張燕鐸,「應用禁忌搜尋法於污水下水水最佳化之設計-以中興大學為例」,國立中興大學環工系,碩士論文,2007。 許鎮龍、陳至誠,「污水下水道最佳化設計模式引用之本土化費用方程式演繹」,第十一屆下水道及水環境再生研討會論文集,2001。 彭聖萍,「平行模擬退火法於配水管網最佳化設計之應用」,碩士論文,中興大學環境工程學研究所。 葉恩仲,「模擬退火法在地下水復育優選問題之應用」,碩士論文,中興大學環境工程學研究所,2002。 歐陽嶠暉,「下水道工程學」,長松出版社,桃園,1981。 潘子欽,高正忠,「以基因演算法結合二次規劃求解下水道收集系統計優選模式」,下水道工程實務研討會, 2003。 駱尚廉,廖浡延,「污水下水道自淨設計之流量-坡度-管宰圖」,第九屆下水道研討會論文集,155-171,1999。 薛富南,「基因演算法應用於污水下水管網系統設計最佳化之研究」,立德管理學院資源環境系,碩士論文,2007。 羅薪又,劉恆昌,「污水下水道規劃設計參數之應用探討」,第十屆下水道研討會論文集,23-31,2000。 Charalambous, C. and Elimam, A. A., “Heurisitic design of sewer networks,” Journal of the Environmental Engineering, ASCE, 116(6), 1181-1199, 1990. Chelouah, R. and Siarry, P., “Tabu search applied to global optimization,” European Journal of Operational Pesarech, 123, 256-270. 2000. Desher, D. P. and Davis, P. K., “Designing sanitary sewers with microcomputer,” Journal of the Environmental Engineering, ASCE, 115(6), 993-1007, 1986. Elimam, A. A., Charalambous, C. and Ghobrial, F. H., “Optimum design of large sewer networks,” Journal of the Environmental Engineering, ASCE, 115(6), 1171-1190, 1989. Ermolin, Y. A., “Mathematical modeling for optimized control of Moscow’s sewer net work,” Applied Mathematic Modelling, 23(7), 543-556, 1998. Ermolin, Y. A., Zats, L. I. and Kajisa, T., “Hydraulic relibility index for sewage pumping stations,” Urban Water, 4, 301-306, 2002. Glover, F. and Laguna, M., Tabu Search., Kluwer Academic, Boston., 1999. Gupta, A., Mehndiratta, S. L. and Khanna, P., “Gravity wastewater collection systems optimization,” Journal of the Environmental Engineering, ASCE, 109, 1195-1209, 1983. Gupta, J. M., Agarwal, S. K., and Khanna, P., “Optimum design of wastewater collection systems,” J. Envir. Engrg. Div., ASCE, 102(5), 1029-1041,1976. Holland, M. E., Computer Model of Wastewater Collection Systems, Harvard Water Resources Group, Harvard University, Cambridge, Mass, 1966. Kloahan, F. and Liang, M., “A tabu search approach to optimization of drilling operations,” Computer ind. Engng, 31(1/2), 371-374, 1996. Lee, I., “Aritificial intelligence search methods for muliti-machine two-stage scheduling with due date penalty, inventory, and machining cost,” Computers & Operations Research, 28, 838-852, 2001. Liang, L. Y., Thompson, R. G. and Young, D. M., “Optimising the design of sewer networks using genetic algorithms and tabu search,” Engineering, Construction and Architectural Management, 11(2), 101-112, 2004. Lin, M. D., Liu, Y. H., Liu, G. F. and Chu, C. W., “Scatter search heuristic for least-cost design of water distribution networks”, Journal of Environmental Engineering and Management, 37, 857-876, 2007. Merrit, L. B. and Bogan, R. H., “computer-Base Optimal Design of Sewer System”, Journal of the Environmental Engineering Division, ASCE, Vol. 99, No. EE1, pp. 35-53, 1973. Afshar, M. H., “Partially Constrained Ant Colony Optimization Algorithm for the Solution of Constrained Optimization Problems: Application to Storm Water Networks Design”, Advances in water Resources, 30, 954-965, 2007. Salhi, S., “Defining tabu list and aspiration criterion within tabu search methods,” Comprter Ops Res, 29, 67-86, 2002. Siarry, P., and Berthiau, G. (1997). "Fitting of Tabu Search to optimize functions of continuous variables." International Journal for Numerical Methods in Engineering, 40(13), 2449-2457. Swamee, P. K., “Design of sewer line,” Journal of the Environmental Engineering, ASCE, 127(9), 776-781, 2001. Tasubakitani, S. and James, R. E., “Optimizing tabu list size for the trasvel salesman problem,” Computer Ops Res, 25(2), 91-97, 1997. Walsh, S. and Browm, C. L.,”Least cost method for sewer design,” Journal of Environmental Engineering, 99, 333-345, 1973. Wang, T. Y. and Wu, K. B., “A parameter design procedure for the simulated annealing algorithm under the computational time constraint”, Computer & Operation Res, 26, pp. 665-678, 1999. Yeh, S. F. and Lin, M. D., “Development of Cost Functions of Sewer Collection Systems in Taiwan,” Proc. of A&WMA 99th Annual Conference, New Orleans, LA, U.S.A., 2006. Sung, Y. H., Lin, M. D., Lin, Y. H., and Liu, Y. L., “Tabu Search Solution of Water Distribution Network Optimization”, Journal of Environmental Engineering, 17, 177-187, 2007.
摘要: 
污水下水道系統為國家重要的基礎建設,除了可以改善河川污染問題之外,污水下水道普及率更是被視為一個國家建設發展與環境品質中的一項重要指標。根據內政部營建署統計資料得知2007年台灣地區公共污水下水道普及率為 17.48%,跟其他已開發國家及開發中國家相比較都明顯落後,亟待提升,因此污水下水道建設已成為政府近期的主要施政項目之一。然而污水下水道系統之建設經費非常龐大,完整的污水下水道系統包括污水收集管線及污水處理廠,在目前政府財源有限的情況下,如何妥善地以最合乎經濟效益的方式規劃污水下水道系統,已是一個刻不容緩的問題。
一般而言,一個具有經濟效益的設計,多是希望能以最小的成本,建置出符合設計規範的污水下水道系統,此一工作則有賴優選技術之應用。優選技術大致可分為定率式與序率式方法二大類型,其中定率式包括有傳統的線性規劃、非線性規劃、動態規劃等,然而這些方法因本身的尋優機制容易陷入局部最佳解中,較不適用於求解污水下水道管網設計最佳化等,屬於高複雜度且非線性的問題。而序率式方法乃包括所謂的啟發式演算法之遺傳演算法、模擬退火法(simulated annealing, SA)、禁忌搜尋法(tabu search, TS)、分散搜尋法、螞蟻演算法等,則都曾成功地應用於求解高度複雜及非線性優選問題。
本研究即以TS與SA,作為求解污水下水道系統配置問題之最佳化工具,求解最小建置成本,本研究將以四個案例做為求解能力測試,並與傳統污水設計模式CPAMI做比較。研究成果顯示,利用TS與SA可求得低成本並符合各項污水下水道設計規範之設計方案;反觀由CPAMI所求得配置方案,建置成本較高,且有部分管線不符合下水道設計規範,由此可見,在污水下水管網配置問題中,TS模式及SA模式具有良好尋優能力。

The sewerage system is the important capital construction of the country. It not only improves polluting of rivers, but also be one important indicator of the country's construction development and environmental quality.
According to the statistics from Construction and Planning Agency, Ministry of the Interior in 2007, the public sewage popularity of Taiwan is 17.48%. It falls behind other developed counties obviously. So sewage system is main administrative project of government. But the building costs of sewage system is very expensive, it is important to build sewage system with cost-benefit in the limited financial situation.
Generally, optimal tool can help engineers to use the minimal layout cost to design a standard and regular sewerage system. Therefore, this study uses tabu search (TS) and simulated annealing (SA), the heuristic algorithm developed for solving complicated global optimization problems, to solve the minimal cost problem of sewage system designs. Four sewage system(two virtual and two realistic) were uses as case studies and a model “ CPAMI “ traditionally used by engineers for sewage system designs is also employed in this study to compare the design ability with TS and SA.
The results indicate that TS and SA are capable of finding out high quality solution (feasible and low cost design)very efficiently. However, the solutions obtained by the traditional model “CPAMI” were either infeasible (with some violations of flow velocity restrictions ) or expensive. The performance of TS and SA in sewage system designs obviously are better than conventional techniques.
URI: http://hdl.handle.net/11455/5453
其他識別: U0005-2108200815424800
Appears in Collections:環境工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.