Key Ideas

• Online retailers need to find cost-effective inventory placement plans that balance variable costs and fixed costs, a challenging problem due to its large scale and computational complexity.
• We design a large-scale optimization framework that solves the problem with a three-step process: aggregating items into clusters, solving the cluster-level problem with column generation, and disaggregating cluster-level solutions into item-level placement plans with a performance guarantee.
• The framework delivers value for businesses through scale (handling millions of items), speed (solving problems 18.77 times faster than the previous industry standard), and savings (reducing the placement cost by 1.7%).

Overview

In online retail, customer orders can be shipped from any fulfillment center, near or far, at different costs. In contrast, traditional brick-and-mortar retail customers are served primarily by the closest physical store. The flexibility of online retail shipping makes it possible to achieve lower costs and higher service levels. However, it also requires all the fulfillment centers to be considered together as a whole rather than in isolation, which increases computational complexity and calls for new inventory optimization techniques.

This case study focuses on the strategic decision of inventory placement, the problem of selecting fulfillment centers in which to place items. We define a placement plan as a chosen subset of fulfillment centers for placing each item, along with an estimate of the inventory levels.

The goal is to determine a cost-minimizing placement plan for each item, while satisfying customer demand requirements and fulfillment center capacity constraints. The objective is to minimize the sum of two types of costs: variable costs and fixed costs.

• Variable costs are proportional to the volume of inventory handled. We focus on the outbound shipping cost, but there may also be other variable costs, such as inbound shipping and receiving costs, or the cost of labor for picking and packing items before outbound shipment.
• Fixed costs are charged when an item is placed at a fulfillment center, regardless of its inventory level. This can represent actual monetary costs, such as a flat-rate inbound delivery cost charged by upstream suppliers for every separate delivery location. Fixed costs also incentivize items to be consolidated in fewer fulfillment centers to reduce logistical overhead, a concept known as “sparsity”. This concept is particularly important for fulfillment centers that have limited containers for carrying unique items, as well as for low-demand items that have few units and should not be split across too many locations.

A good placement plan balances the trade-off between variable costs and fixed costs. On the one hand, placing items in more fulfillment centers can achieve a lower variable cost, as the items can be placed closer to the customers. On the other hand, consolidating items in fewer fulfillment centers incurs a lower fixed cost. Finding a placement plan that achieves the “happy medium” can significantly reduce operational costs, which is crucial for online retail businesses because they often have a low profit margin.

The Challenge

The difficulty of the inventory placement problem arises from its scale and computational complexity in various aspects:

• Large number of items: An online retailer may offer thousands or millions of items in their catalog.
• Large fulfillment network: There may be dozens or hundreds of fulfillment centers, serving hundreds of customer demand regions.
• Fixed costs: Fulfillment fixed costs introduce discrete (binary) variables into the optimization formulation, increasing the computational complexity of the problem.
• Capacity constraints: Fulfillment center capacity constraints create coupling between items because they share the same space. This requires all items to be optimized jointly rather than independently.

To demonstrate the impracticality of a naive solution approach with off-the-shelf software, we solve a small sample problem with a network of 88 fulfillment centers, 99 customer demand regions, and 1,000 items. Using Gurobi, an optimality gap of 6-7% is reached after 5 hours on a personal laptop, and the gap does not improve much after an additional 5 hours. For problems with more items, even constructing the formulation becomes prohibitive in terms of computer memory. Thus, a more efficient approach is needed.

The Solution

We develop a large-scale optimization framework that consists of three main steps (Figure 1):

1. Item aggregation. First, the items are aggregated into clusters based on similarity in demand patterns. In our numerical experiments, we use k-means clustering based on the Euclidean distance between weighted vectors of item attributes. In practice, similarity measures and cluster procedures should be chosen according to the business context. For instance, existing item categorization may naturally lend itself to some partition. Also, if historical demand data identifies certain items that are likely to be purchased together, it may be a good idea to aggregate them in the same cluster, so that they are predisposed to being shipped from the same fulfillment center in one package.
2. Column generation. Next, the cluster-level optimization problem is solved efficiently using the technique of column generation, a specialized, highly efficient technique for quickly solving large problems. We develop a column-based reformulation wherein a column for a cluster is a placement plan in which each customer region is fully served by a single fulfillment center. Intuitively, the columns can be thought of as a set of “bases” that span the solution space of the original cluster-level problem. By only generating and retaining low-cost columns as we go, the reformulated problem can be solved quickly.
3. Cluster disaggregation. Finally, cluster-level solutions are disaggregated into item-level placement plans. Since each cluster contains many items, there is flexibility to perform disaggregation in a way that does not deviate too much from the cluster-level plan.

Mathematically, these three steps can be viewed as a series of approximations that break down the scale and computational complexity of the original item-level placement problem. To ensure that the final approximate solution has a near-optimal cost, we derive mathematical bounds on the optimality gap that can be easily calculated and provide guarantees on the solution quality.

Users have the ability to choose the number of clusters depending on their computational resources. Having more clusters means a more fine-grained approximation and therefore a smaller optimality gap, but it would also require more time and computer memory to solve.

Figure 1

Implementation and Outputs

We demonstrate the effectiveness of this solution framework with a sample problem that consists of 1,000,000 items, to be placed in a network of 88 warehouses serving 98 customer regions in the U.S. (Figure 2). Our program is implemented in Python and Gurobi.

Figure 2

For this sample problem, our large-scale computation framework produces a placement plan in 3.54 hours, with a 0.74% optimality gap (that is, the cost is no more than 0.74% higher than the optimal cost).

We compare our results with a sequential placement heuristic similar to the status quo algorithm used by our industry partner. The heuristic is to place one item at a time, according to some user-specified order. After an item is placed, the remaining fulfillment center capacities are given as input to the placement problem of the next item. The main advantage of the sequential placement heuristic is its simplicity. By placing one item at a time, it avoids the complexity of jointly optimizing a large number of items. The main drawback, however, is that sequentially solving 1,000,000 instances of a simple problem can still take a long time, and that the myopic approach can result in an arbitrarily suboptimal cost.

For the same sample problem, the sequential placement heuristic produces a placement plan with a 2.45% optimality gap in 66.45 hours.

Compared to the status quo heuristic, our solution is 1.7% lower in cost while being 18.77 times faster. (Figure 3)

Figure 3

Results and Business Impact

Our large-scale optimization framework helps online retail companies stay competitive by delivering inventory placement plans with scale, speed, and savings.

• Scale: The solution framework is able to handle large fulfillment networks and millions of items. Even at this scale, it still accurately models a combination of variable and fixed costs, as well as capacity constraints, allowing it to capture different types of realistic business considerations.
• Speed: The solution framework solves the problem in a few hours rather than a few days. This means that decision-makers can re-run the optimization frequently as updated inputs are received, allowing them to respond to changing conditions quickly.
• Savings: The solution framework outperforms status quo heuristics in producing a low-cost placement plan, resulting in cost savings. Moreover, it also produces a performance guarantee (optimality gap) that gives businesses the peace of mind that the placement plan has a near-optimal cost.

Takeaway

Cost-minimizing inventory placement is crucial for reducing the operational cost of online retail businesses. The problem is challenging to solve with off-the-shelf software due to its scale and computational complexity. Our large-scale optimization framework produces low-cost placement plans quickly by utilizing the three-step technique of item aggregation, column generation, and cluster disaggregation. For a large, realistic sample problem, our framework produces a placement plan in 3.54 hours that is within 0.74% of the optimal cost, outperforming the status quo heuristic by being 1.7% lower in cost and 18.77 times faster. Our framework delivers scale, speed and savings for online retail businesses.

This case study was performed by Dr. Chen