TRICKYwalkthrough
ETA Prediction with ML
A user starts navigation from downtown Los Angeles to the airport at 4:45 PM. The Contraction Hierarchies algorithm returns the shortest path: 18.5 miles across 47 road segments.
But the user arrives in 55 minutes because of rush hour traffic, a school zone, and a construction detour. Static edge weights are useless for ETA.
“The naive ETA is the sum of each segment's length divided by its speed limit, giving 22 minutes.”
We need to predict what traffic will look like 30 to 60 minutes into the future, not just what it is right now. The basic approach: real-time segment speed from GPS probes (see the live traffic concept).
For each segment on the path, we compute . This works if traffic stays constant, but traffic at 5:15 PM will differ from traffic at 4:45 PM.
For segments without current probe data (rural roads, low-traffic areas), we fall back to historical speed patterns bucketed by time of day, day of week, and road type. Google stores years of historical probe data, creating a speed profile for every road segment at 15-minute granularity.
The breakthrough came from DeepMind's 2020 collaboration with Google Maps. Their ML model uses supersegments, aggregations of multiple consecutive road segments, as the prediction unit.
Features include: current speed on the supersegment, historical speed at this time, speeds on upstream supersegments (to detect approaching congestion), weather conditions, road type, and special events. The model predicts speed 10, 20, and 30 minutes into the future.
Google Maps reports 97%+ ETA accuracy within the predicted time window. The model runs inference at route request time, adding about 20ms to the query.
Trade-off: ML models require continuous retraining as road networks change, construction patterns shift, and new neighborhoods develop. A model trained on 2023 data degrades on 2024 road patterns.
Google retrains weekly using the latest 90 days of probe data. What if the interviewer asks: why not just use current speeds for ETA?
Because a 30-minute drive means traffic conditions at the destination are 30 minutes in the future. Current speed only works for very short routes under 5 minutes.
Related concepts