Design a maps routing service

Junctions are nodes. Each road segment is a one-way edge with a weight, the travel time. The shortest route is the path with the lowest total weight. Our continent has 100 million nodes and 250 million edges, which fits in about 4.2 GB of memory.

Dijkstra's algorithm grows a disc of settled nodes around the start, always taking the nearest unsettled one, until it reaches the end. For a trip across the continent the disc covers about half of all nodes. Settling 50 million nodes at 5 million a second takes about 10 seconds on one core. Searching from both ends at once helps, but only by a small factor. We need a search that touches about a thousand nodes.

Shortcuts do this by spending time in advance. Rank the nodes by importance. A node on a quiet dead-end street is unimportant, and a motorway junction is important. Then remove nodes one at a time, least important first. When you remove a node v, look at each pair of its neighbours, u before it and w after it. If the best path from u to w goes through v, add a shortcut edge from u to w with the combined weight, and remember v as its middle. If a short search finds an equally good path that avoids v, no shortcut is needed.

This is called a contraction hierarchy. After it, every node has a level, and every shortest path climbs to higher levels and then descends again. A query runs one search forward from the start and one backward from the end, and each may only move to higher levels. The two meet near the top, and the best meeting point gives the answer. In our estimate each search settles about 1,000 nodes in all, 0.2 ms of CPU, which is 50,000 times faster than plain Dijkstra. The shortcuts add about 1.8 GB.

To return the real roads, unpack each shortcut: it knows its middle node, so replace it by its two halves, and repeat until only ordinary edges remain.

The catch is that the shortcuts are computed from the weights. That matters in the next section.

The aggregator matches each point to a road segment, using the previous point and the heading to choose between parallel roads. For each segment and 2-minute window it takes the median speed, and uses the segment's usual speed for that time of the week when fewer than a few phones reported. That is 1 million points a second, or about 50 MB/s.

Why shortcuts break. A shortcut's weight is a sum of road weights, and the decision to add it, or to skip it because a witness path was just as short, was made with the old speeds. A jam on a witness path means a skipped shortcut is now needed. Without it, searches return wrong routes. The simple fix is to rebuild the hierarchy, but that takes about 30 minutes. In 30 minutes there are 15 refresh cycles, so routes would always be answering for traffic that has already gone.

Separate the structure from the weights. A partition overlay keeps the part that does not depend on speeds fixed, and recomputes the rest fast. Once, offline, cut the graph into compact cells, say 10,000 cells of about 10,000 nodes, and group cells into larger ones in levels. The nodes of a cell that have a road to the outside are its boundary nodes, about 100 in each. The overlay then holds, for each cell, the shortest travel times between all pairs of its boundary nodes.

Customizing. When speeds change, recompute only the cells that contain a changed road. For one cell, run a search from each of its 100 boundary nodes inside the cell: 100 searches of at most 10,000 nodes is 1 million settled nodes, or 0.2 s. If 10% of cells changed, that is 1,000 cells and 200 core-seconds. On 32 cores it takes about 6 seconds, and the cells are independent, so it parallelizes perfectly. Then refresh the larger cells that contain them. A routing server swaps in the new weights atomically, so a search never sees half an update.

Querying. Search in full detail inside the start cell and the end cell, and on the overlay for everything between, from both ends. It touches more nodes than a hierarchy, typically a few ms, which fits our budget. A road closure is just a weight of infinity, applied by the same path within a cycle, or sooner by patching its cell.

A spatial index, a grid of small squares that list the segments inside them, finds the road segments within about 50 m of a point. Choose among them by distance, by the direction of travel when it is known, and by road class, so a driver on a motorway is not snapped to the service road beside it. The point usually lies in the middle of a segment, so split the segment into two temporary edges, with the point as a node, for this one search.

Alternatives. Find routes that differ from the best one in a useful way. A simple method picks a few via-nodes from the two searches, builds a route through each, and keeps one only if it shares at most 80% of its roads with the best route, is at most about 25% slower, and has no sharp detours. Show at most two.

ETA calibration. A sum of road speeds is not an arrival time. Junction delays, traffic lights and turns add time. Compare the predicted time of finished trips with the times that the phones really took, grouped by road class, region and hour of the week, and learn a correction for each group. Track the median relative error, the aim being under 10%, and test any new model on live traffic in shadow mode before it answers anyone.

Sharding. The graph is about 6 GB with shortcuts, so a continent fits in the memory of one machine. We shard for CPU, for update speed and to scale up to the planet, not for capacity. Each server group holds full detail for the cells of a few regions and the coarse overlay for the rest. Requests go to the group of the start's region, which keeps its working set hot. A long trip uses the upper overlay levels between regions, which are small and held everywhere. Each cell update lands only on the groups that hold that cell.

Caching. Key a route by the grid squares of the snapped start and end, about 200 m across, with the departure minute and the options. A time to live of 60 seconds keeps routes fresh. Commutes and popular trips hit often. On a hit, only the first and last few hundred metres are adjusted for the exact points.