Efficient and fast map matching with Valhalla

[Updated on 14.09.2022] [Updated on 04.07.2022]

The Valhalla (documentation, source code) is a fast, efficient, multimodal and open-source routing service that is being used by many mapping and routing giants. The engine provides an easy-to-use interface to use OpenStreetMap (OSM) data for routing purposes. Instead of talking about the routing engine, my focus is on map-matching which is one of the many APIs offered within the Valhalla.

Map matching

As the name suggest, map-matching is a process to associate geographical coordinates to a digital map (More info on Wikipedia). In this case, our task is to match the bicycle tracks data to the map. The map-matching API in Valhalla is called Meili. A great tutorial that focuses on Meili can be found here. In this post, my target is to document the entire process from setting up a Valhalla server to using it in Python.

1. As usual, the docker solution is the preferred one which avoids the installation of libraries on a local machine thereby providing an OS-independent solution. I found the docker image form gis-ops as a good starting point. If you are on Windows, then try using PowerShell, because git-bash behaves strangely with volume mounting.

2. Pull the prebuild docker image and start the server. In case, if we need to build from the source, then documentation is here.

   1. Pull the docker images from GitHub. For the same, you might need to login with your GitHub’s credentials.

     docker login docker.pkg.github.com
     docker pull docker.pkg.github.com/gis-ops/docker-valhalla/valhalla:latest
   

   1. We will mount the local folder to the drive. Therefore, create a folder called custom_files and download the OSM data from the generous server of geofabrik as:

         cd custom_files
         wget http://download.geofabrik.de/europe/germany/baden-wuerttemberg-latest.osm.pbf
   

   The above download part can be skipped and can be coupled directly during the docker run but for simplicity, I downloaded it here.

   1. Then, we can turn on the server for Valhalla. Below, we define a local volume to mount i.e. where we will provide the OSM extracts and this folder is linked to the docker server (-v option). Various options can be found here which can be passed to Docker via -e flag. In the following, I only use build_admins which will also create a database for the countries and states. Then, I also set serve_tiles as True which will first build the map tiles from the mounted $PWD\custom_files and then directly start serving. This is different compared to the older version of this docker image.

        docker run -dt -p 8002:8002 -v $PWD\custom_files:/custom_files/ -e serve_tiles=True  -e build_admins=True  docker.pkg.github.com/gis-ops/docker-valhalla/valhalla:latest 
   

   1. [Optional] In the above, we’ve used the -d option for the silent operation. So, during the trial phase, we can see the logs with standard docker commands. First, find the running container id and then follow its log.

        docker ps
        docker container logs -f <CONTAINER_ID_OBTAINED_FROM_ABOVE>
   

   1. For the downloaded ~500 MB OSM extract, it took around 30 minutes. Otherwise, you can start with smaller extracts, SSD drive is recommended for regular builds or larger file sizes. Once the graph build is finished, you will observe some output like INFO: Finished tarring 110 tiles to /custom_files/valhalla_tiles.tar. Thereby, you will also see a valhalla_tiles.tar file which has the optimized graph.

   2. Check the running container by docker ps, and you should be able to see the docker status and opened port which is 8002.

3. Now, we are good to go to use the server. To test whether the server is running:
   1. We could try http://localhost:8002/ in the browser. We should see "error_code":106. It indicates that the server is running but we did not pass any specific API address and we could see available end points.
   2. As a tar file is available due the map build process in custom_files folders, so we could query this data with the help of curl in our terminal.

    curl http://localhost:8002/route --data '{"locations":[{"lat":48.632608,"lon":9.010350,"type":"break"},{"lat":48.631776,"lon":9.011528,"type":"break"}],"costing":"auto","directions_options":{"units":"miles"}}' | jq '.'
   

4. We can take the inspiration from the already mentioned blog to automatize things in Python.

5. Finally, you can find a complete notebook alongside a sample gpx trace on my GitHub, which illustrates the map matching with figures. To use this, you need to start Valhalla’s server as mentioned above for the Baden-Wuerttemberg state in Germany because the attached GPX traces are from this state.

It is worth mentioning that default settings allow you to perform a map-matching to ~200 KM. To surpass this limit, you need to change the settings in valhalla.json in your custom_files folder and restart the docker.

How much time to build for entire planet?

The answer depends heavily on the underlying hardware one is using. On a system with 16 GB RAM and 1 TB of HDD hard disc, the process went on for more than 12 days and then ultimately I aborted the process. Building the tiles is a computationally expensive process, therefore, always use the SSD for large areas as it will make IO very fast and this appears to be a bottleneck in this operation. Additionally, keep around 600 GB of space, even though the final tar file will be of much less size. This is required because program write down many temporary files during the graph building process. This space requirement will grow significantly if you also want to have elevation tiles, as elevation only can take up to 1.6 TB of space. On a good system equipped with SSD, 8 cores and 16 GB of RAM, it took around 2.5 days. For entire 1 day, I can see 100% of CPU was used, so I assume that the build time can build down further if we use more cores. If you don’t have the resources, and then you can also buy the tiles, but it’s a bit expensive in my opinion because of the subscription model.

Reach out to me on Instagram for a faster reply!