Decentralized Online Order Fulfillment in Omni-Channel Retailers

Abstract

We consider an order fulfillment problem of an omni-channel retailer that ships online orders from its distribution center (DC) and brick-and-mortar stores. Stores use their local information, not observed by the retailer, that can lead them to accept or reject fulfillment requests of items in an online order. We investigate the problem of sequencing requests to stores and inventory rationing decisions at the DC to minimize expected costs under uncertain store acceptance behavior and when items are indistinguishable in terms of shipping. First, under the scenario that stores are used only when the DC has insufficient inventory, we propose a Markov Decision Process formulation and analyze the performance of myopic policies that are preferable because of their interpretability. We show that the performance rate of a myopic approach that orders stores by cost only depends on the number of items in an order, which is small in practice. We also determine conditions for the range of acceptance probabilities for the myopic policy to be optimal for small-sized orders. Using optimality conditions for a special case of the problem, we develop an adaptive variant of the myopic policy, and propose a new degree-based strategy that balances shipping costs and acceptance probabilities. Numerical testing suggests that the best-performing sequencing policy is within 1% of optimality on average. Moreover, using two years of data from a large omni-channel retailer in North America, we observe that adaptive policies, albeit more complex, are beneficial in reducing costs and split deliveries if acceptance rates can be estimated accurately. Second, we determine when the retailer should ship from stores or ration the inventory at the DC. We show that for single-item orders, the optimal policy has a threshold structure, where, remarkably, the highest priority region is also subject to rationing. We then consider the novel multi-unit-single-item rationing problem, and leverage the structure of the single-unit model to develop a heuristic. We numerically establish the efficacy of rationing models and our heuristic.

1. Introduction

Retail operations have significantly evolved in the last two decades with new online services and accompanying changes in shopping habits, a trend that has accelerated during the coronavirus disease 2019 (COVID-19) pandemic. In the first quarter of 2022, e-commerce sales in the United States increased by US $32 billion compared to the previous two years, with many omni-channel systems combining their brick-and-mortar stores with online shopping services (Fu, 2022). Albeit bringing new operational challenges, such combination also offers opportunities to leverage physical presences in designing flexible and resilient systems (Verhoef et al., 2015).

One opportunity is in the synergy of online order fulfillment. Retailers who dedicate warehouses or distribution centers (DCs) to online orders may also use their brick-and-mortar stores for distribution, a logistic process known as ship-from-stores, or SFS (Hand, 2023). SFS is effective when DCs either have insufficient item availability, or are unable to consolidate all order items in a single shipment (i.e., requiring split deliveries), thus adding to packaging costs and customer inconvenience (Hare, 2022). SFS can also save distribution costs, since regional rates may be cheaper than national shipments from DCs (e.g., Blanco, 2021). Moreover, in some cases, DCs may wish to ration inventory for large sales, such as during the holiday season. These advantages of SFS operations are critical for omni-channel retailers to remain competitive in a constantly growing e-commerce landscape (Ishfaq and Bajwa, 2019; Howland, 2014) and have fostered an active research stream in online order fulfillment (Xu et al., 2009; Acimovic and Graves, 2015; Jasin and Sinha, 2015).

Nonetheless, while the retailer has complete knowledge of the inventory information and logistics controls at DCs, the brick-and-mortar store setting is highly uncertain. First, inventory levels are censored because of the natural in-store reallocation of products as they are manipulated, displayed to customers, or even misplaced due to human errors. Second, employee workload can vary significantly by virtue of seasonal sales, special events, and in-store traffic, reducing their capacity to pick items, package them, and ship the parcels to complete the order processing. Finally, store managers may wish to ration inventory for walk-in customers.

In these scenarios, it is common for stores to reject an order fulfillment request due to the workload or lack of inventory, an event that is also known as a pick-up failure (Das et al., 2023; Difrancesco et al., 2021). The rejection rates are often non-negligible; Figure 1 depicts the percentage of rejections (fully or partially) out of approximately 110,000 orders per year based on data provided by a large-scale retailer in North America, which can reach up to 25% during special sale periods such as Thanksgiving. In these high-rejection periods, prioritizing stores only based on costs (e.g., if those stores are located in the same city as the order’s destination address) could result in multiple split deliveries and higher shipping costs than selecting more expensive stores first.

Figure 1.

Average rejection rates over all stores (100+) of a partnering retailer.

To address these challenges, we investigate a decentralized online order fulfillment system where there exists a single DC and brick-and-mortar stores can accept or reject orders. Based on inventory levels at the DC, the retailer may choose to sequentially place requests to brick-and-mortar stores to fulfill the order. The store may then use its complete inventory and logistics information to ship the order fully, partially (i.e., shipping only some of the items in this order), or reject the request entirely. If the order is rejected or only partially completed, the retailer places a new request at a different store for the remaining items, choosing stores one at a time until the order is completed. The retailer’s objective is to sequence store requests to minimize shipping costs while accounting for store location, uncertainty in fulfillment request, and split deliveries.

This sequential process, first studied by Das et al. (2023), accounts for the fact that SFS is still often a costly process from a store’s perspective. Specifically, despite improvements in inventory visibility, a store employee must physically check if the items in an order are still available, potentially triggering pick-up failures (Pymnts, 2016). Since thousands of orders may be processed daily, the sequential process ameliorates the SFS workload at each location. Moreover, in a setting where requests are placed to multiple stores simultaneously, stores that frequently accept requests but repeatedly are not picked by the retailer may eventually choose to reject orders more often.

Within this context, we investigate both the problem of sequencing stores and inventory rationing decisions at the DC. First, under the scenario that the DC has insufficient inventory for a given order, we formalize the retailer’s problem of sequencing fulfillment requests from stores. More precisely, the retailer knows the order-specific processing costs from each of the available stores, such as shipping and packaging, as well as store acceptance probabilities from estimates based on past orders. After ruling out stores without inventory for the items (according to retailer’s partial information), the retailer selects stores that minimize total expected shipping costs when the number of items accepted per request is uncertain and items have little differentiation in shipping costs and rejection probabilities. One challenge is the scale of modern systems, as large retailers receive hundreds of orders in short periods. For example, our industry partner reported over 5,000 orders per day on average in 2019, and numbers have grown significantly following COVID-19; we therefore focus on low-complexity policies that emphasize scalability and ease of use.

Specifically, we propose a Markov Decision Process (MDP) based on store-dependent acceptance probabilities and consolidated shipping costs, which is adequate when the number of items in an order is small, as consistent with the online retailer setting (Brightpearl, 2017). We investigate theoretical guarantees and structural properties of distinct myopic policies. In particular, we show the approximation ratio of a cost-based myopic policy depends only on the number of items, while a likelihood-based myopic policy can be arbitrarily poor, even when minimizing split deliveries. We also demonstrate that, for a two-item case, the cost-based myopic policy is surprisingly robust to perturbation in the acceptance probabilities, which is particularly relevant if these probabilities are difficult to estimate. Furthermore, we develop more complex policies that incorporate information from the number of items left to ship at each stage of the sequence. Extensions based on delay costs and item-dependent probabilities are also discussed.

Next, we extend our model to incorporate the DC into the fulfillment operations. Specifically, we develop an inventory rationing model where the retailer decides whether the order should be fulfilled from the inventory of the DC, or through the sequential store fulfillment process. In contrast to traditional inventory rationing systems, the DC may still be required to fulfill an order or incur a lost-sale cost, in case stores reject some or all units of the order. We show that, for single-item orders, the optimal policy has a threshold structure that depends on the store shipping and lost-sales costs. Notably, we demonstrate that even the highest-priority orders (i.e., those with highest shipping cost) are often subject to rationing. Finally, we discuss the novel multi-unit-single-item rationing case. We demonstrate the complexity of this problem and leverage the results from the single-item case to introduce an effective heuristic.

To derive further insights, we assess the sequential fulfillment policies numerically on artificial settings and on a case study provided by a retail partner, who implements the decentralized system based on around 100 brick-and-mortar stores in North America. Our data corresponds to approximately 3.2 million online orders received during 2018 and 2019. On artificial settings inspired by the case study, the analysis for orders with few items suggests the cost-based myopic policy is typically 2%–3.5% above optimal, while more complex (adaptive) variants may reduce the average optimality gaps to under 0.5%. We also evaluate the benefits of single-unit rationing policy compared to the strategy that strictly prioritizes the DC, (i.e., no-rationing), and observe 20%–30% decrease in expected costs, on average. We also demonstrate the effectiveness of our heuristic for the multi-unit-single-item case, where we observe average optimality gaps below 4%.

1.1. Main Contributions

Our study considers a decentralized system in omni-channel retailing while incorporating store responses to fulfillment requests placed by the retailer. Our main contributions include: (i) Introducing an MDP model for store sequencing that considers uncertainty in fulfillment requests (see (2)); (ii) providing theoretical analysis of low-complexity and interpretable cost-based and likelihood-based myopic policies (Proposition 1–4); (iii) developing an adaptive policy that simultaneously considers the trade-off between shipping costs and acceptance probabilities (Section 5.3); (iv) providing theoretical analysis of inventory rationing for single-items at the DC (Proposition 7 –10) and introducing a practical heuristic for multi-unit-single-item orders (Section 6.3); and (v) demonstrating the impact of our policies using real-data of a large-scale retailer (Section 7.4).

1.2. Organization

Section 2 reviews the related literature on online order fulfillment and inventory rationing. Section 3 formalizes the problem and presents optimality-preserving conditions that we leverage in our structural results. Section 4 presents a theoretical performance study of interpretable and low-complexity policies, including cases where they match the optimal policy, and Section 5 investigates alternative nonmyopic policies. Section 6 formalizes the inventory rationing problem at the DC and shows the structure of optimal policies for single-item orders. Finally, Section 7 provides the results of numerical experiments performed on synthetic and real data, and Section 8 articulates future directions. We also discuss extensions with delay costs and item-dependent parameters in Section EC.2 in the online supplement. Proofs are included in Section EC.3.

2. Related Works

Research in online order fulfillment is prevalent in the operations management literature. Earlier studies have focused on network design problems that locate depot and stores to enhance distribution processes. Alptekinoğlu and Tang (2005) investigated the assignment of orders among different sales locations, evaluating the trade-off between using the depot and stores to satisfy online demand. Bretthauer et al. (2010) proposed a model to determine which of the fulfillment centers should handle e-sales to minimize logistics costs. Liu et al. (2010) proposed a similar model while keeping the delivery network of the in-store demand unchanged. This paper, in turn, addresses the operation perspective of online order allocation, considering a fixed network and the dynamic aspects of assigning stores to orders consecutively.

Dynamic order fulfillment literature aims to take advantage of the time between order placement and fulfillment, period at which new orders may arrive. There are solution methodologies which periodically re-evaluate the real-time order allocation decisions considering the latest order placements (Xu et al., 2009), demonstrating that accumulating online orders and exploiting inventory level information prior to making real-time allocation decisions reduces shipping and holding costs (e.g., Mahar and Wright, 2009; Mahar et al., 2009). In contrast to our setting, the inventory at stores in these works is known and shipping decisions are fully controlled by the retailer.

Another research stream that this work relates to is online fulfillment process logistics. Acimovic and Graves (2015) and Jasin and Sinha (2015) analyzed the benefits of a forward-looking approach by forecasting the future demand and adjusting the allocation of orders to fulfillment centers. In addition to order allocation decisions, Torabi et al. (2015) highlighted savings by considering inventory transshipment between the order fulfillment centers. They emphasized the computational aspects of their solution, developing a mixed-integer programming model based on Benders decomposition. Our formulations, in turn, emphasizes approximation algorithms that are of polynomial complexity and easy-to-interpret by practitioners.

In the stream of omni-channel retailing, various number of operational problems are studied, such as order fulfillment, inventory management, pricing, and assortment optimization. We refer the reader to the excellent book by Gallino and Moreno (2019) for a comprehensive survey of existing methods and challenges. For further details on alternative order fulfillment strategies of an omni-channel retailer, we refer to the survey by Hübner et al. (2022).

SFS operations of an omni-channel retailer are studied in the literature under various settings (e.g., Difrancesco et al., 2021; Bayram and Cesaret, 2021; Guo and Keskin, 2023). Most relevantly, Das et al. (2023) considered a sequential SFS fulfillment process where store requests are placed one at a time, similar to our framework. The authors study systems with multiple single-item orders and focus on acceptance ratios that depend on inventory levels, assessing the value of the sequential process on a numerical study using U.S. retail data. In this paper, we investigate the sequential process of multi-item orders where orders are processed one at a time, analyzing their theoretical and/or numerical performance. We also incorporate the DC and investigate rationing policies that take store accept/reject decisions into account.

Our formulation is also closely related to classical sequential testing (Ünlüyurt, 2004; Segev and Shaposhnik, 2022). Given a set of components, each with a probability of failure and a testing cost, the goal is to define a sequence of components to test to minimize total expected cost. If a single component failure suffices to fail the entire system (i.e., components are in series), the optimal testing procedure is a bang-per-buck policy that sequences the components in nondecreasing order of the cost-to-failure ratios. For general settings, the complexity of an offline (nondynamic) testing sequence is either unknown (Segev and Shaposhnik, 2022) or NP-Hard in the presence of budget constraints (Boothroyd, 1960). In our context, placing a fulfillment request at a store can be perceived as testing a component, where failure probabilities correspond to acceptance decisions. Similarly, we consider probabilities distributed according to Bernoulli variables that are identical and independent per item. The distinction is in the cost structure. More precisely, if a store rejects all items of an order, no shipping is paid; that is, our setting considers state-dependent costs, while the testing cost is constant in both previous applications. We observe that this distinction affects the structure of the optimal policy for orders with multiple items (see Section 4).

Inventory rationing with multiple demand classes is also pervasive within the operations management literature. Typically, demand is partitioned into high- and low-priority classes, and only high-priority classes are served when the inventory levels drop below a threshold level. Current literature focuses on static policies determining a fixed threshold level (e.g., Melchiors et al., 2000; Deshpande et al., 2003), or dynamic policies where threshold levels vary over time (e.g., Fadıloğlu and Bulut, 2010). Rationed demand may either be backlogged (e.g., Liu et al., 2015; Ding et al., 2016), or lost (e.g., Goedhart et al., 2022). The topic is also studied in make-to-stock production systems, introduced by Ha (1997) with M/M/1 for two demand classes. Subsequent work extended the analysis to M/G/1 with multiple demand classes (e.g., Abouee-Mehrizi et al., 2012), and established the optimality of rationing in special settings (e.g. Baron and Kerner, 2016).

We consider dynamic threshold policies, where demand is neither lost or backlogged, but instead directed to stores to be fulfilled. Our theoretical analysis focuses on the single-item case (e.g., Melchiors et al., 2000; Pang et al., 2014) and, in contrast to existing work (e.g., Deshpande et al., 2003; Alfieri et al., 2017), we establish that even the highest-priority demand class may be subject to rationing because of store rejections. We also address rationing decisions under a multi-unit-single-item system, a problem that has not been previously considered to the best of our knowledge.

3. The Decentralized Order Fulfillment Problem

This section introduces a MDP model in Section 3.1 that captures the sequential nature of the problem and serves as the basis for our structural study and insights. In Section 3.2, we discuss practical aspects of our model and its underlying assumptions.

3.1. Problem Description and Formulation

We consider an omni-channel retailer that fulfills online orders arriving from an e-commerce system. Each order is composed of a set of products, their requested quantities, and a single destination address where all product items must be shipped to. Once an order arrives, the retailer has the flexibility to fulfill it either through its DCs or via brick-and-mortar stores located in distinct geographic areas. We restrict our attention to orders that are not processed by the DCs (e.g., due to lack of inventory) and require stores for fulfillment.

Our formulation assumes an online prescriptive setting where decisions are made immediately upon an order arrival, that is, there exists a single order in the system, and store selections are made prior to the next order arrival. The order contains a list of $m\in {\mathbb{Z}}_{+}$ product items that require shipping; possibly referring to the same stock-keeping unit. In a retailing setting, $m$ is discrete and typically below three on average (Brightpearl, 2017). We exclude ship-alone items, such as microwaves, as they are processed separately by retailers.

When an order is received, the retailer observes an estimate of store inventory levels and produces a set of $n$ stores $\mathcal{N}=\{1,2,\dots ,n\}$ that could ship the $m$ items. A request is then sent to a single store, $i\in \mathcal{N}$ , to fulfill the order. If the store accepts, even if only partially, the retailer pays a fixed cost of $c_i>0$ that captures an average of package consolidation and parcel rates with respect to the destination address; otherwise, no cost is paid, as no shipping occurs. In the scenario whereby items are left in the order, another store is selected from the remaining set, $\mathcal{N}\setminus \{i\}$ , and the process is repeated until either the order is completed or no more stores remain.

The acceptance mechanism is store-dependent and assumes items are equivalent in terms of shipping, that is, probabilities only depend on the number of items left in the order. Thus, we model the number of items $K_{k,i}$ shipped by the $i$ th store for a $k$ -item order as a Binomial random variable with distribution ${\mathbb{P}}_i(j;k):=(\genfrac{}{}{0ex}{}{k}{j})p_i^j{\overline{p}}_i^{k-j},$ for all $j\in \{0,\dots ,k\}$ , where $p_i$ and ${\overline{p}}_i:=1-p_i$ denote an item’s acceptance and rejection probability at store $i$ , respectively.

A policy in this setting is a function $\pi :{\mathbb{Z}}_{+}\times 2^{\mathcal{N}}\to \mathcal{N}$ that, given a state $(k,\mathcal{S})$ composed of $k\in \{1,\dots ,m\}$ items to ship and the set $\mathcal{S}\subseteq \mathcal{N}$ of available stores, chooses a store $i:=\pi (k,\mathcal{S})\in \mathcal{S}$ to place a new fulfillment request. The expected shipping cost of $\pi$ is defined by

$$\begin{array}{r}{V}_{\pi }(k,\mathcal{S}):=\mathbb{E}[\mathbb{1}\{K_{k,i}\ge 1\}{c}_i+V_{\pi }(k-K_{k,i},\mathcal{S}\setminus \{i\})]\end{array}$$

(1)

for all $k>0$ and $|\mathcal{S}|>1$ , where $\mathbb{1}\{C\}$ is the indicator that evaluates to 1 if condition $C$ is true and 0 otherwise, and $\mathbb{E}[\cdot ]$ denotes the expectation of $K_{k,i}$ with respect to probabilities ${\mathbb{P}}_i(\cdot ;k)$ . The process stops either when all items have been shipped, that is, $V_{\pi }(0,\mathcal{S}):=0$ for all $\mathcal{S}$ , or the retailer has exhausted all store options, that is, $V_{\pi }(k,\mathrm{\varnothing }):=g(k)$ for all $k>0$ and some penalty function $g:{\mathbb{Z}}_{+}\to {\mathbb{R}}_{\ge 0}$ representing the loss of customer valuation for not shipping $k$ of the requested items. In particular, since item probabilities are state independent, we can assume $g(k)=0$ for all $k$ without loss of generality. We formalize this insight in Lemma 1.

Lemma 1

The relative ordering of policies with respect to their value function remains the same for any penalty function $g(\cdot )$ .

We wish to find the policy ${\pi }^{*}$ with minimum expected shipping cost; that is, given the set of feasible policies $\mathrm{\Pi }$ , $V_{{\pi }^{*}}(k,\mathcal{S})=V(k,\mathcal{S}):=\underset{\pi \in \mathrm{\Pi }}{min}{V}_{\pi }(k,\mathcal{S})$ . Note that if a policy $\pi$ chooses store $i$ at a state $(k,\mathcal{S})$ , the cost $c_i$ is only paid if at least one item is shipped, which occurs with probability $1-{\mathbb{P}}_i(0;k)=1-{\overline{p}}_i^k$ . Thus, the optimal policy ${\pi }^{*}$ equivalently solves the Bellman equations

$$\begin{array}{rl}& V_{{\pi }^{*}}(k,\mathcal{S})\\ & =\underset{i\in \mathcal{S}}{min}\{(1-{\overline{p}}_i^k)c_i+\sum _{j=0}^{k-1}{\mathbb{P}}_i(j;k)V_{{\pi }^{*}}(k-j,\mathcal{S}\setminus \{i\})\},\\ & \mathrm{\forall }k\in \{1,\dots ,m\},\mathrm{\forall }\mathcal{S}\subseteq \mathcal{N}\setminus \mathrm{\varnothing },\end{array}$$

(2)

where $V(0,\mathcal{S})=0$ for all $\mathcal{S}\subseteq \mathcal{N}$ , $V(k,\mathrm{\varnothing })=0$ for all $k>0$ . Our objective is to approximate $V(m,\mathcal{N})$ and ${\pi }^{*}$ for an initial state of $m$ products and store set $\mathcal{N}$ .

Example 1

Consider a setting where $m=2$ items must be shipped, and there are two available stores, $\mathcal{N}=\{1,2\}$ , with costs $(c_1,c_2)=(\mathrm{\$}10,\mathrm{\$}26)$ and acceptance probabilities $(p_1,p_2)=(0.3,0.9)$ . That is, the first store has lower shipping costs but tends to accept items less often than the second store; this depicts the key trade-off of the retailing system.

Let ${\pi }_1$ be a policy that always picks the cheapest store $1$ first, that is, ${\pi }_1(2,\{1,2\})=1$ . If store $1$ accepts all items, only $c_1=\mathrm{\$}10$ is charged in shipping. If store $1$ rejects all items and store $2$ accepts at least one item, the retailer pays $c_2=\mathrm{\$}26$ . However, if both stores accept exactly one item, we observe the highest cost of $c_1+c_2=10+26=\mathrm{\$}36$ . The total expected cost is $V_{{\pi }_1}(2,\{1,2\})=(1-{0.7}^2)\cdot 10+2\cdot 0.3\cdot 0.7(0.9\cdot 26)+{0.7}^2[(1-{0.1}^2)\cdot 26]=\mathrm{\$}27.54$ . However, if we alternatively start with the most expensive store, we obtain a policy ${\pi }_2$ with cost $V_{{\pi }_2}(2,\{1,2\})=(1-{0.1}^2)\cdot 26+2\cdot 0.9\cdot 0.1(0.3\cdot 10)+{0.1}^2[(1-{0.7}^2)\cdot 10]=\mathrm{\$}26.33$ . Intuitively, ${\pi }_2$ results in cheaper cost because of the high acceptance probability of $p_2=0.9$ . More precisely, ${\pi }_2$ presents a lower likelihood of the store experiencing an order split, incurring a total cost of $c_1+c_2$ .

A sample path from a policy $\pi$ is a store sequence $\{i_1,i_2,\dots ,i_{n^{\prime }}\}$ , $n^{\prime }\le n$ , of requests. A policy $\pi$ is adaptive if for a fixed $\mathcal{S}\subseteq \mathcal{N}$ , the choice of the next store $i\in \mathcal{S}$ at a state $(k,\mathcal{S})$ may change according to $k$ . Conversely, a policy is nonadaptive, thus has a unique sample path, if the store sequence is defined a-priori at the initial state $(m,\mathcal{N})$ . Non-adaptive policies are simpler to implement and often preferable in practice. However, in Section 5, we show that there exists an adaptivity gap (Dean et al., 2008), that is, nonadaptive policies are not necessarily optimal.

In both cases, the formulation (2) has inherent solution and approximation challenges. In the most general adaptive setting, the state-space size is $2^n$ (number of subsets of $\mathcal{N}$ ) times $m$ , and hence it is not trivially addressable by value or policy iteration algorithms when $n$ or $m$ are large. The nonadaptive case is also challenging: the complexity of identifying an optimal sequence remains open, as in related computational questions in sequential testing problems (e.g., Segev and Shaposhnik, 2022). We provide further intuition on its theoretical hardness in our investigation of optimality conditions and extensions in Section 5 and Section EC.2, respectively.

3.2. Model Discussion

We incorporate several choices and assumptions. First, the set of stores $\mathcal{N}$ , probability estimates $p$ , and costs are updated per order, since orders are processed one at a time in an online fashion. However, both $\mathcal{N}$ and $p$ are held constant throughout the sequencing process because the time for store decisions is assumed small. Such information may also not be available to retailers; for example, in our industry partner system the inventory levels at stores are updated only once per week. We also note that inventory data are often inaccurate due to, e.g., displaced inventory in stores. Extensions that incorporate costs due to delays in store decisions are presented in Section EC.2.

Another important modeling assumption is that shipping costs are independent of the number of items in a package. In practice, shipping costs are likely to increase with the size of a fulfillment. However, our data reveal that mailing rates drive the costs when $m$ is small, and shipping a few items from the same store leads to only negligible real-cost deviations from our average estimate $c_i$ for the $i$ th store. Thus, we assume that $c_i$ captures a package consolidation cost; that is, the cost per shipping from each store is constant even if an order is only partially fulfilled.

Next, the number of accepted items in the proposed model is approximated by a Binomial distribution with parameter $p_i$ for each store $i$ . Conceptually, this assumes that items are equivalent from a shipping perspective, and that the acceptance decisions are defined by independent and identically Bernoulli distributions with success $p_i$ . While not general, the resulting model is challenging from a policy perspective and reveals insights on shipping decisions. In particular, this was also a good approximation for our data since acceptance probabilities are mostly correlated with the walk-in busyness level of stores, as also stated on discussions with industry partners. We analyze an extension where probabilities are item-dependent in Section EC.2.2. We also note that it may be difficult to estimate item-dependent probabilities, e.g., in the case of slow-moving SKUs.

Finally, we focus on the case where the number of items $m$ is discrete and small, often significantly smaller than the number of stores $n$ . This is the pervasive case in customer-centric retail operating systems. Brightpearl (2017) reported, for example, that the average number of items in an order in the United States and the United Kingdom in 2017 was 2.26 and 2.48, respectively. In our dataset, this number is 2.84; see details in Section 7.4. We also highlight that, if $m$ is large, policies tend to have little differentiation since the probability of paying shipping cost—the term $(1-{\overline{p}}_i^k)$ in (2)—approximates to 1 as $k$ grows large; that is, splitting occurs with high probability.

4. Analysis of Myopic Policies

In this section, we investigate the theoretical performance of myopic policies based on costs and probabilities. We start in Section 4.1 by demonstrating that ordering stores by cost (from lowest to highest) is optimal for single-item orders. We expand on this analysis in Section 4.2 to show that in the general case, the performance of such a policy only depends on the number of items in the order and not on costs, and we analyze its sensitivity to acceptance rates for two items. Finally, we investigate in Section 4.3 a policy that orders stores by probabilities and minimizes split deliveries.

4.1. The No-Splitting/Single-Item Case

The simplest setting for our analysis originates when no splitting is allowed; that is, a store only accepts an order if all $m$ items can be shipped. This case is equivalent to a single-product variant when the acceptance probability of each store $i\in \mathcal{N}$ is adjusted appropriately (i.e., to $p_i^m$ ). In particular, when $m=1$ , we can simplify (2) to

$$\begin{array}{r}{V}_{{\pi }^{*}}(1,\mathcal{S})=\underset{i\in \mathcal{S}}{min}\{p_i{c}_i+{\overline{p}}_i{V}_{{\pi }^{*}}(1,\mathcal{S}\setminus \{i\})\},\mathrm{\forall }\mathcal{S}\subseteq \mathcal{N}\setminus \mathrm{\varnothing },\end{array}$$

(3)

with $V_{{\pi }^{*}}(1,\mathrm{\varnothing })=0$ . In this setting, the cost $c_i$ is only incurred for the first store $i$ that accepts the item, in which case, the process stops. This implies that it suffices to order the stores from the cheapest to the most expensive to minimize costs, as we show in Proposition 1.

Proposition 1 (Single-item Optimality)

For $m=1$ , it is optimal to select a minimum-cost store at every state; that is, $\pi (1,\mathcal{S})=i$ for some $i\in \mathcal{S}$ such that $c_i\le c_{i^{\prime }}$ for all $i^{\prime }\in \mathcal{S}\setminus \{i\}$ .

Example 2

Let $\mathcal{N}=\{1,2\}$ with $(c_1,c_2)=(\mathrm{\$}1,\mathrm{\$}2)$ and $(p_1,p_2)=(0.2,1)$ . Store $2$ is guaranteed to accept the order, and hence, sending the first request to the store incurs a constant cost of $\mathrm{\$}2$ . Store $1$ , in turn, results in an expected cost of $0.2\cdot 1+0.8\cdot 2=\mathrm{\$}1.8$ . Even if store $1$ has a significantly lower acceptance rate, no shipping cost is incurred for a rejection.

Note that the result in Proposition 1 is counter to sequential testing problems where, for single items, we must prioritize stores with the lowest cost-to-failure ratio $\frac{c_i}{p_i}$ (Ünlüyurt, 2004) because of the fixed cost per store request. In such a setting, the optimal policy necessarily picks store $2$ first because $\frac{2}{1}<\frac{1}{0.2}$ ; this is an instance where such a strategy is not optimal for our setting.

4.2. The Cost-Based Myopic Policy

For any state $(k,\mathcal{S})$ , the cost-based myopic policy ${\pi }_M$ selects a store $i\in \mathcal{S}$ of minimum cost, which is equivalent to sequencing the $n$ stores such that $c_1\le \cdots \le c_n$ . We assume that stores with the same cost are sorted in descending order of their probabilities, that is, high-acceptance stores are prioritized (if several stores have identical costs and probabilities, their order is random). This policy is simple to apply if acceptance probabilities are unknown or difficult to estimate, and managerially intuitive, often prioritizing stores that are closer geographically to the order’s address.

We next analyze the performance of ${\pi }_M$ to evaluate the trade-offs of not incorporating acceptance probabilities. Surprisingly, the approximation rate is not impacted by the store costs $c_i$ , but rather by the number of items $m$ . Intuitively, even if the optimal policy picks an expensive store first because of its higher acceptance probability, the selected store cost must still be sufficiently low for the choice to be beneficial. We formalize this result in Proposition 2. In particular, it also shows that the bound is asymptotically tight in the number of stores $n$ , that is, there is an instance that approximates the given ratio as $n$ grows to infinity.

Proposition 2 (Cost-based Myopic Performance)

The cost-based myopic ${\pi }_M$ is an $k$ -approximation of the optimal value function for any state $(k,\mathcal{S})$ . Moreover, there exists an instance where ${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{V_{{\pi }_M}(k,\mathcal{S})}{V_{{\pi }^{*}}(k,\mathcal{S})}=k,}$ for all $k\le m$ and $\mathcal{S}\subseteq \mathcal{N}$ , that is, the bound is asymptotically tight in the number of stores.

The performance guarantee in Proposition 2 is of interest because, as highlighted in Section 3, the typical number of items per order in e-retailer systems is small. In other words, the worst-case approximation ratio is still bounded in $m$ even if the number of stores is large (for instance, $n\approx 100$ in our dataset, while $m$ is typically between one and three). We also remark that the worst-case depicted in Proposition 2 occurs when the number of stores goes to infinity, in particular when store costs are similar, in which case, ${\pi }_M$ could pick stores with low acceptance probabilities and increase the total cost. Nonetheless, even for large values of $m$ , we observe numerically that the cost-based myopic provides good-quality solutions (see Section 7).

One important insight behind the good performance of ${\pi }_M$ is that acceptance probabilities should not be excessively high for the policy to perform optimally, suggesting some robustness in different probability scenarios. To derive further intuition, we formally show the probability sensitivity of the policy for two-item orders in Proposition 3. The result assumes that stores are ordered by costs and such costs are strictly distinct; the more general case of stores with possibly identical costs is slightly more intricate and is included in the proof of the result in EC.3.

Proposition 3 (Cost-based Myopic Sensitivity)

Suppose $c_1<c_2<\cdots <c_n$ . For $m=2$ and any arbitrary acceptance probability $p_n$ for the $n$ -th store, the cost-myopic policy is optimal if

$$\begin{array}{r}{p}_i\ge {\displaystyle \frac{2c_i}{c_{i+1}+c_i}},\mathrm{\forall }i\in \mathcal{N}\mathrm{\setminus }\{n\}.\end{array}$$

(4)

To illustrate Proposition 3, consider a scenario where $c_i=0.5c_{i+1}$ for $i=1,\dots ,n-1$ ; that is, store costs are half those of their next expensive store. Store probabilities must be at least $p_i\approx 0.67$ for the cost-based myopic to be optimal; that is, stores accept approximately 67% of the fulfillment requests. Conversely, the worst-case scenario occurs when costs are approximately the same, in which case, acceptance probabilities must be close to one. Note that if two stores have the same costs, the acceptance probability of the cheapest store has to be the highest for the policy to be optimal, as such a case is equivalent to minimizing split deliveries (see Proposition 4).

4.3. Likelihood-Based Myopic Policy

The likelihood-based myopic policy ${\pi }_L$ is a nonadaptive strategy that chooses the store with the highest acceptance probability. That is, ${\pi }_L(k,\mathcal{S})=i$ for any $i\in \mathcal{S}$ , such that $p_i\ge p_{i^{\prime }}$ for all $i^{\prime }\in \mathcal{S}\setminus \{i\}$ . As in the cost-based myopic policy, stores with the same probability are sorted in ascending order of cost $c_i$ (ties are broken randomly). However, unlike the cost-based myopic policy, ${\pi }_L$ could perform arbitrarily poorly in general, as we depict in the example below.

Example 3 (Worst-case of likelihood-based policy)

Consider a single-item, two-store instance with $c_1=\mathrm{\alpha }{c}_2$ and $p=(1-ϵ,1)$ for some $\mathrm{\alpha },ϵ\in (0,1)$ . It follows from Proposition 1 that the cost-based myopic policy ${\pi }_M$ is optimal and, from (3), the optimal expected cost is

$$\begin{array}{r}{p}_1{c}_1+(1-p_1)p_2{c}_2=c_2[(1-ϵ)\mathrm{\alpha }+ϵ].\end{array}$$

The policy ${\pi }_L$ , in turn, picks store $2$ first and always results in a cost of $c_2$ since $p_2=1$ . Thus, the cost ratio of ${\pi }_L$ and ${\pi }_M$ , 1/ $(\mathrm{\alpha }-\mathrm{\alpha }ϵ+ϵ)$ , grows to infinity as $\mathrm{\alpha },ϵ\to 0$ .

Despite the potentially poor performance in terms of costs, there is an important sustainability element of ${\pi }_L$ in that it minimizes the number of shipped packages to satisfy an order, an intuitive result formalized in Proposition 4. We observe that this could have practical relevance either in environmentally focused retailing strategies or when store shipping costs are sufficiently close that the operational benefits of reducing shipping outweigh savings in costs.

Proposition 4 (Split Deliveries)

${\pi }_L$ minimizes the number of split deliveries.

Remark 1

It is also possible to define randomized policies that choose a store uniformly at random from $\mathcal{S}$ at any state $(k,\mathcal{S})$ . There are managerial benefits to this approach; such a strategy incurs a mild level of fairness by distributing requests equally among stores in expectation. However, using a similar argument as above, such policy may perform arbitrarily poorly in terms of $\underset{i}{max}{c}_i$ .

5. Adaptive Heuristic Policies

In this section, we propose two adaptive policies that exploit the system dynamics as in related fulfillment methodologies (Xu et al., 2009). We begin in Section 5.1 by demonstrating a necessary and sufficient condition for optimality of the two-store setting. We leverage this condition in Section 5.2 to propose an adaptive variant of the cost-based myopic which preserves its original approximation ratio. Finally, we propose an adaptive heuristic in Section 5.3 that inspects pairwise store orderings.

5.1. Two-store Optimality Conditions and Adaptivity

Consider the setting with $n=2$ available stores and $m\ge 1$ products. Proposition 5 states a necessary and sufficient condition for the optimal policy to pick store $1$ as the first to place a request.

Proposition 5 (Two-store Optimality Condition)

If $n=2$ and $p_1,p_2<1$ , then ${\pi }^{*}(k,\{1,2\})=1,\mathrm{\forall }k\in \{1,\dots ,m\}$ if and only if

$$\begin{array}{r}\frac{c_1}{({\overline{p}}_2+p_1{p}_2{)}^k-{\overline{p}}_2^k}\le \frac{c_2}{({\overline{p}}_1+p_1{p}_2{)}^k-{\overline{p}}_1^k}.\end{array}$$

(5)

One consequence of Proposition 5 is the existence of an adaptivity gap when $n>2$ ; that is, it is not possible to define a store sequencing a priori that matches ${\pi }^{*}$ because the denominators in (5) are neither increasing nor decreasing in $k$ for fixed $p_1$ and $p_2$ . Thus, the ratio ordering in (5) changes with $k$ . Example 4 demonstrates this behavior for $n=3$ .

Example 4 (Adaptivity Gap)

Consider $\mathcal{N}=\{1,2\}$ with $(c_1,c_2)=(\mathrm{\$}1,\mathrm{\$}2)$ and $(p_1,p_2)=(0.2,0.6)$ . When $m=2$ , (5) implies that picking store 1 first is optimal as the inequality evaluates to $9.06\le 9.69$ . However, the inequality evaluates to $13.05\ge 7.50$ when $m=3$ ; hence, starting with store 2 is optimal. Thus, for an instance with store set $\mathcal{N}=\{1,2,3\}$ and $m\ge 3$ where store $3$ is picked first (e.g., when $m=3$ , $c_3=\mathrm{\$}0.9$ and $p_3=0.65$ ), the store to pick at the subsequent state $(k,\{1,2\})$ depends on the value of $k$ observed at the corresponding stage.

The worst-case performance ratio of nonadaptive policies is bounded above by $O(m)$ because of the cost-based myopic (Proposition 2). As suggested by the lack of exploitable structure in the denominators of (5) and the combinatorial state-space growth of (2), extending Proposition 5 to more than two stores may require conditions that are not trivially tractable in $n$ or $m$ .

5.2. Improving the Cost-Based Myopic Policy

We use Proposition 5 to design a low-complexity adaptive variant of the myopic policy. The policy prioritizes the two minimum-cost stores, choosing their ordering based on (5). We show theoretically that this enhanced myopic policy weakly dominates the cost-based myopic policy, that is, it can never perform worse, and numerically also outperforms the nonadaptive policies (see Section 7).

Consider any arbitrary state $(k,\mathcal{S})$ with $k\ge 1$ items to ship across $|\mathcal{S}|\ge 2$ stores. Our improvement consists of choosing two stores consecutively rather than a single store at every state, updating new pairs based on $(k,\mathcal{S})$ and on the criteria specified by (5). Assume that store indices are ordered by costs, that is, $c_1<c_2<\cdots <c_{|\mathcal{S}|}$ . Then, if the optimality condition (5) is satisfied by stores 1 and 2, we keep the same ordering. Otherwise, we swap the positions of these two stores. That is, the policy is of the form ${\pi }_E:{\mathbb{Z}}_{+}\times 2^{\mathcal{N}}\to \mathcal{N}\times \mathcal{N}$ , ${\pi }_E(k,\mathcal{S})=\text{(1,2)}$ if (5) is satisfied, (2,1) otherwise. In other words, for any $(k,\mathcal{S})$ the enhanced myopic policy ${\pi }_E$ picks the first two stores chosen by the myopic policy and uses (5) to possibly improve their order. Once the ordering of the first two stores is fixed, the third and fourth stores chosen by the cost-based myopic policy is evaluated with (5) and the policy continues to order stores accordingly. Since ${\pi }_E$ picks two stores at a time, we must evaluate (2) accordingly. More precisely, if ${\pi }_E(k,\mathcal{S})=(1,2)$ ,

$$\begin{array}{rl}{V}_{{\pi }_E}(k,\mathcal{S})& =(1-{\overline{p}}_1^k)c_1+\sum _{j=0}^{k-1}{\mathbb{P}}_1(j;k)[(1-{\overline{p}}_2^{k-j})c_2\\ & +\sum _{j^{\prime }=0}^{k-j-1}{\mathbb{P}}_2(j^{\prime };j-k)V_{{\pi }_E}(k-j-j^{\prime },\mathcal{S}\setminus \{1,2\})],\\ & \mathrm{\forall }k\in \{1,\dots ,m\},\mathrm{\forall }\mathcal{S}\subseteq \mathcal{N},|\mathcal{S}|>2,\end{array}$$

and $V_{{\pi }_E}(k,\mathcal{S})=V_{{\pi }^{*}}(k,\mathcal{S})$ for the cases where $k=0$ or $|\mathcal{S}|=1$ .

Proposition 6 (Enhanced Myopic Performance)

$V_{{\pi }_E}(k,\mathcal{S})\le V_{{\pi }_M}(k,\mathcal{S})$ for any state $(k,\mathcal{S})$ . Thus, ${\pi }_E$ is an $k$ -approximation policy at $(k,\mathcal{S})$ .

In terms of computational complexity, ${\pi }_E$ requires an extra comparison at every system state to choose the ordering of a pair when constructing the policy. That is, $n/2$ new computations are made in the worst case scenario until all stores are exhausted. This improvement can be implemented in $O(n\log n+n)$ ; that is, it adds a linear term in comparison the cost-based myopic.

5.3. Degree-Based Heuristic Policy

The condition (5) may be used to suggest stores that are less likely to be optimal based on how often such a condition is violated, which enables techniques inspired by classical clique methodologies (e.g., Walteros and Buchanan, 2020). While the resulting policy is presented here as a heuristic, we observed it is the best-performing policy numerically (if probabilities are accurately estimated). More specifically, let $(k,\mathcal{S})$ be an arbitrary state of the system and consider Definition 1:

Definition 1 (Store Precedence Graph)

Let ${\mathcal{G}}_{k,\mathcal{S}}=(\mathcal{S},\mathcal{E})$ be a directed graph with $\mathcal{S}$ and $\mathcal{E}$ as its node and arc sets, respectively. For two stores $i,i^{\prime }\in \mathcal{S}$ , $i\ne i^{\prime }$ , there exists an arc $(i,i^{\prime })\in \mathcal{E}$ , that is, from store $i$ to $i^{\prime }$ , if and only if (5) holds for $i$ as store 1, $i^{\prime }$ as store 2, and $k=m$ .

The graph ${\mathcal{G}}_{k,\mathcal{S}}$ only imposes a partial ordering of $\mathcal{S}$ as it may include cycles (see Example 5). Given a state $(k,\mathcal{S})$ with $|\mathcal{S}|\ge 2$ , let $\mathrm{\Gamma }(i)=\{(i,i^{\prime })\in \mathcal{E}:i^{\prime }\in \mathcal{S},i^{\prime }\ne i\}$ be the set of outgoing arcs in ${\mathcal{G}}_{k,\mathcal{S}}$ associated with store $i\in \mathcal{S}$ . The degree-based heuristic policy assumes stores with a high out-degree are more likely to precede other stores, written as follows:

$$\begin{array}{rl}{\pi }_D(k,\mathcal{S})& =i\text{for any }i\in \underset{i\in \mathcal{S}}{\arg \max }|\mathrm{\Gamma }(i)|,\\ & \mathrm{\forall }k\in \{1,\dots ,m\},\mathcal{S}\subseteq \mathcal{N}\setminus \mathrm{\varnothing }.\end{array}$$

In cases where multiple stores have the same maximum out-degree, the policy first breaks ties by selecting the store with the lowest shipping cost, and then by selecting the highest acceptance probability (further ties are broken randomly).

Example 5 (Non-optimality and Cycles)

Consider $\mathcal{N}=\{1,2,3\}$ with $(c_1,c_2,c_3)=(\mathrm{\$}3,\mathrm{\$}3.4,\mathrm{\$}6)$ , $(p_1,p_2,p_3)=(0.3,0.5,0.8)$ , and $m=2$ . Using (5), we first compare stores 1 and 2, and observe that $4.65\ge 3.91$ , indicating $(2,1)\in \mathrm{\Gamma }(2)$ as store 2 is preferable over store 1. Further comparisons of stores 2 and 3 and stores 1 and 3 result in the following out-degree sets: $\mathrm{\Gamma }(1)=\{\mathrm{\varnothing }\}$ , $\mathrm{\Gamma }(2)=\{(2,1),(2,3)\}$ , and $\mathrm{\Gamma }(3)=\{(3,1)\}$ . We depict this store precedence graph in Figure 2 for visualization. The node labels represent stores, and their respective shipping cost and acceptance probability are depicted next to each node. We represent the precedence relationship by adding a directed arc from a store to the others that are in its out-degree set. According to these, ${\pi }_D(m,\mathcal{N})=2$ , as store 2 has the maximum out-degree $|\mathrm{\Gamma }(2)|=2$ .

Figure 2.

Store precedence graph of the example.

The cost-based myopic policy is such that ${\pi }_M(m,\mathcal{N})=1$ and ${\pi }_M(m,\mathcal{N}\mathrm{\setminus }\{1\})=2$ , with $V_{{\pi }_M}(m,\mathcal{N})=6.38$ . The enhanced myopic policy swaps stores 1 and 2; ${\pi }_E(m,\mathcal{N})=(2,1)$ , as this ordering violates the optimality condition and improves the expected cost to $V_{{\pi }_E}(m,\mathcal{N})=6.27$ . The degree-based policy starts with store 2 as above. If store 2 rejects both items, the degree-based policy selects store 3 next, ${\pi }_D(2,\mathcal{N}\mathrm{\setminus }\{2\})=3$ , from the initial comparison of stores 1 and 3. If store 2 accepts only one item, the degree-based policy selects store 1 based on condition (5) with $k=1$ , ${\pi }_D(1,\mathcal{N}\mathrm{\setminus }\{2\})=1$ . Note that this illustrates the adaptivity of the policy to the value of $k$ . The resulting policy matches the optimal one and has an expected cost of $V_{{\pi }_D}(m,\mathcal{N})=6.20$ .

Consider the same instance where the shipping cost of store 1 is updated as $c_1=\mathrm{\$}2.4$ . Condition (5) now results in the following out-degree sets: $\mathrm{\Gamma }(1)=\{(1,2)\}$ , $\mathrm{\Gamma }(2)=\{(2,3)\}$ , and $\mathrm{\Gamma }(3)=\{(3,1)\}$ and this creates a cycle. In this case, ${\pi }_D(m,\mathcal{N})=1$ , as it has the lowest shipping cost.

Constructing the store precedence graph at a state requires $O(n^2)$ because every store pair must be verified. The graph may need to be recalculated at all states as edges may change directions due to changes in $k$ . Since any sample path includes at most $n$ stores, the total computational complexity of ${\pi }_D$ is $O(n^3)$ if the policy is recalculated at every order.

6. Inventory Rationing at the DC

The discussion so far has focused on cases where fulfillment requests are placed at stores, because the DC was either out-of-stock, or not capable of consolidating all ordered items into a single shipment. In this section, we investigate the more general setting where the DC has sufficient inventory and the retailer must decide whether it should fulfill the order or place requests to stores. Our analysis focuses on inventory rationing policies at the DC for single-item orders, with the goal of determining cost trade-offs between reserving inventory (e.g., for more expensive orders where shipping from stores is prohibitive) and its interplay with the accept/reject process from stores.

We present our rationing model for single-item orders in Section 6.1. Next, in Section 6.2, we demonstrate that the optimal rationing policy follows a threshold structure that is ordered according to the expected store shipping cost $V(\cdot )$ evaluated in previous sections. We also assess the value of the threshold based on lost-sales costs. Finally, in Section 6.3, we briefly discuss the multi-item case and present an efficient heuristic policy that leverages the resulting single-item thresholds.

6.1. Rationing Model

We assume that, at the beginning of the planning horizon, the retailer observes an inventory level at the DC and sequentially receives a set of single-item online orders during a finite horizon $\mathcal{T}:=\{1,2,\dots ,T\}$ . In particular, we assume exactly one order is placed at each period (see, e.g., El Housni and Topaloglu, 2023). Moreover, each order is differentiated by its region $r\in \mathcal{R}$ . At each period, the retailer may fulfill the order through the DC (which we refer to as send) or place a request to stores to reserve the DC’s inventory (which we refer to as reserve).

If fulfilling through stores, we denote by $f(r):=V(1,\mathcal{N})$ the expected shipping costs of the sequencing process studied thus far, where store costs $c_i$ are appropriately adjusted based on the order’s region $r$ . There is a probability $q:=\prod _{i\in \mathcal{N}}{\overline{p}}_i$ of all stores rejecting the item, in which case the DC is forced to ship it from its own inventory if there is enough quantity left. If shipping through the DC, the retailer pays a fixed cost of $c_0$ that is less expensive than the store costs ( $c_0\le c_i$ for all $i\in \mathcal{N}$ ), due to the typical lower processing costs and shipping agreements.

Let ${\lambda }_r$ be the arrival rate of an order from region $r\in \mathcal{R}$ per period, where $\sum _{r\in \mathcal{R}}{\lambda }_r=1$ . That is, at a period $t\in \mathcal{T}$ and current inventory level $x$ , the retailer observes the region $r$ of a new order and decides between the two actions {send, reserve}. We formulate the decision problem via the dynamic process $J(x,t,r)=J_{{\pi }^{*}}(x,t,r)$ , where

$$\begin{array}{rl}{J}_{{\pi }^{*}}(x,t,r)& =min\{c_0+\sum _{r\in \mathcal{R}}{\lambda }_r{J}_{{\pi }^{*}}(x-1,t-1,r),f(r)\\ & +(1-q)\sum _{r\in \mathcal{R}}{\lambda }_r{J}_{{\pi }^{*}}(x,t-1,r)\\ & +q(c_0+\sum _{r\in \mathcal{R}}{\lambda }_r{J}_{{\pi }^{*}}(x-1,t-1,r))\},\end{array}$$

(6)

for all $x\in \mathbb{Z}$ , $x\ge 1$ , $t\ge 0$ , and $r\in \mathcal{R}$ . Given two constants $M_h,M_l\ge 0$ , we also define

$$\begin{array}{rl}{J}_{{\pi }^{*}}(x,0,i)& =M_h\cdot x,\mathrm{\forall }x\ge 0,\mathrm{\forall }r\in \mathcal{R},\end{array}$$

(7)

$$\begin{array}{rl}{J}_{{\pi }^{*}}(0,t,r)& =f(r)+q\cdot M_l\\ & +\sum _{r\in \mathcal{R}}{\lambda }_r{J}_{{\pi }^{*}}(0,t-1,r),& \mathrm{\forall }t>0,\mathrm{\forall }r\in \mathcal{R}.\end{array}$$

(8)

More specifically, the first term in (6) refers to shipping the item from the DC (send), which incurs a cost of $c_0$ plus future expected costs. The second term of (6) refers to shipping from stores (reserve), which incorporate the expected store sequencing cost $f(r)$ . In particular, if some store accepts the item, which occurs with probability $1-q$ , the DC preserves its inventory $x$ . If all stores reject the item, which occurs with probability $q$ , the cost is equivalent to send.

The terminal conditions (7) and (8) represent holding and zero-inventory scenarios, respectively. In other words, if there is inventory left at the store by the end of the period, the retailer pays a holding (or salvage) cost $M_h<c_0$ per unit at hand, as modeled by (7). If the inventory level is zero, then the retailer must necessarily place a shipping request from stores; if all reject, the retailer pays a penalty cost of $M_l$ representing, e.g., lost sales.

In this setting, rationing becomes useful when inventory is scarce. More precisely, if the inventory level is sufficiently high, it is always beneficial to ship from the DC due to its lower shipping cost $c_0$ . Conversely, if $x$ is small relative to $t$ , the retailer may decide to reserve inventory to satisfy a later order that is more expensive to ship from stores, that is, with a high $f(r)$ , as we discuss in Section 6.2. We formalize the result for large inventory levels in Proposition 7.

Proposition 7

If $x\ge t$ , the optimal policy always satisfies orders from the DC, that is,

$$\begin{array}{r}{\pi }^{*}(x,t,r)=\mathtt{s}\mathtt{e}\mathtt{n}\mathtt{d},\mathrm{\forall }x\ge t,r\in \mathcal{R}.\end{array}$$

and $J_{{\pi }^{*}}(x,t,r)=t{c}_0+(x-t)M_h$ .

6.2. Optimal Policy Structure

We next derive the structure of the optimal policy ${\pi }^{*}$ and draw insights concerning optimal rationing decisions. Let $\overline{J}(x,t)=\sum _{r\in \mathcal{R}}{\lambda }_r{J}_{{\pi }^{*}}(x,t,r)$ be the expected cost for a given state $(x,t)$ . We present the basic properties of the value function and $\overline{J}(x,t)$ in Proposition 8.

Proposition 8

The following two properties hold:

$J(x,t,r)$ is nondecreasing in $t$ when $M_h\le c_0$ , and nonincreasing in $x$ .

$\overline{J}(x,t)$ is submodular in $x\le t$ for a fixed $t$ , that is,

$$\begin{array}{rl}\overline{J}(x& -1,t)-\overline{J}(x,t)\le \overline{J}(x-2,t)\\ & -\overline{J}(x-1,t),\text{ for all }2\le x\le t.\end{array}$$

The first property of Proposition 8 states that as there are more periods and demand to satisfy, the shipping cost would increase. Moreover, the shipping cost is also nonincreasing as the inventory level at the DC increases, since the retailer can leverage the lower-shipping option at the DC. The second property, which is crucial to our optimality structure, states that the rate at which expected costs decrease slows down with each additional unit of inventory.

Based on both properties, we show that the optimal policy ${\pi }^{*}$ is a threshold-based strategy. That is, for a given period-region $(t,r)$ pair, there exists a rationing level, $x_R(t,r)$ , such that the optimal policy is to reserve when the inventory falls below $x_R(t,r)$ , and to send otherwise. Furthermore, this threshold is ordered according to $f(r)$ . We formalize the result in Proposition 9.

Proposition 9 (Threshold Policy)

At every period $t>0$ and for every region $r\in \mathcal{R}$ , there exists a rationing threshold $x_R(t,r)$ , such that:

$$\begin{array}{r}{\pi }^{*}(x,t,r)=\{\begin{array}{ll}\mathtt{r}\mathtt{e}\mathtt{s}\mathtt{e}\mathtt{r}\mathtt{v}\mathtt{e},& x\le x_R(t,r),\\ \mathtt{s}\mathtt{e}\mathtt{n}\mathtt{d},& x>x_R(t,r).\end{array}\end{array}$$

Furthermore, for any $r,r^{\prime }\in \mathcal{R}$ such that $f(r)\le f(r^{\prime })$ , $x_R(t,r)\ge x_R(t,r^{\prime })$ for all $t>0$ .

In view of Proposition 9, regions with low and high values of $f(r)$ can be seen as low- and high-priority classes, respectively; that is, orders with low $f(r)$ will have a higher threshold $x_R(t,r)$ and therefore are shipped by stores (i.e., reserve) more often. We provide further insights of the structure of the optimal rationing behavior in Example 6 and Figure 3.

Figure 3.

Threshold inventory levels at each time period for different regions.

Example 6

Let $\mathcal{R}=\{1,2,3\}$ and three stores $\mathcal{N}=\{1,2,3\}$ . We construct an instance where the $i$ -th store is closest to the $i$ -th region. Specifically, for region $1$ , the store shipping costs are $c(1)=(\mathrm{\$}2,\mathrm{\$}7,\mathrm{\$}4)$ ; for region $2$ , the store shipping costs are $c(2)=(\mathrm{\$}7,\mathrm{\$}2,\mathrm{\$}4)$ ; finally, for region $3$ , they are $c(3)=(\mathrm{\$}4,\mathrm{\$}7,\mathrm{\$}2)$ . Store probabilities are fixed to $(p_1,p_2,p_3)=(0.8,0.5,0.2)$ . The expected store fulfillment costs calculated by the cost-myopic policy, which is optimal in this case, are $f(1)=\mathrm{\$}2.32,f(2)=\mathrm{\$}2.74$ , and $f(3)=\mathrm{\$}4.24$ , establishing $f(1)\le f(2)\le f(3)$ , that is, class 1 (region 1) is low priority, class 2 is medium priority, and class 3 is high priority. We set $M_h=1$ and $M_l=50$ .

Figure 3 depicts the threshold values $x_R(t,i)$ over time periods $t\le 10$ for these regions. The illustrated optimal policy rations inventory when the state $(t,x)$ falls below the threshold line for a region, using the DC otherwise. Note that the threshold value of the lower-priority classes ( $1$ and $2$ ) is larger than or equal to the threshold of the higher priority classes(2 and 3) at any given $t$ , as formalized in Proposition 9. The optimal action satisfies orders from the DC at any state $(x,t,r)$ where $x\ge t$ , represented by the red dashed line (Proposition 7). Finally, the highest priority class (class 3) is rationed at optimality, that is, the green line is strictly above $0$ for $t>1$ .

Strikingly, and in contrast to the rationing literature, where the highest priority class is never subject to rationing at optimality, in our setting, it is common for the highest priority region to be rationed, as seen in Example 6. Intuitively, such rationing may occur because of store rejections: There is a positive probability, $q$ , that a rationing request will fail, that is, shipping will be done from the DC. Then, if the DC is out-of-stock after all stores rejected the item, the lost-sales cost $M_l$ may exceed the regular cost. When the inventory at the DC is low, limiting such potential future stock-outs and their associated cost makes rationing (attempting to ship from stores) optimal even for the highest priority class.

To gain further intuition on the optimal multi-level rationing, we note that the magnitude of $M_l$ plays a critical role in the threshold levels. As the lost-sales cost $M_l$ increases, so does the threshold value, as we show in Proposition 10.

Proposition 10

Let $r^{*}:={\arg \max }_{r\in \mathcal{R}}f(r)$ . Then,

If $M_l=0$ , $x_R(t,r^{*})=0$ .

For $0<q<1$ and $t>0$ , $x_R(t,r)=t-1$ for all $r\in \mathcal{R}$ if $M_l\ge M(t):=\frac{f(r^{*})-(1-q^{t-1})\sum _{r\in \mathcal{R}}{\lambda }_{r}f(r)}{q^{t-1}(1-q)}.$

Proposition 10 has the following implications. When there is no cost for lost sales ( $M_l=0$ ), our model reduces to previous rationing problems in that no rationing occurs for the high priority classes. Conversely, if the lost-sales cost $M_l$ is sufficiently high as specified in Proposition 10, the retailer should ration inventory (reserve) for all regions whenever the number of periods to go—and hence the demand—is larger than the inventory level, and otherwise only use the DC when the inventory level is above or equal to $t$ .

6.3. Multi-unit-single-item Orders

Here, we extend the rationing model to multi-unit-single-item orders, a problem that has not been previously considered in the literature to the best of our knowledge. In particular, let $\overline{m}$ be the maximum number of units in an order. We refer to an order from region $r\in \mathcal{R}$ with $m$ units as $r_m$ , which is now associated with an arrival rate of ${\lambda }_{r_m}$ where $\sum _{r\in \mathcal{R}}\sum _{k=1}^{\overline{m}}{\lambda }_{r_m}=1$ . Let ${\mathcal{R}}^{\prime }$ be the set of all possible region-size combinations $\mathcal{R}\times \{1,\dots ,\overline{m}\}$ of $r_m$ . Further, let $q_{k,m}$ be the probability that $k$ units would not be accepted by any store for an order of size  $m$ . The optimality equations in this setting are

$$\begin{array}{rl}{J}_{{\pi }^{*}}(x,t,r_m)& =min\{\phantom{\sum _{k=0}^m}{c}_0+{\overline{J}}_{{\pi }^{*}}(x-m,t-1),f(r_m)\phantom{su{m}_{k=0}^m}\\ & +\sum _{k=0}^m{q}_{k,m}(\mathbb{1}\{k\ge 1\}{c}_0+{\overline{J}}_{{\pi }^{*}}(x-k,t-1))\},\end{array}$$

(9)

for all $x\in \mathbb{Z}$ , $x\ge m$ , $t\ge 0$ , and $r_m\in {\mathcal{R}}^{\prime }$ . The termination conditions (7) and (8) and the definition of $\overline{J}$ are analogous to the above. In particular, (9) now reduces the inventory by $m$ and considers that $k$ units are rejected by all stores and still require shipping.

Analogously to the single-item case, Proposition 7 can be extended to show that the optimal policy ${\pi }^{*}(x,t,r_m)$ is send when $x\ge \overline{m}\cdot t$ . Nonetheless, the problem is significantly more complex and does not present a threshold structure. This occurs because the submodularity property from Proposition 8 no longer holds, that is, the marginal impact of changes in inventory of $x$ does not have a clear structure as a function of the order size $m$ , as demonstrated below.

Example 7

Consider the following setting where $\overline{m}=2$ , $c_0=\mathrm{\$}1$ , $M_l=\mathrm{\$}100$ , $M_h=1$ , and two regions $r$ and $r^{\prime }$ . There are two stores $\mathcal{N}=\{1,2\}$ with $c(r)=(\mathrm{\$}3,\mathrm{\$}8)$ , $c(r^{\prime })=(\mathrm{\$}8,\mathrm{\$}3)$ , and probabilities are fixed to $(p_1,p_2)=(0.8,0.5)$ . We also have $(f(r_1),f(r_1^{\prime }),f(r_2),f(r_2^{\prime }))=(\mathrm{\$}3.2,\mathrm{\$}4.7,\mathrm{\$}4.4,\mathrm{\$}7.4)$ . The arrival rates are $({\lambda }_{r_1},{\lambda }_{r_1^{\prime }},{\lambda }_{r_2},{\lambda }_{r_2^{\prime }})=(0.2,0.15,0.1,0.55)$ .

For $r_1^{\prime }$ at $t=3$ , one can verify that the optimal policy reveals a nonthreshold pattern. Specifically, ${\pi }^{*}(2,3,r_1^{\prime })=\mathtt{r}\mathtt{e}\mathtt{s}\mathtt{e}\mathtt{r}\mathtt{v}\mathtt{e}$ , ${\pi }^{*}(3,3,r_1^{\prime })=\mathtt{s}\mathtt{e}\mathtt{n}\mathtt{d}$ , and ${\pi }^{*}(4,3,r_1^{\prime })=\mathtt{r}\mathtt{e}\mathtt{s}\mathtt{e}\mathtt{r}\mathtt{v}\mathtt{e}$ , whereas with a threshold policy, once the retailer picks send at $x=3$ , it would also select send at inventory levels higher than that, including $x=4$ . Given the optimal policy at state $(3,3,r_1^{\prime })$ , it follows that $c_0+\overline{J}(2,2)=\mathrm{\$}11.09\le f(r_1^{\prime })+q_{0,1}\overline{J}(3,2)+q_{1,1}(c_0+\overline{J}(2,2))=\mathrm{\$}12.07$ .

For the state with one more unit inventory, $(4,3,r_1^{\prime })$ , we compare the following costs: $c_0+\overline{J}(3,2)=\mathrm{\$}7.95$ and $f(r_1^{\prime })+q_{0,1}\overline{J}(4,2)+q_{1,1}(c_0+\overline{J}(3,2))=\mathrm{\$}7.93$ . This shows that the decrease in DC shipping costs ( $\overline{J}(2,2)-\overline{J}(3,2)=\mathrm{\$}3.14$ ) is less than the reduction in store shipping costs (which leads to $\overline{J}(3,2)-\overline{J}(4,2)=\mathrm{\$}4.25$ ). Thus, the marginal benefit to the cost increases with more units of inventory at the DC, that is, submodularity does not hold here in contrast to the single-item case.

The lack of submodularity and consequently the optimal rationing not following a threshold level demonstrated in Example 7 implies that optimizing the rationing decisions in the presence of multiunit orders is very challenging. Therefore, we leverage the single-unit insights to introduce a heuristic policy for the multi-unit case. Conceptually, this algorithm treats an order of size $m$ as a single “bundled” item, and ships it from the DC as a single unit. Under this approximation, if stores reject any number of units during rationing, an $m$ -unit bundle is assumed to be shipped from the DC regardless. Consequently, our bundling policy (BP), denoted as ${\pi }_B$ , solves the following model for all $x\ge m$ , $t>0$ , and $r_m\in {\mathcal{R}}^{\prime }$ :

$$\begin{array}{rl}{J}_{{\pi }_B}(x,t,r_m)& =min\{\phantom{\sum _{k=1}^m{q}_{k,m}}{c}_0+{\overline{J}}_{{\pi }_B}(x-m,t-1),\\ & f(r_m)+q_{0,m}{\overline{J}}_{{\pi }_B}(x,t-1)\\ & +\sum _{k=1}^m{q}_{k,m}(c_0+{\overline{J}}_{{\pi }_B}(x-m,t-1))\},\end{array}$$

(10)

where the boundary conditions are same as before, except (8) is valid for $x<m$ instead of $x=0$ .

We note that this bundling problem has the same structure as the single-item optimality equation (6), and hence the optimal policy yields a threshold for each $r_m\in {\mathcal{R}}^{\prime }$ . The motivation to use this policy is the small number of units typically found in orders. In our case study in Section 7.4, $m$ is on average $1.62$ , and 62% of the orders have only a single unit. Thus, the error of treating multiunits orders as a single unit in (10) tends to be small. In particular, our numerical study in Section 7.8 suggests that the policy performs well for random instances with practical $m$ values. We also remark that, for small values of $t$ , one could still solve the original recursion (9) in computationally reasonable times, which will further improve the accuracy of the heuristic.

7. Numerical Study

We present a numerical study of the store sequencing and inventory rationing policies considering synthetic and real data. We focus on three policies for store sequencing: the cost-based myopic policy (MPC) from Section 4.2, the adaptive variant of the cost-based myopic policy (EMP) from Section 5.2, and the degree-based adaptive heuristic (DBH) policy from Section 5.3. For our inventory rationing study, we perform a numerical analysis of the BP from Section 6.3. In Section 7.1, we assess how empirical performance is affected for varying shipping costs and number of stores when sequencing stores. In Section 7.4, we present a counter-factual analysis based on current fulfillment operations of a partner retailer. Finally, in Section 7.8, we evaluate the empirical performance of the BP policy.

Additional results and detailed tables are included in the electronic companion. In particular, we present results for the likelihood based policy (denoted by PRB) in Table EC.1, which tends to underperform with respect to other policies in view of Example 3. Further, we report additional numerical testing under misspecified probabilities in Section EC.1.

Table 1 presents a summary of the policies we investigate. The column “Policy Description” provides the general policy strategy. “Time Compl.” states their computational complexity assuming that the policy is recomputed per order, and considering all possible computations from the initial state until the order is shipped or all stores are exhausted. Finally, “Approx. Ratio” provides the approximation ratio with respect to the optimal value $V_{{\pi }^{*}}(m,\mathcal{N})$ .

Table 1.

Summary of policies and their respective theoretical performance.

Name	Policy description	Time Compl.	Approx. Ratio
Cost-based myopic ( ${\pi }_M$ )	Order by $c_i$	$O(n\log n)$	$m$
Likelihood-based myopic ( ${\pi }_L$ )	Order by $p_i$	$O(n\log n)$	unbounded
Enhanced myopic ( ${\pi }_E$ )	Pick two minimum stores by $c_i$ , order by (5)	$O(n+n\log n)$	$m$
Degree-based heuristic ( ${\pi }_D$ )	Pick store satisfying (5) more frequently	$O(n^3)$	–

Table 2.

Summary statistics for random cases with $m=2$ and varying numbers of stores $n$ .

		$\mathit{n}=5$			$\mathit{n}=10$			$\mathit{n}=15$
	Cost	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case
Policy	range	(%)	(%)	(%)	(%)	(%)	(%)	(%)	(%)	(%)
MPC	U(1-5)	2.01	21.46	38.34	1.59	17.25	31.90	1.04	14.25	30.23
	U(1-10)	2.69	26.00	41.84	2.33	22.92	49.14	1.90	19.80	38.94
	U(1-25)	3.20	29.14	51.58	3.13	27.08	48.74	2.86	24.26	46.50
	U(1-50)	3.47	29.49	54.18	3.49	30.38	47.97	3.26	28.25	48.44
	U(1-75)	3.53	31.25	53.87	3.50	28.84	46.59	3.39	29.32	50.32
	U(1-100)	3.52	31.20	53.92	3.68	30.77	65.31	3.63	28.97	52.64
EMP	U(1-5)	1.04	17.44	38.34	0.94	15.20	30.29	0.69	12.89	30.23
	U(1-10)	1.42	21.76	41.84	1.33	19.37	49.14	1.13	17.93	38.94
	U(1-25)	1.63	22.67	48.26	1.74	21.36	48.64	1.62	20.50	44.14
	U(1-50)	1.80	23.79	52.73	1.93	25.55	44.95	1.82	23.11	48.38
	U(1-75)	1.90	24.50	50.92	1.99	24.03	45.80	1.86	24.08	48.00
	U(1-100)	1.85	25.16	53.92	2.03	24.29	64.34	2.01	24.00	51.74
DBH	U(1-5)	0.18	5.71	23.64	0.49	11.30	34.90	0.64	13.94	54.31
	U(1-10)	0.16	4.80	36.92	0.44	8.78	49.51	0.59	12.34	58.44
	U(1-25)	0.15	4.32	34.15	0.40	9.39	34.90	0.50	10.75	69.64
	U(1-50)	0.15	4.66	20.99	0.36	8.29	47.63	0.43	9.72	54.06
	U(1-75)	0.15	4.28	24.95	0.36	8.56	36.61	0.44	10.16	64.84
	U(1-100)	0.12	3.92	17.86	0.38	8.78	47.90	0.45	10.00	53.24

7.1. Performance Analysis for Sequential Fulfillment

We compare the performance of the three policies in terms of their relative optimality gaps, that is, how far the observed cost is from the optimal. The optimality gap of a policy $\pi$ is calculated by the ratio $[V_{\pi }(m,\mathcal{N})-V_{{\pi }^{*}}(m,\mathcal{N})]/V_{{\pi }^{*}}(m,\mathcal{N})$ , recalling that $V_{\pi }(m,\mathcal{N})$ and $V_{{\pi }^{*}}(m,\mathcal{N})$ are the expected cost of $\pi$ and the optimal value function, respectively, associated with the MDP (2). The models are solved by a direct backward recursion. We found such a gap provides clearer insights into policy trade-offs. We also report the empirical approximation ratios $V_{\pi }(m,\mathcal{N})/V_{{\pi }^{*}}(m,\mathcal{N})$ in EC.4.

7.1.1. Experimental Setup

The shipping cost in each instance is selected uniformly at random from the discrete set $\{1,2,\dots ,C\}$ , where $C\in \{5,10,25,50,75,100\}$ . The choices of $C$ are based on an analysis of shipping data in North America from our retail partner, where costs vary between $ 4.5–$11 (local shipping), $8–$27 (regional shipping), and $22–$48 (national shipping). We include $C=\mathrm{\$}75$ and $C=\mathrm{\$}100$ to investigate extreme cases. The probability $p_i$ for each store $i\in \mathcal{N}$ is selected uniformly at random from $[0,1]$ . We consider $m\in \{2,3,4\}$ items and $n\in \{5,10,15\}$ stores. For each configuration $(n,m,c)$ , we report the summary statistics of 10,000 samples.

7.1.2. Results

Table 2 and the plots in Figure 4 depict the descriptive statistics and the average optimality gap, respectively, of the three policies for the case $m=2$ , where $U(1,C)$ denotes instances with a cost upper bound of $C$ . The corresponding approximation ratios are in Table EC.1. DBH has the best performance, with average optimality gaps below 0.5% for the majority of instances, and with 99th percentile gaps within 5%–10%. EMP provides better results than MPC, approximately halving the average optimality gap in all configurations. The quality of the approximate policies is inversely proportional to $C$ , as higher variance in costs implies that a wrong store choice is potentially more consequential, especially as MPC only relies on costs. The same behavior is observed as $n$ increases, suggesting policies are less sensitive to the number of stores. However, while the maximum optimality gaps of MPC and EMP aretheoretically 100% (Propositions 2 and 6), this is never achieved for such configurations, and both policies are, on average, below 4%. Furthermore, the 99th percentile gaps for MPC and EMP are below 31% and 26%, respectively. We remark that the worst-case gap observed across all 10,000 replications, albeit rare, can be high; inspection suggests this may occur in instances similar to the worst-case scenario described in Proposition 2.

Figure 4.

Average optimality gaps for random cases with $m=2$ and varying numbers of stores $n$ (in color). (a) $n=5$ ; (b) $n=10$ ;(c) $n=15$ .

Table 3.

Summary statistics for random cases with $n=10$ and varying numbers of items $m$ .

		$\mathit{m}=2$			$\mathit{m}=3$			$\mathit{m}=4$
	Cost	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case
Policy	range	(%)	(%)	(%)	(%)	(%)	(%)	(%)	(%)	(%)
MPC	U(1-5)	1.59	17.25	31.90	6.6	46.37	94.90	10.43	63.7	128.83
	U(1-10)	2.33	22.92	49.14	8.65	56.21	126.49	12.94	76.1	177.01
	U(1-25)	3.13	27.08	48.74	7.86	52.29	96.69	11.95	71.19	133.21
	U(1-50)	3.49	30.38	47.97	5.11	40.68	72.63	8.33	57.46	105.28
	U(1-75)	3.50	28.84	46.59	8.27	57.61	88.26	12.39	78.15	118.49
	U(1-100)	3.68	30.77	65.31	8.32	54.19	89.17	12.49	72.13	121.40
EMP	U(1-5)	0.94	15.20	30.29	4.09	42.34	94.90	6.88	58.3	128.83
	U(1-10)	1.33	19.37	49.14	5.24	48.65	123.60	8.32	66.05	171.85
	U(1-25)	1.74	21.36	48.64	4.75	45.74	95.78	7.67	62.15	130.72
	U(1-50)	1.93	25.55	44.95	3.37	37.94	72.63	5.97	54.16	105.28
	U(1-75)	1.99	24.03	45.80	4.99	50.93	82.47	7.92	67.40	118.49
	U(1-100)	2.03	24.29	64.34	5.16	46.92	85.56	8.19	63.51	119.03
DBH	U(1-5)	0.49	11.30	34.90	1.23	24.49	69.74	1.72	32.45	85.30
	U(1-10)	0.44	8.78	49.51	1.00	22.17	82.03	1.58	34.13	94.13
	U(1-25)	0.40	9.39	34.90	1.09	23.54	119.39	1.77	35.16	113.57
	U(1-50)	0.36	8.29	47.63	1.16	24.61	74.87	1.59	32.66	75.77
	U(1-75)	0.36	8.56	36.61	0.98	21.70	107.03	1.68	33.30	106.97
	U(1-100)	0.38	8.78	47.90	1.00	21.20	66.56	1.54	30.41	113.11

Table 3 and Figure 5 depict similar metrics for a varying number of items $m$ and $n=10$ stores. The corresponding approximation ratios are in Table EC.2. Results for $n=5$ are also qualitatively similar and they are presented in Table EC.3. The increase in average optimality gaps is more pronounced as $m$ grows, especially because of the higher likelihood of split deliveries. However, DBH is still below 2%, on average, and its 99th percentile gap is below 20%. MPC generates sequences that are 5%–12% from optimal, on average, for $m=\{3,4\}$ , with 99th percentile gap of, at most, 78% across all cases, whereas EMP finds solutions within 4%–8%, on average, from the optimal value for the same settings and has 99th percentile gap of, at most, 67%.

Figure 5.

Average optimality gaps for random cases with $n=10$ and varying numbers of items $m$ (in color). (a) $m=2$ ; (b) $m=3$ ;(c) $m=4$ .

Additionally, we evaluate the robustness of our algorithms under conditions involving item-dependent probabilities. The policies are adapted with these probabilities as follows: For MPC, ties are broken in favor of the store that has the highest maximum acceptance probability across all items. For EMP and DBH, the store degrees are determined for each item separately; these values are then summed to determine the final degree scores. Given that the number of items plays a critical role, we examine cases where $n=5$ and $m=\{2,3,4\}$ . For consistency, we maintain the experimental setup used for determining shipping costs. Acceptance probabilities for each item at each store, denoted by $p_{ij}$ , are generated uniformly at random from $[0,1]$ . Average optimality gaps and summary statistics of 10,000 samples are reportedbelow.

Table 4 and Figure 6 depict the same metrics for distinct number of items $m$ and $n=5$ stores. For $m=2$ , all algorithms maintain similar performance for this benchmark as in the store-dependent case, with an average performance of within 3% across all settings. As the number of items increases, the average performance of MPC and EMP increases, whereas DBH exhibits minimal increases in average gaps. Specifically, DBH maintains an average gap below 2%, on average, and its 99th percentile gap continues to be under 20%.

Table 4.

Summary statistics for random cases with $n=5$ , varying $m$ and item dependent acceptance probabilities.

		$\mathit{m}=2$			$\mathit{m}=3$			$\mathit{m}=4$
	Cost	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-Case
Policy	Range	(%)	(%)	(%)	(%)	(%)	(%)	(%)	(%)	(%)
MPC	U(1-5)	3.02	30.17	70.00	4.80	33.03	57.05	6.08	34.88	82.96
	U(1-10)	2.78	28.41	70.63	4.85	34.62	68.46	5.77	35.44	81.96
	U(1-25)	2.72	27.63	62.04	4.62	35.08	99.91	5.59	34.26	93.14
	U(1-50)	2.85	28.67	59.37	4.59	34.01	99.34	5.64	33.97	71.06
	U(1-75)	2.82	29.50	73.52	4.56	35.21	96.82	5.74	35.09	77.08
	U(1-100)	2.67	27.08	59.18	4.57	35.32	72.30	5.95	37.66	80.36
EMP	U(1-5)	2.78	29.91	70.00	3.31	27.44	56.70	4.23	27.74	76.43
	U(1-10)	2.34	26.41	70.63	3.32	29.18	67.82	3.93	27.86	75.72
	U(1-25)	2.20	25.58	62.04	3.14	27.84	84.35	3.75	26.07	58.28
	U(1-50)	2.27	26.32	59.37	3.11	27.80	76.21	3.72	26.74	74.19
	U(1-75)	2.19	25.63	73.52	3.15	28.87	80.17	3.74	26.94	56.46
	U(1-100)	2.19	24.49	49.22	3.00	27.76	65.27	3.85	29.49	67.69
DBH	U(1-5)	1.13	17.04	50.76	1.64	17.82	45.80	1.95	16.85	79.15
	U(1-10)	1.14	16.52	61.15	1.49	15.98	57.25	1.82	16.76	85.93
	U(1-25)	0.95	14.09	51.69	1.41	14.69	86.23	1.64	14.33	45.81
	U(1-50)	0.95	14.46	51.83	1.37	15.11	58.24	1.66	15.11	50.86
	U(1-75)	0.95	14.17	47.07	1.35	14.71	50.68	1.65	15.53	58.08
	U(1-100)	0.93	13.62	41.64	1.32	14.90	39.34	1.61	14.73	47.44

Figure 6.

Average optimality gaps for random cases with $n=5$ and varying numbers of items $m$ (in color). (a) $m=2$ ; (b) $m=3$ ;(c) $m=4$ .

7.2. Case Study for Sequential Fulfilment

The retailer’s network consists of a single DC dedicated to online order fulfillment and approximately 100 brick-and-mortar stores throughout North America. The data includes online order transactions over a two-year span (2018 and 2019). Each order contains a timestamp, estimated shipment times, fulfillment location, quantity, and customer address. Furthermore, each order also contains the full history of acceptance and rejection decisions throughout the system. Finally, we are able to track weekly inventory and sales data on an item level for each store.

We consider only orders shipped from stores (i.e., only partially fulfilled by the DC) and separate them into single and multi-item orders for our analysis. After filtering accordingly, our dataset contains approximately 3.2 million orders; two million single-item orders (one million each year) and 1.2 million multi-item orders (approximately 500,000 in 2018 and 700,000 in 2019). Each multi-item order is composed of 2.8 items, on average, across the two years; 90% of the orders have five or fewer items, and we restrict our analysis to these in this study. The average number of requests each of the 100 stores fulfilled (either fully or partially) is 32,000 per year.

The average rejection rates for such orders in 2018 and 2019 are depicted in Figure 1; note that the figure refers to 52 fiscal weeks. We observe that rejections are rare at the beginning of both years, and there is an upward trend in the latter weeks. In the peak period, which coincides with Black Friday and holiday season, the average rejection rates vary between 20 and 30%. This occurs because of item availability (either due to inconsistent inventory or item displacement), managers keeping the inventory for walk-in customers, or simply lack of personnel to pack and ship the order during these busy periods. In particular, our analysis suggests rejection rates are correlated with exogenous features (e.g., sales periods), but we generally observe little or no correlation with order-specific characteristics, such as inventory levels, item types, or order sizes.

In terms of shipment costs, the retailer’s postal service contract classifies packages as local, regional, and national for cost purposes. If both the store and the destination are in the same city, shipments are classified as local. When both locations are within the same postal region, shipments are regional, and otherwise shipments are national. The percentages of orders of each type for both years are approximately 11%, 58%, and 31%, respectively. According to the data, customers receive their order in multiple packages approximately 44% of the time; this is costly for the company in monetary terms and also in terms of greenhouse gas emissions, and is not desirable for customers.

7.2.1. Simulation Setup

Based on the observations above, we simulate the system on periods where the acceptance rate is relatively low, that is, the last four months of the two years. This corresponds to approximately 1.2 million and 600,000 single and multi-item orders, respectively. The simulation processes one order at a time based on its associated timestamp. The number of items shipped per order and store are chosen randomly based on the binomial trials from our formulation (2), updating inventory based on weekly sales data at each store. The set $\mathcal{N}$ is composed only of stores which have sufficient inventory levels to ship all items in the order. Costs are fixed to the average shipping fees according to the three postal categories (local, regional, national) for each origin-destination pair. We report average metrics for 10,000 replications of the simulation process, comparing it to retailer decisions for the same orders and under the same cost structure.

In line with our model assumptions and consistent with the exogenous nature of acceptance decisions observed in our data, the acceptance probabilities are fixed per day and per store. To estimate the potential savings of the new policies, we use out-of-sample testing by considering the real empirical probabilities at each store on the previous day. That is, the probability $p_i$ of store $i$ on a given day is determined by the number of orders shipped (fully or partially) divided by the number of requests the store receives on the previous day. If no request was placed at a particular store, that is, there is no available data on the acceptance probability of that store, we pessimistically assume the acceptance probability is zero. We remark that this corresponds to the best-case average improvements obtained by DBH, given that acceptance probabilities are known in advance. However, this method rules out confounding errors due to inaccuracies in acceptance prediction, which is an important but separate question (motivating, e.g., our analysis in Section EC.1).

7.2.2. Results—Single Items

Table 5 assesses MPC for single-item orders from the data, which is optimal in this setting (Proposition 1). We also include historical practice (Current) for reference only, as we are not able to include algorithmic details due to nondisclosure agreements. The columns refer to the percentage of store requests where at least one item is shipped (Acceptances), the average and the maximum number of stores rejecting at least an item in one order (# of Rejections/Order), and the total cost savings in % with respect to current practice.

Table 5.

Performance of the current and MPC on single-item orders with rejection decisions.

		Acceptances			# of Rejections/order
Fiscal year	Policy	Local (%)	Regional (%)	National (%)	Average	Maximum	Cost savings(%)
2018	Current	7.9	58.1	34.0	0.265	13	–
	MPC	38.6	58.0	3.3	0.110	10	14.5
2019	Current	15.0	54.5	30.6	0.143	14	–
	MPC	43.7	53.1	3.3	0.081	9	13.5

Table 6.

Performance of the MPC and DBH on multi-item orders with rejection decisions in 2019.

		Acceptances			# of Rejections/order		Deliveries
		Local	Regional	National			Single	Two	Three	Four	Five	Cost savings
Number of items	Policy	(%)	(%)	(%)	Average	Maximum	(%)	(%)	(%)	(%)	(%)	(%)
$m=2$ (61.1%)	Current	9.6	55.5	34.9	0.172	13	43.2	56.8	−	−	−	−
	MPC	33.0	56.9	10.1	0.177	11	83.1	16.9	−	−	−	33.8
	DBH	28.6	60.1	11.3	0.157	12	85.3	14.7	−	−	−	34.2
$m=3$ (23.8%)	Current	8.5	55.2	36.3	0.175	18	32.2	39.6	28.3	−	−	−
	MPC	26.1	54.2	19.7	0.257	9	74.9	19.5	5.6	−	−	38.7
	DBH	15.8	58.7	25.5	0.149	9	83.3	11.3	5.4	−	−	40.4
$m=4$ (10.4%)	Current	8.0	55.1	36.9	0.179	19	27.7	32.6	26.0	13.7	−	−
	MPC	20.8	46.8	32.4	0.288	11	70.2	20.0	2.0	7.9	−	37.3
	DBH	11.3	48.1	40.6	0.161	8	79.6	11.0	1.4	8.0	−	38.9
$m=5$ (4.7%)	Current	7.9	54.6	37.5	0.189	24	23.5	29.6	23.7	16.0	7.2	−
	MPC	15.8	38.4	45.8	0.296	10	67.5	17.8	2.7	0.6	11.5	32.6
	DBH	9.1	37.5	53.4	0.162	9	76.7	9.1	1.9	0.6	11.7	34.3

Historically, the percentage of local shipments is only 7.9% in 2018 and 15% in 2019, whereas national shipments constitute over 30% of all shipments in both years. MPC increases the rate of local shipments and result in 14.5% and 13.5% savings in shipping costs in the last four months of 2018 and 2019, respectively. Improvements are also observed in the number of requests. In 2018, an order was rejected 0.265 times, on average, and the maximum number of rejections one order received was 13. The average and maximum rejection counts, in turn, decrease to 0.11 and 10, respectively. Similar observations can be made for 2019 data; average rejection rate per order improves by 0.062, and the maximum is 5 rejections fewer for MPC.

7.2.3. Results—Multiple Items

Table 6 provides the resuls for multi-item orders in 2019 (results for 2018 are added to the electronic companion in Table EC.5 as they are similar). Besides the same metrics as above, we evaluate split delivery rates by calculating the number of shipped packages in percentage (Deliveries). We include “Current” for reference.

The table suggests that MPC results in slightly higher local shipments compared to DBH. This is expected as MPC prioritizes shipping costs, whereas DBH considers shipping costs and acceptance probabilities simultaneously. In particular, for larger values of $m$ , DBH has a higher percentage of national shipments compared to the current practice, as it potentially chooses stores that are more expensive but are more likely to accept more items. For larger order sizes, the policies still manage to ship at least 85% of them in either one or two packages. However, we observe that MPC and DBH increase the number of five-way split deliveries in comparison to practice. This occurs because in our definition of $\mathcal{N}$ , we only consider the set of stores with enough inventory to ship all items, thus reducing the set of available stores. We also observe that although MPC improves general costs, it also rejects more orders, as it disregards acceptance probabilities.

7.3. Performance Analysis for Rationing

In order to assess the value of inventory rationing, we first compare the single-unit optimal policy to the strategy where the DC is strictly prioritized over stores due to its lower shipping cost $c_0$ (i.e., no-rationing). We then evaluate the performance of the multi-unit inventory rationing policy BP. For the single-unit case, we evaluate the average cost improvement of the optimal policy (6) with respect to the no-rationing model. For BP, we compare the average optimality gap, here given by $[J_{{\pi }_B}^{\prime }(x,t,r_m)-J_{{\pi }^{*}}(x,t,r_m)]/J_{{\pi }^{*}}(x,t,r_m)$ , where $J_{{\pi }_B}^{\prime }(x,t,r_m)$ evaluates the cost of the decisions taken by BP over the original value function (9), and $J_{{\pi }^{*}}(x,t,r_m)$ is the expected optimal cost. Models are solved by a backward recursion.

7.3.1. Experimental Setup

We select shipping costs from stores uniformly at random from the discrete set $\{1,2,\dots ,C\}$ , where $C\in \{25,50,100\}$ . Acceptance probabilities are chosen uniformly at random from $[0,1]$ . We normalize the shipping cost from the DC as $c_0=\mathrm{\$}1$ , and set $M_h=1$ . We consider $|\mathcal{R}|\in \{2,5\}$ regions and explore scenarios with $t\in \{10,20,30\}$ units of remaining periods or demand, and consider all cases where the inventory levels are $x\le \overline{m}t$ ( $\overline{m}=1$ for single-unit orders).

For the single-unit experiments, we choose the arrival rate of each region uniformly at random from $[0,1]$ , normalizing the total arrival rate to 1. We also explore the effects of lost-sales cost with $M_l\in \{10,50,100\}$ . For the multi-unit experiments, we set $M_l=\mathrm{\$}100$ and consider $\overline{m}\in \{2,3,4,5\}$ units per order. In our data, the distribution of order sizes $[1,2,3,4,5]$ is $[62\mathrm{\%},23\mathrm{\%},9\mathrm{\%},4\mathrm{\%},2\mathrm{\%}]$ , with an average of 1.62 units. We choose the arrival rate of each demand size across all regions according to this distribution. For experiments with $\overline{m}\le 4$ , we update the rates as follows to keep the average order size the same: For $\overline{m}=2$ , $\overline{m}=3$ , and for $\overline{m}=4$ , we use $[38\mathrm{\%},62\mathrm{\%}]$ , $[58\mathrm{\%},25\mathrm{\%},17\mathrm{\%}]$ and $[61\mathrm{\%},23\mathrm{\%},9\mathrm{\%},7\mathrm{\%}]$ , respectively. Moreover, for a given $m\in \{1,\dots ,\overline{m}\}$ , the arrival rate of that demand size is distributed among regions uniformly at random.

For each configuration $(r,M_l,t)$ for the single-unit experiment, and $(r,\overline{m},t)$ for the multi-unit experiments, we report summary statistics of 300 samples (100 samples for each $C$ ). We use DBH to evaluate $f(\cdot )$ , and while solving BP, we use the original recursion (9) for $t\le 5$ .

7.3.2. Results

Table 7 presents the average cost improvement (in %) of the optimal single-unit rationing model with respect to the DC-only policy (no rationing) for each $(r,M_l,t)$ configuration. Results suggest that, even with small lost-sales costs, expected costs can be improved by 10%–30% on average with rationing. As expected from Proposition 10, as $M_l$ increases, the regions are rationed earlier in the process and thus, the benefits of rationing increase, up to almost 80% cost decrease.

Table 7.

Single-unit no-rationing results with varying number of regions $|\mathcal{R}|$ , lost-sales cost $M_l$ , and demand $t$ .

		$|\mathcal{R}|=2$			$|\mathcal{R}|=5$
Lost-sales cost	Demand left	Average (%)	$\mathbf{99}\mathit{t}\mathit{h}$ Perc. (%)	Best-case (%)	Average (%)	$\mathbf{99}\mathit{t}\mathit{h}$ Perc. (%)	Best-case (%)
$M_l=10$	$t=10$	9.16	36.74	47.77	17.96	45.60	51.08
	$t=20$	12.04	53.65	61.80	21.28	42.89	48.36
	$t=30$	11.17	42.93	63.73	22.70	46.52	59.44
$M_l=50$	$t=10$	20.84	52.19	60.74	20.33	40.78	46.44
	$t=20$	25.05	54.82	58.88	24.67	47.18	55.34
	$t=30$	28.51	63.83	68.11	26.19	51.36	58.38
$M_l=100$	$t=10$	32.37	62.02	66.59	23.44	46.25	49.74
	$t=20$	38.77	70.15	75.35	28.33	52.22	55.22
	$t=30$	40.51	69.57	77.89	30.14	55.59	61.33

Table 8 presents the performance of BP across all $(r,\overline{m},t)$ configurations. The average optimality gap among all settings remain mostly well below $3\mathrm{\%}$ . We observe that the optimality gaps tend to increase with demand. This increase is likely due to the expanded state space introducing more opportunities for BP to deviate from the optimal decisions. On the other hand, the optimality gaps improve with the number of regions. This improvement may be attributed to the decreasing arrival rates per demand class; errors in policy decisions for any demand class get a lower weight in the expected future costs, thus reduce the deviations from the optimal. Finally, we observe that the performance metrics are quite robust to the variations in the order sizes.

Table 8.

Multi-unit rationing results of bundling policy (BP) with varying numbers of regions $|\mathcal{R}|$ , order sizes $\overline{m}$ , and demand $t$ .

		$|\mathcal{R}|=2$			$|\mathcal{R}|=5$
	Maximum	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-case	Average	$\mathbf{99}\mathit{t}\mathit{h}$ Perc.	Worst-case
Demand left	order size	(%)	(%)	(%)	(%)	(%)	(%)
$t=10$	2	0.94	4.30	4.87	0.10	1.78	2.94
	3	0.99	4.05	4.64	0.11	1.29	2.45
	4	1.10	3.42	3.62	0.10	1.21	1.29
	5	1.05	3.37	3.50	0.07	1.10	2.56
$t=20$	2	2.59	11.23	16.61	0.19	1.85	6.70
	3	2.17	7.46	7.65	0.19	2.85	2.93
	4	2.16	7.50	8.39	0.33	3.48	5.39
	5	1.95	6.97	7.26	0.13	2.12	4.61
$t=30$	2	3.19	14.98	15.65	0.12	1.74	2.44
	3	3.04	10.40	11.46	0.30	4.66	8.10
	4	2.73	8.41	8.53	0.22	3.59	4.48
	5	2.19	8.31	8.88	0.11	1.31	4.88

8. Conclusions and Future Research

This paper addresses an order fulfillment problem of an omni-channel retailer under a decentralized framework where items are not differentiable. Specifically, when warehouses are unable to fulfill an online order, the retailer leverages its business structure and attempts to ship items through its brick-and-mortar stores. The retailer places requests to stores one at a time, and each stochastically agrees to fully or partially satisfy an order based on censored local information. Decisions must balance the trade-off between stores with lower shipping costs and those having higher acceptance rates to avoid multiple deliveries.

We formulate the problem as a MDP and derive theoretical performances of low-complexity nonadaptive policies, which are of practical interest. More precisely, we show that a myopic policy in terms of cost has an approximation ratio given by the number of items; thus, its worst case performance does not depend on costs or acceptance rates, and is optimal for single-item orders or those where splits are not allowed. We also establish conditions on acceptance probabilities for the myopic policy to be optimal for two-store configurations (e.g., representing local/national choices) and discuss the performance of strategies based only on acceptance ratios or semi-random choices that incorporate fairness. Moreover, we develop two adaptive policies based on a sufficient and necessary condition associated with the optimality of two-store sequences. The first weakly improves the myopic policy and preserves its cost-independent approximation ratio, while the second is a degree-based heuristic on an auxiliary store network. Finally, we investigate natural extensions that incorporate delay costs and discuss settings with item-dependent acceptance ratios.

We then extend the analysis to incorporate the DC into the fulfillment operations, by making inventory rationing decisions. We show for single-item orders, optimal policies have a threshold structure, and even the highest-priority demand class may be subject to rationing. We then show the complexities of settings with multi-unit-single-item orders, and develop a heuristic based on bundling multiple units, which leverages single-item threshold levels.

Finally, we perform a computational study on synthetic and real data provided by a large-scale retailer partner in North America. Analysis of artificial data suggests the cost-based myopic policy is, at most, 2%–3.5% above optimal. Its adaptive variant halves the optimality gap in most configurations, and the degree-based policy is 0.5% from the optimal on average. For the rationing problem, we characterize the optimal threshold rationing structure for the single-item case and demonstrate numerically that these policies can bring 20%–30% cost decrease, on average, compared to the model without any rationing decisions. For the multi-unit-single-item case, we numerically show that the BP reaches optimality gaps of mostly below 1%, on average, and it is quite robust to the variation in order sizes.

We suggest several avenues for future research. In particular, one limitation of our study is that it assumes acceptance probabilities are exogenous and known in advance. In practice, estimating these probabilities may require accurate predictive models which could better inform the store sequencing process. Another area for exploration can be determining policies with approximation guarantees for the multi-unit/item cases that extend our current results, or evaluating policies with item-dependent parameters. It would also be meaningful to investigate alternative systems where requests are placed at multiple stores simultaneously instead of sequential decision making.

Supplemental Material

sj-pdf-1-pao-10.1177_10591478241255066 - Supplemental material for Decentralized Online Order Fulfillment in Omni-Channel Retailers

Supplemental material, sj-pdf-1-pao-10.1177_10591478241255066 for Decentralized Online Order Fulfillment in Omni-Channel Retailers by Opher Baron, Andre A Cire and Sinem K Savaser in Production and Operations Management