Advanced search
1 file | 1.45 MB

An effective heuristic for computing many shortest path alternatives in road networks

Stéphanie Vanhove (UGent) and Veerle Fack (UGent)
Author
Organization
Abstract
We propose a simple and effective heuristic that allows fast generation of a large set of shortest path alternatives in weighted directed graphs. The heuristic is based on existing deviation path algorithms for exact k shortest paths. It precalculates a backward shortest path tree and thus avoids doing many shortest path computations, but as a result it does not necessarily find the exact set of k shortest paths. Computational results on real-world road networks are reported. Our tests show that the quality of the paths produced by the heuristic is most satisfactory: typically, the kth path found by the heuristic is less than 1% longer than the exact kth shortest path, for values of k up to 10,000. Moreover, the heuristic runs very fast. We also show how the heuristic can be enhanced to an exact k shortest paths algorithm, which performs well in comparison with the existing exact k shortest path algorithms.
Keywords
route planning, geographic information science, OPTIMIZATION PROBLEMS

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 1.45 MB

Citation

Please use this url to cite or link to this publication:

Chicago
Vanhove, Stéphanie, and Veerle Fack. 2012. “An Effective Heuristic for Computing Many Shortest Path Alternatives in Road Networks.” International Journal of Geographical Information Science 26 (6): 1031–1050.
APA
Vanhove, Stéphanie, & Fack, V. (2012). An effective heuristic for computing many shortest path alternatives in road networks. INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE, 26(6), 1031–1050.
Vancouver
1.
Vanhove S, Fack V. An effective heuristic for computing many shortest path alternatives in road networks. INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE. 2012;26(6):1031–50.
MLA
Vanhove, Stéphanie, and Veerle Fack. “An Effective Heuristic for Computing Many Shortest Path Alternatives in Road Networks.” INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE 26.6 (2012): 1031–1050. Print.
@article{3064680,
  abstract     = {We propose a simple and effective heuristic that allows fast generation of a large set of shortest path alternatives in weighted directed graphs. The heuristic is based on existing deviation path algorithms for exact k shortest paths. It precalculates a backward shortest path tree and thus avoids doing many shortest path computations, but as a result it does not necessarily find the exact set of k shortest paths. 
Computational results on real-world road networks are reported. Our tests show that the quality of the paths produced by the heuristic is most satisfactory: typically, the kth path found by the heuristic is less than 1% longer than the exact kth shortest path, for values of k up to 10,000. Moreover, the heuristic runs very fast. 
We also show how the heuristic can be enhanced to an exact k shortest paths algorithm, which performs well in comparison with the existing exact k shortest path algorithms.},
  author       = {Vanhove, Stéphanie and Fack, Veerle},
  issn         = {1365-8816},
  journal      = {INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE},
  keywords     = {route planning,geographic information science,OPTIMIZATION PROBLEMS},
  language     = {eng},
  number       = {6},
  pages        = {1031--1050},
  title        = {An effective heuristic for computing many shortest path alternatives in road networks},
  url          = {http://dx.doi.org/10.1080/13658816.2011.620572},
  volume       = {26},
  year         = {2012},
}

Altmetric
View in Altmetric
Web of Science
Times cited: