Route planning on road graphs

Exact, and seconds too slow

Ask a navigation app for the fastest way from a farmhouse outside Lyon to a hotel in Turin and the answer comes back in well under a second: a little over three hours, through the Fréjus tunnel, every turn listed. The algorithm in every textbook finds the same route exactly, and on a road network the size of Western Europe it needs seconds to do it. A maps service answering hundreds of thousands of route requests a second cannot spend seconds on each; closing that gap is what route planning is about.

Junctions, segments and minutes

To a routing engine the road network is a graph: each junction is a node, each stretch of road between two junctions is an edge, and each edge carries a weight, the cost of driving it. For the fastest route the weight is travel time, the segment's length divided by the speed cars actually make on it, so two kilometres of motorway weigh about a minute and the same two kilometres through a village centre several. Edges are directed: a one-way street is an edge in one direction only, and the two carriageways of a motorway are separate edges, each with its own speed. A banned left turn belongs to a pair of segments rather than to either one, so a common model gives every permitted turn an edge, and a cost, of its own.

Research benchmarks model Western Europe's roads as roughly 18 million junctions and 42 million directed segments.

Dijkstra searches in every direction

Dijkstra's algorithm grows outwards from the start. It keeps a priority queue of junctions ordered by the best time found so far to reach each one, repeatedly takes the closest, fixes that time as final, and updates the junction's neighbours. When the destination comes off the queue, its time is the answer, and walking back through the junction each one was reached from gives the route. With travel times that are never negative, the answer is exact.

The cost is in that order. Before Turin comes off the queue, every junction the farmhouse can reach in less than three hours has come off first, in every direction: Geneva, Dijon, Clermont-Ferrand, none of them on the way. On a continental graph that is millions of junctions, and seconds of work, for one long query.

Aiming at the destination

The first idea is to aim. A-star (A*) orders the queue by the time taken to reach a junction plus an estimate of the time still left from there to the destination, so junctions in the direction of Turin tend to come off before the ones behind the farmhouse. The estimate must never exceed the true remaining time; an estimate that can overshoot lets A* return a slower route.

With travel-time weights, the safe estimate is weak. The straight-line distance to Turin divided by the fastest speed on any road never overshoots, but most roads are far slower than a motorway, so the estimate sits well below the real time and the search spreads almost as wide as Dijkstra's.

Shortcuts computed ahead of time

What closes the gap is to move most of the work out of the query. Most junctions are minor: the lane to the farmhouse, a crossroads in a village. A long route spends nearly all of its time on a small set of important roads, and contraction hierarchies build that observation into the graph before any query arrives:

1. Preprocessing ranks every junction by importance, minor ones first.
2. It removes the least important junction, B, and checks, for each pair of its neighbours A and C, whether the fastest way from A to C went through B.
3. If it did, it adds a shortcut edge from A to C, weighing the two segments' times added together, and records that the shortcut stands for A, B, C. If another road is just as fast, no shortcut is needed.
4. It moves on to the next junction in the ranking, until every junction has been removed and ranked. Removal only orders the work: queries run on every original segment plus every shortcut, each junction labelled with its rank.

A query then runs two searches, one forward from the farmhouse and one backward from the hotel, and each follows only edges that lead to a more important junction. Both climb onto the main roads within a few steps and meet near the top of the ranking, where the best meeting point gives the fastest time. On a continental graph that settles hundreds of junctions instead of millions and answers in well under a millisecond. Unpacking each shortcut into the segments it stands for, recursively, turns the answer back into a list of roads, and turn-by-turn directions are read from that list.

The price is paid up front: minutes of computation for a continent, extra edges, and the whole structure held in memory on every query server. That is also why a routing engine at continental scale usually loads a purpose-built structure from files instead of querying a general-purpose graph database: the structure is chosen for that latency. Storing and querying relationships is the subject of Graph databases.

When traffic changes the weights

A shortcut's weight is a sum of segment times. When a crash turns the approach to the Fréjus tunnel into a 40-minute queue, every shortcut containing those segments carries the wrong time, and the decision about which shortcuts exist at all was taken under the old times. Rerunning the whole preprocessing for every change in traffic costs minutes each time, and traffic never stops changing.

Many engines built for live traffic split the preprocessing in two. The slow part picks the shortcuts from the shape of the network alone, which roads meet where, so they stay valid whatever the times, and runs again only when the map itself changes. A fast customization step then recomputes the shortcut weights from the current segment times, quickly enough to run every few minutes, and the query servers swap in the new weights. Customizable contraction hierarchies and Customizable Route Planning are published designs of this kind; what a given maps provider runs is usually not public.

The segment times come from phones and cars reporting their speed: a write firehose (High-write ingestion) turned into a time per segment over short windows (Stream processing: windows, watermarks & state).

The same weights make the route's ETA: its segment and turn times added up, so every error in them lands in the arrival time. A segment time measured now describes the road now: the tunnel queue may be gone by the time the car gets there, two hours later, and the Turin ring road may be full by then. Routing on time-dependent weights, a predicted time for each segment at each time of day, answers that better. Predicting ETAs with a learned model brings a serving problem of its own, covered in Model serving: inference, versions & safe rollout.

From a GPS point to a road

The search starts and ends at junctions; the app sends two coordinates. Snapping finds the road segment nearest each coordinate, which is a proximity query over segments (Geospatial indexing & proximity search covers finding what is near), and joins each point to that segment's ends, with the time along the part between them: from the start to the ends the car may drive toward, and to the destination from the ends it may arrive by, only one in each case on a one-way street. The nearest segment is not always the right one: a phone on a motorway can snap to the bridge above it, a car on the southbound carriageway to the northbound one, and the heading, speed and class of road break those ties. If the engine may not use the farmhouse's private track, the farmhouse snaps to the nearest road the engine may use, not always the one the track comes out on, and the route starts there.

Drawing it on the Grid

The Maps & Route Planning Challenge asks for this system at hundreds of thousands of routes a second: draw the query path apart from the weight path, a route service holding the preprocessed graph in memory behind the gateway and a pipeline from speed reports to fresh weights. Then label how often new weights reach the route servers, and what an ETA ignores between two updates.