ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

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

  • School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China

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
    Abstract

  • Abstract

    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.

    Abstract

    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.
    • FullText(HTML)
  • loading
    • References(7)
  • [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.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    Get Citation
    PDF
    XML
    [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.
    Recommended articles
    TrendMD
    Volume 44 Issue 10 page: 874-880
    Cover

    Article Metrics

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

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return