Teaching Valhalla That Hiking Is Not Flat
From Morskie Oko, the lake under the highest peaks of the Polish Tatras, a trail climbs to Czarny Staw pod Rysami, the next lake up. It is 500 metres long and rises 180 metres. The time written for it is 30 minutes up and 20 minutes down. At Valhalla's default walking speed of 5.1 km/h, the distance alone takes six minutes.
Our routing runs on Valhalla, and its tiles already store the elevation along every edge. In June we tried to turn that elevation into hiking times that agree with the times people walk by. Here is what we compared against, the models we tried on the way, and the curve that went into the tiles.
Times to compare against
In Lesser Poland, many hiking relations in OpenStreetMap carry a walking time for each direction, and the two often differ: uphill and downhill are different walks. After cleaning, we had 115 relations, 230 timed directions. We split them into 80 relations for tuning and 35 for checking by a hash of the relation ID, so that the split never changes between runs.
Switzerland has the most systematic times we know of. The signpost times there are computed by software from a formula Stephan Weber derived in the 1980s, used officially since 2006: the time is the horizontal length multiplied by a polynomial of degree 15 in the slope. The constants are not published. The signage handbook says the times assume 4.2 km/h on the flat without breaks, and that sections steeper than 40% are timed by walking them. In OpenStreetMap we found 241 Swiss relations with times for both directions, and 295 timed directions matched the routing graph exactly.
Later we added a third set from the Italian Alps, with many short, steep and difficult routes, to see whether a model fitted on the first two had learned hiking or only local habits.
Every prediction was made on the relation's own geometry. Routing between the end points of a relation was useful for testing the service, but some of those routes were more than four times longer than the trail itself.
Ascent and descent
The first model was the one most people write first: time on the flat plus time for every metre climbed and every metre descended. Tuned on the Polish trails, at 4.6 km/h on the flat, 375 metres an hour up and 600 metres an hour down, it missed the Polish times by 6.9 minutes on average.
On the Swiss trails it missed by 32.6 minutes, and almost always in the same direction: it gave Swiss trails half an hour more than their signs. Valhalla's original timing was wrong by about as much the other way, 27 minutes too fast.
Counting metres up and down throws away where they are. A steady climb and a staircase of steep steps with flat bits between them add up to the same ascent; so do a gentle downhill, which is fast, and a steep one, which is slow. Noise in the elevation data adds small ups and downs that were never walked.
We also tried the difficulty grade that OpenStreetMap puts on mountain paths, sac_scale. It helped only on the
highest alpine grades and fitted the tuning trails better than it predicted the others; some Swiss routes with high
grades were already too slow before any penalty.
Time as a function of slope
Waldo Tobler's hiking function from 1993 gives the walking speed directly from the slope: 6 km/h at a slight downhill of 5%, slower in both directions. Applied to the net climb of a whole route, it ignores everything between the ends and missed by 24 minutes in Poland and 60 in Switzerland. Applied along the elevation profile it did better, but it is too fast for real trails. With its parameters , the same shape missed by 10.4 minutes there and by 9.3 in Poland; , by 6.9 in Poland and 21.8 in Switzerland.
A slope function was clearly the right kind of model, and the exact shape still mattered. Polynomials of the Swiss kind, fitted to the Swiss trails, did best of all; a blend of a degree-5 and a degree-6 polynomial had the lowest error over all three sets. But a polynomial of that degree can do anything just outside the slopes it was fitted on, and nobody can say from its coefficients what it will do there.
So we fitted a curve given by eight points instead: seconds per kilometre at −40, −20, −8, −5, +3, +8, +20 and +40%, straight lines between them, and constant beyond ±40%, the slopes the Swiss handbook also leaves to people who walk them. The route is cut into pieces of 150 metres, and each piece takes the time the curve gives for its slope:
The fastest walking on the curve is at a 5% descent, 14.7 minutes per kilometre. Below that it slows down again: at −40% a kilometre takes 42 minutes. Uphill it slows all the way, and at +40% it climbs about 350 metres an hour. is faster at every slope on the chart.
On the clean check trails of all three sets, 250 timed directions, the polynomial blend missed by 7.532 minutes on average and the curve by 7.578. We gave up 0.046 minutes, about three seconds per trail, for a curve we can read, bound and explain when a route is wrong. In percent of the trail time the curve was a little better, 13.1% against 13.3%.
On real trails
Here is the curve on the trail from the beginning, cut into the pieces it times:
Up to Czarny Staw it gives 30 minutes, as the sign does, and 18 minutes against 20. On the , which barely changes height, and on , it is within a few minutes in both directions.
the sign says 3 hours 20 minutes and the curve 1 hour 57. The upper part of that trail is a scramble with chains, and the slope of the ground says nothing about that. The largest misses in Poland are all of this kind, technical Tatra routes with the highest difficulty grades.
Some misses are not the model's at all. A quality check flagged trails whose source data disagreed with itself, and
on those every model missed by around half an hour. One Swiss relation had the bare number 334 as its time: as
minutes that is 5 hours 34, but it may have been meant as 3:34. Others had a total ascent in the source that the
elevation profile could not reproduce.
Inside each edge
While we searched for the model, it ran in a research hook that rewrote the time of a finished route: it took the elevation of the whole path and cut it into 150-metre pieces from the start. That cannot choose a route. Valhalla chooses routes by the costs of single directed edges, so the time has to add up edge by edge.
So the pieces start again at the beginning of every edge, and the last piece of an edge is shorter. The ticks under the profile above are the edge boundaries. We checked whether the restart changes the predictions:
, the error on the 154 clean check trails in Poland and Switzerland went from 8.74 to 8.36 minutes. Most of the change is in Switzerland, where the restarts make the predictions a little slower and the curve was a little fast. The largest single change was on a 40 km Swiss route, 34 minutes slower. The Italian set is not in this check, because it was built without a routing service that reports edge boundaries.
In the tiles
Since the time of an edge depends only on the edge, it can be computed once, when the tiles are built. The elevation step of the tile build cuts every edge into its pieces and stores the seconds for each direction separately: the two directions of a trail are different walks.
The seconds go into the extended directed-edge block that Valhalla tiles already have for extra attributes, so the
base DirectedEdge layout does not change. They take 16 bits, plus one bit that says the value is there; the rest of
the block stays reserved. 16 bits hold 65,535 seconds, more than 18 hours on one edge. If the build ever computes more,
it stores nothing for that edge and logs a warning with the way ID, so the edge can be looked at. Ferries, transit connections, shortcuts and
edges closed to pedestrians get no value.
Old code reads the new tiles, because the edge layout it knows is unchanged. New code reads old tiles, because an
edge without the value falls back to Valhalla's previous pedestrian formula. The model applies only to pedestrian
requests with type=hiking, where the stored seconds replace the slope and difficulty factors in the edge time.
Ordinary walking, wheelchair and blind pedestrian routes do not change.
To try the hiking profile, create an API key. For questions about Valhalla navigation tiles or custom routing deployments, write to [email protected].