Portal de Periódicos da CAPES

Highway hierarchies star

2009; Linguagem: Inglês

10.1090/dimacs/074/06

2472-4793

Daniel Delling, Peter Sanders, Dominik Schultes, Dorothea Wagner,

Constraint Satisfaction and Optimization

We study two speedup techniques for route planning in road net- works: highway hierarchies (HH) and goal directed search using landmarks (ALT). It turns out that there are several interesting synergies. Highway hi- erarchies 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 approxi- mately shortest travel times, this combination yields significant speedups (be- tween 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.