The naive ETA formula is distance_km / avg_speed_kmh × 60. A 10km trip at 50 km/h = 12 minutes. That would make Uber useless — because that estimate is off by 2× at rush hour, 0.5× at 2am, and wrong in a different direction on rainy days. Here's every reason ETA is a hard problem:
EVERYTHING THAT AFFECTS YOUR REAL TRAVEL TIME
Road network topology — you can't drive through buildings
Turn restrictions — no U-turns, one-ways, no-left-turn at signals
Traffic congestion — NH-48 (Gurugram corridor) at 8am vs 2am: 5× speed difference
Traffic signals — red lights add 30–90s per intersection
Road class — highway vs residential: different speed profiles
Day of week — Friday 5pm vs Monday 5pm: dramatically different
Weather — rain slows traffic 15–25%
Events — stadium letting out = gridlock in a 1km radius
Construction zones — sudden lane closures
Accidents — cascade slowdowns 2–3km upstream
Uber's ETA system layers three approaches on top of each other: (1) graph-based routing to find the fastest path through the road network, (2) historical + real-time speed data to set accurate edge weights on that graph, and (3) a machine learning model that corrects the residual error that routing alone can't capture. Let's build up each layer.
DISTANCE ÷ SPEED ≠ ETAGRAPHS + ML + PROBE DATA
02
The Road Network: A Directed Weighted Graph
Model every city as a directed weighted graph. Nodes = road intersections and endpoints. Directed edges = road segments (one-way streets are single-direction edges; two-way streets are two edges in opposite directions). Edge weight = estimated travel time in seconds.
🗺 ROAD GRAPH EXPLORER — Hover an edge to inspect its properties
Simplified Delhi NCR sample
ROAD CLASSES
Motorway — 100 km/h
Primary — 60 km/h
Secondary — 50 km/h
Residential — 30 km/h
EDGE PROPERTIES
Hover over a road segment to inspect its properties
US SCALE
Nodes: ~50M (intersections)
Edges: ~120M (segments)
Time buckets: 672 / edge
OSM → simplified 160×
WHERE DOES THE ROAD DATA COME FROM?
OpenStreetMap (OSM) — the Wikipedia of maps. Uber, Google, and Apple all base their road graphs on OSM data, enriched with proprietary corrections and live data.
Government sources — SOI (Survey of India), Bhuvan geoportal data for speed limits
Uber's own trips — billions of historical GPS traces are the best possible source of actual travel times on each segment
Graph simplification — raw OSM has ~8B nodes globally. After removing redundant intermediate nodes on straight roads, Uber contracts this to ~50M nodes for the US — 160× reduction while preserving routing accuracy
03
Interactive: A* vs Dijkstra Pathfinding
Both algorithms find the shortest path. Dijkstra explores in all directions equally (like a flood fill). A* uses a heuristic (straight-line distance to goal) to prioritize promising directions — exploring far fewer nodes. Click cells to place 🚧 traffic jams, then run both algorithms to see the difference in explored nodes.
PATHFINDING VISUALIZER — Road Network Routing
Click cells to toggle traffic jams | Green=start | Red=goal
A* visits fewer nodes because the heuristic (straight-line distance) guides search toward the goal.
Dijkstra vs A*: The Core Difference
Dijkstra's Algorithm
Always expands the node with the lowest cost from start. No hint about which direction the goal is. Explores in all directions simultaneously — like a flood fill.
Priority queue ordered by g(n) = cost from start to n
Guaranteed optimal on non-negative weights
Explores ~O(V) nodes on continent-scale graph → millions of nodes per query
Classic solution, too slow for production routing
A* Algorithm
Expands the node with the lowest estimated total costf(n) = g(n) + h(n), where h(n) is the heuristic estimate to the goal.
Admissible = never overestimates → still finds optimal path
Explores 10–100× fewer nodes than Dijkstra on road networks
Still too slow for planet-scale routing → need Contraction Hierarchies
⚖️ ALGORITHM COMPARISON — Same 15km Urban Route
Dijkstra
Strategy: expand cheapest
Heuristic: none
Nodes explored: ~2,000,000
Query time: ~400ms
Preprocessing: none
❌ Too slow for production
A* Algorithm
Strategy: cheapest + heuristic
Heuristic: Euclidean / max_v
Nodes explored: ~200,000
Query time: ~40ms
Preprocessing: none
⚡ 10× faster but still too slow
CH + Bidir
Strategy: upward only, bidir
Heuristic: hierarchy level
Nodes explored: ~500–2,000
Query time: ~1–3ms
Preprocessing: ~2 hours once
✅ What Uber actually uses
Key insight: A* uses f(n) = g(n) + h(n) — actual cost so far + estimated remaining. The heuristic h(n) = straight-line distance / max possible speed is always an underestimate (admissible), so A* always finds the optimal path while exploring far fewer nodes.
04
Contraction Hierarchies: Planet-Scale Routing in Milliseconds
Even A* is too slow for Uber's scale. Querying a 50M-node US road graph 100,000 times per minute at 40ms each = impossible. The solution is Contraction Hierarchies (CH) — a preprocessing technique that creates "highway shortcuts" so queries only need to explore a tiny subset of the graph.
1
Offline: Rank every node by "importance"
Compute an importance score for each node. Less important nodes are contracted first. Importance = edge difference (how many new shortcut edges are needed if this node is removed) + query count (how often this node appears in shortest paths). Highway interchanges = very important. Dead-end residential streets = very unimportant.
For each contracted node N with neighbors A and B: if removing N would make A→B longer, add a shortcut edge A→B with cost = A→N + N→B. This preserves all shortest paths without N. After contracting 90% of nodes, the "contracted graph" is much smaller but all shortest paths still exist — they just use shortcuts instead of intermediate nodes.
3
Online: Bidirectional Dijkstra, upward only
At query time: run Dijkstra from both the start and the goal simultaneously, but only traverse edges that go upward in the hierarchy (toward more important nodes). The two searches meet somewhere near the top of the hierarchy (major highway nodes). The optimal path = the best middle node found by both searches.
4
Unpack shortcuts to get the actual route
The query returns a sequence of nodes that may include shortcut edges. Each shortcut was created by contracting an intermediate node, so you recursively expand shortcuts until you have the full list of real road segment edges. This expansion is fast (precomputed shortcut tree) and happens after the query completes.
Algorithm
Nodes Explored
Query Time (US graph)
Preprocessing
Dijkstra
~2,000,000
~400ms
None
A*
~200,000
~40ms
None
Bidirectional A*
~50,000
~10ms
None
CH + Bidirectional
~500–2,000
~1–3ms
~2 hours once
TIME-DEPENDENT CH: THE REAL CHALLENGE
Static CH works beautifully — but ETA requires time-dependent edge weights (rush hour vs. off-peak). You can't precompute shortcuts for all possible departure times. Uber's solution: maintain multiple CH overlays (one per time bucket) for the most common scenarios, and use a time-dependent variant for edges where speed varies significantly. The preprocessing runs nightly as traffic patterns shift seasonally.
05
Interactive: Time-of-Day ETA Explorer
The same 8km route across Delhi NCR has wildly different ETAs depending on when you travel. Drag the hour slider to see how historical probe data changes the speed profile — and the ETA — for every segment of the route.
Why P75?
Uber shows P75 so that 75% of trips arrive at or before the shown ETA. Showing P50 would mean half of riders arrive "late" by the app's own estimate. Too conservative (P95) would look bad vs competitors.
06
Real-time Probe Data: Every Driver is a Sensor
Historical speed profiles tell you what a road is usually like at 8am on Mondays. But today's 8am Monday could have a marathon closing 12 blocks, or a water main break, or an unexpected clear day. Real-time probe data — GPS traces from every active driver and trip — provides the current ground truth.
📡 PROBE DATA PIPELINE — From GPS ping to ETA weight
📱
GPS Ping
Every 4s driver_id, lat, lng speed, heading ±5m accuracy
▶
🎯
Map Match
Hidden Markov Model GPS → road segment uses: lat, lng, heading, speed
At 3am, there are far fewer active drivers — fewer probes per segment. Segments with zero probes fall back entirely to historical data. This is why Uber ETAs are slightly less accurate at 3am despite low traffic — not because of congestion, but because of reduced probe coverage. At peak hours (rush hour), probe density is so high that real-time data dominates and historical data barely matters.
07
The ML Layer: Correcting What Routing Can't Know
Even with perfect probe data, the routing model has systematic blind spots. The graph can't model: a driver who always runs 3 minutes late because they stop for coffee. A pickup zone where every rider takes 90 seconds to walk out of the building. Traffic signal timing that creates a 45-second cluster effect. This is where the machine learning correction layer earns its keep.
🤖 XGBoost FEATURE IMPORTANCE — hover a bar for details
Trained on 500M+ trips
FEATURE DETAIL
Hover a bar to see what this feature measures and why it matters to ETA accuracy.
Routing features
Time features
Real-time context
Pickup zone
TYPICAL ML CORRECTION MAGNITUDES
Rush hour (Mon 8am): +15–40% over routing estimate
Rain (heavy): +20–35% correction
Major event nearby: +50–120% correction within 500m
2am weekday: −10–20% (roads genuinely faster, signals in night mode)
Airport pickup zone: +3 min constant (terminal walk time)
Stadium after game: +200–500% within 1km
Highway-only route: routing is more accurate, smaller correction
Complex urban with many turns: routing underestimates, ML adds time
08
Two-Phase ETA: Pickup + Trip
Uber always computes two separate ETAs with different uncertainty characteristics. Getting them right is what separates a good rideshare from a bad one.
Phase 1: Driver → Pickup (Pickup ETA)
Displayed as: "Your driver is 4 min away"
Route: driver's current location → rider's pin
Updated every 4 seconds as driver moves
Highest accuracy: current position is known, route is short
Uses real-time probe data heavily — short routes are sensitive to current conditions
Driver's current speed / heading feeds into dead reckoning between pings
ML correction: smaller, mainly pickup zone walk-time factor
Phase 2: Pickup → Destination (Trip ETA)
Displayed as: "Trip: 22 min"
Route: pickup pin → destination pin
Computed once at trip match, updated during trip
Lower accuracy: future traffic is uncertain
Uses historical profiles more heavily (can't know real-time 20 min from now)
ML correction: larger uncertainty bounds
Shown as P75 with wider range during surge
Recalculates if route deviates significantly
⏱ UBER REQUEST TIMELINE — <50ms from tap to "driver found"
ONGOING UPDATES — After driver is matched
Every 4s (en route)
Phase 1 ETA recalculates Driver GPS → new position "4 min → 3 min → 2 min" Dead reckoning smooths display
Every 30s (during trip)
Phase 2 ETA recalculates Traffic changes en route "22 min → 19 min" etc Full reroute if deviated
On event (accident/reroute)
Full Phase 2 recalculation New route via CH routing New ETA pushed to app "Traffic detected — rerouting"
09
What Uber Actually Shows You (And Why)
The Percentile Strategy
Condition
Display
Percentile
Why
Normal, low surge
"4 min"
P75
Conservative enough for most trips
High surge / bad traffic
"4-7 min"
P50–P90
Widen range; uncertainty is real
Airport pickup
"8 min"
P90
Airport is unpredictable; set expectations
Trip ETA upfront pricing
"22 min"
P75
Price locked to this estimate
ETA Accuracy Metrics Uber Tracks
ETA Error Rate: % of trips where actual > shown ETA by >5 min
RMSE: Root mean square error across all trips
P75 Calibration: Should be exactly 75% of trips arrive at or before P75 ETA
Per-market accuracy: Delhi NCR is harder than Jaipur (density, complexity)
ETA drift: Does the 4-second ETA update feel smooth or jumpy?
UBER'S INTERNAL TARGET
Within 1 minute accuracy for 85% of pickup ETAs. Trip ETAs within 2 minutes for 80% of trips. They publish annual "transparency reports" showing ETA accuracy by city.