臺灣博碩士論文加值系統

摘 要

本研究是介紹一種優化汙水下水道佈線設計的新方法。我們從大型積體電路電子繞線設計(routing design)技術中獲得了這一概念，稱為避免障礙直線式史坦納最小樹方法(OARMST)，然後使用混合整數線性規劃(MILP)解決並開發優化汙水下水道佈線設計模式。下水道佈線設計是根據水理重力原理設計，並且應將連絡每個下水道排放節點進行污水排放工作。然而經過優化程序，史坦納點將輔助連接每個汙水排放節點並協助排放汙水流到主幹管中的汙水匯流井。 這些史坦納點將架構出優化佈線系統。優化之汙水下水道系統建造成本:包含地面開挖和下水道管道安裝所需的總成本。理想下水道佈線設計應包含最平坦的可接受坡度的最短管線分佈，並且管道盡可能安裝在最接近地面的位置。在汙水佈線設計中在目標式設定應認真考慮地面高程和埋設管道的深度，因為管線開挖土方與總成本有高度相關。而且這些限制條件必須符合建議的最小和最大坡度之間可接受的管道坡度以及埋設管道的最小深度之規定。本研究建立兩套3維空間考量史坦納汙水佈線優化模式;二階段及全階段方式。經過執行成果比較，全階段方式可得較佳解。此外，全階段方式將所有非線性限制式和目標函數都轉換為簡單的線性格式。並分析了三種類型的優化，包括A型:目標函數只考慮管道長度的最低成本，B型: 只考慮管線開挖量的最低成本，以及C型:管道長和開挖量兩者皆考慮的最小總成本-其目的是要顯示設定整體考量之目標式在優化下水道佈線設計之重要性。最後，與專家的下水道佈線設計相比較，本研究所提出的優化模式執行成果可以節省超過38.83％的成本。

Abstract

This paper introduces a novel method for optimizing sewer layouts. The study obtained the concept from an integrated circuit electronic routing design technique known as the obstacle-avoiding rectilinear Steiner minimal tree method and then solved the developed model problem using mixed integer linear programming. The sewer layout must be designed on the basis of the force of gravity, and sewerage should be carried from each sewer discharge nodes. However, the Steiner nodes serve as optional nodes to link each discharge node and flow to sinks in the main stream. The Steiner nodes are utilized for minimizing the total cost required for installing pipes by cutting the ground and the total cost of sewer pipes. The sewer layout should contain the shortest pipe distribution at the flattest acceptable slope, and the pipe should be installed closest to the ground surface. However, the ground elevation and the depths at which pipes are buried should be seriously considered during the layout design because the ground cutting volume is highly related to total costs. The constraints are subject to the acceptable pipe slopes between the recommended minimum and maximum slopes and the minimum depth at which the pipe is buried. The study constructs two 3D consideration models for optimizing sewer layout design; two stages style and whole stage style. After the comparison, the whole stage style can get the better solution. Furthermore, all the nonlinear constraints and the objective function of the whole stage style are transformed into a simple linear format. The study analysed three types of optimizations including Type A: only considering the minimum cost of the pipe on the objective function, Type B: only considering the minimum cost of cutting the ground, and Type C: considering the minimum total cost of both pipes and cutting the earth to illustrate the importance of considering all conditions to obtain an optimal sewer layout design. The proposed optimization model can save more than 38.83% of the cost required to realize the expert’s manual sewer layout design.

目錄

摘 要 …………………………………………………i
Abstract …………………………………………………iii
目 錄 ………………………………………………v
圖目次 ………………………………………………viii
表目次 ………………………………………………xi

第一章 前言 ………………………………………………………1
1.1研究緣起與目的 ……………………………………………1
1.2 研究內容 ……………………………………………………3

第二章 文獻回顧 ………………………………………………… 6
2.1 避免障礙直線式最小史坦納樹(OARSMT)研究歷史
回顧 ………………………………………………………… 6
2.1.1 史坦納樹 ……………………………………… 6
2.1.2. 避免障礙直線式最小史坦納樹(OARSMT)電路
繞線設計在 VLSIs領域 …………………………………… 10
2.1.2.1迷宮繞線法(maze routing approach)………… 10
2.1.2.2順序法(Sequential based approach) ……… 11
2.1.2.3蟻行優化經驗法(Ant colony optimization heuristic) ………………………………………………12
2.1.2.4連接圖方法(Connection graph approach) …13
2.1.2.5 小結 ……………………………………………17
2.2 汙水管網優化研究歷史回顧……………………………. 18
2.2.1 汙水管網設計基本參數敘述 …………………18
2.2.2 汙水下水道管網系統優化研究文獻 …………… 23
2.2.2.1 固定汙下水道管網佈線下之水力設計優(hydraulic design optimization for a fixed layout) ……………… 23
2.2.2.2 汙水管佈線優化(layout optimization) ……24
2.2.2.3 小結 ……………………………………………25

第三章 研究方法及問題建構與假設 …………………………26
3.1在都市汙水下水道管網設計中注入OARSMT概念之
運用 ……………………………………………………………26
3.2構建連接圖(connection graph) ……………………… 27
3.3 運用混整線性規劃(MILP)產生史坦納點方法 …………28
3.4 問題建構與假設……………………………………………31
3.4.1地形測量(Topographic survey) ………………… 32
3.4.2最小/最大管線坡度考慮和假設 …………………… 32
3.4.3常數的管溝槽開挖寬度設計之假設 ……………… 34
3.4.4汙水下水道管線成本評估和假設 ………………… 35

第四章 下水道佈線優化模式 ………………………………… 36
4.1 兩階段建構污水管網三維度史坦納樹佈線優化
模式 ……………………………………………………………37
4.1.1第一階段建構下水道佈線優化模式 ………………38
4.1.2第二階段在已優化下水道佈線系統下建構
下水道管底高程及管線坡度優化模式 ………………………47
4.2 全階段一次整體建構污水管網三維度史坦納
樹佈線優化模式…………………………………………………49
4.2.1非線性模式建立 ………………………………………49
4.2.2非線性模式轉換成可執行優化模式 ……………… 55
4.2.2.1額外增加管段成本限制式 …………………55
4.2.2.2 變換目標函數 …………………………………56
4.2.3 一個小案例 ………………………………………56

第五章 案例分析 …………………………………………………61
5.1 專家設計的下水道佈線系統 ……………………………63
5.2 本研究優化模式之執行和成果 …………………………65
5.2.1 兩階段建構污水管網三維度史坦納樹.
佈線優化模式之執行成果 ………………………………… 67
5.2.2 全階段一次整體建構污水管網三維度
史坦納樹佈線優化模式執行成果 …………………………68
5.3執行成果比較分析驗證 …………………………………72
5.3.1全階段整體史坦納樹佈線優化模式執
行成果三型態A、B及C比較分析驗證 ……………………72
5.3.2 二階段史坦納樹佈線優化模式與全階
段整體史坦納樹佈線優化模式執行成果比較
分析驗證 ……………………………………………………74
5.3.3 專家設計的下水道佈線系統經優化管
道底高程模式執行成果與全階段整體史坦納
樹佈線優化模式執行成果比較分析驗證 …………………76

第六章 結論與建議 ………………………………………………78

參考文獻 ………………………………………………………80

附錄 ………………………………………………………86

參考文獻

Ebtehaj, I., Bonakdari, H., and Sharifi, A., (2014), “Design criteria for sediment transport in sewers based on self-cleansing concept”, Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2014 15(11):914-924.

Burch, N. and Holte, R. and Muller, M., O’Connell, D. and Schaeffer, J., (2010), “Automating Layouts of Sewers in Subdivisions”, ECAI 2010 H. Coelho et al. (Eds.) IOS Press, 2010

Moeini, R., and Afshar, M. H., (2012), “Layout and size optimization of sanitary sewer network using intelligent ants”, Advances in Engineering Software, 2012 – Elsevier.

Argaman, Y., Shamir, U. and Spivak, E., (1973), “Design of optimal sewerage systems”, Journal of the Environmental Engineering Division,

Swamee, P. K. and Sharma, A. K., (2013),” Optimal design of a sewer line using Linear Programming”, Applied Mathematical Modelling, 37 4430–4439

Holland, M. E., (1966), “Computer models of wastewater collection system”, Ph. D. thesis presented to Harvard University, at Cambridge, Mass.

Swamee, P. K., “Design of Sewer Line”, Journal of Environmental Engineering, 127, 9, pp. 776-781. 2001

Merrit, L.B. and Bogan, R.H., (1973), “Computer-Base Optimal Design of Sewer System”, Journal of the Environmental Engineering Division, ASCE, Vol. 99, No.EE1, pp. 35-53.

Gupta, A., Mehndiratta, S.L. and Khanna, P., (1983), “Gravity Waste water Collection Systems Optimization”, Journal of the Environmental Engineering Division, ASCE, Vol. 109, No. 5, pp.1195-1208.

Kulkarni, V.S. and Kanna, p., (1985 ), Pumped Wastewater Collection System Optimization, Journal of Environmental Engineering, Vol. 111, No. 5, pp.589-601, Oct.

Nzewi, E.U., Gray, D.D. and Houck, M.H., (1985), “Optimal Design Program for Gravity Sanitary Sewers”, Civil Engineering Systems, Vol. 2, pp.132-141.

Safavi, H. and Geranmehr, M. A., (2017), “Optimization of sewer networks using the mixed-integer linear programming”, Urban Water Journal, VOL. 14, NO. 5, 452–459.

Tekeli, S, Belkaya, H, (1986),” Computerized layout generation for sanitary sewers”, J Water Resource Plan Manag 112:500–51.

Mays, L.W. and Yen, B.C., (1975) “Optimal cost Design of Branched Sewer Systems”, Water Resources Research, Vol. 11, No. 1, pp. 37-47.

Jang, SH. (2006), “Urban Storm Sewer Optimal Layout Design Model by DDDP Technique”, 2006 Asia Oceania Geosciences Society, AOGS 2006, Singapore.

Weng, H. T. and Liaw, S. L., (2005),” Establishing an Optimization Model for Sewer System Layout with Applied Genetic Algorithm”, Journal of Environmental Informatics 5 (1) 26-35.

Navin, P. K. & Mathur, Y. P. (2016), “Layout and Component Size Optimization of Sewer Network Using Spanning Tree and Modified PSO Algorithm”, Water Resource Manage DOI10.1007 / s11269-016-1378-7.

Chang, Y. T. (2008), “An effective Obstacle-Avoiding Rectilinear Steiner Minimal Tree construction algorithm in SOC designs”, Thesis, Department of information Computer Engineering, Chung Yuan Christian University.

Wu, P. C. (2007), “A fast and stable algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree construction”, Thesis, Department of computer science, National Tsing Hua University.

Garey, M. R. and Johnson, D. S., (1977), “The rectilinear Steiner tree problem is NP-complete,” SIAM J. Appl. Math., vol. 32, no. 4, pp. 826-834, 1977.

Lin, C. H., (2008), “Efficient algorithms for Obstacle-Avoiding Rectilinear Steiner Minimal Tree construction”, Thesis, The department of Computer Science and Information Engineering, National ChangHua University.

Lee, C. Y., (1961),” An algorithm for connections and it application, IRE Trans. On Electronic Computer”, pp. 346-365, 1961.

Dorigo, M., Maniezzo, V., and Colomi, A., (1996), The Ant system: Optimization by a colony of cooperating agents, IEEE Trans. On Systems, Man, and Cybernetics-part B, vol. 26, no. 1, pp.1-13, 1996.

Feng, Z., Hu, Y., Jing, T., Hong, X., Hu, X., and Yan, G., (2006), An O(nlogn) algorithm for Obstacle-Avoiding routing tree construction in the λ-geometry plan, in Proc. ISPD, 2006, pp.48-53.

Hu, Y., Feng, Z., Jing, T., Hong, X.L., Yang, Y., Yu, G., Hu, X.D., Yan, G.Y., (2004), FORst: A 3-step Heuristic for Obstacle-Avoiding Rectilinear Steiner Minimal Tree construction, Journal of Information & Computational Science vol. 1, no. 3 pp. 107-116, 2004.

Shen, Z. C., Chu, C. C. N., and Li, Y. M., (2005), Efficient Rectilinear Steiner Tree construction with rectilinear blockages, in Proc. ICCD, pp 38-44, 2005.

Lin, C. W., Chen, S. Y., Li, C. F., Chang, Y. W., and Yang, C. L., (2008), Obstacle-Avoiding Rectilinear Steiner Minimal Tree construction based on Spanning Graphs IEEE, Trans. On Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 4, pp. 643-653, Apr. 2008.

“Public Sewer Pipeline Design Manual”, (2014), Construction and Planning Agency, Ministry of the Interior, Taiwan.

“Taichung overall sewerage pipe network system build plan”, (2011), Water Resources Bureau, Taichung City Government, Taiwan.

Tehranipoor, Mohammad, (2008), ” Steiner tree problem, CAD algorithms”, ECE Department, University of Connecticut, http://www.engr.uconn.edu/~tehrani/teaching/cad/07_steiner.pdf

“Guidelines for Sewage Works Design”, (2008), Saskatchewan Environment and Resource Management

Akers, S. B., (1967)” A Modification of Lee’s path connection Algorithm”, IEEE Trans. On Electronic Computer, vol. EC-16, pp. 97- 98.

Rubin, F., (1974), “ The Lee connection Algorithm”, IEEE Trans. On Computer, vol. 23, pp. 907-914.

Soukup, J., (1978), “Fast Maze Router”, in Proc. Of 15th Design Automation Conference, pp. 100-102.

Handlock, (1977), “ A Shortest Path Algorithm for Grid Graphs”, Networks, vol. 7, no. 4, pp.323-334.

Mani, N. and Quach, N. H., (2000), “Heuristics in the routing Algorithm for circuit layout design”, in IEE Proc.- Comput. Digit Tech., vol.147, no. 2, pp.59-64, Mar. 2000.

Hightower, D. W.,(1969), “ A solution to the line routing problem on the continuous plan” in Proc. Of the Design Automation Workshop, pp. 1-24.

Mikami, K. and Tabuchi, K, (1968), “ a computer program for optimal routing of printed circuit connectors”, in Proc. Of IFIPS, pp. 1475-1478, H47.

Yang, Y., Zhu, Q., Jing, T., Hong, X., and Wang, Y. , (2003), “Rectilinear Steiner minimal tree among obstacles”, in Proc. ASIC, pp. 348-351.

Fujimoto, M., Takafuji, D. and Watanabe,(2005), T.,”Approximation algorithms for the rectilinear Steiner tree problem with obstacles”, IEEE International Sympossium on circuits and Systems, Vol. 2, pp. 1362-1365. May 2005.

Ganley, J. L., Cohoon, J.P.,(1994), “Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles”, IEEE International Symposium on Circuits and Systems, vol. 1, pp.113-116, 30 May- 2 June 1994.

Hu, Y., Jing, T., Hong, X., Feng, Z., Hu, X. and Yan, G., (2005), “An-OARSMan: Obstacle-Avoiding Routing Tree Construction with Good Length Performance”, in Proc. Of ASP-DAC ’05., pp.18-21.

Hu, Y., Jing, T., Hong, X., Feng, Z., Hu, X. and Yan, G. ,(2004), “An Efficient Rectilinear Steiner Minimum Tree Algorithm Based on Ant Colony Optimization:, ICCCAS　2004, Communications, circuits and Systems, Vol. 2, pp.1276-1280, jun.,2004.

Shen, Z. C., Chu, C. C. N., and Li, Y. M., (2005), “ Efficient rectilinear Steiner tree construction with Rectilinear blockages”, in Proc. ICCD, pp. 38-44.

Lin C. W., Chen S. Y., Li C. F., Chang Y. W., and Yang, C. L.,(2008), “Obstacle-Avoiding rectilinear Steiner Tree construction based on spanning Graphs”, IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no.4, pp. 643-653, Apr. 2008.

Wu, P. C., Gao, J. R., and Wang, T. C., (2007), “ A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction”, ASP-DAC’07., pp.262-267.

Mays, L.W. and Wenzel, H. G., (1976), Optimal design of multilevel branching sewer systems, Water Resources Research, AGU, Vol. 12, No. 5, pp. 913-917, October.

Mays, L.W., Wenzel, H. G. and Liebman, J. C.,(1976), Model for layout and design of sewer systems, Journal of the Water Resources Planning and Management Division, ASCE, Vol. 102, No. WR2, pp. 385-405, November.

Karovic, O. and Mays, L.W.,(2014), Sewer system design using simulated annealing in Excel, Water Resources Management, 28:4551-4565, DOI10.1007/s11269-014-0750-8.

Steele, J.C., Mahoney, K., Karovic, O., and Mays, L.W., (2016), Heuristic Optimization Model for the Optimal Layout and Pipe Design of Sewer Systems, Water Resources Management, 30(5), 1605-1620, DOI 10.1007/s11269-015-1191-8.

Herring, M.l, ”The Euclidean Steiner Tree Problem”, Denison University, April 28, 2004.
Wikipedia, “Steiner tree problem,” https://en.wikipedia.org/wiki/Steiner_tree_problem

翁新賀,(2010),”污水下水道用戶接管運用改良史坦納樹之最佳化模型, 碩士論文,國立中興大學土木工程學系。

翁煥廷，(2006)，「污水下水道管網系統規劃設計最佳化模式之研究」，博士論文，國立中央大學環境工程研究所。

張永泰, (2007),”應用於系統晶片設計之有效避免障礙物的直角化最小史坦納樹建構演算法, 碩士論文,中原大學資訊工程學系。

林志鴻,(2008),”有效率演算法用於避免障礙之最小史坦納樹建構, 碩士論文, 國立彰化師範大學資訊工程學系。

內政部營建署，「下水道工程設施標準」，民國98 年11 月。

內政部營建署，「污水下水道設計指南」，民國93 年2 月。

內政部營建署，「污水下水道管線設計手冊」，民國94 年5 月。

台中市政府,”台中市污水下水道管網系統整體規劃建置計畫”,台中市污水下水道系統規劃重新評估報告書, 社團法人台灣下水道協會，民國100年3月。