Hands-on Tutorials
Optimizing Meal Allocation and Production Strategies for Meal-Kit Services
An algorithmic approach for box services with items that have limited inventory and vary in utility across users.
Quick. We have 15 items and three users. Each user has assigned a unique score to all 15 items. Our task is to divide the number of items equally amongst our users while maximizing the overall score. How do we determine what the best score is? We could iterate through each possible combination, storing the best outcome, although that would result in evaluating close to a million scenarios. Still feasible, but this solution would quickly deteriorate as we add more users or items. Perhaps the question should instead be, how do we efficiently determine what the best score is?
I’ve become a huge fan of meal delivery services over the past year, which has had me pondering the unique problems these services face and how machine learning or optimization may render a solution. This post will detail what I believe is one of the more exciting ideas; optimizing the allocation of meals across users. Note that the context of “optimization” here is not the over-used business terminology to describe an attempt at making things better, but an explicit mathematical optimization; given a list of constraints, the goal is to determine the best available option that maximizes (or minimizes) some objective function.
What is meal delivery?
The meal delivery service is a relatively new business model, originating in Sweden in 2007. In 2012, three meal kit companies entered the United States: Blue Apron, HelloFresh, and Plated. The market has since grown to support around two dozen providers, with each falling under one of two main umbrellas:
- Meal kits — pre-portioned food ingredients and recipes to prepare homecooked meals; sometimes partially-prepared
- Meal delivery — pre-cooked meals; sometimes frozen
Some differences across companies appeal to various consumers, whether it be a specific diet such as keto or paleo or another restriction, such as vegan or vegetarian. Regardless of the amount of pre-preparation included in a meal delivery service, or the underlying meal contents, one thing shared is that they often run on a subscription plan. A customer can choose their meals at some cadence, typically a week, and can skip weeks or altogether cancel if desired.
Reconstructing the problem
Let’s reconstruct the opening query in a more general light under the context of meal delivery. In a given week, a food delivery service will have a list of users, m, and meals, n. While not every user will have scored each meal, we will pretend it is possible to predict an item’s value for each user accurately; I will address how to construct these predictions in a future post on recommendations. We can think of a large m x n matrix, where each entry is the score by user m on meal n.
Note that in the rating matrix, there exists a mix of integers and floats. Since most rating systems exist on an ordinal scale, such as 1 through 5, some scores will be from that integer set representing an explicit assignment by a user. The floats, on the other hand, are unrated items by the user. We have carried out some form of matrix completion to estimate what these scores might be, and, while possible, it is unnecessary to constrain those outputs to be integers themselves. We would be giving up information if we were to perform this binning operation. The realization is that users can only score on a discrete scale, which means that we have a slight misrepresentation of their actual scores. However, in reality, a user might honestly score a meal at 3.5 if given a chance, but the system constrains these choices to make the scoring process more user-friendly. Therefore, in these scenarios, it might be more consistent to set all numbers with a predicted score to represent them on the same distribution; we’ll ignore this nuance.
On top of that, we will need an inventory; there will either be a pre-existing inventory of meals, a plan for preparing new meals, or both. Regardless, we will assume that this inventory is accurate. In theory, the inventory is unbounded so that we could have anything at or above zero. To mix in additional complexity, each user has a set number of meals in their weekly subscription. The bounds here range anywhere from 2–6, which we will also need to consider in our solution. An example of those vectors:
Jumping ahead a bit, we should expect an output matrix of matched dimension, with each entry either being a 1, indicating if we selected the item for the user, or a 0, indicating we did not select the item for them. An example of this is below:
It is important to mention that the assignment of 0’s and 1’s here is arbitrary and does not equate to the optimal solution. In fact, the solution above is not even possible, given the last column. We need to figure out a formulation that can adequately choose which items are “on” or “off.”
To start thinking of that formulation, we need to consider the two primary constraints that we must impose to solve the problem. Unlike our original framing, the number of user-requested meals does not need to equal our inventory. Still, for the problem to be feasible, our stock needs to be at least as large as the number of requested meals. The sums along the vertical axis in the “selection” matrix must be less than or equal to their corresponding element in the inventory vector. We carry out the same summing procedure on the horizontal axis, but the constraint here is more explicit; the number of meals selected for a user should be equal to their desired meal count. In summary, each meal and each user will have a single constraint formula, meaning our system has m + n equations we are not allowed to violate.
We also need to define our objective function, which will be the overall utility based on our customers’ ratings. The element-wise product, more formally known as the Hadamard product, is calculated using the selection matrix and the rating matrix.
From here, a summation across all of the elements determines the value we were able to produce. It should be clear that our objective is to maximize this number while staying within the bounds of our constraints. Putting this all together into mathematical equations looks something like this:
The first line represents what we are trying to maximize, which is the rating times whether the item is selected or not; we use x to represent the selection matrix. The second line represents our constraint on the users’ subscription sizes; for each user, if we sum across the meals that have been selected for them, it should equal their subscription size. The third line represents our constraint on the meal inventories; for each meal, if we sum across the users, the total number of selections should be less than or equal to the inventory. The final line is just a constraint that each user either receives a meal exactly once or not at all.
Solving the problem
Okay, great, we were able to wave our hands and build some fancy-looking, but not really fancy, math equations; how do we solve them?
As with all naive approaches, we could start by randomly assigning meals to users, crossing our fingers that all of the constraints will be met (ha!). If we’re worried about those limitations, we could simulate thousands of these scenarios and hope that at least a few of them would be feasible. Instead of being completely random, we could start with a heuristic approach; assign each user their top-rated recipes, matching their total meal count. Of course, unless each meal’s inventory is unrealistically large, this strategy will violate inventory constraints. We will need to iterate through all overconsumed meals, select a user from that group, perhaps the one with the least to lose from the change and assign them their highest-rated meal that remains in our inventory. We can continue this process until all the constraints are met. However, while this will yield a legitimate solution, it is inefficient and does not guarantee an optimal solution.
Enter binary integer programming.
Anyone who has worked on mathematical optimization will likely recognize that the structure proposed above matches a binary integer program. Still, for those who are unfamiliar with the form, it is the following:
Knowing that we have created a problem with this form, we can use various Python packages, such as Pyomo, OR-Tools, or PuLP, to formulate these optimization models. We can then send this formulation to an optimization solver, such as Gurobi or CPLEX, which will leverage one of several techniques to solve the problem efficiently. While proprietary solvers certainly have more specialized approaches to solving different problems, two standard techniques are cutting planes and branch and bound. While I won’t go into great detail, here are the general ideas behind these approaches. For branch and bound, we conduct a state-space search across candidate solutions, moving down each branch if and only if the bounds suggest a better solution is possible and also feasible. If not, then these branches are effectively pruned. Cutting planes attempt to cull the space differently by adding linear inequalities to refine the feasible set.
Flipping the problem upside-down.
If we had yet to produce any of our inventory and wanted to determine the best meals to maximize customer value, this same strategy would work. However, by removing the inventory constraint, the problem has become unbounded, and the best solution is to make everyone their top meals! Since this is uninteresting, what if we were to impose an overall budget on the meals we can produce. Theoretically, suppose we know all the ingredients associated with a given recipe and each ingredient’s cost. In that case, we should build out the best menu while being constrained to some budget. To do this, we will need a components matrix and a cost vector, such as below:
From those two components, we can calculate the cost of any given meal. Our original objective remains the same, but now instead of an inventory constraint, we have a budget constraint:
If we add up the cost for all the ingredients for all the selected meals, it should be less than some value. As we limit the budget, the optimal solution of meals will change, and the utility provided to the customers will likely drop, although, technically, it could stay the same. An exciting view would be to plot the customer value based on budget to find if there are any clear reasons why the budget should be increased or decreased.
Additional constraints
Likely, the real world is not as simple as we made it out to be in the above formulations, but rest assured that we can set additional constraints to account for these scenarios. For example, if we could buy ingredients in bulk to receive a discount, how might that change the chosen meals? Or perhaps there are production constraints that only allow us to create a certain number of unique meals. Or maybe we want to ensure that certain users we have identified as likely to churn should require more attention in their meal selection. Or suppose we want to make sure any user does not end up with five Italian meals. Overall, we can effectively add any modification to the formulation as a new constraint or revise the objective function to cater towards a different goal.
Final thoughts
Meal-delivery services, similar to all box services, are often constrained on a certain amount of inventory that they can provide to their customers. In these situations, the general approach of assignment is likely a heuristic, but techniques exist within optimization to find better solutions that are also efficient. The main limitation comes in how to formulate that problem, which is not always a trivial task. Hopefully, this post sheds some light on these tools and makes them less daunting for future use!
Note: I have not worked in the meal delivery industry. Many assumptions here will be naive, and the potential for hidden barriers is high. For example, delivery logistics may yield additional constraints, making the problem much more complex or even infeasible altogether. I fully expect most meal delivery companies to be approaching the following issues with a more solid understanding of the real-world nuances than I can hope to detail in this post.
All images by the author unless noted otherwise.
