Reach for A*: Shortest Paths on Road Networks

We study the problem of finding point-to-point shortest paths in a setting where preprocessing is allowed. We are interested in exact algorithms only, and our focus is on road networks. Our algorithms use several different strategies to speed up the queries. First, we use A* search to direct the search towards the goal. Second, we use the notion of "reach" to identify and prune local intersections.

Third, we add shortcuts to the graph to reduce the number of highway (i.e., non-local) edges. Our best query algorithm is thousands of times faster than Dijkstra's algorithm on the road networks of the United States and Western Europe, each with roughly 20 million vertices. This is joint work with Andrew Goldberg, Chris Harrelson, and Haim Kaplan.