Finding Time-Dependent Shortest Paths over Large Graphs
Authors
- Bolin Ding (UIUC, USA)
- Jeffrey Xu Yu (The Chinese University of Hong Kong, China)
- Lu Qin (The Chinese University of Hong Kong, Hong Kong SAR, China)
Abstract
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 w_{i,j}(t) specifies how much time it takes to travel from node v_i to node v_j, 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.