Show HN: Valhalla, an open source routing engine
mapzen.com
mapzen.com
Also, it's not so much that the routing engines are proprietary -- the best ones are not. The underlying databases are the secret sauce.
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).
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).
For a public source, Dennis Luxen updated his Linkedin profile.
Thanks for adding your knowledge about the internals of Valhalla code.
I'm the author of GraphHopper. Easy to setup, fast and flexible. Try it here: https://graphhopper.com/maps/
No, it is not only about the database. Also about algorithms. But a lot about engineering and optimizing.
But there is a free hosted service (with API signup) for convenience.
Conf, the lesser known God of configurations and setups. He made sure that everything was well defined in a single place in a concise format, such as acceleration due to gravity, etc.
Your feature/bug: the router told you to take a ferry. You'll see the ferry route represented here: http://www.openstreetmap.org/search?query=SF%2C%20CA#map=13/...
I'm scanning the different subprojects on Github and I think Tyr is the one I need, but I'm not entirely sure..
So the 100+ million number is irrelevant.
Computing the geodesic distances was slow but not that slow because I used a variation of R* with some caching on top, but I still had to compute around 5MM distances or so.
Whereas route calculation can't be easily offloaded.
There is also a Postgres/Postgis extension pgRouting (http://pgrouting.org/) that will do routing in the database.
http://www.openstreetmap.org/directions?engine=osrm_car&rout...
It varies around the world, for the US (which I'm more familiar with) intercity is pretty solid, last mile stuff you might be missing a street.
Searching for a specific address can be an issue, but road data is pretty good.
There are also numerous dev gatherings that examine OSM applications and data quality. One starts in a few days: http://stateofthemap.us/program/ You might check out the program and see if your application area is addressed.
Summary: OSM data offers the best free geospatial vector data available. It is a good starting point. For serious commercial applications, however, the data are rarely ready "out of the box". You will almost certainly need to improve/transform/annotate the data for your own purposes. Keep in mind that consequential improvements are expected to be submitted back to the OSM project.
The road data is very good to excellent in most of the developed/Western world, particularly in Europe.
The footpath data is really the only available of online global maps, and is often excellent (down to details of surface quality).
The POI data is very good in continental Western Europe (down to trees, benches, water fountains etc), and then otherwise will vary depending on the city, or the country.