跳到主要內容

臺灣博碩士論文加值系統

(3.235.120.150) 您好!臺灣時間:2021/08/06 03:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃麒瑋
研究生(外文):Chi-wei Huang
論文名稱:探勘道路事件資訊以運用於即時道路網路中連續性最快路徑規劃
論文名稱(外文):Continuous Fastest Path Planning in Real-Time Road Networks by Mining Traffic Event Information
指導教授:曾新穆曾新穆引用關係
指導教授(外文):Shin-Mu Tseng
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:72
中文關鍵詞:資料探勘最快路徑規劃全球定位系統道路事件
外文關鍵詞:Global positioning systemFastest path planningTraffic eventData mining
相關次數:
  • 被引用被引用:0
  • 點閱點閱:201
  • 評分評分:
  • 下載下載:30
  • 收藏至我的研究室書目清單書目收藏:1
近年來行動裝置設備的發展越來越便利,關於行動網路上的服務也變的越來越重要,導航服務便是眾多發展的服務之ㄧ。關於過去有關最快路徑的研究多半是針對靜態或是動態的網路去探討。然而道路網路的狀態會隨著即時性的交通狀態及道路事件而改變,以致於最後影響了導航結果的改變。為此,導航路徑規劃應同時考慮到道路事件以用來面對道路事件對於規劃的影響性。本論文中,提出一個新的道路事件預測演算法名為Traffic Event Prediction Algorithm <TEPA >,此演算法是藉由探勘道路事件歷史資料所挖掘出的道路事件知識作為預測發生於即時網路上的道路事件所造成的影響性。此外,連續性最快路徑規劃存在著高計算成本,本論文於此提出四種針對連續行最快路徑規劃的策略,該些策略將作為應對即時性道路資訊時路徑規劃的策略及改善規劃路徑時所存在著的高計算成本。最後,藉由設計一套包含道路事件及道路網路下的資料產生器,模擬現實生活中之道路網路狀況,並經由一系列的實驗,證明本論文之方法在不同環境參數下有優異的效率與正確率。
The mobile devices have become more and more convenient in recent years, and the services in mobile environment are regarded as more and more important. Navigation service is one of the mobile development services. Most of studies discussed how to find the fastest path in a static or dynamic road networks. However, the road networks will vary due to the change of real time traffic situation and traffic events. Finally, the navigation result will also change. Therefore, the navigation path planning should take into account the traffic events for solving the real-time traffic event effect. In this paper, we propose a novel prediction-based algorithm named TEPA (Traffic Event Prediction Algorithm) by mining traffic event knowledge from traffic event logs. TEPA can be used to predict the effects of traffic events occurred in real-time road networks. In addition, there is high computation cost for continuous path planning in a real-time road network. We propose four continuous path planning strategies in order to find the fastest path with consideration of the real-time traffic information and improvement on the real-time computation cost. Finally, we conducted a series of experiments to evaluate the performance of the proposed method under different system conditions by varying various parameters.
英文摘要 i
中文摘要 ii
誌謝 iii
表目錄 vi
圖目錄 vii
第一章 導論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 問題描述 4
1.4 研究貢獻 6
1.5 論文架構 6
第二章 文獻討論 7
2.1 全球定位系統〈Global Positioning System〉 7
2.2 導航系統〈Navigation System〉 8
2.3 路徑規劃 8
2.3.1 距離基礎的路徑問題 9
2.3.2 時間基礎的路徑問題 11
2.3.3 連續性路徑導航問題 13
2.4 資料探勘方法 14
2.4.1 相似度測量方法 15
2.4.2 叢集方法 16
2.4.2.1 密度基礎的叢集方法 17
2.4.2.2 叢集相似度搜尋技術 17
第三章 研究方法 19
3.1 方法架構 19
3.2 資料樣式之定義 20
3.3 TEPA〈Traffic Event Prediction Algorithm〉 23
3.3.1 決定道路分群 23
3.3.2 決定最大頻繁事件回復長度 25
3.3.3 移除雜訊 30
3.3.4 決定事件影響序列 33
3.4 連續性最快路徑規劃策略 35
3.4.1 路徑選擇策略 36
3.4.1.1 事件迴避路徑選擇策略 36
3.4.1.2 事件忽略路徑選擇策略 37
3.4.1.3 事件預測路徑選擇策略 38
3.4.1.4 路徑選擇策略綜合探討 42
3.4.2 路徑重新計算機制 42
3.4.2.1 無限制重新計算機制 〈Brute Force〉 42
3.4.2.2 路徑限制重新計算機制 〈Bounding Path〉 43
3.4.2.3 範圍限制重新計算機制 〈Bounding Area〉 44
3.4.2.4 路段限制重新計算機制 〈Bounding Area with Path〉 46
第四章 實驗分析 48
4.1 道路資料之模擬 48
4.2 實驗規劃 52
4.3 TEPA效能實驗 54
4.3.1 事件評估資訊之影響 54
4.3.2 交通擁塞程度之影響 55
4.3.3 道路網路規模之影響 56
4.3.4 事件發生頻率之影響 57
4.4 連續性最快路徑規劃策略效能實驗 59
4.4.1 範圍限制大小之影響 59
4.4.2 交通擁塞程度之影響 60
4.4.3 道路網路規模之影響 61
4.4.4 事件發生頻率之影響 63
4.5 實驗總結 66
第五章 結論 67
5.1 研究結論 67
5.2 未來發展 68
參考文獻 69
[1].R. Agrawal, J. Gehrke, D. Gunopulos, P. Raghavan, “Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications.” Proc. Of the ACM SIGMOD InternationalConference on Management of Data, Seattle, Washington, June, 1998.
[2].A. Awasthi, Y. Lechevallier, M. Parent, and J. M. Proth. “Rule based prediction of fastest paths on urban networks.” In Proceedings of the 8th International IEEE Conference on Intelligent Transportation Systems, Vienna, Austria, September, 2005.
[3].A. Ben-Dor, Z. Yakhini, “Clustering gene expression patterns.” Proceedings of the 3rd Annual International Conference on Computational Molecular BiologyRECOMB , 1999.
[4].H. D. Chon, D. Agrawal, and A. El. Abbadi, “FATES: Finding A Time dEpendent Shortest path.” In Proceedings of the 4th International Conference on Mobile Data Management, Melbourne, Australia. pages 165–180, 2003.
[5].E. W. Dijkstra. “A Note on Two Problems in Connection with Graphs.” Numerische Mathematik , Vol. 1, No. 1, pages 269-271, December 1959.
[6].F. Engineer. “Fast Shortest Path Algorithms for Large Road Networks.” In Proceedings of the 36th Annual ORSNZ Conference, Wellington, New Zealand. 2001.
[7].M. Ester, H.-P. Kriegel, J. Sander and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise.” Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining, pages 226-231, 1996.
[8].M. Fu, B. J. LI, Z. Zhi. “A Route Algorithm for the Shortest Distance Within a Restricted Searching Area.” Transactions of Beijing Institute of Technology, 2004.
[9].L. Fu, L. Rilett. “Expected shortest paths in dynamic and stochastic traffic networks,” Transportation Research, Methodological, vol. 32 pages 449-516,1998
[10].M. Fu, B. Xue. “A Path Planning Algorithm Based on Dynamic Networks and Restricted Searching Area.” IEEE International Conference on Automation and Logistics, 2007.”
[11].garmin website. http://www.garmin.com.tw/.
[12].H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. P. Sondag. “Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach.” In Proceeding of the 14th international conference on Very Large Data Bases, Vienna, Austria, September 2007.
[13].P. E. Hart, N. J. Nilsson, and B. Raphael. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pages 100-107, 1968.
[14].S. He, W. Guan. “Empirical Investigations on Traffic Phase Transitions at Beijing Ring Road.” IEEE Intelligent Transportation Systems Conference, 2007.
[15].ISO14819-1~ISO14819-6,“Traffic and Traveler Information (TTI)-TTI messages via traffic message coding”.
[16].A. K.Jain and R. C. Dubes, “Algorithm for Clustering Data,” Prentice Hall,, 1988.
[17].E. Kanoulas, Y. Du, T. Xia, and D. Zhang. “Finding Fastest Paths on A Road Network with Speed Patterns.” In Proceeding of the 22nd International Conference on Data Engineering, 2006.
[18].D. Kopitz and B. Marks, “Traffic and Travel Information Travel Information broadcasting - protocols for the 21st century,” Traffic and Travel Information EBU Technical Review, 1999.
[19].N. Lassabe, A. Berro, and Y. Duthen. “Improvement of a Shortest Routes Algorithm.” In Proceedings of the 10th International IEEE Conference on Intelligent Transportation Systems, Seattle, WA, USA, September 2007.
[20].C.-C Lee, Y.-H. Wu, A. L.P.Chen. “Continuous Evaluation of Fastest Path Queries on Road Networks.” International Symposium on Spatial and Temporal Databases, pages 20-37, 2007.
[21].N. Lefebvre, M. Balmer. “Fast Shortest Path Computation in Time-Dependent Traffic Networks.” Swiss Transport Research Conference, 2007.
[22].E. H.-C. Lu, C.-C. Lin, and V. S. Tseng, “Mining the Shortest Path within a Travel Time Constraint in Road Network Environments.” In Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems, October, 2008.
[23].K. Nachtigall. “Time depending shortest-path problems with applications to railway networks.” European Journal of Operational Research, Vol. 83, pages 154-166, 1995.
[24].G. Nannicini, P. Baptiste, G. Barbier, D. Krob, L. Liberti. “Fast Paths in Large-Scale dynamic road networks.” Computational Optimization and Applications, 2008.
[25].N. Nilsson. “Problem-Soving methods.” Artificial Intelligence, 1971.
[26].S. Pallottino and M. G. Scutella. “Shortest Path Algorithms in Transportation models: classical and innovative aspects.” Equilibrium and Advanced Transportation Modelling, pages 245-281. Kluwer Academic Publishers, 1998.
[27].“RDS Forum”. http://www.rds.org.uk/rds98/rds98.htm.
[28].S. Russell, P. Norvig. “Artificial Intelligence: A Modern Approach.” 2003.
[29].K. Sung, M. G. H. Bell, M. Seong, S. Park. “Shortest paths in a network with time-dependent flow speeds.” European Journal of Operational Research, Vol. 121, No.1, pages 32–39, 2000.
[30].F. B. 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, pages 69-82, 1997.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top