臺灣博碩士論文加值系統

隨著電腦軟硬體的日益成熟，人們已廣泛使用電子地圖在各項地理資訊應用系統中。各大相關電子廠商莫不競相投入各式應用服務的開發，其中重要的兩個核心技術為空間資料索引與最佳路徑搜尋技術。由於手持嵌入式設備受體積、電源、價格等因素之影響，其記憶體容量通常較小，因而大多無法一次將所有地圖資料全部載入。當即時瀏覽地圖時，主記憶體與輔助記憶體之傳輸速率自然成為關鍵的瓶頸，記憶體的存取次數也將直接影響地圖資料顯示的速度，我們首先將探討適合的多維度空間索引方法以解決此一問題。其次，網路分析功能對於提升地理資訊一直扮演重要角色，而其中尋找最佳路徑已成為最重要的功能之一。最佳路徑不僅僅是一般地理意義上最短的幾何距離，亦可衍生為其他的度量值，如最短的旅行時間、最省的運輸費用等。由於最佳路徑問題經常使用在各種急難救助等系統，計算時間往往必須在短短數秒內完成。當道路資料量龐大時，要快速找到一條最佳路徑實屬不易。固然傳統Dijkstra演算法是目前多數系統解決最短路徑問題採用的理論基礎，只是不同系統為了時效上的考量採用了不同的實現方法。此研究即以傳統Dijkstra演算法為基礎，在向量地圖中運用各種策略型方法並加以組合，以快速實現最短路徑之搜尋。經由實驗結果顯示，策略型方法的執行效率明顯優於傳統Dijkstra演算法。

As the rapid development of computer hardware and software, people have widely used electronic maps in a variety of geographical information application systems. One of most important technologies is the indexing and searching technology on spatial data. For a general embedded device, memory size is often insufficient to load all maps into memory at once because of the volume, power and cost. When browsing a large map, the transmission speed between main memory and auxiliary memory is a critical bottleneck. The access frequency of memory will influence the display speed of map data. This research firstly uses the multi-dimensional indexing technology to solve the key problem. Next, one of the most important issues is to find the best path in network analysis. The best path is not only the meaning that the required distance is shortest, but it is also possible to general geographical meaning, such as travel time, transportation charges, etc. Since the shortest path problem is usually applied to urgent tasks, these systems by request should calculate the shortest path as soon as possible. Most systems solving the shortest path are almost based on Dijkstra algorithm, and many systems use different approaches according to own properties. Based on traditional Dijkstra algorithm, this research adopts heuristic approaches to meet the requirement. We will show some experimental results to demonstrate the performance.

第一章 簡介
1.1 地理資訊系統與智慧型運輸系統
1.2 電子地圖之製作與應用
1.3 電子地圖導覽與網路分析功能之關鍵性問題
第二章 相關文獻
2.1 多維度資料索引結構在電子地圖的探討
2.2 適用於智慧型運輸系統最短路徑演算法相關文獻探討
2.3 典型最短路徑演算法目前已改善的方式
第三章 電子地圖導覽之設計
3.1 電子地圖原始數值檔
3.2 電子地圖索引資料結構之設計與編碼
3.3 給定一已知點與給定一已知視窗範圍之查詢方法
3.4 以空間填充曲線取得索引區塊的位置
第四章 策略型路徑搜尋技術
4.1 目標導向搜尋方法
4.2 雙向搜尋最短路徑方法
4.3 投影導向搜尋最短路徑方法
4.4 限制區域搜尋最短路徑方法
4.5 組合路徑搜尋技術
第五章 整合道路權重路徑搜尋技術
5.1 GIS道路屬性資料
5.2 選擇道路權重方法
5.3 行駛時間估算方法
第六章 實驗結果
6.1 電子地圖空間資料搜尋結果分析
6.2 策略型最佳路徑搜尋演算法實驗分析
第七章 結論

[1]A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” International Conference on Management of Data, pp. 47-57, 1984.
[2]A White and R.Jain, “Similiarity Indexing with the SS-tree,” Proceeding of the ACM SIGMOD International Conference on Data Engineering, pp.516-523, 1996.
[3]A.V. Goldberg and T. Radzik, “A Heuristic Improvement of the Bellman-Ford algorithm,” Applied Mathematics Letters, Vol. 6, No. 3, pp. 3-6, 1993.
[4]Andrew Goldberg, Haim Kaplan and Renato Werneck, “Reach for A*: Efficient Point-to-Point Shortest Path Algorithms,” In Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 269-284, 2006
[5]Dorothea Wagner and Thomas Willhalm, “Geometric speed-up techniques for finding shortest paths in large sparse graphs,” Proc. 11th European Symposium on Algorithms (ESA), vol. 2832 of LNCS, pp. 776-787, 2003.
[6]E. W. Dijkstra, ”A Note on Two Problems in Connection with Graphs,” Numeriche Mathematik, pp. 269-271, 1959.
[7]Edward P.F. Chan and Ning Zhang, “Finding Shortest Paths in Large Network Systems,” Proc. 9th ACM International Symposium on Advances in Geographic Information Systems, pp. 160-166, 2001.
[8]Floyd R.W., “Algorithm 97: Shortest path,” Communications of the ACM, pp. 345-350, 1962.
[9]F. Benjamin Zhan, “Three Fastest Shortest Path Algorithms on Real Road Networks,” Journal of Geographic Information and Decision Analysis, vol. 1, no. 1, pp. 69-82, 1997.
[10]F. Benjamin Zhan, Charles E. Noon, “A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Paths,” Journal of Geographic Information and Decision Analysis, vol. 4, no. 2, pp. 1-13, 2000.
[11]Fu Mengyin, Li Jie, Zhou Peide, “Design and Implementation of Bidirectional Dijkstra Algorithm,” Computer Journal of Beijing Institute of Technology, vol. 12, no. 4, pp. 366-370, 2003.
[12]J. T. Robinson, “The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes,” ACM International Conference on Management of Data, pp. 10-18, 1981.
[13]J. A. Orestein, “Spatial Query Processing in an Object-Oriented Database System,” ACM International Conference on Management of Data, pp. 326-333, 1986.
[14]J. Tayeb, O. Ulusoy and O. Wolfson, “A Quadtree-based Dynamic Attribute Indexing Method,” The Computer Journal, Vol. 41, No. 3, pp. 185-200, 1998.
[15]J K Lawder, P J H King, “Using Space-filling Curves for Multi-Dimensional Indexing,” In Proceedings of BNCOD 17, Lectures Notes in Computer Science, Springer, pp. 20-35,2000.
[16]Jin Wang and Stefan Schroedl, “Lane Keeping Based on Location Technology,” In IEEE Transactions on Intelligent Transportation Systems, pp. 351-356, 2005.
[17]Keith A. Redmill, Takeshi Kitajima and Umit Ozguner, “DGPS/INS Integrated Positioning for Control of Automated Vehicles,” IEEE Intelligent Transport Systems Conference Proceedings, pp. 172-178, 2001.
[18]Martin Holzer, Frank Schulz and Dorothea Wagner, “Engineering Multi-Level Overlay Graphs for Shortest-Path Queries,” In Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 371-384, 2006.
[19]N. Beckmann, H.P. Kriegal, R. Schneider, and B. Seeger, “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” Proceeding of the ACM SIGMOD International Conference on Management of Data, pp. 322-331, 1990.
[20]Philippe Rigaux, Michel Scholl and Agnes Voisard, “Spatial Databases with Application to GIS, Morgan Kaufmann Publishers,” pp.192-208, 2002.
[21]Peng Dong, Chongjun Yang, Xiaoping Rui and Qimin Cheng, “An Efficient Buffer Generation Method in GIS,” IEEE Geoscience and Remote Sensing Symposium (IGRSS), Vol. 6, No.2, pp. 3706-3718, 2003.
[22]Peter Sanders and Dominik Schultes, “Highway hierarchies hasten exact shortest path queries,” In Proceedings 17th European Symposium on Algorithms (ESA), vol. 3669 of Springer LNCS, pp. 568-579, 2005.
[23]Seth Pettie, Vijaya Ramachandran and Srinath Sridhar, “Experimental Evaluation of a New Shortest Path Algorithm,” The 4th International Workshop on Algorithm Engineering and Experiment, Lecture Notes in Computer Science, pp. 120-140, 2002.
[24]T. Sellis, N. Roussopoulos and C. Faloutsos, “The R+-tree: A Dynamic Index for Multi-dimensional Object,” Proceedings of International Conference on Very Large Data Bases, pp 507-518, 1987.
[25]V. Gaede, and O. Gunther, “Multidimensional Access Methods,” ACM Computing Surveys, Vol. 30, No. 2, pp. 170-231, 1998.
[26]吳玉珍、何毓芬，交通路網數值地圖與車用導航系統之發展及應用，國土資訊系統通訊，2001。
[27]周天穎，地理資訊系統理論與實務，逢甲大學地理資訊系統研究中心，2003。
[28]交通部運輸研究所，台灣地區發展智慧型運輸系統(ITS)系統架構之研究，2004。
[29]交通部運輸研究所，區域級智慧型運輸系統示範計畫─核心交通分析與預測系統(第二年期)，2005。
[30]交通部運輸研究所，新世紀台灣地區交通路網數值地圖圖資1.3版，2006。
[31]張瑞隆，電子地圖在台灣的應用現況與趨勢，國土資訊系統通訊，2006。
[32]朱子豪，應用空間資訊技術於國土利用調查作業，台灣地理資訊學會年會暨學術研討會論文，2006。
[33]王聖銘、黃鴻鈞、鄧東波，跨平台多媒體空間資訊技術的發展，台灣地理資訊學會年會暨學術研討會論文，2006。
[34]MapInfo CAD, Geographic Information System, http://www.mapinfo.com/
[35]PAPAGO衛星導航軟體, http://www.papago.com.tw