Why plain search is too slow
A road network is a graph of intersections and segments. Classic shortest path search explores outward from the start, and on a continent sized graph that explores millions of nodes per query, far too slow for an interactive request.
Precompute to prune
Scalable routers move work offline:
- Contraction hierarchies add shortcut edges that skip over unimportant nodes, so an online query only touches a thin upper layer.
- Partitioning cuts the map into regions and precomputes distances between boundary nodes, so cross region queries jump between borders.
- Landmarks precompute distances to a few anchor points to give the search a strong directional heuristic.
Layering the live world
- Static structure is precomputed; live traffic is layered on as time dependent edge weights.
- Queries return alternatives, not just one path, so the client can offer choices.
- Heavy precomputation is rebuilt periodically while queries keep serving the previous snapshot.
Key idea
Route planning at scale shifts the heavy work offline into shortcuts and partitions so each online query touches only a thin precomputed layer.