在現今智慧型運輸系統(Intelligent Transportation Systems, ITS)的蓬勃發展及全球定位系統(Global Positioning System，GPS)導航裝置的普遍應用，使得路徑規劃成為我們所依賴的功能，但在目前市區道路的交通流量中，各道路在同時段之行車速度差異極大，且並未考慮各路段在同時段之行車速度，造成到達時間與實際不符。
因此，本文提出簡易交通道路分層模型 (Simple Hierarchy Route Networks Model, SHRNM)，依道路的等級、加上不同的行車速率及交通狀態，利用Dijkstra演算法來進行最快路徑搜尋，測試其可行性，並與Google Map之最快道路功能比較，最後以台中市交通道路進行模擬，來驗證所提出之道路模型之效益。由測試結果可知，用9個路徑作比較，得其平均平方誤差為9.5(min2)。

In the intelligent transportation systems (ITS) and the wide-spread Global Positioning System (GPS), the optimal shortest path algorithms is one of the important tools to be accepted in the commercial market. In the nowadays, the road networks in metropolitan are very complexity. To speed up the vehicles and shorten the arrival time for the drivers, the different speed limits of roads are developed for efficiently transportation systems. Therefore, in this thesis, a simplified hierarchy road network model (SHRNM) is proposed for the optimal shortest road route discovery for transportation systems in metropolitan area. The Dijkstra algorithms are applied for the optimal path calculation. In our model, the metric of shortest path is the driving time. Thus, the shortest path can easily be found in proposed simple road traffic model. Finally, to verify the feasibility of SHRNM, the shortest path for the Taichung transportation roads, is performed to compare with Google Map. From the results, the mean square error (MSE) between SHRNM and Google Map is 9.5 (min2) with 9 routes discovery.

目錄
中文摘要……………………………………………………………….... I
英文摘要………………………………………………………………. II
致謝…………………..…………………………………………………III
目錄…………………….…………………….……………….…...……IV
表目錄……………………………………………...…………………...VI
圖目錄…………………………………………………...……………..VII
第一章 緒論……………………………………………………………..1
1.1 研究背景…………………………………………………………….1
1.2 研究動機…………………………………………………………….3
1.3 章節概要…………………………………………………………….4
第二章 相關研究………………………………………………………..6
2.1 地理資訊系統……………………………..………………………...7
2.2 最短路徑……………………………………….……………………8
2.2.1 Dijkstra 演算法……………….…...………………………....9
第三章 簡易交通道路分層模型………………………………………18
3.1 環境配置…………………………………………………………...18
3.2 模擬分析…………………………………………………………...22
3.2.1 無交通號誌……………………………….…………........22
3.2.2 交通號誌……………....…………...……………………..24
3.2.3 具交通號誌及交通事故………………………..……...….24
3.2.4 模擬結果……………………………………………...…...26
3.3 小結…………………………………………...…………..…..........27
第四章 簡易交通道路分層模型以台中市區之交通道路為例之應用…………………………………………………...…….....…29
4.1 實際交通環境…………………………………...……...……...…..29
4.2 SHRNM與實際交通道路配置…………………………………….34
4.3 模擬分析…………………………………………………………...35
4.3.1 SHRNM與台中市區交通道路…………………………….36
4.3.2 模擬結果…………………………………………………...36
4.4 小結……………………….………………………...……......……42
第五章 結論……………………………………………..……....….....44
參考文獻與連結………………………..………………........….……..45

表目錄
表2-1 交通部2003~2013年車輛統計表.................................................6
表2-2 節點陣列圖……………………………………………………..11
表3-1 四種道路行駛時間……………………...……….……………..20
表3-2 無交通號誌-最快道路行駛時間……………………….………23
表3-3 無交通號誌-最快道路駕駛時間………….……………………24
表3-4 交通號誌-固定道路駕駛時間………….………………..…..…25
表3-5 交通號誌-最快道路駕駛時間…………….………....….……...25
表3-6 交通號誌與交通事故-固定道路行駛時間…...….........…….....26
表3-7 交通號誌與交通事故-最快道路行駛時間….……....................26
表4-1 Google Map 一週行駛時間表………………….………….....33
表4-2 四種道路行駛時間………………………………………….....35

圖目錄
圖1-1 智慧型運輸系統示意圖………………………………...……….2
圖2-1 Google Map 搜尋介面…………………………………....……...8
圖2-2 交通網路之說明例子…………………………….……..…...…10
圖2-3第一步驟後(a)節點陣列值 (b)節點圖……………...………..…12
圖2-4第二步驟後(a)節點陣列值 (b)節點圖…………………….……13
圖2-5第三步驟後(a)節點陣列值 (b)節點圖……………..…………...14
圖2-6第四步驟後(a)節點陣列值 (b)節點圖………………...………..15
圖2-7第五步驟後(a)節點陣列值 (b)節點圖…….……………..……..16
圖2-8完成尋找後(a)節點陣列值 (b)節點圖……………..….………..17
圖3-1簡易交通道路分層模型圖………………………………….…...19
圖3-2交通號誌與交通事故分佈圖…………………………….……...19
圖3-3 無交通號誌-固定道路駕駛時間…………….....................…....23
圖3-4 交通號誌-固定道路行駛路徑………………...………….….....25
圖3-5 交通號誌與交通事故-固定道路行駛路徑………..……...........26
圖3-6固定道路行駛時間與最快道路行駛時間比較……….…….......27
圖4-1 市區道路路徑結果…………………………….......……..….....30
圖4-2 外環道路路徑結果……………………...………………….......31
圖4-3 快速道路路徑結果……………………………………..…........31
圖4-4 高速公路路徑結果………...........................................…..…...32
圖4-5 台中市交通道路-SHRNM…...................................…………..34
圖4-6 SHRNM與台中市區交通道路配置圖…….….........................37
圖4-7 平日之Google Map與SHRNM行駛時間比較........................39
圖4-8 假日之Google Map與SHRNM行駛時間比較........................39
圖4-9 以Google Map為地點配置圖...................................................40
圖4-10 Google Map與SHRNM 五個地點行駛時間比較.................41
圖4-11 以SHRNM為地點配置圖.........................................................41
圖4-12 Google Map與SHRNM 四個地點行駛時間比較..................42

[1] http://www.its-taiwan.org.tw 中華智慧型運輸系統協會
[2] http://www.iot.gov 交通部運輸研究所
[3] http://www.gis.tw 逢甲大學地理資訊系統研究中心
[4] 陳育春，Google Maps API應用開發，佳魁，2010 。
[5] 江寬，龔小鵬，Google API開發詳解 : Google Map與Google Earth
雙劍合壁，文魁資訊，2008。
[6] 安守中，GPS定位原理及應用，全華科技圖書，2005。
[7] 蔡長俽，簡良益，GIS 系統建置理論與實務, 研勤科技，2004。
[8] 余家豪(2007)，行動代理人訊息寄送之容錯，碩士論文，朝陽科技大學。
[9] 劉後欣(2004)，行動代理人訊息傳輸之保證，碩士論文，朝陽科技大學。
[10] 林芳昌、張君瑋，多階層式主機與無線感測網路基礎下以最短搜尋時間法規最適交通路徑，台灣網際網路研討會(TANET)，義守大學，pp. 1-6，2008。
[11] C. Zhang, F. Zhang, J. Ren and J. Ren, “Multidimensional Traffic GPS Data Quality Analysis Using Data Cube Model,” Proceedings of International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE), pp. 307-310, December, 2011.
[12] D. Fan and P. Shi, “Improvement of Dijkstra’s Algorithm and Its
Application in Route Planning,” Proceedings of Seventh International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), pp. 1901-1904, 2010.
[13] I. Chabini and S. Lan, “Adaptations of the A* Algorithm for the Computation of Fastest Paths in Deterministic Discrete-time Dynamic Networks,” Proceedings of IEEE Transactions on Intelligent Transportation Systems, pp. 60-74, Mar. 2002.
[14] N. A. M. Nordin, N. Kadir, Z. A. Zaharudin and N. A. Nordin, “An Application of the A* Algorithm on the Ambulance Routing”, Proceedings of IEEE Colloquium on Humanities, Science and Engineering Research (CHUSER ), pp. 855-859, Dec. 2011.
[15] G. J. Shen, “An Intelligent Hybrid Forecasting Model for Short-term Traffic Flow”, Proceedings of the World Congress on Intelligent Control and Automation, pp. 486-491, July 2010.
[16] M. K. Mainali, S. Mabu and K. Hirasawa, “Evolutionary Approach for the Traffic Volume Estimation of Road Sections,” Proceedings of IEEE International Conference on Systems Man and Cybernetics (SMC), pp. 100-105, 2010.
[17] J. Mouzna, S. Uppoor, M. Boussedjra, M. Pai,” Density Aware Routing using Road Hierarchy for Vehicular Networks,”
Proceedings of IEEE SOLl09, Chicago, 2009.
[18] Q. Yang, A. Lim, and P. Agrawal “Connectivity Aware Routing inVehicular Networks,” Proceedings of IEEE International Conference on Wireless Communications and Networking (WCNC), pp. 2218-2223, 2008.
[19] M. Barbehenn, "A Note on the Complexity of Dijkstra''sAlgorithm
for Graphs with Weighted Vertices,” IEEE Computers, vol. 47,1998.
[20] B. R. Qazi, H. Alshaer, and J. M. H. Elmirghani, “Analysis and
Design of a MAC Protocol and Vehicular Traffic Simulator for Multimedia Communication on Motorways,” IEEE Transaction on Vehicular Technology, vol. 59, no. 2, 2010.
[21] C. Long and M. Shuai, “Wireless Sensor Networks: Traffic Information Providers for Intelligent Transportation System,” Proceedings of International Conference on Geoinformatics Information Technology, pp. 1-5, 2010.