電子地圖相關的應用在近年來相當受到矚目，其中相當有趣且值得研究的議題是路徑規劃與導引。這個議題牽涉到了在網路模型中尋找最短路徑或最低成本路徑的問題。將各種路徑、道路以及運輸系統已適當的網路模型表達，就可以套用與圖論、網路模型等領域相關的最短路徑或最低成本路徑演算法。本研究提出一套基於區域資訊與網路模型的路徑規劃與引導機制，此機制的優點為運算更具有效率，且可以依照環境變化動態提供引導服務。本研究也提出了此機制的可能應用情境。本論文第一章會對研究內容作初步的介紹，接著介紹相關研究、本研究設計的網路模型、演算法、實驗結果以及結論，最後會附上本研究的參考資料。

The applications of electronic maps have become more and more popular. An interesting field is itinerary or route planning and navigation. This is related to the shortest path or lowest-cost path problem on graph. The roads and public transit systems can represent as a network model. Applying routing algorithms on the network model would find out a shortest path or lowest-cost path on map. We proposed a scheme based on local information of each node to find lowest-cost path on the network model. The advantages of this scheme are computing efficiency and guiding dynamically. We also proposed the possible applications for this scheme. This paper is organized with introduction, related works, network model, algorithms we proposed, simulation, conclusions and references.

第1章	介紹	1
1.1	研究動機	1
1.2	可能的應用情境	1
1.3	研究目的與預期成果	2
第2章	相關研究	3
2.1	尋找最短或最低成本路徑	3
2.2	Dijkstra演算法	3
2.3	A*演算法	4
2.4	Bellman-Ford演算法	5
2.5	道路與運輸系統網路特性	6
2.6	室內區域性定位的可行性	6
第3章	網路模型	8
3.1	節點	8
3.2	連線	8
3.3	地形屏障	9
3.4	支援立體空間之座標資訊	9
3.5	區域資訊與整合	10
第4章	演算法討論	12
4.1	其本的路徑尋找規則	12
4.2	加入不同運輸系統後的考量	13
4.3	避開地形屏障	18
4.4	演算法歸納	18
第5章	實驗與討論	21
5.1	使用A*演算法之優勢	21
5.2	避開地形屏障	24
5.3	移動成本計算分析	27
第6章	結論	30
參考資料	31
附錄 – 英文論文	33

圖目錄

圖 1 : 建築物內應用情境示意圖	2
圖 2 : Dijkstra演算法示意圖	4
圖 3 : A*演算法示意圖	5
圖 4 : 區域資訊應用示意圖	11
圖 6 : 臺北捷運淡水線北端路線圖	14
圖 5 : 延伸連線示意圖	14
圖 7 : 關係節點概念示意圖	15
圖 8 : 實驗用網路模型	23
圖 9 : 隨選50組路徑直線距離與最短路徑比較	23
圖 10 : Dijkstra演算法找出的路徑長度與拜訪節點數目	23
圖 11 : A*演算法所找出的路徑長度與拜訪節點數	23
圖 12 : 兩種演算法找出的路徑長與最短路徑比較	23
圖 13 : 兩種演算法拜訪節點數比較	23
圖 14 : 單純化的格子狀網路模型	24
圖 15 : 隨選50組路徑的最短路徑長與直線距離	24
圖 16 : 兩種演算法所找出的路徑長與最短路徑比較	24
圖 17 : 兩種演算法尋找路徑時拜訪節點數比較	24
圖 18 : 模擬地形屏障之網路模型	26
圖 19 : 選擇50組路徑之最短路徑長與直線距離	26
圖 20 : 未考量地形屏障的A*演算法，拜訪節點數與路徑長	26
圖 21 : A*演算法加入考量地形屏障，拜訪節點數與路徑長	26
圖 22 : 加入考量地形屏障前後，拜訪節點數比較	26
圖 23 : 模擬真實環境的網路模型	27

表目錄

表 1 : 區域資訊來源實作方式歸納	19
表 2 : 演算法整理	20
表 3 : 使用各路線需花費的成本	28
表 4 : 各節點前往目的節點之估計成本	28
表 5 : 移動成本計算結果	29

[1]	Silke Feldmann, Kyandoghere Kyamakya, Ana Zapater and Zighuo Lue, “An Indoor Bluetooth-based positioning system: concept, Implementation and experimental evaluation”, ICWN, 2003
[2]	Gunter Fischer, Burkhart Dietrich and Frank Winkler, “Bluetooth Indoor Localization System”, WPNC, 2004
[3]	Mark D. Hickman and Nigel H. M. Wilson. “Passenger Travel Time and Choice Implications of Real-time transit Information”, Transportation Research Part C: Emerging Technologies, vol. 3, issue 4, p.p. 211-226, 1995
[4]	Sverre Holm, “Hybrid Ultrasound-RFID Indoor Positioning: Combining the Best of Both Worlds”, IEEE International Conference on RFID, 2009
[5]	Takeshi Ikeda, Yutaka Inoue, Akio Sashima, Kiyoshi Yamamoto, Tomohisa Yamashita and Koichi Kurumatani, “ComPass System: An Low Power Wireless Sensor Network System and its Application to Indoor Positioning”, ACM Proceedings of the 5th International Conference on Soft Computing as Transdisciplinary Science and Technology, 2008
[6]	James J. Kuffner, Jr. and Steven M. LaValle, “RRT-Connect: An Efficient Approach to Single-Query Path Planning”, In Proc. 2000 IEEE Int’l Conf. on Robotics and Automation (ICRA 2000), 2000
[7]	Yongtaek Lim and Hyunmyung Kim, “A Shortest Path Algorithm for Real Road Network Based on Path Overlap”, Journal of the Eastern Asia Society for Transportation Studies, vol. 6, pp. 1426 - 1438, 2005
[8]	P. Prasithsangaree, P. Krishnamurthy and P.K. Chrysanthis, “On Indoor Position Location with Wireless Lans”, IEEE PIMRC, 2002
[9]	Dominik Schultes, “Route Planning in Road Networks”, Universitat Fridericiana zu Karlsruhe, 2008
[10]	Tesoriero R., Gallud, J. A., Lozano, M., and Penichet, V. M. R., “Using Active and Passive RFID Technology to Support Indoor Location-Aware Systems”, IEEE Transactions on Consumer Electronics, vol. 54, No. 2, May, 2008
[11]	F. Benjamin Zhan, “Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures”, Journal of Geographic Information and Decision Analysis, vol.1, no.1, pp. 69-82, 1997
[12]	Konstatinos G. Zografos and Konstantinos N. Androutsopoulos, “Algorithms for Itinerary Planning in Multimodal Transportation Networks”, IEEE Transactions on Intelligent Transportation Systems, vol. 9, No. 1, March, 2008