道路網上最快路徑查詢之持續評估

Continuous Evaluation of Fastest Path Queries on Road Networks.

李佳蓁(Chia-Chen Lee)

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

在空間網路資料庫中，搜尋兩點間(起點以及終點)之路徑是一個時常使用並且基本的操作。在過去的研究當中，大多著重於最短路徑的搜尋，也就是找到一條由起點出發至終點的路徑，使得其距離最短。然而，在很多如導航系統這樣的實際的應用中，交通的狀況以及行車所需要的時間不斷地改變。並且，使用者通常期望得到一條最快的路徑，也就是能夠花費最少時間，由起點抵達終點的路徑。而這個路徑可能不是最短的路徑。這促使我們注意到最快路徑查詢以及連續最快路徑查詢之持續評估的問題，以適應動態的交通狀況以及道路環境。要處理一個連續最快路徑查詢，可以採用離散時間模式，也就是在每個時間片段重新對最快路徑查詢做評估，然而這是一個計算量十分驚人的方式。當系統中有大量的查詢同時存在時，這個重新評估的花費會更高。在本論文中，我們提出了ㄧ個新的方法，這個方法採用了影響區塊、容忍參數的內涵，以及一個網格式索引結構。藉由容忍參數，只要一個查詢的最快路徑與答案接近，系統不需要對此查詢做重新評估。另外，當系統要處理多重查詢時，網格式索引結構可以加速查詢之評估。最後，我們利用真實的道路資料以及模擬的交通狀況來做實驗。實驗結果顯示本論文提出之方法有非常好的表現。

關鍵字

道路網 ； 最快路徑 ； 連續性查詢

並列摘要

Finding the shortest path between two given positions (the origin and the destination) is an essential operation in spatial network databases. Previous studies focus on evaluating the shortest path query, which will find the path with the shortest network distance. However, in the applications on road networks such as the guided driving, the traffic conditions often vary as time goes and the user is actually interested in the path with the minimum travel time (called the fastest path), which may not have the shortest network distance. This motivates us to study the issues of continuously evaluating the fastest path query in order to capture the dynamics of road networks. Repeatedly evaluating the fastest path query at every moment is infeasible due to its computationally expensive cost. The cost is higher if more queries are evaluated at the same time. In this paper, we propose a novel approach that employs the concepts of the affecting area and the tolerance parameter, and a grid-based index structure. With the tolerance parameter, a query is not reevaluated as long as the travel time of the current answer is close enough to that of the fastest path. Furthermore, with the grid-based index, the dynamics of road networks and the queries are fused together to achieve the efficient re-evaluation of multiple queries. Experiments based on real road networks are performed and the results show the great performance of our approach.

並列關鍵字

road network ； fastest path ； continuous query

參考文獻

[1] R. Agrawal and H. Jagadish. Materialization and Incremental Update of Path Information. In Proc. Fifth Int’l Conf. Data Eng., pp. 374-383, 1989.

[3] J. Esser and M. Schrechenberg. Microscopic Simulation of Urban Traffic Based on Cellular Automata. International Journal of Modern Physics, Vol. 8, pp. 1025-1036, 1997.

[4] E. Dijkstra. A Note on Two Problems in Connection with Graphs. Numeriche Mathematik, Vol. 1, pp. 269-271, 1959.

[6] L. Fu, and L. Rilett. Expected shortest paths in dynamic and stochastic traffic networks, Transportation Research, Methodological, vol. 32, pp. 499-516.

[9] Y. Huang, N. Jing, and E. Rundensteiner. Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types. In Proc. Third ACM Workshop Geographic Information Systems, pp. 93-100, 1995.