Making Valhalla Understand Monday Morning
The weekly profiles described here stayed an experiment and never became part of our production traffic data; later evaluations closed this line of work. Production routing uses a day speed and a night speed per road, computed in local road time with a 180-day freshness half-life, which the June post describes.
In our GPS data, German urban motorways run at 84% of their weekly average speed between seven and eight on Monday morning, and at 113% at the same hour on Sunday. This is the week of that road group: the faint line is every five-minute slot, the solid one the average over an hour.
Hover over the week to read it. The is slow too. Other groups have other weeks: lose speed for the whole working day.
Valhalla can take a curve like this for every edge of its graph and use it when a route has a departure time. In May we tried to give it one from our own GPS data. This post is about how much of such a curve the data could support.
What Valhalla takes
For predicted traffic, Valhalla reads up to three things per directed edge from a CSV file. The free-flow speed is used at night, between 19:00 and 07:00 local time. The constrained-flow speed is used during the day. The third, optional field is a whole week of speeds: 2,016 five-minute slots, compressed into 200 coefficients of a discrete cosine transform.
Before this work we already exported the first two for the whole drivable graph, 41,231,017 directed edges: a day speed and a night speed for every road, computed from matched GPS traces.
Five observations per road
We have more than a billion matched GPS observations, but most roads see only a handful of them. A weekly curve has 2,016 numbers. Learn 2,016 numbers from five measurements and the result looks detailed and is noise, and a router that trusts it sends drivers around congestion that does not exist.
So the day and night speeds are deliberately plain. Each road starts from its own medians, and where it has few observations, they are pulled toward the typical speed of its road class in its country. A road with plenty of data keeps its own speeds; a road with little data mostly gets the speeds of roads like it.
Three models we shelved
The first attempts looked for rush-hour intervals inside the day of each road. A fixed ladder of one-hour and three-hour intervals was robust and easy to read, but congestion does not start on the hour. An adaptive tree searched for the splits in the data itself and looked very good on the observations it was fitted on. On held-out dates it fell apart: as we gave the test more observations per road, the error of the plain day-and-night model on the same roads fell from 3.8 to 0.5 km/h, and the tree's grew from 3.7 to 5.4 km/h. A model built for fast-slow-fast days won on the roads it selected and lost by 0.8 to 1.0 km/h on held-out data.
What stayed from those weeks is the test bench. Every model is fitted on some dates and scored on others, and every result is compared with the same model trained on shuffled timestamps: if a model does as well when the time of day is random, its curve is not about the time of day.
Borrowing the shape
The model that passed did not learn a curve per road. Roads are grouped into cohorts by country, road class and density zone, rural, suburban or urban, and each cohort gets one weekly template, the typical shape of its well-observed roads, normalized to a mean of 1. The curves in the first figure are such templates.
A road keeps its own level and takes the shape from its cohort, in proportion to how much it has been observed:
profile[slot] = scalar[slot] × (1 + strength × (template[slot] − 1))
strength = support / (support + 20)
support = occupied slots × distinct dates / 2016
Here scalar is the road's own day speed from 07:00 to 19:00 and night speed otherwise. This is one real road, a
suburban motorway in Germany with a night speed of 112 km/h and a day speed of 105:
Its observations give it a support of 37 and a strength of 0.65. the profile is the dashed day-and-night step; it follows the template almost completely. Roads whose strength stayed below 0.1 got no profile at all and kept the two plain speeds.
200 coefficients
Valhalla does not store the 2,016 speeds. It stores the first 200 coefficients of their discrete cosine transform as 16-bit integers, 400 bytes per edge, and rebuilds the speed of a slot from them when a route asks for it. That keeps the slow changes of the week and drops the fast ones:
With 200 coefficients this road comes back with a mean difference of 1.28 km/h. The largest differences are at the sharp steps of the curve, where the transform rings. keep only the days. Over all 86,466 profiles we built, the mean round-trip error was 0.69 km/h.
Only the decoded profile ever reaches the router, so every score was computed after this round trip. The roads that got a profile were the 86,466 best observed ones in Germany, the Netherlands, Switzerland, Ukraine and the United States, 0.21% of the graph. On held-out dates the decoded profile beat the plain day and night speeds on 63.4% of them. Trained on shuffled timestamps, the same model won on 48.4%, so about fifteen points of that are the time of week. And the codec was not the limit: the measured weekly curve of each road, pushed through the same 200 coefficients, beat the plain speeds on 88.9% of the roads.
On real routes
A model that wins edge by edge can still make routes worse, so we built 132 test routes: motorway corridors, city crossings, service roads, roads with known large errors. Each was routed twice through Valhalla, once with the day and night speeds only and once with the weekly profiles added, at five times of the week:
On Monday at 08:00, 94 of the 100 routes that cross profiled edges got slower, by 2.0% at the median, on top of day speeds that already contain the average day. No route changed its time by more than 8%, and 12 of the 132 took a different path.
Writing this up in October, we found a detail the route test could not show. Our pipeline numbers the slots of the week from Monday 00:00, and Valhalla reads them from Sunday 00:00. So in these tiles every day used the curve of the next one: Monday morning got Tuesday's morning, and Friday at 17:00 got Saturday's. That is probably why the Friday row is almost neutral, at an hour the templates above show as slow. Weekday mornings look alike, so the Monday result holds, but any future weekly profile has to be shifted by a day before it is encoded.
To try the routing stack, create an API key. To discuss a Valhalla deployment, write to [email protected].