Published in

Traffic in Valhalla

Real-Time and Historical Traffic in Valhalla

Apart from its numerous unique features, Valhalla, as the only FOSS routing engine, also has fully integrated support for traffic data:

  • live traffic: Integrate a live traffic feed from e.g. TomTom or HERE in your Valhalla routing engine instance, for optimal ETA calculation in shorter routes
  • historical traffic: Valhalla supports up to 5 mins intervals of historical traffic data from e.g. TomTom or HERE, for optimal ETA calculation on short and long routes

Ideally, Valhalla is operated with both traffic signatures. Internally, live traffic is mostly used in close proximity to the route’s origin point and its influence deteriorates linearly moving away from the origin. Meanwhile other speed data sources such as historical traffic data will be blended into the routing calculations at the same rate the impact of live traffic lessens. If in a pinch, for most use cases historical traffic data is far more valuable than real-time traffic data.

Note, that not all actions/endpoints support traffic-/time-aware calculations. While /route and /isochrones support traffic, /sources_to_targets (aka /matrix) does not.

Purchasing appropriate data is less expensive than most people assume. In the case of an asset-based TomTom contract (e.g. for fleet management, where each vehicle is an asset), costs are within a few Euro per asset per year. It’s a very valuable investment if ETA accuracy is of essence.

Showcases

We created two animations to showcase the impact traffic information has on routing.

The following video shows a time series of 500 routes which are requested every 15 minutes of the week. Increasing ETAs are obvious from 8:00 am to 7:00 pm:


A more impressive video shows a time series of 5 isochrones, also in 15 mins intervals over the whole week:


Traffic implementation in Valhalla

You might be asking, why other FOSS routing engines don’t support a traffic implementation. The reason is: it’s tough business.

Consider what happens on a route from e.g. Berlin to Munich: as the routing algorithm tracks its way towards Munich, time passes and that needs to be accounted for in order to properly respect time-dependent speeds or restrictions (such as “no access between 9am – 5pm”) with all its complexities, such as timezones.

So for true traffic support, a routing engine must be able to track the time along the routing algorithm’s expansion. That requires more flexible algorithms which lack a lot of the performance goodies one typically likes to see in a routing engine, such as conventional Contraction Hierarchies.

Below we describe some of the internals of Valhalla’s traffic implementations. If you need help or support, contact us at .

Historical traffic data

Valhalla supports loading each edge (aka road segment) with a total of 2016 time-dependent speed values, which corresponds to a full week’s worth of 5 mins intervals. It’s the quasi-standard of commercial traffic data.

This kind of traffic data source needs the same base street network as the traffic data it’s originating from. In practice: if you consider buying TomTom historical traffic data, you’d need the TomTom MultiNet street network data to build a Valhalla routing graph first. We provide services & software to convert TomTom & HERE data to make it usable with FOSS routing engines such as Valhalla.

Once you have a routing graph built, you need to transform the historical traffic data into Valhalla’s expected CSV format with the following columns:

edge_id freeflow speed constrained speed variable speeds
0/3196/0 45 35 BbwACv/mAA//8gAK//kA

The first column is simply the internal GraphId. A mapping of “OSM” IDs (aka TomTom/HERE IDs) to internal GraphIds can be generated with the tool valhalla_ways_to_edges. The second and third column are the freeflow (night time) and constrained (day time) speeds. The tricky part is the last column: it’s a DCT-II compressed version of the 2016 variable speed values. There is an implementation for compression and decompression in the Valhalla repository as well.

Once the CSV traffic “tiles” have been generated, you can load the historical data on top of the routing graph with Valhalla’s valhalla_add_predicted_traffic tool.

Live traffic data

While historical traffic data is still somewhat easy, since you only have to generate the traffic “tiles” once, real-time traffic integration is a lot more involved. Typically data providers offer a feed which updates minutely for every supported region of the world. If the graph covers an entire continent such as Europe, that feed will contain speed updates for millions of edges.

Valhalla implements live traffic via a memory mapped tar archive. The internal directory tree is the exact same as for the routing tiles. A single traffic tile consists of:

  • tile header with info about tile ID, edge count, tile version etc
  • 64 bit integer for every edge in the corresponding routing tile, which consolidates info on segmented speeds and congestion on this edge

The valhalla_build_extract tool will produce a blank skeleton of a traffic.tar with the -t option. The path to this archive should be stored in Valhalla’s configuration file at mjolnir.traffic_extract. Whenever one of the 64 bit integers in the traffic archive changes, the Valhalla server will realize it and take into account the new value(s).

The challenge is to actually develop that external application (in whatever language) to update the traffic archive, and that is performant and accurate enough to provide meaningful traffic updates on large regions. The gist of it is:

  • pull updated traffic information from provider
  • match each traffic segment’s OpenLR(/TMC) geometry string to Valhalla’s graph using /trace_attributes to retrieve all edges’ GraphIds. Beware that the traffic provider’s geometries might not be the same as your routing graph’s geometries, e.g. TomTom live traffic feed on a OSM routing graph, so you might have to do a more complex flow of /locate, /route and /trace_attributes to reliably match the provider’s geometries to your graph
  • once you have the Valhalla representation of a OpenLR traffic entry, you can start matching the entry’s speeds to the graph edges to compose the TrafficSpeed struct for each edge; breakpoints only come into play for start & end edges of OpenLR records
  • after you did this process for all traffic entries, you should have one TrafficSpeed 64 bit integer for each Valhalla edge which matched to the current traffic input
  • at this point you still need to match those shortcuts whose edges had their speeds updated: Valhalla uses shortcuts in its more performant bidirectional algorithm on longer routes; here you need to calculate the weighted average of all underlying edge speeds and only set the overall_encoded_speed part of the shortcut’s TrafficSpeed packed 64 bit struct
  • finally you have completed a traffic update and you can now write these entries into the existing traffic archive which is shared with the Valhalla server

This is only a brief summary of the high-level steps which need to be taken. There’s a lot more details to be said about the whole process. The most important part is: don’t use HTTP when matching OpenLR to Valhalla’s graph! That’s much too slow. Either develop the application in C++, in Python (and use our pyvalhalla bindings) or develop bindings in your favorite language (and of course open-source them! ;)).

Related projects

We maintain a multitude of related projects, most of which are open-source:

  • pyvalhalla: High-level Python bindings to the C++ Valhalla library.
  • Valhalla QGIS Plugin: A fairly simple QGIS Plugin to request routes, isochrones & matrices from a Valhalla HTTP server, complete with batch support via Processing algorithms.
  • Valhalla Docker: A user-friendly docker image to start a Valhalla container to build and serve routing graphs for routing, isochrones, matrices etc.
  • routingpy: Python library to requesting from a multitude of providers (e.g. Mapbox, Vahlhalla, Google Maps etc.) with a common interface. All provider interfaces in routing-py require the same arguments so it’s very trivial to switch providers.
  • GIS tutorials: Regularly updated tutorials on geospatial topics covering many routing problems, QGIS Plugin developement, PostgreSQL/PostGIS/pgrouting and many more. They’re open-source so the community has a chance to propose fixes or point out problems/mistakes.
  • prop2osm: We can help you convert any proprietary road dataset to the OpenStreetMap format so open-source routing engines like Valhalla & OSRM can build graphs from your proprietary data. By default we support TomTom & HERE, but adding other sources is fairly trivial. The software can be licensed or we convert data for you as a service including proper quality control.