5 ms·

the very simple algorithm we used for Streets & Trips to start was "get to an interstate on both ends, then route the middle bit" with a bias towards staying on

by RyJones 12y ago

the very simple algorithm we used for Streets & Trips to start was "get to an interstate on both ends, then route the middle bit" with a bias towards staying on larger roads longer. as it turns out you don't get optimal results but you do get pretty good results with very little computation.

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 ago
  Can you point to the actual code?
  - dbaupp 12y ago
    Looks 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 ago
  It 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 ago
  If 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.

by RyJones 12y ago

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 ago
Can you point to the actual code?
- dbaupp 12y ago
  Looks 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 ago
It 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 ago
If 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.