4 ms·
The algorithm behind OSRM is actually fairly new, and quite clever. By generating some expensive lookup tables up front, it's possible to do exact shortest-path
by teraflop 12y ago
The algorithm behind OSRM is actually fairly new, and quite clever. By generating some expensive lookup tables up front, it's possible to do exact shortest-path route finding on huge near-planar graphs (like, say, all the roads in the USA) in a matter of milliseconds, or even microseconds.
It's a great example of how theoretical CS research can have a huge impact on practical applications.
http://en.wikipedia.org/wiki/Contraction_hierarchies http://en.wikipedia.org/wiki/Contraction_hierarchies
http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf http://algo2.iti.kit.edu/documents/routeplanning/geisberger_... (PDF)
- frik 12y agoCan you point to the actual code?
- dbaupp 12y agoLooks like it might be https://github.com/Project-OSRM/osrm-backend/tree/master/contractor https://github.com/Project-OSRM/osrm-backend/tree/master/con... , but I don't know for sure.
- karussell 12y agoIt is not a lookup table - think more of some additional shortcuts you introduce for a certain mode. This way you get lots of speed but loose flexibility. In GraphHopper you can enable and disable it, the code is here https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java https://github.com/graphhopper/graphhopper/blob/master/core/...
- lorenzhs 12y agoIf you are interested in further details on algorithms for route planning, check out http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/routenplanung/index#termine_und_material http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... for a whole lecture on them (slides are in English). Each chapter also contains a list of relevant publications.