ISSN 0253-2778

CN 34-1054/N

Open AccessOpen Access JUSTC Original Paper

An efficient lower-bounding approach to point-to-point shortest path problem

Funds:  Supported by National Natural Science Foundation of China (61033009,61303047).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.10.012
More Information
  • Author Bio:

    ZHANG Zhong, male, born in 1987. Research field: Routing algorithm. E-mail: bergdino@mail.ustc.edu.cn

  • Corresponding author: SUN Guangzhong
  • Received Date: 24 April 2014
  • Accepted Date: 28 May 2014
  • Rev Recd Date: 28 May 2014
  • Publish Date: 30 October 2014
  • Querying for the shortest path from a source vertex to a sink vertex in real time is a fundamental problem in numerous applications. Several lower-bounding schemes have been proposed to solve the problem so far, such as A* search and ALT algorithm. But these schemes adopted loose valuations on distance so that there are great potentialities for improving the lower bounds. A novel two-stage goal directed lower-bounding approach, called ACT algorithm, was proposed, which combined A* search, centers and triangle inequality with no prior domain knowledge. Unlike previous schemes, the new algorithm can obtain excellent distance bounds by exploiting a large number of pre-computed data. The experimental results on real road networks show that ACT algorithm significantly outperforms all previous algorithms. In some instances, the vertices scanned by ACT algorithm are only about 25% more than those on optimal paths.
    Querying for the shortest path from a source vertex to a sink vertex in real time is a fundamental problem in numerous applications. Several lower-bounding schemes have been proposed to solve the problem so far, such as A* search and ALT algorithm. But these schemes adopted loose valuations on distance so that there are great potentialities for improving the lower bounds. A novel two-stage goal directed lower-bounding approach, called ACT algorithm, was proposed, which combined A* search, centers and triangle inequality with no prior domain knowledge. Unlike previous schemes, the new algorithm can obtain excellent distance bounds by exploiting a large number of pre-computed data. The experimental results on real road networks show that ACT algorithm significantly outperforms all previous algorithms. In some instances, the vertices scanned by ACT algorithm are only about 25% more than those on optimal paths.
  • loading
  • [1]
    Delling D, Sanders P, Schultes D, et al. Engineering route planning algorithms[M]//Algorithmics of large and complex networks. Springer Berlin Heidelberg, 2009: 117-139.
    [2]
    Pohl I. Bi-directional and heuristic search in path problems[M]. Department of Computer Science, Stanford University, 1969.
    [3]
    Gutman R J. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX 2004), 100-111.
    [4]
    Goldberg A V, Harrelson C. Computing the shortest path: A search meets graph theory[C]//Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005: 156-165.
    [5]
    Goldberg A V, Kaplan H, Werneck R F. Reach for A*: Efficient point-to-point shortest path algorithms[C]//IN WORKSHOP ON ALGORITHM ENGINEERING & EXPERIMENTS. 2006.
    [6]
    9th DIMACS Implementation Challenge:http://www.dis.uniroma1.it/challenge9/download.shtml.
    [7]
    Goldberg A V, Werneck R F F. Computing Point-to-Point Shortest Paths from External Memory[C]//ALENEX/ANALCO. 2005: 26-40.
  • 加载中

Catalog

    [1]
    Delling D, Sanders P, Schultes D, et al. Engineering route planning algorithms[M]//Algorithmics of large and complex networks. Springer Berlin Heidelberg, 2009: 117-139.
    [2]
    Pohl I. Bi-directional and heuristic search in path problems[M]. Department of Computer Science, Stanford University, 1969.
    [3]
    Gutman R J. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX 2004), 100-111.
    [4]
    Goldberg A V, Harrelson C. Computing the shortest path: A search meets graph theory[C]//Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005: 156-165.
    [5]
    Goldberg A V, Kaplan H, Werneck R F. Reach for A*: Efficient point-to-point shortest path algorithms[C]//IN WORKSHOP ON ALGORITHM ENGINEERING & EXPERIMENTS. 2006.
    [6]
    9th DIMACS Implementation Challenge:http://www.dis.uniroma1.it/challenge9/download.shtml.
    [7]
    Goldberg A V, Werneck R F F. Computing Point-to-Point Shortest Paths from External Memory[C]//ALENEX/ANALCO. 2005: 26-40.

    Article Metrics

    Article views (13) PDF downloads(77)
    Proportional views

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return