Delivery time estimation (ETA)

01 · CONTEXT AND REQUIREMENTS

Why ETA matters

An ETA is the estimated time of arrival. According to Uber's engineering blog, it is used to compute fares, estimate pickup times, match riders with drivers, and plan deliveries, among other decisions. Building this prediction is a classic problem of ML system design.

To justify replacing the previous model with deep learning, the team had to overcome three main challenges. Latency: the model must return an ETA in a few milliseconds at most. Accuracy: the mean absolute error (MAE) needs to improve significantly over the incumbent XGBoost model. Generality: predictions must hold globally for all lines of business, such as mobility and delivery.

For several years Uber refined ETAs with gradient-boosted decision tree ensembles. A point was reached where growing the dataset and the model with XGBoost became unviable, and the team decided to explore deep learning for the relative ease of scaling to large datasets with data-parallel SGD.

02 · HYBRID APPROACH

Physical route plus learned correction

Traditional routing engines split the road network into small segments, represented by weighted edges of a graph. They use shortest-path algorithms to find the best route and sum the weights to get the ETA.

The limit of this approach is that the road graph is only a model and does not perfectly capture real conditions on the road: the map is not the territory.

The described solution is a hybrid. The physical model is the routing engine, which uses map data and real-time traffic measurements and predicts the ETA as the sum of segment traversal times along the best path. On top of it, machine learning predicts the residual between the router's ETA and the outcomes observed in the real world.

The practical reason for this split is that it is usually easier to incorporate new data sources and keep up with fast-changing business requirements by updating the post-processing model than by refactoring the routing engine itself.

03 · FEATURES

How the features enter the model

The post-processing model considers spatial and temporal features, such as origin, destination, and request time, as well as traffic information in real time and the nature of the request, for example delivery or pickup. This is Uber's highest-QPS (queries per second) model.

DeepETA generates embeddings for all categorical features and discretizes the continuous ones before generating the embedding. Counterintuitively, discretizing the continuous features gave more accuracy than using them directly, and quantile buckets outperformed equal-width buckets.

Origin and destination arrive as latitude and longitude, and the team quantizes these locations into grids of several resolutions. Three strategies were explored for mapping the grids to embeddings.

04 · LATENCY

How to make the model fast

The transformer-based encoder gave the best accuracy, but was too slow for the latency requirements of real-time online serving. The original self-attention has quadratic complexity, and the team chose the linear transformer, which uses the kernel trick to avoid computing the attention matrix.

Another gain comes from sparsity. The model is relatively shallow, with few layers, and the vast majority of parameters are in embedding tables. Although it has hundreds of millions of parameters, each prediction touches only a tiny fraction of them, about 0.25%.

Discretizing the inputs also speeds up serving: mapping latitude and longitude to an embedding is quantizing the coordinates and doing a hash lookup, in constant time. It is the classic space-for-time trade, since large embedding tables learned in training reduce the computation needed at serving time.

05 · GENERALITY AND LOSS

One model for all lines of business

The distribution of absolute errors varies a lot between deliveries and rides, long and short trips, pickup and drop-off, and global mega-regions. For that reason the decoder includes per-segment bias adjustment layers, which correct the raw prediction and improve MAE. The team preferred this layer over a multitask decoder because of latency constraints.

Different use cases call for different point estimates: to compute fares you want an average ETA, controlling for the effect of outliers, and other cases call for a specific quantile of the ETA distribution. To accommodate this diversity, DeepETA uses a parameterized loss function, the asymmetric Huber loss, which is robust to outliers.

06 · SERVING AND RETRAINING

From request to prediction

Once trained and deployed on Michelangelo, the model needs to serve predictions for real-time ETAs. The first diagram shows the path of an online query; the second, the retraining cycle.

1. Consumer requests pass through several services until they reach uRoute.

2. uRoute is the frontend for all routing queries.

3. uRoute asks the routing engine for the route lines and ETAs.

4. With that ETA and other model features, uRoute queries Michelangelo's online prediction service.

5. The prediction service provides the DeepETA model's predictions, which estimate the residual between the router's ETA and the observed outcomes.

1. Periodic automatic retraining workflows train and validate the model.

2. The model is trained and deployed on Michelangelo.

3. With the model deployed, predictions are served to users for real-time ETA.

As a next step, the team mentions exploring continuous and incremental training, which would allow training the ETAs on fresher data.

07 · TRADE-OFFS

Decisions and costs at a glance