Instacart: shopper routing

01 · CONTEXT

Delivering groceries on time

Instacart delivers groceries and takes on the challenge of completing each delivery on time and with the right products.

Over a few hours there are thousands of orders to deliver, and doing this efficiently is the job of logistics systems. This case is based on a 2017 post written by a former VP of Data Science at the company, which describes a classic optimization problem combined with machine learning.

02 · THE PROBLEM

From TSP to SCVRPTWMT

The simplest formulation is a traveling salesman problem in which the shopper must go to the store first. With a fleet, each shopper receives a batch of orders to buy and then deliver in sequence, and the problem becomes a VRP, which generalizes the TSP.

Exact algorithms exist for TSP up to tens of thousands of deliveries, and even with millions of deliveries heuristics land within 2–3% of optimal.

The sum of all the constraints is described in the post as an SCVRPTWMT.

03 · FROM GREEDY TO NEW

The fulfillment engine

The starting point was a variation of a greedy algorithm: sort orders by deadline, find the free shopper who can do the first order fastest, look for orders that fit without delay, and dispatch.

Since then the company has introduced new approaches, with a large impact on speed. In the post, minutes per delivery in San Francisco were cut in half, without compromising late deliveries or order quality.

1. One of the changes is to decompose the problem into subproblems, and one of them is batching deliveries.

2. A machine learning model predicts the expected time distribution for each combination of shopper and assignment.

3. Another subproblem is shopper assignment; the subproblems are solved nearly to optimality.

4. Heuristics limit the search space, handle anomalies, refine the solutions, and help adapt to uncertainty.

5. The batch plan is recalculated every minute and the dispatch decision is made at the right time.

04 · THE SURROUNDING SYSTEM

The engine is just one piece

The application that decides which orders each shopper handles is the fulfillment engine, but it is only one component of the logistics system, which also predicts demand and behavior, manages capacity and peak pricing, and plans the schedule.

1. The fulfillment engine is only one of the components of the logistics system.

2. Another component predicts demand and shopper behavior.

3. Another manages capacity and peak pricing.

4. Another plans and adapts the shopper schedule.

5. The systems are highly interdependent, and the company increasingly uses simulations to optimize them together.

05 · GPS DATA

Seeing the system with location data

To optimize shopper assignment and routing, and to communicate with consumers, Instacart collects a GPS data stream stream. Roughly every 10 seconds, the device reports timestamp, latitude and longitude, speed, direction, and accuracy, and the whole adds up to tens of millions of updates per day across the country.

1. The shopper's device periodically reports timestamp, position, speed, direction, and accuracy.

2. The platform collects this stream of location data.

3. Location is used to optimize shopper assignment and routing.

4. The data is also used to communicate well with consumers.

5. Datashader turns millions of points into visualizations that generate hypotheses and confirm changes in production.

In short, the case combines optimization with real constraints, machine learning to estimate times, and field data to analyze the system.