隨著通信系統和資訊科技的發展，改變了原有交通系統的原貌，因此智慧型運輸系統(Intelligent Transport Systems,ITS)應運而生，其中最短路徑算ITS中最基本的一個問題，以往的最短路徑演算法都是找出兩點間之最短路徑，並不會將目前道路的實際狀況納入考量，因此本論文提出結合PSO與Dijkstra演算法優化智慧型系統，將該地區實際情況等級分類，並且使用粒子群演算法(Particle Swarm Optimization,PSO)，找出目前該地區車輛的趨向會集中於哪個熱點，熱點在本研究中為容易造成車潮或人潮擁塞的地點，像是百貨公司、量販店、夜市等等地區，本研究根據交通管理系統所找到的熱點來調整附近道路的旅行時間，並使用代克思托(Dijkstra)演算法找出兩點之間最適合的最短路徑，在模擬實驗的結果顯示，透過本論文提出的研究方法，可以隨著目前車輛的趨向，避開那些可能發生塞車的道路，產生較佳的最短路徑。

Given the importance of travel time as a factor in motorist decisions to avoid congestion, travel time prediction in Advanced Traveler Information Systems is an important issue. A simulation-assignment-based travel time prediction model for traffic corridors is constructed in proposal. Based on the concept of simulation-assignment models, two algorithms are proposed for travel time prediction: the PSO and the Dijkstra-based models. Simulation results for roads in Taiwan show that the method proposed can help avoid traffic congestion with optimal path distance.

中文摘要 I
ABSTRACT II
致謝 III
目錄 V
圖目錄 VII
表格目錄 VIII
第一章 1
緒論 1
1.1簡介 1
1.2研究動機與目的 2
1.3章節提要 3
第二章 4
相關研究 4
2.1智慧型運輸系統與最短路徑 4
2.2粒子群優演算法 6
2.3 K-平均(K-MEANS)分群演算法 9
2.4本研究提出之研究方法 11
第三章 13
研究架構 13
3.1道路網路 14
3.2熱門度與限速分級 15
3.3 粒子群演算法(PSO)演算法 18
3.4更新道路網路 19
3.5代克思托(DIJKSTRA)演算法 20
3.6終止演算 21
3.7熱點數量的影響 22
第四章 23
實驗模擬 23
4.1模擬道路網路 24
4.2熱點熱門度分級 24
4.3粒子群演算法(PSO)演算法分析 26
4.3.1建構初始化群組 27
4.3.2.粒子適應度計算 27
4.3.3.決定粒子最佳解與全域最佳解 27
4.3.4.更新粒子速度與位置 27
4.3.5.是否到達終止目標 28
4.4更新道路網路 29
4.5 代克思托(DIJKSTRA)演算法與結果 30
4.6 較大道路網路 31
4.7熱點數量影響 32
第五章 35
結論與未來工作 35
5.1 結論 35
5.2 未來工作 36
參考文獻 37

[1] M. Ben-Akiva, A. De Palma and I. Kaysi, “Dynamic network models and driver information systems,” Transportation Research 25A (5), pp. 251–266, 1991.
[2] M. Chen and I.J. Chien, “Dynamic freeway travel time prediction using probe vehicle data: Link-based versus path-based,” Transp. Res. Rec., vol. 1768, pp. 157-161, 2001.
[3] E.W. Dijkstra, “A note on two problems in connexion with graphs,” In Numerische Mathematik, pp. 269-271, 1959.
[4] N.M. Garcia, P. Lenkiewicz, M.M. Freire, and P.P. Monteiro, “On the Performance of Shortest Path Routing Algorithms for Modeling and Simulation of Static Source Routed Networks -- an Extension to the Dijkstra Algorithm,” ICSNC '07 Proceedings of the Second International Conference on Systems and Networks Communications, 2007.
[5] C.W. Hou, Particle Swarm Optimization for Supply Chain Inventory Management Problems, Master Thesis, Department of Logistics Management, National Kaohsiung First University of Science and Technology, 2011.
[6] C.L. Huang, Finding the Shortest Path for the Public Transportation Systems, Master Thesis, Department of Information Management, Tamkang University, 2009.
[7] T.C. Huang, Y.M. Huang, and S.C. Cheng, “Automatic and interactive e-learning auxiliary material generation utilizing particle swarm optimization,” Expert Syst Appl, Vol. 35, pp. 2113-2122, 2007.
[8] Y.F. Huang, Using K-means Clustering Algorithms for Anomaly Detection, Master Thesis, Department of Computer Science and Engineering, National Taiwan Ocean University.
[9] J.S. Jhang, An Arrhythmia Recognition System Based on K-means Clustering、Wavelet Transform and Support Vector Machine, Master Thesis, Department of Mechatronic Technology, National Taiwan Normal University.
[10] G.W. Jiang, J. Wang, and B. Chen, “The Shortest Path Algorithm Based on Hierarchical Road Network,” ITS Telecommunications Proceedings, pp. 156-158, 2006.
[11] J. Kennedy, and R. Eberhart, “Particle swarm optimization,” Neural Networks, pp. 1942-1948, 1995.
[12] K.L. Lee, A Study of Using K-means Algorithm to Classify English Examination Questions, Master Thesis, Department of Applied Information Science, Leader University, 2006.
[13] J.F. Leng, and W. Zeng, “An Improved Shortest Path Algorithm for Computing One-to-One Shortest Paths on Road Networks,” Information Science and Engineering (ICISE), pp. 1979-1982, 2009.
[14] H.W. Li, An Application of Particle Swarm Optimization to Simulate Price Fluctuation of the Financial Product, Master Thesis, Department of Information Management, National Pingtung Institute of Commerce, 2010.
[15] C.H. Lin, The Study on Shortest Path Algorithm for Vehicle Navigation, Master Thesis, Department of Transportation Technology and Management, National Chiao Tung University , 2007.
[16] X. Liu, Z. Fang, G. Qu, H. Yang, and T. Pan, “A Framework of Agent-Based Collaborative Intelligent Transport System,” Computer Supported Cooperative Work in Design, 2007.
[17] X.. Ma, W. Burghout, and H. Koutsopoulos, “Evaluation of real-time travel time estimation method and disruption using noisy automatic vehicle identification measurements,” in Proc. 88th Annu. Meeting Transp. Res. Board, Washington, DC, 2009.
[18] J.B. MacQueen, “Some Methods for classification and Analysis of Multivariate Observations,” Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297, 1967.
[19] H.B. Mu, J.N. Yu, and L.Z. Liu, “Shortest path algorithm for road network with traffic restriction,” Power Electronics and Intelligent Transportation System (PEITS), pp. 381-384, 2009.
[20] Y.L. Shih, A study for evaluating influence factors of learning achievement in mathematics of senior elementary students using K-means cluster analysis, Master Thesis, Department of Industrial Management, Chung Hua University.
[21] M.L. Tam and W.H.K. Lam, “Short-term travel time prediction for congested urban road networks,” in Proc. 88th Annu. Meeting Transp. Res. Board, Washington, DC, 2009.
[22] C.C. Tsai, Adaptive E-Course Composition Process based on Particle Swarm Optimization, Master Thesis, Department of Computer Science and Information Engineering, National Cheng Kung University, 2009.
[23] X.J. Wang, and B. Du, “Particle swarm optimization based on intelligent transport system,” Science And Technology Information, Vol. 15, pp. 357-364, 2008.
[24] C.P. Wu, PSO-based Localization in Wireless Sensor Networks, Master Thesis, Department of Electrical Engineering, Tamkang University, 2008.