Finding Fastest Paths on A Road Network with Speed Patterns
Citations Over TimeTop 10% of 2006 papers
Abstract
This paper proposes and solves the Time-Interval All Fastest Path (allFP) query. Given a user-defined leaving or arrival time interval I, a source node s and an end node e, allFP asks for a set of all fastest paths from s to e, one for each sub-interval of I. Note that the query algorithm should find a partitioning of I into sub-intervals. Existing methods can only be used to solve a very special case of the problem, when the leaving time is a single time instant. A straightforward solution to the allFP query is to run existing methods many times, once for every time instant in I. This paper proposes a solution based on novel extensions to the A* algorithm. Instead of expanding the network many times, we expand once. The travel time on a path is kept as a function of leaving time. Methods to combine travel-time functions are provided to expand a path. A novel lower-bound estimator for travel time is proposed. Performance results reveal that our method is more efficient and more accurate than the discrete-time approach.
Related Papers
- → Instant Art, Instant Culture: The Unspoken Policy for American Schools(1984)62 cited
- → Instant Art Instant Culture: The Unspoken Policy for American Schools(1986)5 cited
- Study on the Development Situation and Tendency of International Instant Noodles Industry(2010)
- The Current Situation and Main Problems Analysis of Domestic Instant Rice Products(2008)
- Study on fast analysis of instant rice(2010)