How Uber Eats Uses Machine Learning to Estimate Delivery Times
Estimating the perfect times for drivers to pick up food delivery orders for a number of different restaurants can be one of the most difficult of computational problems. Think of it like the Traveling Salesperson NP-Hard combinatorial optimization problem: The customer wants food delivered in a timely manner, and the delivery person wants to food ready when they roll-up. If the estimates are off by even a tiny bit, then customers are unhappy and delivery people will work elsewhere.
Yet, car-sharing service Uber is building a global service, called Uber Eats, that will rely on accurate predictions to succeed. The secret to its success will be machine learning, built from the company’s in-house ML platform, nicknamed Michelangelo.
Zi Wang, Uber senior software engineer at Uber who leads the company’s time prediction work, offered a explained at QCON New York last month that explained the process of using AI to make these time estimates.
Launched in 2015 in Toronto, Uber Eats is already available in 400 cities worldwide, with 220,000 participating restaurants. It provides a food delivery service for restaurants, using freelance drivers from its car-sharing service. The ability to predict delivery times — both when the food is ready and how long it takes to deliver it — are paramount to the service’s success. It booked over $8 billion in orders for 2018.
Wang’s lessons could be valuable to other businesses in the emerging O2O (online-to-offline) e-commerce vendors, who must squeeze their profits from narrow and unpredictable tolerances.
Wang started at Uber in 2015 to refine the company’s dispatch system, but the work led him into ML.
The goal of the service is to make food delivery reliable, effortless, and affordable for end-users. “We want to sure the food will be delivered seamlessly, which requires us to predict the future and balance between orders and delivery partners,” Wang said. For each order, the system must make three predictions: the time of delivery, the time it takes to deliver the food, and the time it takes for the restaurant to prepare the order. Predictions are made more difficult, given that Uber doesn’t have any insight into how long it takes for a restaurateur to prepare any given meal.
Timing is the key. Uber Eats wants to dispatch the delivery person to arrive just when the order is ready. If it is too early then the delivery person will wait around unnecessarily, losing money from other possible orders. But wait too long and the food may arrive late, or cold, to the hungry customers.
When users open the app and peruse a selection of restaurants, they are given a general estimate of how long it will take for the food to arrive. It also offers restaurants the ability to estimate of how long it would take the food to be prepared, which the restaurants can adjust if they want.
All data is collected by Kafka and pushed to a streaming engine for pre-processing and storage in a Cassandra data store, where it is processed by Spark for data modeling. Models that are trained and are ready to use are stored in Cassandra model repository.
Finding the optimal state for the dispatch system’s problem space, with so many moving pieces, is a NP hard computer problem, Wang admits. “For every decision we are making, we are taking into consideration all the partners,” Wang said, referring to the eater, the delivery person and the restaurant. The optimal state is one in which each stakeholder gets the most desirable possible outcome: fastest delivery time for the eater, most accurate arrival time for the delivery person, and the most accurate food preparation estimate for the restaurant.
Once an order is placed, the dispatch system must generate the most accurate time to send the driver to the restaurant.
“We want the food delivery partner to arrive at the exact time the food will be ready. We don’t want them to arrive too late because the food will be cold. we don’t want them to arrive too early because they waste their time waiting there, and also they would take the parking and dining spaces from the restaurant,” Wang said.
Prior to ML, Uber Eats used a Greedy algorithm for determining when to dispatch a delivery person, which solved the problem by estimating the best local answer for each delivery, without optimizing the problem space for all the drivers in that area. This did not work well for the service as a whole, as it led to late deliveries and delivery people waiting in the restaurant parking lot for orders to be finished.
A greedy algorithm will simply find the closest driver for a particular order. In contrast, a global optimization would resolve the best times for all the drivers and all the pickups. Wang offered a hypothetical example: A greedy algorithm would match two drivers to their closest orders, for a total travel time of six minutes, might switch the pickups for those two drivers so that the total time for both orders would only be four minutes.
With ML in place, a travel time estimate can be taken from the history of all travel times, and for all restaurants in the area, given all the jobs and all the available drivers. Uber Eats’ approach combines historical data, near-real-time data and real-time data. “With a global matching algorithm, we are able to consider all jobs and supplies at the same time,” he said. “We are able to solve the entire set of jobs and supplies in a single global optimization problem.”
The order preparation time, however, can be tricky, in no small part because there is no way for Uber to be there to see how long it takes the kitchen staff to prepare the food. It can be estimated by when the delivery person leaves the restaurant, though this is of limited value, as the food may already be finished by the time the delivery person arrives.
This is where ML can provide insight, with additional contextual clues, both historical, and in near real-time: This system draws from such factors as average food prep time in the past week, the number of outstanding orders and how much each order cost, and even what day of the week it is. Even real-time indicators can be used, such as how many other orders are being handled at the time, even those from other delivery services.
“Combining all these features helps us make much more accurate predictions than just relying on a single one of them,” he said.
