近年來行動裝置設備的發展越來越便利，關於行動網路上的服務也變的越來越重要，導航服務便是眾多發展的服務之ㄧ。關於過去有關最快路徑的研究多半是針對靜態或是動態的網路去探討。然而道路網路的狀態會隨著即時性的交通狀態及道路事件而改變，以致於最後影響了導航結果的改變。為此，導航路徑規劃應同時考慮到道路事件以用來面對道路事件對於規劃的影響性。本論文中，提出一個新的道路事件預測演算法名為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.

[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.