< Back to previous page


A low-memory alternative for time-dependent Dijkstra

Book Contribution - Book Chapter Conference Contribution

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 DijkstraU+2019s 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.
Book: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Proceedings
Pages: 933 - 938
Publication year:2020