Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks

By R. J. Gutman. ALENEX/ANALC, 2004

303 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/8a8fd2078ea3e0c4549cb76c8220ffcedb8cc311

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Highway Hierarchies Hasten Exact Shortest Path Queries (2005, background): “Reach based routing [7] excludes nodes from consideration if they do not contribute to any path long enough to be of use for the current query.”
Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm (2008, background): “Gutman [5] observed that a shortest-path search can be pruned at nodes with a reach too small to get to either source or target from there.”
A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks (2011, background): “Highway hierarchies [26, 27] and reach [20, 19] use hierarchical properties of road networks to sparsify the search.”
Engineering Route Planning Algorithms (2009, methodology): “Gutman [31] observed that a shortestpath search can be stopped at nodes with a reach too small to get to source or target from there.”
Exact Routing in Large Road Networks Using Contraction Hierarchies (2012, methodology): “Also the RE algorithm of [Gutman 2004; Goldberg et al. 2007] has been implemented by [Goldberg 2006] on a mobile device, yielding query times of ‘a few seconds including path computation and search animation’ and requiring ‘2–3 GB for USA/Europe’.”
Map-matching for low-sampling-rate GPS trajectories (2009, background): “Note that a road may contain several road segments.”
Computing the shortest path: A search meets graph theory (2005, methodology): “a b o u t the work of G u t m a n [19], who s tudies the P 2 P”
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (2008, methodology): “We can prefer contracting globally unimportant nodes based on some path based centrality measure such as (approximate) betweenness [12] or reach [13,6].”
Route Planning in Transportation Networks (2015, background): “Another hierarchical approach is Reach [130].”
PHAST: Hardware-Accelerated Shortest Path Trees (2011, methodology): “, [10], [11], [ 2], [13], [14]) or the computation of certain centrality measur es, like betweenness [15], [16].”
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms (2006, methodology): “We improve the reach-based approach of Gutman [17] in several ways.”