A low-memory alternative for time-dependent Dijkstra
- Author
- Simon Van den Eynde (UGent) , Jeroen Verbrugghe, P. Audenaert (UGent) , Ben Derudder (UGent) , Didier Colle (UGent) and Mario Pickavet (UGent)
- 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
- |
- |
- 2.51 MB
-
(...).pdf
- full text (Published version)
- |
- UGent only
- |
- |
- 2.53 MB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8675974
- 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. 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings, 933–938. 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: