Name
Abstract | ||
|---|---|---|
Computing driving directions in road networks is a fundamental problem. Although it can be solved in essentially linear time by Dijkstra's algorithm [6], this is not fast enough to enable interactive queries on large-scale inputs. Instead, modern algorithms typically work in two stages: first an offline preprocessing routine computes some auxiliary data, which is then used to answer exact queries in real time. The past decade has seen a surprisingly diverse set of techniques that follow this approach [1, 2, 7, 8, 9], mostly relying on the fact that road networks tend to have a strong hierarchy. These methods work very well when minimizing driving times, but are much less efficient with other cost functions. I will present a practical algorithm that has no such draw-backs, and can compute shortest paths on continental road networks with arbitrary metrics (cost functions). Our customizable route planning approach [3] uses very little space per metric, supports real-time queries, and can incorporate a new metric in a few seconds, thus enabling real-time traffic updates and personalized cost functions. Instead of relying on a strong hierarchy (which is metric-dependent), we use the fact that road networks can be efficiently partitioned into loosely connected regions. To find such partitions, we use a recent algorithm [4] based on the notion of natural cuts, which are sparse regions separating much denser areas. Our routing algorithm can be naturally extended to handle more elaborate queries, such as building distance tables, finding nearby points of interest, or suggesting alternative paths. This makes it ideal to implement a flexible, general-purpose journey planner, especially when combined with algorithms for public transportation networks [5]. In fact, our system is currently in use by Bing Maps. This is joint work with Daniel Delling, Andrew Goldberg, Thomas Pajor, and Ilya Razenshteyn. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2442942.2442943 | CTS@SIGSPATIAL |
Keywords | Field | DocType |
real-world route planning,strong hierarchy,road network,joint work,practical algorithm,modern algorithm,continental road network,cost function,routing algorithm,recent algorithm,personalized cost function | Route planning software,Planner,Theoretical computer science,Preprocessor,Point of interest,Time complexity,Hierarchy,Mathematics,Ilya,Dijkstra's algorithm | Conference |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Renato F. Werneck | 1 | 1743 | 84.33 |