Maps routing - precompute, then watch it go stale

Two hundred million route requests a day over a graph of 130 million edges whose weights change every five minutes. Every requirement below is really a question about how much work may be done before the question is asked.

Ask these before designing

• Is the cost function fixed? Contraction hierarchies are precomputed FOR a cost function. One metric (fastest by car) is one hierarchy. Fastest, shortest, avoid-tolls, lorry-with-a-height-limit and bicycle are five hierarchies, or one much harder algorithm.
• Must the route be optimal, or merely good? Optimal permits CH and forbids most heuristics. "Good" permits A* with landmarks and a much simpler operation. Interviewers rarely say which they want, and the answer changes the entire board.
• How live is live traffic? Five-minute aggregates are a different system from thirty-second ones. The second forces the overlay design; the first would almost permit folding traffic into a nightly rebuild.
• Does the route have to stay stable during the trip? If a reroute may fire whenever a better path appears, the driver is sent round in circles as the traffic oscillates. Stability is a product requirement that constrains the algorithm.
• Is the road graph the same for everybody? Turn restrictions, vehicle profiles and access rules make it not quite one graph, and every per-user variation is either a filter at query time or another hierarchy.
• What is the acceptable staleness for a road that closed permanently? This is the requirement that decides the rebuild cadence, and it is usually stated as traffic freshness by mistake.

Functional

• Given two points, return an optimal route with a distance, a duration and turn-by-turn geometry.
• Snap each endpoint to a real road edge, respecting direction and access rules.
• Apply live traffic to the duration and, where it is severe enough, to the route itself.
• Serve an ETA that accounts for expected conditions along the route at the time the driver will actually be there.
• Ingest GPS probes from navigating devices, map-match them to edges, and aggregate speeds.
• Rebuild the hierarchy on a schedule without interrupting queries.

Non-functional

• Route p50 12 ms, p99 90 ms. The p99 is dominated by queries whose shortcut path has been invalidated by the overlay, which is the design’s honest cost rather than a tuning problem.
• The answer must be the true optimum under the applied weights, or the product is quietly wrong in a way no user can detect and every competitor comparison exposes.
• Traffic visible in the ETA within 90 s of the probes that imply it.
• 99.99% for routing, degrading to free-flow weights rather than failing.
• The graph is immutable per version. A route computed against version N must be unpackable against version N, which makes version pinning per session a correctness requirement.

Explicitly out of scope

Map data production and conflation, geocoding and address search, indoor and pedestrian routing, ride dispatch (that is the matching board), multi-stop vehicle routing, which is a different NP-hard problem wearing the same coat.