/valhalla

Open Source Routing Engine for OpenStreetMap

Primary LanguageC++OtherNOASSERTION

 ██▒   █▓ ▄▄▄       ██▓     ██░ ██  ▄▄▄       ██▓     ██▓    ▄▄▄
▓██░   █▒▒████▄    ▓██▒    ▓██░ ██▒▒████▄    ▓██▒    ▓██▒   ▒████▄
 ▓██  █▒░▒██  ▀█▄  ▒██░    ▒██▀▀██░▒██  ▀█▄  ▒██░    ▒██░   ▒██  ▀█▄
  ▒██ █░░░██▄▄▄▄██ ▒██░    ░▓█ ░██ ░██▄▄▄▄██ ▒██░    ▒██░   ░██▄▄▄▄██
   ▒▀█░   ▓█   ▓██▒░██████▒░▓█▒░██▓ ▓█   ▓██▒░██████▒░██████▒▓█   ▓██▒
   ░ ▐░   ▒▒   ▓▒█░░ ▒░▓  ░ ▒ ░░▒░▒ ▒▒   ▓▒█░░ ▒░▓  ░░ ▒░▓  ░▒▒   ▓▒█░
   ░ ░░    ▒   ▒▒ ░░ ░ ▒  ░ ▒ ░▒░ ░  ▒   ▒▒ ░░ ░ ▒  ░░ ░ ▒  ░ ▒   ▒▒ ░
     ░░    ░   ▒     ░ ░    ░  ░░ ░  ░   ▒     ░ ░     ░ ░    ░   ▒
      ░        ░  ░    ░  ░ ░  ░  ░      ░  ░    ░  ░    ░  ░     ░  ░
     ░

Valhalla is an open source routing engine and accompanying libraries for use with OpenStreetMap data. Valhalla also includes tools like time+distance matrix computation, isochrones, elevation sampling, map matching and tour optimization (Travelling Salesman).

Build Status

Linux/MacOs Windows MinGW64 Code Coverage
Circle CI Build Status Valhalla MinGW Build codecov

License

Valhalla, and all of the projects under the Valhalla organization, use the MIT License. Avatar/logo by Jordan.

OpenStreetMap data in the ./test/data is licensed under ODbL and copyrighted by OSM contributors. Additional information on licenses and other requirements concerning the data sources most frequently used by Valhalla can be found in the docs.

Overview

There are several key features that we hope can differentiate the Valhalla project from other routing and network analysis engines. They are:

  • Open source software, on open source data with a very liberal license. Should allow for transparency in development, encourage contribution and community input, and foster use in other projects.
  • Tiled hierarchical data structure. Should allow users to have a small memory footprint on memory constrained devices, enable offline routing, provide a means for regional extracts and partial updates.
  • Dynamic, runtime costing of edges and vertices within the graph via a plugin architecture. Should allow for customization and alternate route generation.
  • C++ based API. Should allow for cross compilation of the various pieces to enable routing on offline portable devices.
  • A plugin based narrative and manoeuvre generation architecture. Should allow for generation that is customized either to the administrative area or to the target locale.
  • Multi-modal and time-based routes. Should allow for mixing auto, pedestrian, bike and public transportation in the same route or setting a time by which one must arrive at a location.

Demo Server

FOSSGIS e.V. hosts a demo server which is open to the public and includes a full planet graph with an open-source web app on https://valhalla.openstreetmap.de. The HTTP API is accessible on a slightly different subdomain, e.g. https://valhalla1.openstreetmap.de/isochrone. Usage of the demo server follows the usual fair-usage policy as OSRM & Nominatim demo servers (somewhat enforced by rate limits).

Platform Compatibility

Valhalla is fully functional on many Linux and Mac OS distributions, and is also used on iOS and Android devices.

For Windows, not all functionality is fully supported yet. Building the Valhalla library works flawlessly, as well as the following application modules:

  • TOOLS: utilities to query and benchmark various components
  • DATA_TOOLS: utilities to build input data and handle transit
  • PYTHON_BINDINGS: use all actions (route, isochrones, matrix etc) via the Valhalla Python library (needs a full (i.e. development) Python distribution in the PATH)

Organization

The Valhalla organization is comprised of several library modules each responsible for a different function. The layout of the various modules is as follows:

  • Midgard - Basic geographic and geometric algorithms for use in the various other projects.
  • Baldr - The base data structures for accessing and caching tiled route data.
  • Sif - Library used in costing of graph nodes and edges. This can be used as input to loki and thor.
  • Skadi - Library and service for accessing elevation data. This can be used as input to mjolnir or as a standalone service.
  • Mjolnir - Tools for turning open data into Valhalla graph tiles.
  • Loki - Library used to search graph tiles and correlate input locations to an entity within a tile. This correlated entity (edge or vertex) can be used as input to thor.
  • Meili - Library used to for map-matching.
  • Thor - Library used to generate a path through the graph tile hierarchy. This path and attribution along the path can be used as input to odin.
  • Odin - Library used to generate manoeuvres and narrative based on a path. This set of directions information can be used as input to tyr.
  • Tyr - Service used to handle http requests for a route communicating with all of the other valhalla APIs. The service will format output from odin and support json (and eventually protocol buffer) output.
  • Tools - A set command line tools that exercise bits of functionality from the library components above and provide the basis for quality testing and performance benchmarking.
  • Demos - A set of demos which allows interacting with the service and APIs.

Documentation

Documentation is stored in the docs/ folder in this GitHub repository. It can be viewed at valhalla.github.io/valhalla.

Installation

To run Valhalla locally or your own server, we recommend using our Docker image. Checkout our docker image here: https://github.com/orgs/valhalla/packages. Also, there's a community Docker image with more "magic" than the native one.

If you want to build Valhalla from source, follow the documentation.

For more information on binaries, see Command Line Tools section below and the docs.

Contributing

We ❤️ contributions to Valhalla. They could be non-technical, e.g. translations into other languages via Transifex or documentation improvements, or technical ones like bug fixes or feature implementations. It's important to open an issue before setting out to work on a PR.

Ideally, get familiar with our Contribution guidelines first.

Benchmarks

Valhalla includes several microbenchmarks which you can build and run using:

make benchmarks
make run-benchmarks

They are enabled by the -DENABLE_BENCHMARKS=On CMake flag and are currently only available for Linux and MacOS.

Command Line Tools

valhalla_service aka one-shot mode

If you can't (e.g. Windows Server) or don't want to have the full-fledged HTTP API running, you can have the (almost) exact same behavior with the 'valhalla_service' executable in so-called "one-shot" mode. It's simple, just pass the config file, the action (route, isochrone, matrix etc) and the stringified JSON request (or alternatively a file containing the request to circumvent shell command length issues):

valhalla_service valhalla.json isochrone '{"locations":[{"lat":42.552448,"lon":1.564865}],"costing":"auto","contours":[{"time":10,"color":"ff0000"}], "show_locations":true}'
# Alternatively you can pass a file with the same contents
valhalla_service valhalla.json isochrone isochrone_request.txt

It's important to note that all Valhalla logs for one-shot mode are piped to stderr while the actual JSON response will be in stdout. To completely silence the logs, pass type: "" to midgard.logging in the config file.

Batch Script Tool

Related projects

The following projects are open-source and built with the intention to make it easier to use Valhalla and its features:

  • OpenStreetMapSpeeds: A project conflating open GPS data to improve Valhalla's speed classification. The current JSON is from early 2022 and can be downloaded here and used by setting the path in the mjolnir.default_speeds_config config option.
  • docker-valhalla: An easy-to-use, relatively magical Docker image for Valhalla, which only requires setting a few environment variables in docker-compose.yml to get a full-featured Valhalla instance.
  • valhalla-operator: A k8s operator to deploy and manage Valhalla.
  • valhalla-app: A React based web app for Valhalla, powering https://valhalla.openstreetmap.de/.
  • valhalla-qgis-plugin: A QGIS plugin for Valhalla, also available in the official QGIS plugin store. Note, it's almost deprecated and will be replaced with a much superior alternative.
  • routingpy: A Python client for most open-source routing engines, including Valhalla, with a common interface for all engines. Available on PyPI.
  • routingjs: A TypeScript client for most open-source routing engines, including Valhalla, with a common interface for all engines. Available as engine-specific packages on npm.
  • pyvalhalla: Python bindings for Valhalla, so its APIs can be used from within Python without a HTTP service. Available on PyPI.
  • Valhalla_jll.jl: Valhalla binaries shipped for Julia.