How does this compare to Project OSRM [1]?

[1] https://github.com/Project-OSRM/osrm-backend

this blog post explains some of the major differences in the two architectures: https://mapzen.com/blog/valhalla-why_tiles

The OSRM routing engine appears to focus on contraction hierarchies; is that also the case for Valhalla? http://en.wikipedia.org/wiki/Contraction_hierarchies

Also, source code is here: https://github.com/valhalla

Since most routing software is proprietary, I think it would be good to combat it by using a strong copyleft on the Valhalla components. GPLv3+ for client software and AGPLv3+ for server software would be awesome.

No thanks, I'd like to be able to see something like this in a GPS unit, even if that GPS unit isn't totally copyleft as well

Glancing at the Valhalla repos, it looks like the MIT license across the board: https://github.com/valhalla ; https://github.com/valhalla/thor/blob/master/COPYING ; https://github.com/valhalla/chef-valhalla/blob/master/LICENS... ; etc...

Also, it's not so much that the routing engines are proprietary -- the best ones are not. The underlying databases are the secret sauce.

> The underlying databases are the secret sauce.

No, it is not only about the database. Also about algorithms. But a lot about engineering and optimizing.

You make a great point about engineering. The interaction of algorithms/techniques and the database, as well as computational infrastructure and UI/UX, are all significant areas of differentiation. I still disagree about algorithms themselves as a differentiator -- everyone has access to excellent shortest path algorithms already. Other geospatial optimizations (scheduling, circuits, flows, etc) are a different story; as represented by the many scientific disciplines that pursue those problems: operations research, graph theory, network science, location science, etc.

what are the best ones?

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

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

@karussell,

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

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

ah, easy, thanks :) !

How do you define best?

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

+1 ...and open source under Apache License 2.0 :)

I'm a bit confused. This doesn't seem like free software after reading the web page. It seems that the client is free, but the server component is proprietary SaaS and you have to get an API key through MapZen? I see several repositories on their GitHub account, but it's not apparent if this is all that is needed to self-host.

There is no proprietary component, if you want to self-host it's all here: https://github.com/valhalla

But there is a free hosted service (with API signup) for convenience.

Awesome. Thanks for clarifying.

its all you need to self host. check out the chef repository. it should be all you need to throw it up on aws

Looks great! I really like the norse themed repository names ... though I'm not familiar with "demos" and "conf", are they some sort of mythical norse figures as well?

Demos, the great God of demonstrations and examples. He preferred to teach other Gods, as opposed to humans. Usually he could be found skulking nearby or with API, the God of documentation.

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.

How do you pronounce API?

"demos" must be a typo of "deimos".

I think I may have found an issue with this. I tried to get directions, and it fell off a random road and then proceeded to have me swim across the San Francisco Bay:

- http://i.imgur.com/wWilOoC.png

Having worked in the routing space (not on this project) and reviewing the code, the implementation is professional-grade. Where as OSM data is rich and challenging to work with for routing purposes.

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

There doesn't seem to be any priority on freeways. I could route across the entire U.S. and never get on a freeway....

A quick question: I have a list of 100+ million points with their geographical distance, but I want to improve it and calculate the "driving distance". How expensive in terms of time/ops would that be?

I'm scanning the different subprojects on Github and I think Tyr is the one I need, but I'm not entirely sure..

Are you a salesman by any chance?

Nah just trying to write a paper with GIS data..

Nah. Ebay already solved that problem.

Obligatory: https://xkcd.com/399/

Heh, I liked it better when it was implied.

I assume you want to calculate the driving distance from the user's location. So you pick something like 20-50 nearest points (a very cheap and quick operation with a geo-spatial index) and then you will calculate the driving distance to each of them using something like Valhalla, which is much more expensive, but it scales linearly and can be parallelized.

So the 100+ million number is irrelevant.

The problem is I have 5MM "users" through several years and I want to compute their distance to a set of points that change through time, so I do care a lot about speed.

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.

How can computing geodesic distances be slow? Isn't it rather trivial math? I'm pretty sure 5 million of them can be calculated in a few seconds on my laptop. And it can be offloaded to the client.

Whereas route calculation can't be easily offloaded.

You sure can do this on your own machine. Have a look here for how to set this up on your own machine: https://github.com/valhalla/chef-valhalla/blob/master/README...

Thanks!!

With Contraction Hierarchies you can get several hundred routes (or distances) per second. If you want to calculate distance matrices you can get a lot faster.

Neat project.

There is also a Postgres/Postgis extension pgRouting (http://pgrouting.org/) that will do routing in the database.

Any plans to add public transport support?

Yes -- if you're at State of the Map US in NYC this weekend, we'll be demoing it live. Stay tuned.

Looking forward!

I think they already have. take a look at [0] and the reply.

[0] https://news.ycombinator.com/item?id=9663193

Does anyone know how good the OpenStreetMap data is? I thought I'd heard that it was pretty incomplete.

Try it for some routes you are familiar with:

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.

The address data is quite partial, which makes searching for locations more difficult.

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.

I've used OSMAnd on my phone and found it to be comparable to or better than a standalone Garmin unit, but nowhere as good as Google Maps. That's doing the route calculations on the phone itself using pre-downloaded data, and I'm not sure how much detail gets stripped in the packaging process. You can't search for a particular house number, for example. In some states and on some highways it'll tell you which lane you need to be in for the right exit ramp, but that level of detail seems to be pretty spotty.

Depends on the application. The developers that made Valhalla (Mapzen) recently hired my doctoral program office mate Indy Hurt to answer some aspects of that question. She's on Twitter at @indymapper. Elsewhere in academia, Muki Haklay has been studying the problem -- here's a link to one of his original papers that can provide a seed to find his more recent work: http://www.ucl.ac.uk/~ucfamha/OSM%20data%20analysis%20070808...

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.

Excuse me if this sounds irrelevant, but why name it after Nordic mythology?

WE SHALL RIDE THROUGH THE GATES OF VALHALLA, SHINY AND CHROME!

Oh what a website.. WHAT A LOVELY WEBSITE!