Post Syndicated from Sharath Rao original https://spectrum.ieee.org/artificial-intelligence/machine-learning/the-algorithms-that-make-instacart-roll
It’s Sunday morning, and, after your socially distanced morning hike, you look at your schedule for the next few days. You need to restock your refrigerator, but the weekend crowds at the supermarket don’t excite you. Monday and Tuesday are jam-packed with Zoom meetings, and you’ll also be supervising your children’s remote learning. In short, you aren’t going to make it to the grocery store anytime soon. So you pull out your phone, fire up the Instacart app, and select your favorite grocery store. You click through your list of previously purchased items, browse specials, search for a new key-lime sparkling water a friend recommended, then select a delivery window. About 2 hours later, you watch a shopper, wearing a face mask, place bags on your porch.
The transaction seems simple. But this apparent simplicity depends on a complex web of carefully choreographed technologies working behind the scenes, powered by a host of apps, data science, machine-learning algorithms, and human shoppers.
Grocery delivery isn’t a new concept, of course. In our great-grandparents’ day, people could select items at a neighborhood store and then walk home empty-handed, the groceries to follow later, likely transported by a teenager on a bicycle. Customers often had basics like milk and eggs delivered weekly. But with the advent of the fully stocked supermarket, with its broad selection of staples, produce, and specialty foods, customers shifted to selecting goods from store shelves and toting them home themselves, though in some cities local stores still offered delivery services.
Then in 1989, Peapod—followed in the mid-1990s by companies like Webvan and HomeGrocer—tried to revive grocery delivery for the Internet age. They invested heavily in sophisticated warehouses with automated inventory systems and fleets of delivery vehicles. While these services were adored by some for their high-quality products and short delivery windows, they never became profitable. Industry analysts concluded that the cost of building up delivery networks across dozens of large metro areas rapidly ate into the already thin margins of the grocery industry.
Timing, of course, is everything. Cloud computing and inexpensive smartphones emerged in the decade after the launch of the first-generation online grocery companies. By 2012, when Instacart began, these technologies had created an environment in which online grocery ordering could finally come into its own.
Today, retailers like Target and Whole Foods (via Amazon) offer delivery and pickup services, using their existing brick-and-mortar facilities. Some of these retailers run their delivery businesses from warehouses, some pull from the stocked shelves of retail stores, and some fulfill from a mix of both. Small, online-only companies like Good Eggs, Imperfect Foods, and Thrive Market offer curated selections of groceries sourced from local farms and suppliers.
Meanwhile, food and grocery delivery services emerged to bring brick-and-mortar restaurants and stores into the online economy. These businesses—which include DoorDash, Shipt, and Uber Eats in the United States, and Buymie, Deliveroo, and Grofers, based elsewhere—have built technology platforms and fulfillment networks that existing stores and restaurants can use to reach customers online. In this model, the retailer’s or restaurant’s physical location nearest the customer is the “warehouse,” and a community of independent contractors handles fulfillment and delivery.
Our employer, Instacart, is the North American leader in this type of online grocery service, with more than 500 grocers, including Aldi, Costco, Food Lion, Loblaws, Publix, Safeway, Sam’s Club, Sprouts Farmers Market, and Wegmans, encompassing nearly 40,000 physical store locations in the United States and Canada. At the onset of the COVID-19 pandemic, as consumers heeded stay-at-home orders, we saw our order volume surge by as much as 500 percent, compared with the volume during those same weeks in 2019. The increase prompted us to more than double the number of shoppers who can access the platform from 200,000 in early March to 500,000 by year-end.
Here’s how Instacart works.
From the customer’s perspective, the ordering process is simple. Customers start by opening a mobile app or logging on to a website. They enter their delivery zip code to see available retailers. After choosing a store or retail chain, they can browse virtual aisles of produce, deli, or snacks and search for specific products, clicking to add items to an online shopping cart and specifying weights or quantities as appropriate. When finished, they see a list of available 2-hour delivery windows, from later the same day to a week or more in the future. Customers can adjust their orders up until the shoppers start picking their items off store shelves, usually an hour or two before the delivery window. They can enter preferred substitutions beforehand or chat with their shoppers in real time about what’s available. Once the groceries are out of the store and on the move, customers get alerts when their orders are about to be delivered.
That’s Instacart from a customer’s perspective. Behind the scenes, we face huge technical challenges to make this process work. We have to keep track of the products in nearly 40,000 grocery stores—billions of different data points. We have to predict how many of our 500,000-plus shoppers will be online at a given time in a given area and available to work. We have to group multiple orders from different customers together into batches, so that the designated shopper can efficiently pick, pack, and deliver them. When products run out, we suggest the best replacements. Finally, we dispatch shoppers to different delivery addresses along the most efficient route. We’re crunching enormous volumes of data every day to keep the customer-facing Instacart app, our Shopper app, our business management tools, and other software all humming along.
Let’s start with how we keep track of products on the shelf. The average large supermarket has about 40,000 unique items. Our database includes the names of these products, plus images, descriptions, nutritional information, pricing, and close-to-real-time availability at every store. We process petabytes daily in order to keep these billions of data points current.
Back in 2012, when Instacart started making its first deliveries in the San Francisco Bay Area, we relied on manual methods to get this product data into our system. To stock our first set of virtual shelves, our founders and a handful of employees went to a store and purchased one of every item, filling up cart after cart. They took everything back to the office and entered the product data into the system by hand, taking photos with their phones. It worked, but it obviously wasn’t going to scale.
Today, Instacart aggregates product data from a variety of sources, relying on automated rule-based systems to sort it all out. Many stores send us inventory data once a day, including pricing and item availability, while other retailers send updates every few minutes. Large consumer products companies, like General Mills and Procter & Gamble, send us detailed product data, including images and descriptions. We also purchase specialized data from third-party companies, including nutrition and allergy information.
One listing in our database could have information from dozens of sources that must be sorted out. Let’s say a popular apple juice just underwent a rebranding, complete with new packaging. Our system has to decide whether to use the image provided by a third-party data provider last week, the image sent in by the local store last night, or the image submitted by the manufacturer earlier that morning.
Our rules address this problem. Usually images and other data provided by the manufacturer on the morning of a rebrand will be more up-to-date than data provided by individual stores the night before. But what if a store and the manufacturer upload data at about the same time? In this case, our rules tell the system to trust the image provided by the manufacturer and trust the price and availability data provided by the store. Our catalog updates automatically and continuously around the clock to account for all sorts of incremental changes—more than a billion data points every 24 hours on average.
Because Instacart doesn’t own and operate its own stores or warehouses, we don’t have a perfect picture of what is on the shelves of a particular store at any moment, much less what will be there later that day or several days in the future. Instead, we need to make well-informed predictions as we stock our virtual shelves. There’s a lot to consider here. Stores in certain regions may get produce shipments on, say, Monday mornings and meat shipments on Thursday evenings. Some stores restock their shelves periodically throughout the day, while others just restock at night. We’ve built two machine-learning models to help us understand what’s on each store’s shelves and manage our customers’ expectations about what they will actually receive in their grocery bags.
Our Item Availability Model predicts the likelihood that popular items are in stock at any location at any given time. We trained this model using our own data set, which includes millions of anonymized orders from across North America. Some items—like a particular brand of organic eggs, chips, or seasoned salt, or niche items like fresh-made stroopwafels—are considered “active,” meaning they’re regularly ordered year-round from a particular store. “Non-active” items include discontinued products as well as seasonal items like eggnog, Advent calendars, and Peeps marshmallows. The model looks at the history of how often our shoppers are able to purchase the items consumers order most. For each, it calculates an availability score ranging from 0.0 to 1.0; a score of 0.8 means the item has an 80 percent chance of being found in the store by a shopper. We can update this score in real time because our shoppers scan each item they pick up or else mark it as “not found.”
Having this score enables us to reduce the chances our customers will order items that won’t be on store shelves when our shoppers look for them, whether that’s a few hours away or days ahead. We do this in several ways. For example, if a customer’s favorite type of peanut butter has a very low availability score, we will automatically bump that listing down in the search results and, in turn, bump up similar products that have a higher availability score. In these times of supply-chain shortages, we’ll also add “out of stock” labels to affected items and prevent customers from adding them to their carts.
The COVID-19 pandemic pushed our Item Availability Model in a number of other ways and challenged our assumptions about customer behavior. In March 2020, at the start of the U.S. shelter-in-place orders, we saw massive spikes in demand for common household products like toilet paper and disinfecting wipes. Such items were flying off the shelves faster than retailers could stock them. Consumers behaved in new ways—instead of buying their preferred brand of toilet paper, they grabbed any kind of toilet paper they could find. In response, we broadened the number of products our availability model scores to include lesser-known products. We also tweaked the model to give less weight to historical data from several weeks earlier in favor of more recent data that might be more representative of the times.
If a customer adds an item with a low availability score to her cart, a second machine-learning model—our Item Replacement Recommendation Model—gets to work, prompting the customer to select a replacement from a menu of automatically generated alternatives in case the first-choice item isn’t in stock.
Giving customers great replacements is a critical part of making them happy. If you’re shopping in-store for yourself, our research suggests that you’ll have to find replacements for about 7 percent of the items on your list. When Instacart shoppers are shopping for you, they can’t just leave out an item—some items may be critical for you, and if you have to make your own trip to the store after unpacking an Instacart order, you might be less likely to use the service again. But our shoppers aren’t mind readers. If the store is out of your preferred brand of creamy peanut butter, should a shopper replace it with crunchy peanut butter from the same brand? What about a creamy peanut butter from a different brand?
We trained our Item Replacement Recommendation Model on a range of data inputs, including item name, product description, and five years of customer ratings of the success of our chosen replacements. When we present a menu of replacement choices, we rank them according to scores assigned by this model. If you select one of the replacements, we’ll remember it for your future orders; if you don’t, our shopper picks from products our model recommends.
That’s how machine learning helps us set expectations with our customers as they fill their shopping carts. Once an order is placed, another piece of technology enters the picture: the Shopper app. The vast majority of Instacart’s shoppers are independent contractors who have signed up to shop for us, meeting requirements and passing a background check. They drive to the stores, select items off the shelves, check out, and deliver the orders. They can choose to work at any time by logging onto the Shopper app. In certain high-volume stores, we also directly employ part-time shoppers who pick and pack orders and then hand them off to contractors for delivery.
The Shopper app includes a range of tools meant to make it easy to access new orders, address issues that shoppers encounter, and guide checkout and delivery. When shoppers are ready to work, they open up the app and select batches of orders. As they go through the store and fill orders, they can communicate with the customers via in-app chat. The Shopper app suggests an item-picking order to help the shopper navigate the store efficiently. Generally, this picking order puts refrigerated and frozen items, along with hot or fresh deli preparations, near the end of a shopping trip. Meanwhile, customers can watch their shopper’s progress via the Instacart app, tracking each item as it’s scanned into the shopper’s cart, approving replacement items, and viewing yet-to-be-shopped items.
When shoppers check out, they can charge the order to a physical card that Instacart mails to them or use a mobile payments system in the Shopper app. If they encounter a problem, they can communicate with our help team through the app. And when they complete a delivery, they can use the app to transfer their earnings to their bank accounts.
We have many orders coming in at once to the same stores, slated to be delivered in the same general vicinity. In a major metropolitan area, we may get more than 50 orders a minute. So we typically group orders into batches to be picked off store shelves at the same time.
Here, our Matching Algorithm comes into play. This technology applies rules of thumb and machine-learning models to try to balance the number of shoppers with customer demand in real time. The algorithm benefits from scale—the more orders we have in a given area, the more options we can give the algorithm and the better decisions it can make. It considers things like a shopper’s age: If shoppers are not yet 21, they may not be eligible to deliver orders containing alcohol. We rerun the Matching Algorithm as often as every few minutes as we get new information about orders and delivery locations.
The algorithm works hand in hand with our Capacity Model. This model calculates how much delivery capacity we have throughout the day as conditions on the ground change. We used machine learning to build this system; it takes demand predictions based on historical data and historical shopping speeds at individual stores and couples them with real-time data, including the number of shoppers completing orders and the number of orders waiting in a queue for each store. We rerun this model every 2 minutes to ensure that we’re getting a close-to-real-time understanding of our capacity. That’s why a customer may log on at 1:00 pm and see only one late-evening delivery slot remaining, but when they look again at 1:30 pm, they see a host of afternoon delivery slots pop up.
While these models are critical to Instacart’s operation, other tools are crucial for getting the groceries from the store to the customer smoothly and predictably.
Our Drive Time Model uses historical transit times and real-time traffic data to estimate when a shopper will arrive at the store. Our Parking Model calculates how long it can take the shopper to get in and out of a particular store’s parking lot. If a shopper is likely to spend 10 minutes cruising for a spot in a small, crowded parking lot, that needs to be built into delivery-time estimates for that store.
Once the shopper is ready to make deliveries, our Routing Algorithm comes into play. This model is our take on the classic “traveling salesman” problem. Given three customers at three different addresses in the same city, what’s the most efficient route from the store to the first location and from there to the next two? That’s tricky enough, but Instacart has to work with added complexity. For example, in highly dense areas like New York City, some shoppers may walk to their destinations. And we need to ensure that all three deliveries are made within their designated delivery windows—if a customer isn’t home, too early can be just as bad as too late. So our algorithm considers the projected arrival time, using real-time traffic conditions, to create a delivery route. Our system also sends the projected arrival time to the customer and an alert when the shopper is just a few minutes away.
All of our databases, machine-learning models, and geolocation technologies work in concert to build an efficient system. But no model is perfect.
And the COVID-19 pandemic proved to be an unexpected stress test for our systems. As stay-at-home orders rippled across North America, with more data flowing into the platform than ever before, we had to repeatedly reconfigure our databases and tools to keep up with the new demand. At the peak, we found ourselves making upgrades multiple times a week.
We also had to speed up the rollout of a new feature we had just started testing: Leave at My Door Delivery, which allows shoppers and customers to remain socially distant. Shoppers can drop groceries on the porch of a house or the reception or lobby area of an apartment building and send customers a photo of their completed orders at the site.
We are continually looking at ways to optimize our technology and operations. Right now, we are exploring how to improve the suggested picking orders in the Shopper app. Today we rely on a set of rule-based formulas guided by human intuition—for example, that it’s best to pick up fresh vegetables and fruit together, since they’re usually in the same section of the store. But not all stores have the same layout, aisles in a given store can be rearranged, and items may get moved around the store seasonally. We’re hoping we can use machine learning to develop an algorithm that determines such “rhythms” in the way a location should be shopped, based on historical item-picking data along with seasonal additions to store shelves and regular changes in store layouts.
As we add retailers and brands and serve more customers, our algorithms and technologies continue to evolve. We retrain all of our models over and over again to better reflect new activity on our platform. So the next time you click on the Instacart app and order groceries to get you through a busy week, know that anonymized data from your order and from your shopper will get fed into this feedback loop, informing the models we train and the technologies we build.
We are proud that our system has been able to keep groceries flowing to people across North America who have been sheltering at home during the pandemic, especially those who are particularly vulnerable to the novel coronavirus. These are extraordinary times, and we’ve taken our responsibility to serve our customers, shoppers, partners, and corporate employees very seriously, as well as to keep them safe. As the world continues to shop from home, we hope that our investments in machine learning will continue to make it easier for everyone to get access to the food they love and more time to enjoy it together.