臺灣博碩士論文加值系統

台灣常年因颱風與豪雨事件所帶來的降雨，釀成嚴重的淹水災害。之前已經有研究提出藉由道路與淹水區域的資訊，規劃出由起點至目的地且能避開淹水的路線，並提出兩種做法。首先，Baseline作法是先找出經過淹水區域的道路，將其從路網圖中移除，然後將其餘可行走之道路經由Dijkstra演算法找出最短路徑。其次，Cloud作法是利用雲端服務先行規劃出一條路徑，若該條路徑淹水，再針對淹水路口尋找鄰近點重新規劃。
本論文主要是根據其所提出的架構，利用索引技術，分別提升該二方法的效率。針對Baseline做法，我們探討分別利用道路資料建立索引，以及利用淹水區塊建立索引，來判斷道路是否淹水的效率。針對Cloud作法，我們利用索引技術尋找淹水路口的鄰近點，並設計兩種不同的索引，第一種是擴充Baseline方法所建立的道路索引，另一種則是利用路口點建立索引。
我們實作上述不同的索引，並進行一系列的實驗，比較執行時間以及成功規劃出可行走之路徑的比率。實驗結果顯示，利用索引的Cloud作法，效率遠勝過使用索引的Baseline做法，且在道路資料量大時，可以達到10倍以上。至於成功率則在最多修正3次的情況下，可以達到九成以上。

The disaster brought by heavy rain has become more and more serious in Taiwan. In the past, a researcher has studied the problem of planning an unflooded path from the given origin to the destination, and proposed two approaches. The first one is called the Baseline approach. It mainly picks out the roads passing through flooded areas, and invokes the Dijkstra algorithm to determine the shortest path based on the remaining unflooded roads. The second proposed approach, called Cloud, utilizes the Google Maps routing planning service to get an initial shortest path. If the path passes through flooded areas, the system will identify nearby alternative roads and re-plan again.
The main goal of this thesis is to improve the efficiency of the two existing approaches by using indexing techniques. For the Baseline approach, we consider the task of determining whether a road is flooded or not, and explore the possibilities of using roads or flooded areas to build indices, respectively. As to the Cloud approach, we consider the task of identifying the nearby alternative roads for a flooded road, and discuss two types of indices. The first one extends the road index constructed for the Baseline approach. The second one uses intersections to build the index.
We have implemented these different indices, and performed a series of experiments to compare their performance. Experimental results show that the Cloud approach with indices is much more efficient than the Baseline approach with indices. The difference may be up to an order of magnitude when the road network is large. Besides, although the Cloud approach cannot always output a path without passing through flooded areas at the first time, it may achieve ninety percent of success rates if it is allowed to adjust its route up to three times.

第 1 章 序論與技術背景 1
1.1　研究動機與目的 1
1.2　研究方法與貢獻 2
1.3　相關研究 3
1.4　論文架構 5
第 2 章 背景定義與相關做法 6
2.1　背景定義 6
2.2　問題假設 10
第 3 章 基於Dijkstra之方法 11
3.1　資料結構 11
3.2 基於道路索引的演算法 14
3.3 基於淹水區塊索引的演算法 18
第 4 章 基於雲端服務之方法 20
4.1　系統架構 20
4.2　主程式 21
4.3　Google路徑查詢模組 23
4.4　鄰近點篩選模組 27
4.5　GSP演算法 33
第 5 章 實驗 40
5.1　輸入檔案格式 41
5.2　系統實作方法與輸出範例 42
5.3　資料集 44
5.4　改變索引建立方式和order之實驗 46
5.5 threshold效率和成功率之實驗 50
5.6 路網圖大小之效率實驗 55
5.7 淹水區域數量和分布之實驗 59
5.8 規劃路徑長度之實驗 62
第 6 章 結論與未來方向 64
附錄A 建立道路索引程式 65
參考文獻 67

[AG84] Antomn Guttman, “R-trees: A dynamic index structure for spatial searching”, Proceedings of the ACM SIGMOD international conference on Management of data, 1984
[BD98] Beman Dawes, David Abrahams, http://www.boost.org/, 1998
[BKSS90] Norbert Beckmann, Hans-Peter begel Ralf Schneider, Bernhard Seege, “The R*-tree: an efficient and robust access method for points and rectangles”, Proceedings of the ACM SIGMOD international conference on Management of data, 1990
[CC15] Dong-Wan Choi, Chin-Wan Chung, “Nearest neighborhood search in spatial databases”, Proceedings of the ICDE conference, 2015
[EW59] Edsger Wybe Dijkstra, “A note on two problems in connexion with graphs ”, Numerische Mathematik, Vol. 1, pp. 269–271, 1959
[GB97] Great Britain, “Admiralty manual of navigation”, The Stationery Office,
Vol. 1, pp. 10, 1997
[HNR68] Peter E. Hart, NILS J. Nilsson, Bertram Raphael, “A formal basis for the heuristic determination of minimum cost paths”, IEEE Transactions on Systems Science and Cybernetics, Vol. 4, No 2, pp. 100–107, 1968
[RT13] Michael N. Rice, Vassilis J. Tsotras, “Engineering generalized shortest path queries”, Proceedings of the ICDE conference, 2013
[ZLTZ13] Ruicheng Zhong, Guoliang Li, Kian-Lee Tan, Lizhu Zhou, “G-Tree: An efficient index for kNN search on road networks”, Proceedings of the CIKM conference, 2013
[李15] 李承翰, “迴避淹水區域之快速路徑規劃研究”, 國立臺灣海洋大學資訊工程研究所碩士論文, 2015
[吳12] 吳佩珊, “基於服務導向架構之洪氾預警系統”, 國立臺灣海洋大學資訊工程研究所碩士論文, 2012
[吳13] 吳錫欽, “緊急車輛之監控與迴避引導系統及壅塞路徑重規劃策略”, 國立臺北科技大學電機資訊學院碩士論文, 2013
[彭11] 彭祥瑋, “行走機器人避障路徑規劃演算法之配置與實現”, 國立中興大學生物產業機電工程研究所碩士論文, 2011
[張09] 張傑, “以改良的A*演算法規劃較佳導引路徑之研究”, 大同大學資訊工程研究所碩士論文, 2009
[國13] 『國家災害防救科技中心』, “一日暴雨600mm淹水潛勢圖”, http://satis.ncdr.nat.gov.tw/, 2013
[劉12] 劉欽鴻, “利用改良的雙向A演算法實現最佳路徑規劃”, 國立成功大學工程科學研究所碩士論文, 2012
[劉13] 劉昱德, “基於地標之淹水警示研究”, 國立臺灣海洋大學資訊工程研究所碩士論文, 2013