Highway hierarchies star
Daniel Delling, Peter W. Sanders, Dominik Schultes, Dorothea Wagner · DIMACS series in discrete mathematics and theoretical computer science · 2009
We study two speedup techniques for route planning in road networks: highway hierarchies (HH) and goal directed search using landmarks (ALT). It turns out that there are several interesting synergies. Highway hierarchies yield a way to implement landmark selection more efficiently and to store landmark information more space efficiently than before. ALT gives queries in highway hierarchies an excellent sense of direction and allows some pruning of the search space. For computing shortest distances and approximately shortest travel times, this combination yields significant speedups (between a factor of 2.5 and 5) over HH alone, while for exact queries using the travel time metric only minor improvements are achieved. We also explain how to compute actual shortest paths very efficiently.