News for hackers. Stuff that matters.
Re:Show HN: Valhalla, an open source routing engine by ma2rten on Friday June 05, 2015 @01:15AM (#9663988)
what are the best ones?
Re:Show HN: Valhalla, an open source routing engine by glennon on Friday June 05, 2015 @04:50AM (#9664513)
For speedy street routing, the Open Source Routing Machine: http://project-osrm.org/ Like Google's proprietary routing engine, it leverages the scale of local and regional travel (via contraction hierarchies, arterial travel is suited for precomputed cacheing); result: the system can be tuned to give near instantaneous results. OSRM had been led by Dennis Luxen of Mapbox, though he just moved to Apple. The OP (Mapzen's Valhalla) appears to have a similar approach as OSRM. Good libraries for other scenarios exist; e.g., cycling and multimodal planning -- see: http://wiki.openstreetmap.org/wiki/Routing and OpenTripPlanner https://github.com/opentripplanner/OpenTripPlanner

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).

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).

Re:Show HN: Valhalla, an open source routing engine by glennon on Saturday June 06, 2015 @06:08PM (#9672477)
@karussell,

For a public source, Dennis Luxen updated his Linkedin profile.

Thanks for adding your knowledge about the internals of Valhalla code.

Re:Show HN: Valhalla, an open source routing engine by karussell on Tuesday June 09, 2015 @07:45AM (#9685264)
ah, easy, thanks :) !
Re:Show HN: Valhalla, an open source routing engine by karussell on Saturday June 06, 2015 @04:05PM (#9672065)
How do you define best?

I'm the author of GraphHopper. Easy to setup, fast and flexible. Try it here: https://graphhopper.com/maps/

Re:Show HN: Valhalla, an open source routing engine by glennon on Saturday June 06, 2015 @06:23PM (#9672533)
+1 ...and open source under Apache License 2.0 :)