Fast Route Planning

Google Tech Talk
March 23, 2009

ABSTRACT

Presenters: Peter Sanders

I give an overview of our current and future work on route planning. Based on contraction hierarchies, a simple technique that allows fast routing by exploiting the hierarchy available in the network, I explain how this can be used for static routing in continent sized road networks in about 0.1 ms, as a basis for transit-node routing that is another two orders of magnitude faster, and for computing distance tables, yet another order of magnitude faster. The latter method has applications, e.g., in logistics optimizations. Perhaps more importantly, we now generalize our techniques to more general settings including turn penalties, traffic jams, mobile hardware, time-dependent edge weights, public transportation, and multicriteria optimization.

• Category

  Science & Technology

[luiza2166]

Audio problems are somewhat common in Google Talks, unfortunately. Wish they did something about it. :(

[calin2k]

interesting presentation, but the audio is bad

[Muhammad Najib]

is the explanation about Route Planning that used in Google Maps Direction API?

[TheOnlyFeanor]

Very insightful talk.

[eciOkMcOwnage]

not direclty the TSP problem, but you can create the "input" for your TSP problem, i.e. if you have a set of nodes T which should be visited by the TSP route, you can compute the TxT distance table (very fast).

Then you need a TSP algorithm which computes a tsp route on the G'=(T,TxT) graph (which is not part of the presentation). There exists algorithms which can solve this problem normally in reasonable time (although the TSP problem is NP-hard).

[Antonio García Domínguez]

I don't mind this new format, but the audio really needs to be improved.

[Faisal Nur]

you actually watchd it all ?