Transit Node Routing Reconsidered. Arz, Luxen, Sanders. Experimental Algorithms 2013.


<These notes are from the arxiv version>

  1. “Transit Node Routing (TNR) is a fast and exact distance oracle for road networks.”
  2. This paper
    1. Provides a means of speeding up preprocessing by an order of magnitude
  3. Basic idea in contraction hierarchies is to do some preprocessing to allow for speedups of Dijkstras
  4. TNR is one of the best methods, and can get queries down to almost constant time (a small number of table lookups)
  5. The basic assumption behind TNR is that queries that span long geographical distances almost always go through centralized connections <highways> called transit nodes

    1. Generally, there are only a few entrances to each transit node, so distances to these entrances as well as pairwise between transit nodes is stored
    2. This information allows for a locality filter, which “… indicates whether the shortest path
      might not cross any transit nodes, requiring an additional local path search.”
  6. A couple of issues with TNR traditionally is very expensive preprocessing, as well as the need for geographic information of the nodes (which a little bit of a poor fit when dealing theoretically with graphs; the hope is that would be abstracted away)
  7. On a rough level, contraction mappings order nodes by importance, and contracting them — removing them temporarily from the graph, and inserting new shortcut edges between that removed node and its neighbors only when necessary to maintain shortest path distances
  8. When doing search, all original edges are considered, as well as the additionally processed shortcut edges (although only those that lead to more important nodes).  <Its not clear if also the original edges are filtered this way, but it seems like it is the case, as the resulting graph forms a DAG.>
    1. Leads to a graph with particular structure (all shortest paths now have a midpoint), which allows for a Dijkstra’s with a minor extension to be used
  9. Basically, these tricks allow for linear as opposed to quadratic all-pair shortest paths to be computed
  10. “TNR in itself is not a complete algorithm, but a framework. A concrete instantiation has to fi nd solutions to the following degrees of freedom: It has to identify a set of transit nodes. It has to fi nd access node for all nodes.”
  11. “CHs order the nodes in such a way that nodes occurring in many shortest paths are moved to the upper part of the hierarchy. Hence, CH is a natural choice to identify a small node set which covers many shortest paths in the road network.”
    1. <This is a loose definition of course, and for a real-world mapping problem you can’t hope to tackle it with an exact solution, so the trick must be what sort of heuristic to use>
  12. The algorithm presented here does not require geometric information about the nodes, resolving that wrinkle
  13. <skimming some parts of the papers, like the lemmas>
  14. <the remainder of the paper is empirical results – actually on a DIMACS dataset of Europe with about 20M nodes/edges>
  15. <discussion of application of other common graph-search extensions/heuristics>
  16. <discussion>
  17. “In particular, at the price of twice the (quite fast) preprocessing time of contraction hierarchies, we get two orders of magnitude faster query time. Our purely graph theoretical locality filter outperforms previously used geometric filters. To the best of our knowledge, this eliminates the last remnant of geometric techniques in competitive speedup techniques for route planning.”
Advertisements
Tagged ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: