Real-time traffic routing is one of the canonical systems design problems — and also one of the most algorithm-heavy LLD problems you’ll encounter. It combines graph theory, data freshness requirements, and high read throughput. Let’s go layer by layer.
Road Graph Representation
The map is modeled as a directed weighted graph:
- Nodes — intersections, identified by a 64-bit integer node_id with lat/lng coordinates
- Edges — road segments connecting two nodes, with attributes: distance_m, speed_limit_kmh, road_type (motorway / arterial / residential), one_way (boolean), and a dynamic weight representing current travel time in seconds
For a city like New York, the graph has roughly 400,000 nodes and 1,000,000 edges. This fits in memory: each edge is about 80 bytes, so 1M edges is 80MB. The graph is stored in an adjacency list backed by memory-mapped files for fast load on startup.
Shortest Path Algorithms
Dijkstra
The baseline correct algorithm for single-source shortest paths on a graph with non-negative edge weights. Time complexity: O((V + E) log V) with a binary heap. For a city-scale graph this runs in about 200-500ms, which is too slow for user-facing requests but useful as a correctness reference and for offline precomputation.
A* Search
A* accelerates single-target queries by adding a heuristic function h(n) that estimates the remaining distance from node n to the destination. The common choice for road networks is Euclidean distance (straight-line haversine). A* only expands nodes where f(n) = g(n) + h(n) is minimal, so it visits far fewer nodes than Dijkstra for point-to-point queries. On city graphs A* is typically 3-10x faster than Dijkstra for single queries. The heuristic must be admissible (never overestimates) to guarantee optimality.
Contraction Hierarchies
For production routing at scale, Contraction Hierarchies (CH) is the standard approach. The idea: preprocess the graph by iteratively removing (contracting) the least important nodes and adding shortcut edges that preserve shortest path distances. The result is a hierarchical graph where queries only traverse shortcuts going up the hierarchy to the destination and then down. CH queries run in under 1ms on continental road networks, 1000x faster than Dijkstra, at the cost of 2-5x more memory for the augmented graph and 10-60 minutes of preprocessing. The preprocessed graph is rebuilt nightly or on significant map updates.
Real-Time Traffic Weight Updates
GPS probe data from active devices is the primary source of real-time speed information. The pipeline: raw GPS pings (device_id, lat, lng, timestamp, speed) arrive via Kafka. A map-matching service snaps each ping to a road segment (see below). Speed observations are aggregated per segment over a 2-minute rolling window. The resulting speed estimate replaces the segment’s travel-time weight in the routing graph. Weight updates are applied to a hot-standby copy of the graph and atomically swapped in every 30 seconds to avoid serving stale routes without locking the read path.
ETA Calculation
ETA = sum of travel time per segment along the path + turn penalties + signal delay estimates. Travel time per segment = segment_distance_m / observed_speed_ms. Turn penalties add 5-15 seconds depending on turn type (left turn across traffic costs more than right turn). Signal timing data, where available from city APIs, adds expected wait time at signalized intersections. The result is a probabilistic ETA: a median estimate plus a confidence interval based on historical variance for that time of day.
Turn Restrictions
Turn restrictions are not expressible as simple edge costs — they depend on the incoming edge, not just the node. A no-left-turn from Street A onto Street B is valid even if turning left from Street C onto Street B is allowed. The standard encoding: expand the graph so each node is split into (incoming_edge, node) pairs. Restricted turns become missing edges in this expanded graph. This doubles the node count but correctly models all turn restrictions including conditional ones (no turn during peak hours).
Map Matching
Raw GPS coordinates have 3-10m of noise and do not align precisely with road segments. Map matching snaps a sequence of GPS points to the most likely path through the road graph. The standard algorithm uses a Hidden Markov Model: each GPS point emits a probability distribution over nearby road segments (emission probability based on GPS error model), and transitions between segments follow road connectivity (transition probability penalizes teleporting across disconnected roads). The Viterbi algorithm finds the most likely sequence of road segments given the GPS trace. This runs in O(T * S^2) where T is the number of GPS points and S is the candidate segment count per point (typically 5-10).
Route Alternatives
Users expect 2-3 route options. Naively running k-shortest paths produces routes that share most of their road segments and look nearly identical. The standard approach is penalized routing: after finding the optimal route, increase the edge weights of its road segments by a penalty factor (typically 1.5x) and run the routing algorithm again. Repeat for the third alternative. The penalty ensures alternatives diverge meaningfully from the primary route. Alternatives are ranked by a weighted combination of travel time, road quality, and the degree of overlap with higher-ranked routes.
Frequently Asked Questions
Q: What are the tradeoffs between Dijkstra, A*, and Contraction Hierarchies for traffic routing?
A: Dijkstra’s algorithm finds the shortest path in O((V + E) log V) time but explores the graph in all directions, making it slow on continental road networks with hundreds of millions of nodes. A* adds a geographic heuristic (great-circle distance to destination) that biases exploration toward the goal, cutting query time by 2-5x on typical road graphs but offering no worst-case guarantee when the heuristic is inadmissible. Contraction Hierarchies (CH) preprocess the graph by iteratively contracting less-important nodes and adding shortcut edges. At query time, bidirectional Dijkstra runs on the contracted graph from both endpoints, meeting in the middle. CH achieves query times under 1 ms on full continental graphs — orders of magnitude faster than plain Dijkstra — at the cost of an offline preprocessing step (minutes to hours) that must be re-run when edge weights change significantly.
Q: How does Hidden Markov Model map matching work for GPS traces?
A: Raw GPS traces have positional error of 5-15 meters and sample at intervals of 1-5 seconds, making it impossible to determine which road segment a vehicle is on by proximity alone. HMM map matching models each GPS observation as an emission from a hidden state (the true road segment) and uses the Viterbi algorithm to find the most likely sequence of road segments. The emission probability is based on the GPS-to-segment distance (Gaussian distribution). The transition probability combines road connectivity — only transitions via connected segments are allowed — with a great-circle distance consistency check between consecutive GPS points. The result is a smooth, topologically valid path on the road network that accurately represents the vehicle’s trajectory even through tunnels and dense urban canyons.
Q: How does the k-shortest paths algorithm work in a routing service?
A: K-shortest paths (KSP) finds the k lowest-cost paths between a source and destination, enabling the routing service to offer alternatives. Yen’s algorithm is the standard approach: it iteratively computes the next-best path by finding deviations from previously found paths. For each candidate path, a spur node is selected and the graph is temporarily modified to exclude edges already used in the root sub-path, then Dijkstra finds the spur path. The root + spur = a candidate that is added to a min-heap. Eppstein’s algorithm provides better worst-case complexity for large k. In production, KSP is typically run with k=3 to 5 and results are post-filtered by diversity heuristics (minimum Jaccard distance between paths) so alternatives are meaningfully different rather than slight variations of the same route.
Q: How do you ingest real-time traffic data into a routing service?
A: Real-time traffic data arrives from multiple sources: probe vehicles reporting GPS traces (first-party fleet data), HERE/TomTom traffic feeds (third-party), and roadside sensor APIs. Each source is consumed by a dedicated ingestor that normalizes data into a canonical traffic event format (segment ID, speed, free-flow ratio, timestamp, confidence). Events are written to a Kafka topic and consumed by a traffic fusion service that applies sensor fusion — weighted averaging by confidence and recency — to produce a current-speed estimate per segment. Segment speeds are written to a distributed key-value store (Redis or DynamoDB) with a short TTL. The routing engine reads segment costs from this store at query time, using free-flow speed as fallback when no recent data is available. Batch historical aggregation runs hourly to compute time-of-day speed profiles used for departure-time routing.
Q: How do you build ETA prediction with machine learning in a routing service?
A: Graph-based ETA (sum of segment travel times) is accurate on free-flowing roads but degrades at intersections, traffic signals, and merge points where queuing effects dominate. ML-based ETA stacks a gradient-boosted model (XGBoost or LightGBM) or a sequence model (LSTM/Transformer) on top of the graph estimate. Features include: graph ETA, time of day, day of week, current congestion index along the route, weather conditions, number of turns and signals, and historical ETA error for the same OD pair and time window. The model is trained on historical trip records where actual arrival time is the label. Inference runs per-route at query time with p99 latency under 5 ms. The model is retrained daily on a rolling 90-day window. Calibration is monitored via a holdout set; if mean absolute error exceeds a threshold, an alert fires and the fallback graph-only ETA is served.
See also: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering
See also: Scale AI Interview Guide 2026: Data Infrastructure, RLHF Pipelines, and ML Engineering