Back to Search
Start Over
Accurate and fast path computation on large urban road networks: A general approach.
- Source :
- PLoS ONE; 2/14/2018, Vol. 13 Issue 2, p1-13, 13p
- Publication Year :
- 2018
-
Abstract
- Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing. While a number of heuristic algorithms have been developed in the past few years for faster path queries, the accuracy of them are always far below satisfying. In this paper, we first develop an agglomerative graph partitioning method for generating high balanced traverse distance partitions, and we constitute a three-level graph model based on the graph partition scheme for structuring the urban road network. Then, we propose a new hierarchical path computation algorithm, which benefits from the hierarchical graph model and utilizes a region pruning strategy to significantly reduce the search space without compromising the accuracy. Finally, we present a detailed experimental evaluation on the real urban road network of New York City, and the experimental results demonstrate the effectiveness of the proposed approach to generate optimal fast paths and to facilitate real-time routing applications. [ABSTRACT FROM AUTHOR]
- Subjects :
- TRANSPORTATION
TRAFFIC engineering
ROADS
NAVIGATION
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 13
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- PLoS ONE
- Publication Type :
- Academic Journal
- Accession number :
- 127992343
- Full Text :
- https://doi.org/10.1371/journal.pone.0192274