A low-memory alternative for time-dependent Dijkstra
Simon Van den Eynde, Jeroen Verbrugghe Pieter Audenaert, Ben Derudder, Didier Colle, Mario Pickavet · 2020
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 time-independent Dijkstra, TLPM significantly increases accuracy in time-dependent routing problems, while keeping runtime and memory usage low.