3 ms·

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

by 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).
  - karussell 11y ago
    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).
    - glennon 11y ago
      @karussell, For a public source, Dennis Luxen updated his Linkedin profile. Thanks for adding your knowledge about the internals of Valhalla code.
      - karussell 11y ago
        ah, easy, thanks :) !
- karussell 11y ago
  How do you define best? I'm the author of GraphHopper. Easy to setup, fast and flexible. Try it here: https://graphhopper.com/maps/ https://graphhopper.com/maps/
  - glennon 11y ago
    +1 ...and open source under Apache License 2.0 :)
karussell 11y ago
> 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.
- glennon 11y ago
  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.

by glennon 11y ago

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).
- karussell 11y ago
  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).
  - glennon 11y ago
    @karussell, For a public source, Dennis Luxen updated his Linkedin profile. Thanks for adding your knowledge about the internals of Valhalla code.
    - karussell 11y ago
      ah, easy, thanks :) !
karussell 11y ago
How do you define best? I'm the author of GraphHopper. Easy to setup, fast and flexible. Try it here: https://graphhopper.com/maps/ https://graphhopper.com/maps/
- glennon 11y ago
  +1 ...and open source under Apache License 2.0 :)

karussell 11y ago

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

glennon 11y ago
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.