12 ms·

Show HN: Valhalla, an open source routing engine

147 points by sevko 11y ago

jastoltz24 11y ago
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?
- Zikes 11y ago
  "demos" must be a typo of "deimos".
- hnyc 11y ago
  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.
  - pki 11y ago
    How do you pronounce API?
sevko 11y ago
Also, source code is here: https://github.com/valhalla https://github.com/valhalla
- davexunit 11y ago
  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.
  - glennon 11y ago
    Glancing at the Valhalla repos, it looks like the MIT license across the board: https://github.com/valhalla https://github.com/valhalla ; https://github.com/valhalla/thor/blob/master/COPYING https://github.com/valhalla/thor/blob/master/COPYING ; https://github.com/valhalla/chef-valhalla/blob/master/LICENSE.md 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.
    - ma2rten 11y ago
      what are the best ones?
      - glennon 11y ago
        For speedy street routing, the Open Source Routing Machine: http://project-osrm.org/ 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 http://wiki.openstreetmap.org/wiki/Routing and OpenTripPlanner https://github.com/opentripplanner/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_dipl.pdf 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.pdf&can=2&q= 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 http://en.wikipedia.org/wiki/List_of_optimization_software I'm partial to Google's OR Tools https://github.com/google/or-tools https://github.com/google/or-tools (Apache License).
deleted 11y ago
[deleted]
- sevko 11y ago
  Source code is here: https://github.com/valhalla https://github.com/valhalla
  - th0br0 11y ago
    Whoops, looks like you responded just after I deleted my comment having seen your other. Thanks! Was searching for that link without success. It's awesome that they wrote most in C++ though!
synaesthesisx 11y ago
WE SHALL RIDE THROUGH THE GATES OF VALHALLA, SHINY AND CHROME!
- mozumder 11y ago
  Oh what a website.. WHAT A LOVELY WEBSITE!
juliangoldsmith 11y ago
Does anyone know how good the OpenStreetMap data is? I thought I'd heard that it was pretty incomplete.
- maxerickson 11y ago
  Try it for some routes you are familiar with: http://www.openstreetmap.org/directions?engine=osrm_car&route=25.774%2C-80.194%3B42.440%2C-76.497#map=5/34.615/-79.080 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.
- wtallis 11y ago
  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.
- glennon 11y ago
  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_web.pdf 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/ 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.
jakobdabo 11y ago
How does this compare to Project OSRM [1]? [1] https://github.com/Project-OSRM/osrm-backend https://github.com/Project-OSRM/osrm-backend
- alpensiedler 11y ago
  this blog post explains some of the major differences in the two architectures: https://mapzen.com/blog/valhalla-why_tiles https://mapzen.com/blog/valhalla-why_tiles
  - glennon 11y ago
    The OSRM routing engine appears to focus on contraction hierarchies; is that also the case for Valhalla? http://en.wikipedia.org/wiki/Contraction_hierarchies http://en.wikipedia.org/wiki/Contraction_hierarchies
davexunit 11y ago
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.
- randyme 11y ago
  There is no proprietary component, if you want to self-host it's all here: https://github.com/valhalla https://github.com/valhalla But there is a free hosted service (with API signup) for convenience.
  - davexunit 11y ago
    Awesome. Thanks for clarifying.
- alpensiedler 11y ago
  its all you need to self host. check out the chef repository. it should be all you need to throw it up on aws
dmitrykoval 11y ago
Any plans to add public transport support?
- randyme 11y ago
  Yes -- if you're at State of the Map US in NYC this weekend, we'll be demoing it live. Stay tuned.
  - dmitrykoval 11y ago
    Looking forward!
- psykovsky 11y ago
  I think they already have. take a look at [0] and the reply. [0] https://news.ycombinator.com/item?id=9663193 https://news.ycombinator.com/item?id=9663193
zzleeper 11y ago
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..
- magila 11y ago
  Are you a salesman by any chance?
  - Dewie3 11y ago
    Nah. Ebay already solved that problem.
    - hnyc 11y ago
      Obligatory: https://xkcd.com/399/ https://xkcd.com/399/
      - Dewie3 11y ago
        Heh, I liked it better when it was implied.
  - zzleeper 11y ago
    Nah just trying to write a paper with GIS data..
- alpensiedler 11y ago
  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.md#building-and-running https://github.com/valhalla/chef-valhalla/blob/master/README...
  - zzleeper 11y ago
    Thanks!!
bebop 11y ago
Neat project. There is also a Postgres/Postgis extension pgRouting (http://pgrouting.org/ http://pgrouting.org/) that will do routing in the database.
TheSwordsman 11y ago
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 http://i.imgur.com/wWilOoC.png
- winddog001 11y ago
  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/37.7862/-122.3625 http://www.openstreetmap.org/search?query=SF%2C%20CA#map=13/...
andrewguenther 11y ago
There doesn't seem to be any priority on freeways. I could route across the entire U.S. and never get on a freeway....
coolandsmartrr 11y ago
Excuse me if this sounds irrelevant, but why name it after Nordic mythology?

147 points by sevko 11y ago

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?

Zikes 11y ago
"demos" must be a typo of "deimos".
hnyc 11y ago
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.
- pki 11y ago
  How do you pronounce API?

sevko 11y ago

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

davexunit 11y ago
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.
- glennon 11y ago
  Glancing at the Valhalla repos, it looks like the MIT license across the board: https://github.com/valhalla https://github.com/valhalla ; https://github.com/valhalla/thor/blob/master/COPYING https://github.com/valhalla/thor/blob/master/COPYING ; https://github.com/valhalla/chef-valhalla/blob/master/LICENSE.md 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.
  - ma2rten 11y ago
    what are the best ones?
    - glennon 11y ago
      For speedy street routing, the Open Source Routing Machine: http://project-osrm.org/ 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 http://wiki.openstreetmap.org/wiki/Routing and OpenTripPlanner https://github.com/opentripplanner/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_dipl.pdf 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.pdf&can=2&q= 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 http://en.wikipedia.org/wiki/List_of_optimization_software I'm partial to Google's OR Tools https://github.com/google/or-tools https://github.com/google/or-tools (Apache License).

deleted 11y ago

[deleted]

sevko 11y ago
Source code is here: https://github.com/valhalla https://github.com/valhalla
- th0br0 11y ago
  Whoops, looks like you responded just after I deleted my comment having seen your other. Thanks! Was searching for that link without success. It's awesome that they wrote most in C++ though!

synaesthesisx 11y ago

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

mozumder 11y ago
Oh what a website.. WHAT A LOVELY WEBSITE!

juliangoldsmith 11y ago

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

maxerickson 11y ago
Try it for some routes you are familiar with: http://www.openstreetmap.org/directions?engine=osrm_car&route=25.774%2C-80.194%3B42.440%2C-76.497#map=5/34.615/-79.080 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.
wtallis 11y ago
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.
glennon 11y ago
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_web.pdf 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/ 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.

jakobdabo 11y ago

How does this compare to Project OSRM [1]? [1] https://github.com/Project-OSRM/osrm-backend https://github.com/Project-OSRM/osrm-backend

alpensiedler 11y ago
this blog post explains some of the major differences in the two architectures: https://mapzen.com/blog/valhalla-why_tiles https://mapzen.com/blog/valhalla-why_tiles
- glennon 11y ago
  The OSRM routing engine appears to focus on contraction hierarchies; is that also the case for Valhalla? http://en.wikipedia.org/wiki/Contraction_hierarchies http://en.wikipedia.org/wiki/Contraction_hierarchies

davexunit 11y ago

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.

randyme 11y ago
There is no proprietary component, if you want to self-host it's all here: https://github.com/valhalla https://github.com/valhalla But there is a free hosted service (with API signup) for convenience.
- davexunit 11y ago
  Awesome. Thanks for clarifying.
alpensiedler 11y ago
its all you need to self host. check out the chef repository. it should be all you need to throw it up on aws

dmitrykoval 11y ago

Any plans to add public transport support?

randyme 11y ago
Yes -- if you're at State of the Map US in NYC this weekend, we'll be demoing it live. Stay tuned.
- dmitrykoval 11y ago
  Looking forward!
psykovsky 11y ago
I think they already have. take a look at [0] and the reply. [0] https://news.ycombinator.com/item?id=9663193 https://news.ycombinator.com/item?id=9663193

zzleeper 11y ago

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

magila 11y ago
Are you a salesman by any chance?
- Dewie3 11y ago
  Nah. Ebay already solved that problem.
  - hnyc 11y ago
    Obligatory: https://xkcd.com/399/ https://xkcd.com/399/
    - Dewie3 11y ago
      Heh, I liked it better when it was implied.
- zzleeper 11y ago
  Nah just trying to write a paper with GIS data..
alpensiedler 11y ago
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.md#building-and-running https://github.com/valhalla/chef-valhalla/blob/master/README...
- zzleeper 11y ago
  Thanks!!

bebop 11y ago

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

TheSwordsman 11y ago

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 http://i.imgur.com/wWilOoC.png

winddog001 11y ago
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/37.7862/-122.3625 http://www.openstreetmap.org/search?query=SF%2C%20CA#map=13/...

andrewguenther 11y ago

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

coolandsmartrr 11y ago

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