A route is a sequence of road segments, each with a travel time estimate. Add them up, you have an ETA. That’s the naive version. It’s also wrong often enough that Google spent years making it less wrong.

The Simple Version and Its Failures#

Sum the edge weights on the shortest path. If the router says the trip is 45 minutes, tell the user 45 minutes. This works fine when traffic weights are accurate and conditions are stable.

The problems start immediately. Edge weights in the road graph come from speed limits or recent GPS probe data. Speed limits are optimistic. Probe data represents current conditions, not conditions 30 minutes from now when you’ll actually be on that road. A commute that starts at 5:30pm looks very different from the same route at 5:30am.

Historical Baselines#

Every road segment has a speed profile by time of day and day of week. Tuesday at 8:15am on the highway between two office parks is reliably 25 km/h. That baseline is learned from months of probe data.

When routing, instead of using current segment speed for the entire trip, you look up the expected speed for each segment at the time you’ll actually traverse it. You’re starting now, but you won’t reach that segment until 20 minutes in. Use the speed it’ll likely have in 20 minutes.

Predicted traversal time for segment S:
  departure_time = now + cumulative_time_to_reach_S
  expected_speed = historical_speed[segment_S][departure_time.hour][departure_time.weekday]
  traversal_time = segment_length / expected_speed

Live Data Blending#

Historical baselines don’t capture today’s specific incident. An accident at 5:45pm doesn’t match the typical Tuesday evening profile. Live probe data overrides the historical baseline for affected segments when enough current data exists.

The blend: if a segment has 10+ GPS pings in the last 5 minutes, trust live data. If it has 0-2 pings, trust historical. Between 3-9 pings, weight the two proportionally.

graph TD A[Route Segments] --> B[For Each Segment: Compute Arrival Time] B --> C{Live Probe Data Available?} C -->|Yes - enough pings| D[Use Live Speed] C -->|No - sparse| E[Use Historical Profile for That Hour/Day] C -->|Partial| F[Weighted Blend] D --> G[Sum Segment Times] E --> G F --> G G --> H[ETA with Confidence Interval] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style F fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style G fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style H fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

At Oracle#

We had SLA predictions for service ticket resolution. “How long until this network fault is resolved?” We naively used mean resolution time per fault type. Terrible. Resolution time varied by time of day (fewer engineers at 3am), fault severity, and which team owned the affected component. Once we segmented the historical data by those dimensions and used the right segment as the baseline, prediction accuracy improved enough to actually be useful. Same principle: segment your history by context, then use the right segment for prediction.

What I’m Learning#

ETA prediction is a time-series forecasting problem disguised as a routing problem. The routing tells you which segments you’ll traverse. The forecasting tells you how fast you’ll traverse them. You need both to get an honest answer. Naive implementations skip the forecasting half and wonder why their ETAs drift as the trip progresses.

How do your systems handle predictions that depend on future conditions you can only estimate?