Re:Show HN: Valhalla, an open source routing engine
by karussell on Saturday June 06, 2015 @04:18PM
(#9672105)
Just curious: Where did you heard about that Dennis moved to Apple :) ?
Some clarification:
* the process of the route finding is done by Dijkstra or A* or with a preprocessing (CH)
* valhalla does not use CH to my knowledge
* route optimization requires a completely different technique and valhalla does not do this
> "The OP (Mapzen's Valhalla) appears to have a similar approach as OSRM"
no :) ! OSRM is limited to CH (really fast) and valhalla is limited to Dijkstra/A* (really flexible).
There's an academic Thesis on the principles of contraction hierarchies that is worth a look if you're in this space. http://algo2.iti.kit.edu/documents/routeplanning/geisberger_... My favorite is actually a Master's thesis that steps through the process of using contraction hierarchies to build a routing engine (MoNav) on OpenStreetMap data. https://code.google.com/p/monav/downloads/detail?name=thesis...
For nuanced or complex problems, set up your objectives and constraints against a good solver: http://en.wikipedia.org/wiki/List_of_optimization_software I'm partial to Google's OR Tools https://github.com/google/or-tools (Apache License).