Using Monte Carlo simulations to balance supply and demand in a marketplace
No order left behind; no shopper left idle. - tech-at-instacart
Using Monte Carlo simulations to balance supply & demand in a marketplace.At Instacart, our goal is to make grocery delivery accessible to everyone. In the last 9 months, we grew tremendously from a handful of established markets to over 100+ markets in the US. Such rapid expansion brings a lot of growth potential but also adds more unpredictability to our demand. Offering every customer same day delivery, while keeping our shoppers busy becomes a very hard problem.This post is about how we use Monte Carlo simulations to balance supply and demand in a rapidly growing, high-variance marketplace.Instacart’s service locations progression from Jan 2017 to Sep 2017Supply-Demand EquilibriumBalancing supply and demand is extremely important for any company that is in the business of taking orders and fulfilling them. If demand exceeds supply, we have a system that decides to stop taking orders and that hinders us from honoring our promise of same day delivery. We define the percentage of demand that was lost on a given day as Lost Deliveries.If we have more supply than demand, our shoppers, the couriers who pick/deliver groceries, are left idle and that hurts their earning potential because they complete fewer orders per hour. Our shoppers like being busy and making good use of their time on our platform.Supply < Demand: Lost Deliveries, Supply > Demand: IdlenessIf we had the same demand every day, we would staff exactly the same number of shoppers every day. But there are several factors contributing to unpredictability in our demand and supply, especially in our new markets, and that makes staffing a very hard problem.How do we staff the right number of shoppers in each market on each day for each hour, to make sure we do not lose too many deliveries and also not keep our shoppers idle? What makes this problem so hard? Where is the variance coming from? We will answer all of these questions, but first let’s define the problem we are trying to solve more formally.Problem StatementFor a given market and a given day, how do we staff :number of shoppers at every hourso as to:minimize shopper idlenessminimize lost deliveriesThe final output of this problem looks something like this:We call these numbers Staffing Levels.What makes this problem so hard?VariancesWe have to deal with the standard supply and demand variations, which only intensify during rush hours, hurricanes, snowstorms, Game of Thrones season finales and long weekends. Shopper productivity isn’t uniform either. Some can zip through an order at an item a minute, while some, especially new shoppers, take their time as they get used to the platform and ramp up. Shoppers also have the flexibility to cancel their shifts as needed, which adds even more unpredictability to our supply.Every component below has variance and impacts staffing decisions:ConstraintsThere are several constraints that make the problem even more complicated. Our demand can be fulfilled from different store locations in each city. Stores are open for different hours. Our picking and delivery times can vary based on how busy the stores and streets are. There are constraints on how long a shopper can work with us if they are a part-time employee. We work with 160+ retailers, and often times we have to adhere to retailer specific rules.Unification of objectivesWe must also quantify the costs associated with idleness and lost deliveries, and unify them into a single function to make better staffing decisions. Idleness leads to increased labor costs while lost deliveries lead to losses in revenue. Lost deliveries can also have a long term cost if we lose a potential repeat customer.Heuristics based methods for staffingIn the beginning, we solved this problem using a mixture of forecasting and heuristics based methods. The core idea behind these approaches was based on adaptive course correction:forecast using previous weeks’ staffing numberscorrect for next week based on previous week’s idleness and lost deliveriesadjust for next week’s demand forecast changesBut with these approaches, we would often lose too many deliveries or keep too many of our shoppers idle. The dependencies on prior week’s outcomes can result in a potentially vicious feedback loop by settling at a local optimum. For example, it might be more optimal to put more shoppers in a store location with more order density around it, than at a store that is not as centrally located. Nuances like that are really hard to capture with these approaches.To deal with all this complexity and uncertainty, we decided to try Monte Carlo Simulations.Simulation Based OptimizationMonte Carlo simulation methods offer several advantages for problems like this:no dependencies on previous week’s outcomesmodel complex systems as interactions between random variablesperform stochastic optimization to deal with variances betterThe idea is to simulate a lot of different variations of demand and supply, and solve for a set of staffing levels that minimizes idleness and lost deliveries costs across all of the simulation runs.Each simulation needs to represent a future date for the market we want to staff for. This means that we need orders, stores, locations of shoppers, predictive models to figure out how long it takes to fulfill the orders, and an estimate on how many shoppers are likely to cancel.Simulating OrdersWe first have to start with how many orders we expect on a future date. We have a demand forecasting algorithm that produces a point estimate for demand for each market for each day. But the actual demand doesn’t always match the forecast and is prone to variance. To account for the variability, we build a distribution of our demand forecast based on its error distribution to determine the number of orders we need to fulfill in each simulation.Example of a demand forecast distribution. Mean = Demand Forecast.Let’s say we sample a number from this distribution and it is 3100 deliveries. We then sample those many number of orders from all the orders that have been placed historically in that market.Spatial distribution of demand in a part of San Francisco (noise added on top of actual data)If we do this over and over again, we address both the variance in the number of orders, and also the variance in space and time density.Simulating ShoppersNot every shopper has the same style of working. Some are slow, some are super fast. We model their speeds as a gamma distribution and sample from that. They are also not static in space. They begin their shifts somewhere between their home locations and store locations, and can be anywhere between their last delivery location and a nearest store location during their shifts. By using Markov models, we model distributions of their locations.Staffing for each simulationOnce we bootstrap a simulation with orders, shoppers, and stores, we figure out the ideal staffing required for that simulation.An example of a Simulation bootstrapped with orders, shoppers and stores.We do so by solving our fulfillment problem, which is basically a Vehicle Routing Problem (VRP) with time windows. We use the same algorithm that we actually use to fulfill our orders in a real-time basis, so as to be consistent and make planning match reality as closely as possible.Solve a VRP for each simulationSolving the above problem gives us an optimal set of routes, each of which has a start and end time, based on when they are due and how long it takes to fulfill them. From these optimal routes, we work backwards and figure out how many shoppers we need. This approach also allows us to automatically staff more shoppers in stores that are part of more optimal routes.Example of working backwards from trips to generate staffing levelsExample of number of shoppers required by hour of dayMultiple SimulationsTo account for all the variability, we repeat the above process hundreds of times by repeatedly sampling and solving for staffing in each simulation.Aggregate results from all simulationsSolving For Final Staffing LevelsUltimately we have to solve for one final set of staffing levels that minimizes all our costs. Let’s say x_h (h: 8 AM to 10PM, x_h are integer variables that range from [0, ∞)) represents the number of shoppers required at hour h. The objective is to solve for all x_h.x_h (h: 8AM to 10 PM) are integer variables that determine number of shoppers requiredIn this particular simulation, if x_h take values represented by the red line, in the regions marked with 1️, we overstaff and hence incur an idleness cost. In the regions marked with 2, we understaff and hence incur a lost deliveries cost.By minimizing these costs across all simulation runs, we solve for all x_h:N: number of simulation runsh: hour of dayld_cost: lost deliveries costx_h: non-negative integer variablesl_h,i: shoppers required at hour h in simulation iFinal set of staffing levelsThe red line represents the values of x_h after solving the above optimization problem.ArchitecturePutting everything we discussed so far together, the architecture of our staffing engine looks like this:We have a core simulation engine that runs several scenarios. We then have an optimizer that takes these simulation runs and constructs a final set of staffing levels.ResultsTo test the performance of this approach, we used the staffing levels generated through this approach in production and tracked metrics for our two main objectives: Lost Deliveries and Idleness, and compared them with our previous approaches.Comparing density plots of Lost Deliveries and IdlenessIn our markets that we have historically staffed high to encourage growth, we were able to significantly reduce idleness while maintaining almost the same amount of lost deliveries. This means that we are able to keep growing fast while keeping our shoppers busy and their earning potential high.Lost deliveries remained steady but significantly lower idleness in our new marketsIn markets where we have historically kept staffing tight to maintain a low level of idleness, we were able to lower our lost deliveries while keeping our idleness the same. This makes us even more available for our customers and allows us to grow faster.Idleness remained steady but lower lost deliveries in our more mature marketsThere’s more comingIn a follow up post, we will discuss how we expanded on this approach to staff for hyper-growth and some of the lessons we learnt from doing this project.If you are interested in working on one of the many challenging problems we have at Instacart, check out our careers page.