Solving Inventory Assortment Problem Using Parametric Cuts
For JD.com, shipping as fast as possible is key to satisfying customers. JD.com is proud to be able to deliver over 90% of its packages in the same or next day. The secret behind this high standard delivery services is JD’s in-house fulfillment capability.
As discussed in our previous post, JD has designed a two-level distribution network and an effective strategy on where to keep which products. JD’s distribution network consists of Regional Distribution Centers (RDCs) and Front Distribution Centers (FDCs) (Figure 1).
The RDC has a large storage capacity so it can ship any product directly to a customer in its region, however, since the coverage area is wide, the package may not be delivered quickly. On the contrary, the FDCs are close to customers and can ship in less than 24 hours. The tradeoff is they cannot hold as many different products.
So, how do we decide which products to keep in the FDC? Well, nobody likes to order a phone and a case online to find out that the case will arrive two days after the phone arrives. Therefore, our goal at JD.com, is to make sure that as many as orders as possible containing one or several products, can be shipped in entirety from the FDC. We call this decision an ‘inventory assortment problem’. We described one solution to this problem using product embedding in a previous post. In this post, we will show how to use network flow optimization to provide an alternative solution to the inventory assortment problem.
The problem we are trying to solve is how to maximize the number of orders that can be shipped entirely from the FDC by selecting up to k products to be placed in the FDC (Figure 2). Though it seems simple, this problem is computationally very hard to solve optimally.
What makes this problem so hard to solve is the capacity constraint — finding exactly k unique products to be placed in the FDC. To simplify the problem, we relax this constraint. Instead of selecting exactly k products, we let λ be the cost to pay for each product placed in the warehouse. This is known as the Lagrangian relaxation of the problem. By removing the capacity constraint and simply adding a cost for placing a product in the FDC, we are left with a selection problem: maximize the number of orders we can fulfill from the FDC minus the cost of the products we selected. The greater the cost, the fewer products we select. We let the cost vary so we can get closer to k.
The relaxation may not sound like a big improvement, however, by enabling us to formulate our problem as a selection problem with given cost parameter λ, it substantially improves the computational efficiency because the selection problem can be formulated as a parametric minimum s-t cut problem, which can be efficiently solved using network flow optimization.
The idea of this algorithm is to embed the transaction data in a graph (Figure 3). On the right-hand side, we create a node for each unique order. These are linked to the sink node t with an arc which capacity is equal to the number of occurrences of the corresponding order (say, the order containing a single item A occurs 10 times and the order containing item A and item C occurs 5 times). The capacity indicates the reward we get for being able to fulfill this order entirely from the FDC. On the left-hand side, we create a node for each unique product. For every product placed in an order, we add an arc from the product node to the order node of capacity infinity. Finally, the source node s is linked to each product node with an arc of capacity λ. This is the penalty we get for including an additional product in the FDC.
In such a graph, a minimum s-t cut separates the nodes in two subsets:
- On the left hand side of the cut, connected to the source node, the so-called Source Set contains the nodes corresponding to products left out of the assortment and missed orders. The arcs linking missed order nodes to the sink node t are, thus, in the cut. Their capacities add up to the sum of missed rewards.
- On the right hand side of the cut, the complementary subset called Sink Set contains the nodes corresponding to products selected in the assortment and fulfilled orders. If a single item in an order is missing from the assortment, an order cannot be fulfilled without having an arc of infinite capacity in the cut. Furthermore, the arcs linking the source node s to selected product nodes are in the cut. Their capacities add up to the total cost of the assortment.
Minimizing this s-t cut indeed minimizes the sum of missed reward and assortment cost. By letting the cost λ of placing a product in the assortment vary, we find nested assortments of products (Figure 4). It is easy to then select a set of products for which the cardinality of the set closely matches k.
We can leverage past information to come up with product placement for a future period. For any given set of orders, our solver outputs a good solution. Assuming the distribution of orders is stationary, we can bootstrap the results to reduce the uncertainty on the input set of orders. We simply sample with replacement orders from the transaction data and average the results we get as output. This creates an optimal set of products to be placed in the FDC to meet future demand.
You may wonder why we came up with such a complicated solution instead of simply selecting the best-selling products. These types of solutions have good performance in practice but are not theoretically sound. Furthermore, our algorithm performs much better with only a few more minutes of computation time. Finally, this method will save several hundreds of millions of customers from receiving a delayed package each year. This is one of the secrets of JD’s fast delivery.
We are open to all kinds of academic research collaborations. Please contact jd_tech_blog@jd.com if you are interested.
