Routing: Under the Hood
The Routing API returns a path between two points in milliseconds, even for routes spanning thousands of kilometres. This page explains the data structures and algorithms that make that possible - so you can reason about why a route takes the shape it does and understand the trade-offs behind the tuning options.
From a map to a graph
Valhalla doesn't route on raw map data - it routes on a graph. During the data import step, every intersection in OpenStreetMap becomes a node, and every road segment between intersections becomes a directed edge. Each edge carries attributes extracted from OSM tags: speed limit, surface type, one-way direction, turn restrictions, access permissions (e.g. no trucks, no bicycles), and more.
This conversion step is non-trivial. A single OSM "way" (a line on the map) is split at every intersection into individual edges. Turn restrictions that span multiple ways become penalty annotations on node transitions. The result is a compact, queryable graph that can be traversed without ever touching the original map file again.
Three hierarchy levels
The graph is organised into three levels, each containing progressively more detail:
- Highway - motorways, trunks, and primary roads only
- Arterial - adds secondary and tertiary roads
- Local - every street, path, track, and footway
Each higher level also gets shortcut edges - pre-computed edges that skip over sequences of minor intersections and compress a chain of local-road hops into a single highway edge. This is the same concept as collapsing a sequence of motorway on-ramps and off-ramps into one straight-line shortcut.
A route climbs this hierarchy as it moves away from its endpoints and descends as it approaches them - mirroring how you'd plan a real drive: local streets to the arterial, arterial to the highway, highway to the destination's arterial, then local streets again.
Bidirectional A*
A* is a heuristic graph search that explores nodes in order of their estimated total cost (distance already travelled + estimate to destination). A single forward A* search from origin to destination works - but searches from both ends simultaneously is significantly more efficient: each frontier only needs to expand halfway before they meet, and the explored area grows as a fraction of what a one-directional search would cover.
Both frontiers respect the hierarchy: they expand local edges near their respective endpoints, climb to arterial, then highway - and the two searches typically meet somewhere on the highway level. The meeting point isn't simply the node where the frontiers overlap; Valhalla checks all candidate meeting nodes and picks the one with the minimum combined forward + backward cost.
Why long routes are hard: the search space problem
On a flat graph, the number of nodes a search must visit to find a path grows roughly with the square of the distance: double the trip, quadruple the work. A cross-continent route on the full local-road graph would require examining hundreds of millions of edges - far too slow for real-time use.
Valhalla addresses this with two complementary techniques: tiles (bounding memory) and hierarchy pruning (bounding computation).
Tile decomposition
Each hierarchy level is stored as a separate grid of geographic tiles. The tile sizes are deliberately unequal: highway tiles cover 4° of longitude/latitude, arterial 1°, local 0.25°. Nothing enters memory until the search frontier physically enters that tile - so a London-to-Moscow route might load 3 highway tiles for the entire middle section, a handful of arterial tiles for the approach roads, and a cluster of tiny local tiles around each city endpoint.
Hierarchy pruning
Once a search frontier has expanded far enough from its endpoint - past a configurable distance threshold - Valhalla stops relaxing local and arterial edges entirely. Only highway-level edges and shortcuts remain on the priority queue. This limits the explored search space to a thin corridor around the highway network rather than the full graph.
The trade-off is documented and honest: pruning can occasionally miss a marginally faster back-road route. You can disable it with disable_hierarchy_pruning: true in costing_options, which forces a full graph search for the true optimum - at a real speed cost. For bicycle and pedestrian costing, hierarchies are always disabled since those modes live entirely on the local level.
Edge scoring and the costing model
Neither "best" nor "fastest" is baked into the graph. Every edge is scored dynamically at request time by a costing model selected via the costing parameter. The model assigns a traversal cost to each edge based on its attributes - speed, surface, road class, access flags - and the user's preferences expressed through costing_options.
Three types of options:
- Cost - seconds added to both the traversal cost and the time estimate. Use for things that genuinely take time (gate crossing, border check).
- Penalty - seconds added only to cost, not to the time estimate. Use to steer the route away from something without overstating its duration (toll avoidance is the classic case).
- Factor - a multiplier on edge cost (0.1–100000). Below 1.0 favours that road type; above 1.0 avoids it. More predictable than penalties for long avoidances because the effect scales with road length.