Title

改良式最小生成樹輔助衛生下水道用戶接管規劃

Translated Titles

Using the Improved Minimum Spanning Tree to assist the planning of Sewage Piping Subscriber Wiring Layout

DOI

10.6845/NCHU.2010.01197

Authors

郭建宏

Key Words

史坦納樹 ; 最小擴張樹 ; 污水佈線 ; 最佳化 ; Steiner Tree ; MST ; NP-Hard ; Optimal Solutions of Sanitary Sewer Wiring Layout

PublicationName

中興大學土木工程學系所學位論文

Volume or Term/Year and Month of Publication

2010年

Academic Degree Category

碩士

Advisor

謝孟勳

Content Language

繁體中文

Chinese Abstract

污水下水道工程之路徑規劃攸關整體建設成本。然而如何選定建置路線是非常重要卻又困難的課題。本研究以污水管線佈設路徑之成本為分析目標,採用圖形理論為基礎,擴充史坦納樹(Steiner Tree)之應用原理,首創改良式的最小擴張樹(Improved Minimum Spanning Tree: IMST)演算法,求解用戶端污水管線佈設時所遭遇到的虛擬轉折點及主幹管匯流井的選擇性問題。這是一種NP-Hard( Non-deterministic Polynomial-time Hard )的問題,本演算法透過貪婪演算及動態規劃的觀念可迅速求解多個用戶端陰井經由多個虛擬轉折點連接到多個主幹管匯流井時總路徑成本最佳化的高度複雜性問題。 本研究另已完成開發管線路徑規劃系統(Pipe Path Planning System)簡稱3PS。透過3PS系統,可於極短的時間內,運用改良式的最小擴張樹(IMST)演算法,自動挑選虛擬轉折點,達到規畫路徑成本最佳化之目的。最後3PS並可快速展繪規畫成果圖,提供有關於管線佈設規畫設計之參考。

English Abstract

The sanitary sewer layout influences the whole construction cost。The questions that how to choose and plan the network are important and very difficult。The research is based on graph theory that expands the application theorem of Steiner Tree。We develop a new algorithm – Improved Minimum Spanning Tree(IMST)and try to make the selections exist the client network that between virtual points(intermediate connection hole)and target points(final outlet)。This is a NP-Hard Problem ( Non-deterministic Polynomial-time Hard ),Including Greedy algorithm and Dynamic Programming Method, IMST can solve the very complex and hard problem faster and easily such as client manholes - intermediate connection holes - final outlets。 Besides,we have accomplished the Pipe Path Planning System - 3PS。Using 3PS and IMST algorithm,we could optimize the cost of sewer layout and draw the achievement graph of optimal planning in a short time。We expect that the 3PS could provide references for pipe planning of sanitary sewer layout engineering。

Topic Category 工學院 > 土木工程學系所
工程學 > 土木與建築工程
Reference
  1. 02.李夢冀,2009,結合空間語法應用於設施管理配置最佳化,中興大學土木工程學系碩士論文。
    連結:
  2. 03.張宇徵,2008,土方工程管理結合GPS與GIS系統之應用與開發,中興大學土木工程學系碩士論文。
    連結:
  3. 04.卓延穎,2007,禁忌搜尋法及模擬退火法於污水管網最佳化設計之應用,中興大學環境工程學系碩士論文。
    連結:
  4. 05.翁煥廷,2005,污水下水道管網系統規劃設計最佳化模式之研究,中央大學環境工程研究所博士論文。
    連結:
  5. 07.林文英,2007,非都市土地使用類別適宜性分析方法之研究,中興大學水土保持學系所博士論文。
    連結:
  6. 08.謝逢鳴,2005,有前處理下最短路徑演算法之研究,淡江大學資訊管理學系碩士論文。
    連結:
  7. 09.黃一誠,2007,分段式NURBS曲線與修正型Dijkstra演算法實現路徑規劃與應用,臺灣大學電機工程學研究所碩士論文。
    連結:
  8. 33.Web Site,http://citeseerx.ist.psu.edu//search?q=Steiner+Tree+Problems
    連結:
  9. 37.Microsoft Corporation,2000,Programming Microsoft SQL Server Database。
    連結:
  10. 39.Sahim Tekeli' and Huseyin Belkaya,1987,COMPUTERIZED LAYOUT GENERATION FOR SANITARY SEWERS,Journal of Water Resources Planning and Management。
    連結:
  11. 40.Ming-I Hsieh,2003,A Faster Approximation Algorithm for Directed Steiner Tree Problem,Master In Computer Science and Information Engineering。
    連結:
  12. 42.Oleg V. Komogortsev,2009,Qualitative and Quantitative Scoring and Evaluation of the Eye Movement Classification Algorithms.
    連結:
  13. 一、中文文獻
  14. 01.非點源污染與市區雨水管理,2000,國立編議館。
  15. 06.曾世賢,2001,921集集地震污水管線災損之GIS震害分析,台北科技大學土木與防災技術研究所碩士論文。
  16. 10.黃家政,2006,在數位化向量地圖中有關快速導覽與最佳路徑之策略性搜尋方法,義守大學資訊工程學系碩士論文。
  17. 11.楊冠笙,2007,資料探勘應用於導航系統的多重路徑規劃,交通大學電機與控制工程系所碩士論文。
  18. 12.王廷基,2005,高效能低功率繞線樹合成研究,清華大學研究計畫。
  19. 13.王廷基,2007,奈米級晶片良率與可靠度提昇方法研究,清華大學研究計畫。
  20. 14.陳寬達,2002,C++Builder深度探險,碁峯。
  21. 15.胡昭民,2008,資料結構使用C語言實作(第二版),博碩文化。
  22. 16.蔡明志,2007,資料結構使用C++(第二版),碁峯。
  23. 17.廖榮貴、王龍發、許正憲、蔡能聰,2007,資料結構與演算法-使用VB.NET、VB2005,文魁資訊。
  24. 18.中村拓男,2002,Delphi於繪圖與圖形處理上的應用,博碩文化。
  25. 19.Jonatban Knudsen,2000,Java 2D Graphics,O’Reilly & Associates。
  26. 20.有馬元嗣,2002,電玩程式設計的邏輯與資料結構-使用C++Builder與Delphi實作,博碩文化。
  27. 21.黃文吉,2003,C++Builder與影像處理。儒林圖書。
  28. 22.康廷數位工坊,2006,.Net網路與I/O技術手冊,松崗。
  29. 23.章立民研究室,Visual Basic 2005檔案與資料存取秘訣,碁峯。
  30. 24.章立民研究室,Visual Basic 2005程式開發與介面設計秘訣,碁峯。
  31. 25.林宗斌,2008,Visual Basic 2008中文版程式設計,儒林圖書。
  32. 26.張真誠、蔡文輝、林敏惠,2003,資料庫管理系統,旗標。
  33. 27.嚴仕偉,2002,程式設計人員專業養成-使用C++Builder,文魁資訊。
  34. 28.日向俊二,2006,Visual Basic 2005功能索引參考手冊,旗標。
  35. 29.陳錦輝,2008,資料結構使用C語言,博碩文化。
  36. 30.董大偉,2006,Visual Basic 2005程式設計與案例剖析,旗標。
  37. 31.陳周造、陳燦煌,2001,C++Builder 5 徹底研究,博碩文化。
  38. 32.王加松、俞熹、于兵,2009,Visual Basic聖經、佳魁。
  39. 二、英文文獻
  40. 34.Web Site,http://steinlib.zib.de/steinlib.php
  41. 35.Ivor Horton’s (1999),Beginning Visual C++6,WROX。
  42. 36.Fred Barwell、Richard Blair、Jonathan Crossland、Richard Case、Bill Forgey、Whitney Hankison、Billy S.Hollis,Rockford Lhotka、Tim McCarthy、John C.Roth,Professional VB.NET,2nd Edition。
  43. 38.Microsoft Corporation,1998,Mastering Visual Basic Development。
  44. 41.Huang-Ming Gao,2005,The Selected-leaf-terminal Steiner Tree Problem and Related Problems,Master In Computer Science and Information Engineering,National Cheng Kung University。