Design an ETA prediction system

The problem

A rider opens the app and sees "Driver arrives in 4 min, you arrive at 18:42". A delivery app shows "25 to 35 min". Behind both numbers is an ETAEstimated time of arrival: a prediction of how long a trip, pickup or delivery will take, shown to users and used internally for matching, pricing and planning. service, and it is one of the most called models in the company: every app open, every candidate driver the matcher considers and every in-trip refresh asks it a question.

It is hard for three reasons. The physical world is only partly visible: the map knows the roads, but not the double-parked truck or the 10 minutes it takes to find the right entrance at an airport. Traffic changes minute by minute, so features go stale fast. And the cost of being wrong is lopsided: a driver who arrives two minutes early is a pleasant surprise, while one who arrives eight minutes late is a cancelled trip and an angry review.

Think of a seasoned taxi dispatcher. They start from the map ("that is a 15 minute drive"), then correct it from experience ("but it is Friday at 6 and it is raining, and the airport pickup always takes longer, so say 22"). The design in this lesson is that dispatcher written down: a routing engine for the map, and a model for the experience.

Requirements

Functional

• Given an origin, a destination, a departure time and a product (car, bike, delivery), return a predicted travel time.
• Return two numbers: a typical time (the median, for ranking and display) and a pessimistic one (the 90th percentile, for "arrive by" promises).
• Serve three callers: the rider app (display), the matcher (rank candidate drivers for one request in a single batch call) and the in-trip screen (refresh as the trip progresses).
• Log every prediction with the features used, so it can be joined to the actual outcome later.

Non-functional

• Latency: P99 under 50 ms for a batch of up to 10 candidate drivers, because the matcher waits for it before offering a trip.
• Freshness: traffic features no more than a couple of minutes old.
• Availability: higher than the model's own. If features or the model fail, fall back to the routing engine's ETA instead of returning an error.
• Accuracy targets by slice (city, hour, trip length, pickup type), not just one global number.

Out of scope

• Building the road graph and the shortest-path algorithm itself (we treat the routing engine as a service with a known interface).
• Matching, pricing and surge, which consume ETAs (see Design a ride-hailing service (Uber) ).
• Food preparation time for deliveries, which is a separate model with its own features.

Estimates

All inputs below are assumptions for a large ride-hailing app, not any company's real figures. The point is the arithmetic: change the inputs and see which number dominates.

# Back-of-envelope sizing for an ETA service. Every input is an assumption; change them and re-run.
trips_per_day = 5_000_000
app_opens_per_trip = 3          # people open the app more often than they book
products_shown = 4              # an ETA per car type on the home screen
candidates_per_request = 10     # the matcher prices ETA for each nearby driver
trip_minutes = 20
refresh_seconds = 30            # the in-trip ETA is re-predicted every 30 s
peak_factor = 3                 # evening peak vs the daily average

per_trip = (app_opens_per_trip * products_shown + candidates_per_request
            + trip_minutes * 60 // refresh_seconds)
per_day = trips_per_day * per_trip
avg_qps = per_day / 86_400
print(f"ETA predictions per trip   {per_trip}")
print(f"predictions per day        {per_day / 1e6:,.0f} million")
print(f"average / peak QPS         {avg_qps:,.0f} / {avg_qps * peak_factor:,.0f}")

drivers_online_peak = 300_000
ping_seconds = 4
print(f"GPS pings per second, peak {drivers_online_peak / ping_seconds:,.0f}")

days_kept, bytes_per_row = 90, 300
print(f"training rows, {days_kept} days    {trips_per_day * days_kept / 1e6:,.0f} million"
      f" ({trips_per_day * days_kept * bytes_per_row / 1e9:,.0f} GB at {bytes_per_row} bytes per row)")

ETA predictions per trip   62
predictions per day        310 million
average / peak QPS         3,588 / 10,764
GPS pings per second, peak 75,000
training rows, 90 days    450 million (135 GB at 300 bytes per row)

• Predictions dwarf trips. Each trip triggers about 62 predictions, mostly in-trip refreshes ($20\times 60/30=40$) and home-screen ETAs ($3\times 4=12$). 5 million trips become 310 million predictions a day, about 3,600 per second on average and 11,000 at peak.
• The feature pipeline is the bigger stream. 75,000 GPS pings per second at peak must be turned into segment speeds. That is a streaming job, not a batch one.
• Training data is cheap to label and large. Every completed trip is a labelled example, so 90 days is 450 million rows and about 135 GB at 300 bytes each: comfortable for gradient boosting on one large machine or a small cluster.
• Latency is the binding constraint. At 11,000 QPS a 10 ms model is easy to scale horizontally; the hard part is fitting routing, feature fetch and inference into 50 ms at P99 for a batch.

Framing, target and metrics

The target: a regression on minutes

ETA is a regression targetA supervised task whose label is a continuous number, here the travel time in minutes or seconds.: the label is the actual travel time of a completed trip, measured from timestamps in the trip log (driver accepts to driver arrives for a pickup ETA, pickup to drop-off for a trip ETA). Three framing choices matter more than the model:

1. Which time? Pickup ETA, trip ETA and delivery ETA are different targets with different features. Train them separately or give one model a "leg type" feature, but never mix the labels without telling the model.
2. Absolute or relative error? A 3 minute miss is terrible on a 5 minute trip and fine on a 60 minute one. Many teams train on the log of the time, or on the ratio to the routing ETA, so that errors scale with trip length.
3. Predict the residual, not the total. The routing engine already knows a lot. The model's job is the gap between what the map says and what really happens (Deep dive 1).

P50 vs P90 error

The average error is not what riders feel. Look at the error distribution: most trips are within a minute or two, and a long tail of trips are 10 or 20 minutes off (an accident, a missed exit, a long pickup). Report error percentiles:

• P50 absolute error: half of trips are within this many minutes. This is "how good is the typical estimate".
• P90 absolute error: 9 trips in 10 are within this. This is "how bad are the bad days", and it is what drives cancellations and complaints.
• Bias: the mean of actual minus predicted. A model can have a small P50 error and still be late on most trips by a little; riders notice systematic lateness more than noise.

Those are metrics on the error. Separately, you can predict a quantileThe value below which a given fraction of outcomes fall; the 90th percentile travel time is a time that 90 percent of similar trips beat. of the travel time itself. The median prediction is late half the time by construction. A promise like "arrives by 18:50" should come from the 90th percentile prediction, which is late only about 1 trip in 10 (Deep dive 3).

Data and labels

• Labels come free and fast. Unlike fraud, where chargebacks arrive weeks later ( Design a fraud detection system ), the true ETA is known minutes after the trip ends. You can retrain daily and measure live accuracy within the hour.
• Clean them. Drop or flag trips where the label does not measure travel: the rider changed the destination, the driver stopped for fuel, the GPS jumped, the trip was cancelled midway. Keep the rules in code and version them with the dataset.
• Beware survivorship. Cancelled pickups are missing from "completed trips", and they are disproportionately the ones where the driver was much later than quoted. Training only on completed trips teaches the model a world slightly faster than reality. Log the cancelled ones with a censored label ("at least this long") or at least measure how many you drop per slice.
• Point-in-time correctness. Every feature must be the value that was available at prediction time, not the value at trip end. Joining a trip to "the traffic speed on its segments" from the hour after departure is Data leakage in its purest form: offline accuracy will be wonderful and production will not.

Features

Group features by how fast they change, because that decides where they are computed.

The "recent residuals" feature deserves a note: the trips that just finished in an area are the most direct evidence of conditions the map cannot see. It needs a streaming join of trip completions to their original predictions, aggregated per cell over a sliding window. See Geospatial indexing for geo cells and Stream processing for windowed stream aggregations.

High-level design

Fallbacks. If the feature fetch or the model times out, return the routing ETA multiplied by a per-city correction factor computed daily. The ETA is never missing, only less accurate. Make the fallback rate a monitored metric: a silent jump in fallbacks looks like a sudden drop in accuracy.

Batching and caching. The matcher's 10 candidates go to the model as one batch, so inference costs about the same as one call. Cache the routing result for a few seconds per origin cell and destination cell pair; do not cache the final ETA for long, because the real-time features are the point.

Deep dives

Deep dive 1: A residual model on top of the routing engine

The routing engine turns the road network into a road graphA graph whose nodes are intersections and whose edges are road segments, each weighted by its expected traversal time., weights each segment with a travel time (historical speeds blended with live ones) and runs a shortest-path search such as A* or contraction hierarchies. Its answer is good, explainable and available everywhere the map is. What it misses is everything that is not a road segment: the pickup itself, parking, turning delays, the airport loop, the way a whole district slows down in rain.

So do not throw it away and learn travel time from scratch. Use it as the baseline and learn the gap:

where $r(x)$ is the routing ETA, $y$ the actual time and $f_{\theta }$ the residual modelA model trained to predict the error of another model or rule, so that the two added together are more accurate than either alone., usually gradient-boosted trees at first and later a neural network once the feature set and data are large. If errors grow with trip length, use the multiplicative form: train on $\log y-\log r(x)$ and predict $\hat{y}=r(x)e^{f_{\theta }(x)}$.

Why the residual beats a direct model that just gets the routing ETA as one more feature: trees cannot extrapolate. A tree model's prediction is an average of training labels, so it can never predict a trip longer than the longest it has seen. The residual form inherits the routing engine's scale and only learns a correction, which is small, smoother and transfers to new cities and long trips.

The sample below makes a synthetic city where the truth is "routing ETA, slowed by rush hour and rain, plus minutes at airports, plus a long-tailed random delay". It compares the routing engine alone, a gradient-boosted model of the raw travel time, and the same model trained on the residual, with 300 trips (a city that just launched) and 24,000 trips. A last row trains the residual model with quantile loss at 0.9.

# ETA on synthetic trips: routing engine alone vs a direct model vs a model of the residual.
import numpy as np
from sklearn.ensemble import HistGradientBoostingRegressor as GBM

rng = np.random.default_rng(7)
n = 30000
route = rng.gamma(4, 3, n)                       # routing engine ETA in minutes (road graph + traffic)
hour = rng.integers(0, 24, n)
rain = rng.random(n) < 0.15
airport = rng.random(n) < 0.08                   # pickup or drop-off at an airport
rush = np.isin(hour, [8, 9, 17, 18])
# What the engine misses: rush hour and rain slow trips, airports add minutes, the tail is long.
true = (route * (1 + 0.18 * rush + 0.12 * rain) + 4 * airport + rng.gamma(2, 1.0, n) - 1) * rng.lognormal(0, 0.12, n)
X = np.column_stack([route, hour, rain, airport])
te = np.arange(24000, n)
long = route[te] > 30                            # long trips in the test set

def report(name, pred):
    err = np.abs(true[te] - pred)
    print(f"{name:30s} P50 {np.percentile(err, 50):4.1f}  P90 {np.percentile(err, 90):4.1f}  "
          f"long trips {err[long].mean():4.1f}  late {np.mean(true[te] > pred):4.0%}")

print("abs error in minutes on 6,000 test trips")
report("routing engine only", route[te])
for k in [300, 24000]:                           # a new city vs a mature one
    tr = np.arange(k)
    direct = GBM(random_state=0).fit(X[tr], true[tr]).predict(X[te])
    resid = route[te] + GBM(random_state=0).fit(X[tr], true[tr] - route[tr]).predict(X[te])
    report(f"direct model, {k} trips", direct)
    report(f"engine + residual, {k} trips", resid)

tr = np.arange(24000)
q90 = GBM(loss="quantile", quantile=0.9, random_state=0).fit(X[tr], true[tr] - route[tr])
report("engine + residual, 90th pct", route[te] + q90.predict(X[te]))

for name, m in [("rush hour", rush[te]), ("rain", rain[te]), ("airport", airport[te])]:
    print(f"slice {name:9s} mean abs error: engine {np.abs(true[te][m] - route[te][m]).mean():3.1f}"
          f"  engine + residual {np.abs(true[te][m] - resid[m]).mean():3.1f}  ({m.sum()} trips)")

abs error in minutes on 6,000 test trips
routing engine only            P50  1.8  P90  5.7  long trips  4.4  late  76%
direct model, 300 trips        P50  1.8  P90  5.0  long trips 11.7  late  48%
engine + residual, 300 trips   P50  1.7  P90  4.6  long trips  3.7  late  49%
direct model, 24000 trips      P50  1.4  P90  3.8  long trips  3.9  late  44%
engine + residual, 24000 trips P50  1.4  P90  3.8  long trips  3.4  late  44%
engine + residual, 90th pct    P50  3.1  P90  5.9  long trips  6.0  late  11%
slice rush hour mean abs error: engine 3.9  engine + residual 2.0  (1008 trips)
slice rain      mean abs error: engine 3.3  engine + residual 1.9  (872 trips)
slice airport   mean abs error: engine 5.7  engine + residual 2.1  (508 trips)

• The routing engine alone has a P50 error of 1.8 min and P90 of 5.7 min, and is late on 76 percent of trips: it is biased, because it cannot see the delays that only ever add time.
• With 300 trips, the direct model looks fine on the P50 (1.8) but falls apart on long trips (11.7 min mean error): none of its 300 training trips had a routing ETA much over 30 minutes, so it cannot predict anything longer. The residual model on the same 300 trips gets 3.7 min on long trips, better than the engine itself.
• With 24,000 trips the two meet on the P50 and P90 (1.4 and 3.8), and the residual model is still better on long trips (3.4 vs 3.9).
• The slices show where the gain comes from: the residual model cuts mean error from 5.7 to 2.1 minutes at airports and from 3.9 to 2.0 in rush hour, exactly the conditions the map cannot see.

Deep dive 2: The real-time feature pipeline

The features that make ETAs good are minutes old, and the pipeline that produces them is a bigger system than the model.

1. Ingest. Driver apps send GPS pings to a log (Kafka or similar). 75,000 pings per second at peak in our estimate.
2. Map-match. Snap each noisy GPS point to the road segment the car is really on, using the sequence of points, not each one alone. Wrong matches (a highway above a local road) corrupt speeds.
3. Aggregate. Per segment, compute the median speed over a sliding window of a few minutes. Segments with few cars get a blend of the live value and the historical speed for that hour, weighted by how many observations there are.
4. Publish. Write the speeds to the routing engine (edge weights) and to the online feature storeA low-latency key-value store holding the latest feature values for serving, kept consistent with the offline feature definitions used in training., keyed by segment and by geo cell. Write the same values, with timestamps, to the offline log for training.

The key rule is one definition, two stores: the training data must be built from the same feature code, with the value as of prediction time, that serving reads. Otherwise you get training-serving skewA difference between the feature values or logic seen in training and those seen at serving time, which silently degrades a model in production., the most common reason a model that wins offline loses online. Logging the features at prediction time, as in Figure 1, is the simplest way to guarantee it: train on what you actually served. Feature stores in depth are covered in Feature stores and training-serving skew .

Freshness is itself a feature to monitor. Store the age of each real-time value with it; if the stream processor falls behind, the model should see "these speeds are 20 minutes old" (and you should get paged), not quietly treat stale data as live.

Deep dive 3: Quantile predictions and which number to show

A model trained with squared error predicts the mean; with absolute error, the median. To predict the 90th percentile, train with the pinball lossQuantile loss: an asymmetric absolute loss that charges tau per unit of under-prediction and (1 - tau) per unit of over-prediction, so its minimizer is the tau-th quantile. at $\tau =0.9$:

Worked example: the trip really takes 25 minutes. Predicting 20 costs $0.9\times 5=4.5$; predicting 30 costs $0.1\times 5=0.5$. Being late is penalized nine times more, so the model pads its answer until only about 10 percent of trips beat it. In the sample above, the 0.9 residual model is late on 11 percent of test trips: close to the 10 percent it promises, which is the check you run (coverageThe fraction of actual outcomes that fall at or below a predicted quantile; a well calibrated P90 has coverage near 90 percent in every slice.) for every slice.

Which number goes where is a product decision, not an ML one:

• Ranking candidate drivers: the P50. You want the truly closest driver.
• "Driver arrives in 4 min": the P50, rounded. People understand that it is approximate.
• "Arrive by 18:50" or a delivery window: the P90 (or a P50 to P90 range). A promise that is broken half the time is worse than a slightly later one that holds.
• Planning and pricing: the full distribution, or several quantiles, because cost depends on the tail.

Try it

1. Start with the routing engine only on normal trips: 67 percent arrive later than quoted. Switch the trips to airport: 98 percent are late, by 5.1 minutes on average. The engine is not noisy, it is biased.
2. Switch the quote to engine plus residual model at P50. On airport trips lateness falls to 48 percent and the P50 error from 4.7 to 1.5 minutes. Try rush hour and rain: each lands near 50 percent late. That is what a median is.
3. Now drag the quantile to P90. About 10 percent of trips are late in every condition, and the late ones are only about 1.7 minutes late. The price is padding: early trips now arrive 3.3 to 4.0 minutes before the quote, and the P50 error roughly doubles. Which quantile would you put behind "arrives by"?

Going deeper

Evaluation and A/B testing

Offline. Split by time, never at random: train on weeks 1 to 8, test on week 9, because random splits leak the day's traffic between train and test ( Backtesting and forecast evaluation covers backtesting). Report P50 and P90 absolute error, bias and P90 coverage, each broken down by city, hour, trip length and pickup type. A model that improves the global P50 by 2 percent while making airports 10 percent worse is not an improvement.

Online. ETAs change behaviour, so offline error is not the business result. A shorter quote may win more bookings and then cause more cancellations when it is missed. Measure what the ETA is for: booking conversion, cancellation rate after match, rider contacts about lateness, and for the matcher, the actual pickup time of matched trips. ETA models are also used inside matching, which means treatment and control riders compete for the same drivers. User-level A/B tests then leak between groups; marketplaces often use switchback testsAn experiment design that alternates treatment and control over time slices within a region, instead of splitting users, to avoid interference in shared marketplaces. instead, alternating the model per city every 30 or 60 minutes. See Offline vs online evaluation and A/B tests for A/B testing basics.

Monitoring

• Live accuracy. Labels arrive within minutes, so you can chart P50 and P90 error and bias per city every hour. This is a luxury most ML systems lack; use it.
• Coverage drift. The share of trips beating the P90 should stay near 90 percent. A drop to 80 percent in one city is an early warning before riders complain.
• Feature health. Freshness of real-time features, share of segments with live data, fallback rate.
• Known shocks. Holidays, big events, road closures, a new bridge, a map data update. Many of these are scheduled: add them as features (event flag, closure flag) and watch the residuals around them. Unexpected ones show up as a spike in recent residuals, which, nicely, is also a feature: the system partly self-corrects within minutes.

Retraining and drift in general are covered in Monitoring, drift and retraining .

Bottlenecks and failure modes

Trade-offs we made

Extensions

• Uncertainty-aware ranking: rank drivers by a blend of P50 and P90, so a driver behind a bridge that is often jammed loses to a slightly further one on a reliable road.
• Delivery ETA: add a food preparation time model and a courier wait model, and predict the sum as a distribution, not a sum of medians.
• Segment-level learning: feed the model the route as a sequence of segments with their live speeds (a transformer or sequence model) once data and latency budget allow.
• Calibrated intervals by city: conformal prediction on top of the quantile models to guarantee coverage per city.

In the wild

Where you will see this: every ride-hailing, food delivery and maps product shows ETAs built this way, from navigation apps' arrival times to parcel carriers' delivery windows. The pattern of a physics or rules baseline plus a learned residual also appears far outside maps, for example in demand forecasting ( Design a demand forecasting system ) and in correcting simulators with real-world data.

Check yourself

Recap