Advanced search
2 files | 5.04 MB Add to list
Author
Organization
Abstract
Time-dependent routing algorithms are a fundamental tool for calculating the fastest routes in road networks since the travel time of each road varies by departure time, due to congestion. While the time-dependent variant of Dijkstra’s algorithm (TD-Dijkstra) can solve the routing problem optimally, it requires a large amount of memory. This paper presents a new memory-efficient time-dependent routing heuristic: the Time-Location Penalty Model (TLPM). Compared to timeindependent Dijkstra, TLPM significantly increases accuracy in time-dependent routing problems, while keeping runtime and memory usage low.

Downloads

  • 7782 i.pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 2.51 MB
  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 2.53 MB

Citation

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

MLA
Van den Eynde, Simon, et al. “A Low-Memory Alternative for Time-Dependent Dijkstra.” 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings, IEEE, 2020, pp. 933–38, doi:10.1109/ITSC45102.2020.9294640.
APA
Van den Eynde, S., Verbrugghe, J., Audenaert, P., Derudder, B., Colle, D., & Pickavet, M. (2020). A low-memory alternative for time-dependent Dijkstra. In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings (pp. 933–938). Rhodes, Greece - online: IEEE. https://doi.org/10.1109/ITSC45102.2020.9294640
Chicago author-date
Van den Eynde, Simon, Jeroen Verbrugghe, P. Audenaert, Ben Derudder, Didier Colle, and Mario Pickavet. 2020. “A Low-Memory Alternative for Time-Dependent Dijkstra.” In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings, 933–38. IEEE. https://doi.org/10.1109/ITSC45102.2020.9294640.
Chicago author-date (all authors)
Van den Eynde, Simon, Jeroen Verbrugghe, P. Audenaert, Ben Derudder, Didier Colle, and Mario Pickavet. 2020. “A Low-Memory Alternative for Time-Dependent Dijkstra.” In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings, 933–938. IEEE. doi:10.1109/ITSC45102.2020.9294640.
Vancouver
1.
Van den Eynde S, Verbrugghe J, Audenaert P, Derudder B, Colle D, Pickavet M. A low-memory alternative for time-dependent Dijkstra. In: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings. IEEE; 2020. p. 933–8.
IEEE
[1]
S. Van den Eynde, J. Verbrugghe, P. Audenaert, B. Derudder, D. Colle, and M. Pickavet, “A low-memory alternative for time-dependent Dijkstra,” in 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings, Rhodes, Greece - online, 2020, pp. 933–938.
@inproceedings{8675974,
  abstract     = {{Time-dependent routing algorithms are a fundamental tool for calculating the fastest routes in road networks since the travel time of each road varies by departure time, due to congestion. While the time-dependent variant of Dijkstra’s algorithm (TD-Dijkstra) can solve the routing problem optimally, it requires a large amount of memory. This paper presents a new memory-efficient time-dependent routing heuristic: the Time-Location Penalty Model (TLPM). Compared to timeindependent Dijkstra, TLPM significantly increases accuracy in time-dependent routing problems, while keeping runtime and memory usage low.}},
  author       = {{Van den Eynde, Simon and Verbrugghe, Jeroen and Audenaert, P. and Derudder, Ben and Colle, Didier and Pickavet, Mario}},
  booktitle    = {{2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings}},
  isbn         = {{9781728141497}},
  issn         = {{2153-0009}},
  language     = {{eng}},
  location     = {{Rhodes, Greece - online}},
  pages        = {{933--938}},
  publisher    = {{IEEE}},
  title        = {{A low-memory alternative for time-dependent Dijkstra}},
  url          = {{http://dx.doi.org/10.1109/ITSC45102.2020.9294640}},
  year         = {{2020}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: