臺灣博碩士論文加值系統

臺灣常年因颱風與豪雨事件所帶來的降雨，釀成嚴重的淹水災害，因此在淹水發生前的預警措施成為重要的研究議題。在之前的研究裡，我們已經建置一個洪氾預警系統，可以快速辨認出有淹水可能的地標。而本文則進一步探討到地標救災之路徑規劃的問題，也就是藉由路徑規劃技術與淹水區域的資訊，快速規劃出由起點至目的地且迴避淹水區域的路線。我們提出了兩個方法，首先，Baseline方法利用R-tree讓淹水區域與道路的最小邊界矩形作空間連接，進而找出淹水的道路，於剔除所有淹水的道路後利用Dijkstra找出最短路徑。接著，我們提出Cloud方法，先將起點與終點送至Google Maps取得其規劃的最短路徑，再找出其中經過淹水區域的道路路口，另尋找其替代的路口節點，接著，利用GSP(Generalized Shortest Path)的演算法計算起點經過替代節點再到終點的最短路徑，然後將所得的路口點送交Google Mapse規劃與呈現最後的路徑。
我們實作Baseline和Cloud兩個方法，並進行一系列的實驗，比較兩個方法的效率、路徑長度及成功規劃出可行走之路徑的比率。實驗結果顯示，Baseline的成功率比Cloud高15%、輸出路徑長度較Cloud短12%，但在效率方面隨著路網資料量提升至萬筆後，Baseline在計算空間連接及路徑規劃的耗時會大幅增加，反之Cloud方法則有穩定的效率表現。

The disaster brought by heavy rain has become more and more serious in Taiwan, and it has been an important research issue to provide warning messages before flood. In the past research, we have built a flood forecasting system. It can identify the landmark which might be inundated. In this thesis, we further investigate the problem of routing planning for landmark rescuing. That is, we wish to quickly determine a route which starts from a given departure point, such as a landmark, avoids flooded areas, and gets to the destination.
We propose two methods. The first one is called the “Baseline” method. It uses the R-tree index to perform spatial join between flooded areas and the minimum bounding rectangles of roads to identify the flooded roads. The Dijkstra algorithm then operates on those remaining unflooded roads to find the shortest path avoiding flooded areas.The second one is called the “Cloud” method. We first submit the departure point and the destination point to the Google Maps routing planning service to get an initial shortest path. We then identify those flooded roads within the path, and find nearby alternative intersections. Then, the departure point, alternative intersections, and the destination point are operated by the GSP (Generalized Shortest Path) algorithm to find an improved shortest path, and finally, the end points of each road within this path will be submitted to Google Maps again to get the final route.
We have implemented these two methods and performed a series of experiments to compare their efficiency, route lengths, and the ratio of successfully getting a route without passing through flooded areas. The results show that the Baseline method has higher success rates, shorter route paths. However, when the roadnetwork is larger, its efficiency will decrease a lot. In contrast, the Cloud method performs quite fast even on a large dataset.

目錄
第 1 章 序論技術背景 1
1.1　研究動機與目的 1
1.2　研究方法與貢獻 2
1.3　相關研究 2
1.4　論文架構 3
第 2 章 背景定義與相關做法 4
2.1　背景定義 4
2.2　Dijkstra演算法介紹 6
2.3　GSP-DF演算法 9
2.4　問題假設 13
第 3 章 Baseline方法 14
3.1　資料結構 14
3.2　 R-tree建樹方法 15
3.3　Baseline演算法 18
第 4 章 Cloud方法 23
4.1　系統架構 23
4.2　雲端路徑查詢模組 24
4.3　替代節點篩選模組 25
4.4　Cloud主程式 26
第 5 章 實驗 30
5.1　系統實作方法與輸出範例 30
5.2　資料集 32
5.3　淹水區域數量之實驗 34
5.4　路網圖數量之實驗 37
5.5　規劃路徑長度之實驗 40
5.6　規劃路徑成功率之實驗 43
5.7　真實資料集之實驗 44
第 6 章 結論與未來方向 45
參考文獻 46
附錄A替代節點篩選程式 47

[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.
[EW59] Edsger Wybe Dijkstra,“A note on two problems in connexion with graphs, ”Numerische Mathematik, 1: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.
[張09] 張傑, “以改良的A*演算法規劃較佳導引路徑之研究”, 大同大學資訊工程研究所碩士論文, 2009.
[彭11] 彭祥瑋, “行走機器人避障路徑規劃演算法之配置與實現”, 國立中興大學生物產業機電工程研究所碩士論文, 2011.
[吳12] 吳佩珊, “基於服務導向架構之洪氾預警系統”, 國立臺灣海洋大學資訊工程研究所碩士論文, 2012.
[吳13] 吳錫欽, “緊急車輛之監控與迴避引導系統及壅塞路徑重規劃策略”, 國立臺北科技大學電機資訊學院碩士論文, 2013.
[劉12] 劉欽鴻, “利用改良的雙向A演算法實現最佳路徑規劃”, 國立成功大學工程科學研究所碩士論文, 2012.
[劉13] 劉昱德, “基於地標之淹水警示研究”, 國立臺灣海洋大學資訊工程研究所碩士論文, 2013.