How does turn-by-turn navigation work at a system level?

Turn-by-turn navigation computes a route from origin to destination using a graph-based shortest-path algorithm over a road network, then monitors the user's GPS position in real time to issue maneuver instructions. It continuously re-routes if the user deviates from the planned path.

What routing algorithms are used in turn-by-turn navigation systems?

Common algorithms include Dijkstra's algorithm for exact shortest paths, A* with a heuristic for faster performance, and Contraction Hierarchies (CH) for preprocessing road graphs to enable sub-second routing on continent-scale networks. Uber and Google both use variants of CH for production routing.

How do you handle real-time rerouting in a navigation system?

Real-time rerouting is triggered when the user's GPS position deviates beyond a threshold from the current route. The system queries the routing engine with the current position as the new origin and recomputes the shortest path. To keep latency low, routing servers maintain in-memory road graph snapshots and use precomputed hierarchies.

How does a navigation service incorporate live traffic data?

Live traffic data is ingested from GPS probes (anonymized device location streams), road sensors, and incident reports. Edge weights in the road graph are updated in near-real-time to reflect current travel speeds. Lyft, Uber, and Google use streaming pipelines (e.g., Kafka) to propagate traffic updates to routing servers with minimal lag.

Low Level Design: Turn-by-Turn Navigation Service

⏱ 4 min read

A turn-by-turn navigation service accepts an origin and destination, computes an optimal route through the road network, and delivers step-by-step maneuver instructions updated in real time as the user moves. Unlike a simple shortest-path query, navigation must handle live traffic, rerouting, and continuous GPS position updates at low latency.

Data Model

Road graph: same node/edge schema as the mapping service, augmented with (edge_id, timestamp, travel_time_s FLOAT) rows in a live_traffic table updated every 30–60 seconds from probe data.
Route: (route_id UUID, user_id BIGINT, origin_lat DOUBLE, origin_lon DOUBLE, dest_lat DOUBLE, dest_lon DOUBLE, created_at TIMESTAMP, edge_sequence BIGINT[], maneuvers JSONB)
Maneuver: a JSON object containing instruction (human-readable text), distance_m, bearing, and road_name.
Position update: (session_id UUID, lat DOUBLE, lon DOUBLE, bearing FLOAT, speed_mps FLOAT, recorded_at TIMESTAMP) — stored in a time-series store (InfluxDB or TimescaleDB) for live tracking and probe data aggregation.

Core Algorithm: A* with Contraction Hierarchies

Vanilla Dijkstra is too slow for continental-scale graphs. Production navigation stacks use Contraction Hierarchies (CH):

Preprocessing: nodes are ranked by importance. Less-important nodes are contracted: virtual shortcut edges replace paths through them, reducing query graph size by orders of magnitude.
Query: bidirectional A* runs simultaneously from origin and destination on the contracted graph. When the two search frontiers meet, the shortest path is extracted and expanded back to real road segments.
Traffic overlay: live edge weights (travel_time_s) override static speed limits. The CH is rebuilt periodically (hourly) for the base graph; traffic adjustments are applied as a thin overlay without full rebuild.

Rerouting

The device streams position updates every 1–5 seconds. A server-side deviation detector compares the current position against the planned edge sequence. If the user is more than 50 m off-route, a new A* query is triggered from the snapped current position to the destination, and the updated maneuver list is pushed to the client within 500 ms.

Map Matching

Raw GPS coordinates have 5–15 m of noise. A Hidden Markov Model (HMM) map-matcher projects noisy GPS observations onto the most probable road segment sequence, enabling accurate instruction triggering (e.g., announcing a turn exactly 300 m before the intersection).

Failure Handling

Routing service unavailable: the mobile client caches the last computed route and continues offline navigation using cached map tiles. Re-sync when connectivity returns.
Traffic data staleness: fall back to historical speed profiles (time-of-day averages) when live probe data is older than 5 minutes.
Position update loss: dead-reckoning using last known speed and bearing maintains position estimate for up to 30 seconds before alerting the user.
Reroute storm: if a road closure sends many users into rerouting simultaneously, a request queue with client-side exponential backoff prevents server overload.

Scalability Considerations

Route computation is CPU-intensive. A fleet of stateless routing workers auto-scales behind a load balancer; the contracted graph is loaded into shared memory (mmap) so workers share a single copy per host.
Live traffic ingestion uses a Kafka topic per geographic region; consumers update the in-memory traffic overlay without locking the routing graph.
Session state (active navigation, position history) is stored in Redis with a TTL; no sticky sessions are required.
Geographic sharding: routing workers are assigned to continental regions, reducing graph size per worker and keeping cross-shard stitching rare.

Summary

Turn-by-turn navigation combines a preprocessed contracted graph for fast shortest-path queries, a traffic overlay for real-time accuracy, HMM map matching for GPS noise reduction, and a low-latency rerouting pipeline. Offline fallback and dead-reckoning ensure the user is never stranded without guidance even under poor connectivity.