Finding time-dependent shortest paths over large graphs

Publication Type:
Conference Proceeding
Citation:
Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings, 2008, pp. 205 - 216
Issue Date:
2008-05-16
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002372OK.pdf314.33 kB
Adobe PDF
The spatial and temporal databases have been studied widely and intensively over years. In this paper, we study how to answer queries of finding the best departure time that minimizes the total travel time from a place to another, over a road network, where the traffic conditions dynamically change from time to time. We study a generalized form of this problem, called the time-dependent shortest-path problem. A time-dependent graph G T is a graph that has an edge-delay function, w i,j(t), associated with each edge (v i, v j), to be stored in a database. The edge-delay function Wi,j(t) specifies how much time it takes to travel from node v i to node Vj, if it departs from v i at time t. A user-specified query is to ask the minimum-travel-time path, from a source node, v s, to a destination node, v e, over the time-dependent graph, G T, with the best departure time to be selected from a time interval T. We denote this user query as LTT(v s v e, T) over G T. The challenge of this problem is the added complexity due to the time dependency in the time-dependent graph. That is, edge delays are not constants, and can vary from time to time. In this paper, we propose a novel algorithm to find the minimum-travel-time path with the best departure time for a LTT(v s, v e, T) query over a large graph G T. Our approach outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice. We will discuss the design of our algorithm, together with its correctness and complexity. We conducted extensive experimental studies over large graphs and will report our findings. Copyright 2008 ACM.
Please use this identifier to cite or link to this item: