Accurate and fast path computation on large urban road networks: A general approach

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, the authors first develop an agglomerative graph partitioning method for generating high balanced traverse distance partitions, and they constitute a three-level graph model based on the graph partition scheme for structuring the urban road network. Then, the authors 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, the authors 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.


  • English

Media Info

  • Media Type: Web
  • Features: Figures; References; Tables;
  • Pagination: e0192274
  • Serial:
  • Publication flags:

    Open Access (libre)

Subject/Index Terms

Filing Info

  • Accession Number: 01669367
  • Record Type: Publication
  • Files: TRIS
  • Created Date: May 2 2018 4:37PM