Advanced search
1 file | 772.43 KB Add to list

The predecessor and the accounting algorithm speed up shortest path calculations in traffic routing applications

Sofie Demeyer (UGent) , Jan Goedgebeur (UGent) , Pieter Audenaert (UGent) , Mario Pickavet (UGent) and Piet Demeester (UGent)
Author
Organization
Abstract
As traffic routing applications usually are heavily burdened due to the many requests, a low execution time of the shortest path algorithms is of uttermost importance. In this article two goal-directed heuristics are presented, which reduce this execution time. By guiding the search toward the destination and neglecting the less interesting areas of the network a remarkable speedup can be realized, especially in large networks like traffic networks. The predecessor algorithm makes use of local information in order to guide the search towards the destination, while the accounting algorithm additionally uses the path's history to direct the search in the right direction. Both algorithms have been tested on a European road network. It is shown experimentally that these heuristics indeed realize a speedup and are more accurate than most existing goal-directed heuristics.
Keywords
road traffic, traffic engineering computing

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 772.43 KB

Citation

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

MLA
Demeyer, Sofie, Jan Goedgebeur, Pieter Audenaert, et al. “The Predecessor and the Accounting Algorithm Speed up Shortest Path Calculations in Traffic Routing Applications.” 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010). Piscataway, NJ, USA: IEEE, 2010. 980–985. Print.
APA
Demeyer, S., Goedgebeur, J., Audenaert, P., Pickavet, M., & Demeester, P. (2010). The predecessor and the accounting algorithm speed up shortest path calculations in traffic routing applications. 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010) (pp. 980–985). Presented at the 13th International IEEE annual conference on Intelligent Transportation Systems (ITSC 2010), Piscataway, NJ, USA: IEEE.
Chicago author-date
Demeyer, Sofie, Jan Goedgebeur, Pieter Audenaert, Mario Pickavet, and Piet Demeester. 2010. “The Predecessor and the Accounting Algorithm Speed up Shortest Path Calculations in Traffic Routing Applications.” In 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010), 980–985. Piscataway, NJ, USA: IEEE.
Chicago author-date (all authors)
Demeyer, Sofie, Jan Goedgebeur, Pieter Audenaert, Mario Pickavet, and Piet Demeester. 2010. “The Predecessor and the Accounting Algorithm Speed up Shortest Path Calculations in Traffic Routing Applications.” In 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010), 980–985. Piscataway, NJ, USA: IEEE.
Vancouver
1.
Demeyer S, Goedgebeur J, Audenaert P, Pickavet M, Demeester P. The predecessor and the accounting algorithm speed up shortest path calculations in traffic routing applications. 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010). Piscataway, NJ, USA: IEEE; 2010. p. 980–5.
IEEE
[1]
S. Demeyer, J. Goedgebeur, P. Audenaert, M. Pickavet, and P. Demeester, “The predecessor and the accounting algorithm speed up shortest path calculations in traffic routing applications,” in 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010), Madeira, Portugal, 2010, pp. 980–985.
@inproceedings{1110731,
  abstract     = {As traffic routing applications usually are heavily burdened due to the many requests, a low execution time of the shortest path algorithms is of uttermost importance. In this article two goal-directed heuristics are presented, which reduce this execution time. By guiding the search toward the destination and neglecting the less interesting areas of the network a remarkable speedup can be realized, especially in large networks like traffic networks. The predecessor algorithm makes use of local information in order to guide the search towards the destination, while the accounting algorithm additionally uses the path's history to direct the search in the right direction. Both algorithms have been tested on a European road network. It is shown experimentally that these heuristics indeed realize a speedup and are more accurate than most existing goal-directed heuristics.},
  author       = {Demeyer, Sofie and Goedgebeur, Jan and Audenaert, Pieter and Pickavet, Mario and Demeester, Piet},
  booktitle    = {2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010)},
  isbn         = {9781424476596},
  keywords     = {road traffic,traffic engineering computing},
  language     = {eng},
  location     = {Madeira, Portugal},
  pages        = {980--985},
  publisher    = {IEEE},
  title        = {The predecessor and the accounting algorithm speed up shortest path calculations in traffic routing applications},
  url          = {http://dx.doi.org/10.1109/ITSC.2010.5625085},
  year         = {2010},
}

Altmetric
View in Altmetric
Web of Science
Times cited: