Drent and Arts

Effective Dual-Sourcing Through Inventory Projection

Effective Dual-Sourcing Through Inventory Projection

Melvin Drent School of Industrial Engineering, Eindhoven University of
Technology, Eindhoven, the Netherlands, PO BOX 513, 5600MB<EMAIL_ADDRESS>Joachim Arts Luxembourg Centre for Logistics and Supply Chain Management,
University of Luxembourg, Luxembourg City, Luxembourg, 6, rue Richard
Coudenhove-Kalergi L-1359<EMAIL_ADDRESS>
We consider a single-echelon inventory system under periodic review with two
suppliers facing stochastic demand, where excess demand is backlogged. The
expedited supplier has a shorter lead time than the regular supplier but
charges a higher unit price. We introduce the Projected Expedited Inventory
Position (PEIP) policy, and we show that the relative difference between the
long run average cost per period of this policy and the optimal policy
converges to zero when both the shortage cost and the cost premium for
expedited units become large, with their ratio held constant. A corollary of
this result is that several existing heuristics are also asymptotically
optimal in this non-trivial regime. We show through an extensive numerical
investigation that the PEIP policy outperforms the current best performing
heuristic policies in literature.

dual-sourcing; inventory; projected inventories; optimal policy; asymptotic
optimality

##  1 Introduction

Dual-sourcing is a common and effective supply chain management practice
employed by companies that operate both globally and domestically. It
generally refers to situations where companies can replenish their inventories
from a regular supplier as well as from an expedited supplier; the latter
offering a shorter lead time than the former but at the expense of a cost
premium. Even though the expedited supplier charges an additional cost,
companies can leverage its responsiveness when inventories deplete
precipitously.

Examples of companies that have utilized a dual-sourcing strategy are
manifold. Allon and Van Mieghem (2010) describe a $10 billion high-tech U.S.
company with suppliers in China and Mexico. The Chinese supplier charges lower
costs than Mexico but shipping its products to the U.S. takes considerably
longer. Rao et al. (2000) describe a similar situation at Caterpillar; they
too use a more expensive expedited supplier whenever a shorter lead time is
desired. While both examples concern two distinct suppliers, dual-sourcing may
also refer to situations where companies can replenish their inventories from
one supplier using two distinct transport modes. For example, Threatte and
Graves (2002) describe a situation in which Polaroid Corporation relies on
ocean transport to ship products from a supplier in Asia to the U.S., but
occasionally uses expedited air transport when inventory levels are critically
low.

In this paper, we treat a setting similar to the ones described above. In
particular, we consider a single-item, single-echelon dual-sourcing inventory
system under periodic review facing stochastic demand, where excess demand is
backlogged. We assume that demands across periods are independently and
identically distributed (i.i.d.). The expedited supplier has a shorter lead
time than the regular supplier but charges a higher unit price. There are no
fixed costs associated with ordering at either supplier. At the end of each
period, linear holding and backorder costs are charged for leftover inventory
and backlogged demand, respectively. We seek to minimize the long run average
total cost per period, which consists of ordering, holding, and backorder
costs.

The dual-sourcing system introduced above has been studied for almost sixty
year now, starting with the contributions of Barankin (1961) and Neuts (1964).
They show that the optimal policy exhibits a simple order-up-to structure when
the lead times of the regular and expedited supplier are one and zero periods,
respectively. Fukuda (1964) later extends this result to the case where the
difference between the lead times of both suppliers is one period,
irrespective of their individual lead times. For lead time differences larger
than one period, Whittemore and Saunders (1977) and more recently Feng et al.
(2006) show that the structure of the optimal policy is complex, and depends
in general on the entire vector of outstanding orders. Although the optimal
policy for general lead time differences can be computed in principle by
stochastic dynamic programming, this is not practical as the state space of
the dynamic program grows exponentially in the lead time difference; that is,
it suffers from the curse of dimensionality. Most researchers have therefore
focused on devising relatively simple but non-optimal replenishment policies
(we will provide a thorough review later in Section 2).

Even though some heuristic policies have been shown to perform numerically
close to optimal in at least certain regimes, theoretical justifications for
such useful asymptotic optimality performance guarantees are mostly lacking;
the only exception being the Tailored Base-Surge (TBS) policy. This policy
orders a fixed amount at the regular supplier every period and uses an order-
up-to rule for placing expedited orders. The TBS policy was first proposed by
Allon and Van Mieghem (2010), though Rosenshine and Obee (1976) and Janssen
and de Kok (1999) have studied a closely related policy before. Numerical
analysis by Klosterhalfen et al. (2011) and Janakiraman et al. (2015)
indicates that the optimality gap of the TBS policy closes as the lead time
difference grows large.

Xin and Goldberg (2018) have recently provided theoretical justification for
these numerical observations by proving that a simple TBS policy is
asymptotically optimal as the lead time of the regular supplier grows large,
with the lead time of the expedited supplier held fixed. The intuition behind
this result is that as the lead time difference grows, the amount of
randomness between when a regular order is placed and when this order arrives
grows so large that a constant order, which ignores the entire vector of
outstanding orders, performs nearly optimal. To our knowledge, this is the
only heuristic policy for dual-sourcing inventory systems under periodic
review with general lead time differences that has an asymptotic performance
guarantee. Unfortunately, the TBS policy performs poorly outside this
asymptotic regime, particularly when either the backorder cost becomes large
or when the unit price charged by the expedited supplier becomes large. When
both cost parameters become large simultaneously, the performance of the TBS
drops even precipitously (Klosterhalfen et al. 2011). Yet, it is exactly this
setting that is prevalent in practice, and it therefore remains an open
research problem to determine control policies that are provably
asymptotically optimal in this regime.

In this paper, we propose such a new policy, which we call the Projected
Expedited Inventory Position (PEIP) policy. The PEIP policy keeps track of the
expedited inventory position (net inventory level plus outstanding orders
arriving within the expedited lead time) and places expedited orders such that
this inventory position reaches a certain target level. Regular orders
entering the information horizon for placing expedited orders may cause the
expedited inventory position to exceed its corresponding target level. This
implies that the expedited inventory position in expectation exceeds the
target level. Under the PEIP policy, regular orders are therefore placed such
that the expected expedited inventory position at the time of the regular
order entering the expedited inventory position is kept at a target level. In
doing so, the PEIP policy leverages all the information contained in the
pipeline – as does the optimal policy. This is in contrast with existing
heuristic policies that either aggregate all outstanding orders or ignore them
entirely and place a constant order every period regardless. We further
provide a separability result that enables efficient optimization of the PEIP
policy. Hence, the PEIP policy is vastly more advanced than existing heuristic
policies, and yet can be optimized efficiently and retains an intuitive appeal
for practitioners. It is also assuring to note that for the case of
consecutive lead times, the PEIP policy reduces to two order-up-to levels,
which is known to be the optimal policy for that specific case (Fukuda 1964).

We show that, under some mild conditions on the demand distribution, the
relative difference between the long average cost per period of the best PEIP
policy and the optimal policy converges to zero when both the shortage cost
and the price for expedited units become large, with their ratio held
constant. Our approach relies on establishing lower and upper bounds on the
average cost rates of the optimal policy and the best PEIP policy,
respectively, in terms of the average cost rates of canonical inventory
systems with only one supplier. We then show that the ratio of these bounds
converge to 1 in the non-trivial asymptotic regime where both the shortage
cost and the price for expedited units grow large. Our research is useful for
practice as it directly leads to an easily implementable heuristic that has
asymptotic performance guarantees in high service regimes where utilizing an
expedited source is expensive. In the capital goods industry, for example, it
is very common that the shortage costs for critical parts as well as the costs
associated with performing an expedited shipment are relatively high (see,
e.g., Westerweel et al. 2021).

The main contribution of this paper is threefold:

  1. 1.

We propose the PEIP policy for periodic review dual-sourcing inventory systems
with general lead time differences, and we present an efficient optimization
scheme to find its optimal policy parameters. This optimization scheme hinges
on a separability result that allows us to decompose the optimization into two
simple one-dimensional optimization problems.

  2. 2.

We prove that the PEIP policy is asymptotically optimal when both the shortage
cost and the cost premium for expedited units become large, with their ratio
held constant. Our proof technique can serve as a template that is readily
applicable to other heuristic polices. We illustrate this by showing that
several existing heuristic policies are also asymptotically optimal in this
non-trivial regime of broad interest.

  3. 3.

Through an extensive numerical investigation, we conclude that the PEIP policy
outperforms the best performing heuristics in literature. Our numerical
investigation further shows that, as the lead time difference between the
regular and expedited supplier grows, the PEIP policy converges to a TBS
policy which is asymptotically optimal in this regime (Xin and Goldberg 2018).

The remainder of this paper is organized as follows. In the next section, we
position our research with respect to other contributions that have been made.
After that, in Section 3, we formally define the decision problem and
introduce the notation that we use throughout this paper. Section 4 presents
the PEIP policy, including analytical results that allow for an efficient
optimization procedure to find the optimal policy parameters. We proceed with
establishing our asymptotic optimality result in Section 5. After that, we
report on a large numerical study in Section 6, and we provide concluding
remarks in Section 7.

##  2 Positioning in the literature

Dual-sourcing systems operating in discrete time as well as their variants
(e.g., continuous review models, multi-echelon systems, etc.) have been widely
studied. For a broad overview of this rich field, we refer the interested
reader to the surveys of Minner (2003) and Svoboda et al. (2021), as well as
to the recent studies of, e.g., Gong et al. (2014), Boute and Van Mieghem
(2015), Arts et al. (2016), Sapra (2017), Song et al. (2017), Drent and Arts
(2021), and the references therein. Here we confine ourselves to contributions
most relevant to our research, a large part of which revolves around heuristic
policies.

Whittemore and Saunders show already in 1977 that optimal policies for the
periodic review dual-sourcing inventory systems we typically face in practice
(i.e. with lead time differences larger than one) are complex and difficult to
compute. Yet it lasted until the beginning of this century before researchers
began to devise various effective heuristic policies. Scheller-Wolf et al.
(2007) propose the Single-Index (SI) policy that uses order-up-to rules for
order placement at the regular and expedited supplier based on only the
regular inventory position (inventory level plus all outstanding orders). By
additionally tracking the expedited inventory position that includes only
orders that will arrive within the expedited lead-time, Veeraraghavan and
Scheller-Wolf (2008) introduce the Dual-Index (DI) policy. Regular and
expedited orders are then placed according to order-up-to rules based on their
respective inventory positions. They propose a simulation-based optimization
and show that this is easily implementable and often results in near-optimal
solutions in numerical examples.

Since then, the DI policy has been extended in various useful ways. Sheopuri
et al. (2010) analyze the more general class of policies that use an order-up-
to rule for placing expedited orders. Arts et al. (2011) incorporate
stochastic lead times and provide an approximate evaluation method so that
optimization can be done without simulation. Sun and Van Mieghem (2018)
introduce the Capped Dual-Index (CDI) policy in which the DI policy is
accompanied with a cap that smooths regular orders. Even though the CDI policy
has been developed in a robust optimization setting under the worst-case cost
performance criterion, numerical analysis indicates that it also performs well
in terms of minimizing the long run average cost per period in a stochastic
setting.

Sheopuri et al. (2010) show that the inventory system with lost sales is a
special case of the dual-sourcing inventory system treated here given that the
expedited supplier follows an order-up-to rule. The intuition behind this is
that the orders placed at the expedited supplier can be thought of as demand
lost from the regular supplier, with the cost premium of the expedited
supplier being the lost sales penalty cost. Inspired by this relation,
Sheopuri et al. (2010) propose the Vector Base-Stock (VBS) policy that uses an
order-up-to rule for the expedited supplier, and a vector base-stock policy
for the regular supplier. Hua et al. (2015) later generalize the VBS policy to
the Best Weighted Bounds (BWB) policy. In addition, by using properties of
$L^{\natural}$-convexity, they show that the optimal expedited orders are more
sensitive to the older (i.e. soon-to-arrive) outstanding orders whereas the
optimal regular orders are more sensitive to the younger outstanding orders.
Extensive numerical investigations indicate that the BWB policy as well as the
CDI policy described earlier are the best performing heuristic policies in the
current literature, and can even outperform advanced deep reinforcement
learning algorithms (Sun and Van Mieghem 2018, Gijsbrechts et al. 2022).

While the PEIP policy is similar to the aforementioned heuristic policies in
that it also assumes an order-up-to rule for the expedited supplier, it
differs significantly in how it operates the regular supplier. First, the PEIP
policy projects the expedited inventory position in deciding upon regular
orders. As such, it controls the expected expedited inventory position
directly taking into account explicitly the excess by which the order-up-to
level of the expedited supplier overshoots; existing heuristics do so only
indirectly. Second, similar to the optimal policy, the PEIP policy leverages
all available state information in deciding upon order placement at the
regular supplier. Existing heuristics either aggregate all available
information, or ignore it entirely and place a fixed amount every period
regardless.

Our research also contributes to the growing body of literature that
establishes asymptotic performance guarantees of heuristic policies for
inventory systems whose optimal policies are difficult to analyze if not
intractable. The relatively few studies that belong to this literature stream
mostly focus on single-echelon inventory systems with lost sales. For such
systems, Huh et al. (2009) and Bijvank et al. (2014) show that certain order-
up-to policies are asymptotically optimal as the lost sales penalty cost
approaches infinity while Goldberg et al. (2016) and Xin and Goldberg (2016)
show that a simple constant order policy is asymptotically optimal as the lead
time approaches infinity. Both heuristic policies perform however poorly
outside their respective asymptotic regimes. This has recently led to the
development of two heuristic policies that have asymptotic performance
guarantees and additionally perform well in both regimes: the Capped Base-
Stock (CBS) policy proposed by Xin (2022, 2021), and the Projected Inventory
Level (PIL) policy proposed by Van Jaarsveld and Arts (2021).

The CBS policy can be interpreted as a hybrid between a constant order policy
and an order-up-to policy, and it thus enjoys the superior performance of both
policies in their respective regimes. The PIL policy places orders such that
the expected inventory level at the time of arrival of an order is raised to a
target level. Van Jaarsveld and Arts (2021) show that the PIL policy is
asymptotically optimal for large lost sales penalty costs as well as for large
lead times, though the latter only under the assumption that demand is
exponentially distributed. The PEIP policy is related to the PIL policy: While
a PIL policy places orders by projecting the expected inventory level, a PEIP
policy places regular orders by projecting the expected expedited inventory
position (while retaining an order-up-to rule for the expedited supplier).

Unlike inventory systems with lost sales, there currently exists only one
heuristic policy for periodic review dual-sourcing inventory systems that has
asymptotic performance guarantees. Indeed, a simple TBS policy is
asymptotically optimal as the lead time difference between the regular
supplier and expedited supplier grows large (Xin and Goldberg 2018). In this
paper, we consider a different asymptotic regime and show that the best PEIP
policy is asymptotically optimal as the unit cost of the expedited supplier
and the shortage cost approach infinity simultaneously. Our main proof
exploits the earlier described relation between lost sales inventory systems
and dual-sourcing inventory systems; this allows us to draw on the asymptotic
results for lost sales inventory systems of Huh et al. (2009). We further
argue that our proof technique in itself has merit too since it can serve as a
template that is readily applicable to existing as well as future heuristic
policies. We illustrate this by showing that the CDI, DI, and SI policy are
also asymptotically optimal in the non-trivial asymptotic regime under
consideration. As such, we extend the literature on asymptotic optimality
results for dual-sourcing inventory systems considerably.

We end this review by remarking that recent advances on asymptotic optimality
results for inventory systems that have complex optimal policies stretch
beyond the lost sales and dual-sourcing inventory systems described above.
See, for instance, Rong et al. (2017) for such results in the context of
distribution systems consisting of one central warehouse and multiple local
warehouses, Janakiraman et al. (2018) on inventory systems with multiple
products that share production capacities, and Fu et al. (2019) on inventory
systems for perishable products. We refer the interested reader to Goldberg et
al. (2021) for a recent and comprehensive review of this growing field.

##  3 Notation and problem formulation

This section provides a formal problem description that mostly follows the
notational conventions of Sheopuri et al. (2010). We consider a single-item,
single-echelon inventory system under periodic review facing stochastic
demand, where excess demand is backlogged. Products can be ordered each period
both at a regular supplier and at an expedited supplier. Let $c^{r}$ ($l^{r}$)
and $c^{e}$ ($l^{e}$) denote the unit prices (lead times) from the regular and
expedited supplier, respectively. We assume that $c^{e}>c^{r}$ and
$l^{e}<l^{r}$, that is, the expedited supplier offers a higher unit price, but
its lead time is shorter. Notice that the present inventory problem reduces to
a standard inventory problem with only one supplier if these assumptions do
not hold. Both lead times are assumed to be deterministic as well as a non-
negative integer multiple of the review period. For notational convenience, we
also define the lead time difference $l=l^{r}-l^{e}\geq 1$.

Let $D_{t}$ denote the random demand in period $t$, with $t$ indexed forward
in time starting from 0, i.e. $t\in\\{0,1,\ldots\\}$. Demand across periods is
a sequence of non-negative i.i.d. random variables. Whenever we drop the
period index of $D_{t}$, we refer to the generic random variable with the same
distribution as $D_{t}$. The cumulative demand over $n$ periods is denoted as
$\mathbf{D}^{n}$. Let $I_{t}$ denote the net inventory level (on-hand
inventory minus backlog) at the beginning of period $t$ after orders have
arrived, but before demand has occurred. Let $q^{e}_{t}$ $(q^{r}_{t})$ denote
the order size placed with the expedited (regular) supplier in period $t$. The
orders that arrive in period $t$ are thus $q^{e}_{t-l^{e}}$ and
$q^{r}_{t-l^{r}}$, and we can consequently write the following recursion for
the inventory level:

$I_{t}=I_{t-1}-D_{t-1}+q^{e}_{t-l^{e}}+q^{r}_{t-l^{r}}.$

At the end of each period $t$, costs are levied as follows. Per unit in on-
hand inventory $(I_{t}-D_{t})^{+}$ carried over to the next period, a cost
$h>0$ is charged. Similarly, a cost $p>0$ is charged for each unit in backlog
$(D_{t}-I_{t})^{+}$ carried over to the next period. Here we use the
convention $x^{+}=\max(x,0)$.

Observe that if the unit price charged by the expedited supplier $c^{e}$ is
higher than the total backlog cost incurred on a unit over $l$ periods, i.e.
$l\cdot p$, then there is no cost benefit to be derived from ordering any
units from the expedited supplier over the regular supplier. In fact, as shown
in Sheopuri et al. (2010), the present inventory problem reduces to a standard
single supplier inventory problem if $c^{e}\geq p\cdot l$. We therefore assume
throughout the remainder that $c^{e}<p\cdot l$. We revisit this assumption in
Section 5 when we expound on the particular asymptotic regime we are
interested in.

Let the state of the system at the beginning of period $t$ after orders have
arrived be given by
$\mathbf{x}_{t}=(I_{t},q^{r}_{t-l^{r}+1},\ldots,q^{r}_{t-1},q^{e}_{t-l^{e}+1},\ldots,q^{e}_{t-1})$.
The sequence of events in any period $t$ is as follows:

  1. 1.

Products that were ordered $l^{e}(l^{r})$ periods ago at the expedited
(regular) supplier are received and added to the on-hand inventory, i.e. order
$q^{e}_{t-l^{e}}(q^{r}_{t-l^{r}})$.

  2. 2.

The size of the order placed with the expedited supplier $q^{e}_{t}$ is
determined based on the current state of the system $\mathbf{x}_{t}$.

  3. 3.

The size of the order placed with the regular supplier $q^{r}_{t}$ is
determined based on the current state of the system $\mathbf{x}_{t}$ and the
order just placed with the expedited supplier $q^{e}_{t}$.

  4. 4.

The demand $D_{t}$ is realized, and holding or shortage costs are charged, in
case that $(I_{t}-D_{t})^{+}>0$ or $(D_{t}-I_{t})^{+}>0$, respectively.

The total cost incurred in period $t$ is denoted by $C_{t}$, i.e.
$C_{t}=c^{e}\cdot q^{e}_{t}+c^{r}\cdot
q^{r}_{t}+h\cdot(I_{t}-D_{t})^{+}+p\cdot(D_{t}-I_{t})^{+}$. An admissible
policy $\pi$ is as a rule that determines the size of the orders placed with
the regular and expedited supplier based only on the historical information
available in that period as outlined in the sequence of events above. All such
admissible policies $\pi$ are contained in the set $\Pi$. Since the total cost
incurred in a period $t$ depends on the policy $\pi$, we henceforth write
$C^{\pi}_{t}$ to denote this dependence explicitly. Our performance measure of
interest is the long run average cost per period

$C^{\pi}=\limsup_{T\rightarrow\infty}\frac{1}{T}\sum\nolimits_{t=1}^{T}C^{\pi}_{t}.$

We assume throughout the remainder that $\mathbf{x}_{0}=\mathbf{0}$. That is,
the initial inventory level equals zero, and there are initially no
outstanding expedited or regular orders due to arrive within their
corresponding lead times. This assumption simplifies our analysis later; it is
however not strictly necessary as we are interested in the long run average
cost per period, which is not affected by any specific choice for the initial
state.

We end this section with two remarks related to the optimal policy
$\pi^{\star}=\operatorname{argmin}_{\pi\in\Pi}C^{\pi}$. First, as shown by
Sheopuri et al. (2010), $\pi^{\star}$ depends on $c_{e}$ and $c_{r}$ only
through the price premium of the expedited supplier, i.e. $c_{e}-c_{r}$. This
result follows intuitively from the observation that any policy that has a
finite long run average cost per period will incur at least a cost of
$c^{r}\cdot\mathbb{E}[\text{D}]$. We will therefore assume without loss of
generality that $c_{r}=0$. Second, even for small lead time differences, the
structure of $\pi^{\star}$ remains poorly understood and depends in general on
the entire vector of outstanding orders. The policy we propose in the next
section also takes into account this entire vector when deciding on the size
of the orders placed with both suppliers. However, different from
$\pi^{\star}$, our policy does allow for tractable analysis and efficient
optimization, even for large-sized problems often encountered in practice.

##  4 The Projected Expedited Inventory Position Policy

In this section, we present the Projected Expedited Inventory Position (PEIP)
policy for operating dual-sourcing inventory systems. We first formally define
the rules under which both suppliers operate, and we subsequently present
analytical results that allow for an efficient solution procedure to find the
optimal policy parameters.

###  4.1 Order placement rules

Under a PEIP policy, the ordering rule for the expedited supplier is assumed
to be an order-up-to rule that operates as follows. At the beginning of each
period $t$ after orders $q^{r}_{t-l^{r}}$ and $q^{e}_{t-l^{e}}$ have arrived,
we review the expedited inventory position

$IP_{t}^{e}=I_{t}+\sum\nolimits_{i=t-l^{e}+1}^{t-1}q^{e}_{i}+\sum\nolimits_{i=t-l^{r}+1}^{t-l}q^{r}_{i},$
(1)

and, if necessary, place an expedited order $q^{e}_{t}$ to raise $IP_{t}^{e}$
to its target level $S^{e}$, i.e. $q^{e}_{t}=(S^{e}-IP_{t}^{e})^{+}$. Note
that regular orders entering the information horizon for placing expedited
orders may cause the expedited inventory position to exceed this target level.
That is, immediately after expedited orders have been placed, there is an
overshoot defined as
$O_{t}=IP^{e}_{t}+q^{e}_{t}-S^{e}=(IP^{e}_{t}-S^{e})^{+}$. This implies that
the expedited inventory position following expedited ordering is in
expectation greater than or equal to the target level. In fact, strictly
greater unless products are sourced exclusively from the expedited supplier,
which we have argued is sub-optimal under the assumptions we make.

The PEIP policy aims to keep the expedited inventory position (and
consequently the overshoot) at a fixed level. Although the expedited inventory
position cannot actually be kept at a fixed level, it can be kept at a fixed
level in expectation. More specifically, the PEIP places regular orders such
that the expected expedited inventory position at the time those orders enter
the information horizon for expedited order placement is raised to a target
level. We henceforth refer to this target level as the projected expedited
inventory position level, denoted $U$.

Before we provide a formal description of this ordering rule, we first state
the following result related to the minimal required information for optimal
regular order placement given that the expedited supplier follows an order-up-
to rule. This information is sufficient to determine the expected expedited
inventory position in the period that the regular order placed now enters the
expedited inventory position.

###### Lemma 4.1

(Sheopuri et al. 2010, Lemma 4.1) Under the assumption that the expedited
supplier follows an order-up-to rule, the optimal regular order in period $t$,
$q_{t}^{r}$, depends on $\mathbf{x}_{t}$ and $q_{t}^{e}$ only through the
$l$-dimensional state description
$\mathbf{x}^{r}_{t}=(O_{t},q^{r}_{t-1},q^{r}_{t-2},\ldots,q^{r}_{t-l+1})$.

Observe from the definition of the expedited inventory position in (1) that
this inventory position in period $t+l$, i.e. $IP^{e}_{t+l}$, includes the
regular order $q_{t}^{r}$ that we will place in the current period $t$. We
write $\mathbb{E}[IP^{e}_{t+l}(q_{t}^{r})|\mathbf{x}^{r}_{t}]$ to denote the
conditional expected expedited inventory position $l$ periods into the future
in period $t$ given the current state of the system $\mathbf{x}^{r}_{t}$ as a
function of the regular order $q_{t}^{r}$ that we will place in period $t$.
The ordering rule for the regular supplier can now formally be described as
follows. In each period $t$ immediately after expedited ordering, we place a
regular order $q^{r}_{t}$ such that
$\mathbb{E}[IP^{e}_{t+l}|\mathbf{x}^{r}_{t}]$ equals the projected expedited
inventory position level $U$. That is, the period $t$ regular order
$q^{r}_{t}$ solves

$\mathbb{E}[IP^{e}_{t+l}(q_{t}^{r})|\mathbf{x}^{r}_{t}]=U.$ (2)

The solution to (2) is unique and can be computed efficiently via a simple
bisection search.

Proposition 4.2 below shows that under the PEIP policy, it is always possible
to place such a non-negative order (possibly zero) to attain the projected
expedited inventory position level $U$. We note that Van Jaarsveld and Arts
(2021) have established a similar result in the context of lost sales
inventory systems. The proof of the proposition can be found in Appendix 8.1.

###### Proposition 4.2

Under the PEIP policy, the conditional expected expedited inventory position
in period $t+l$ before regular ordering in period $t$ is less than or equal to
the projected expedited inventory position level $U$ for all periods
$t\in\mathbb{N}$.

It is worth noting that the regular ordering rule under the PEIP policy is of
the order-up-to type when the lead times of both suppliers are consecutive,
i.e. when $l=1$. To see this, recall that under such an order-up-to rule,
regular orders are placed such that the usual inventory position is kept at a
target level, say $S^{r}$. Now, observe that, following expedited ordering in
some period $t$, we have
$IP^{e}_{t+1}=S^{e}+O_{t}+q_{t}^{r}-D_{t}=S^{r}-D_{t}$, so that
$\mathbb{E}[IP^{e}_{t+1}|\mathbf{x}^{r}_{t}]=S^{r}-\mathbb{E}[D]$. Thus, when
$l=1$, the ordering rule for the regular supplier under a PEIP policy with
projected expedited inventory position level $U=S^{r}-\mathbb{E}[D]$ is
equivalent to an order-up-to rule with target level $S^{r}$. This observation
implies that for the special case of consecutive lead times, the PEIP policy
reduces to the optimal policy (Fukuda 1964). This feature is shared with the
CDI, DI, SI, and BWB policy, but not with the TBS policy.

###  4.2 Optimization procedure

We now turn to the issue of finding the optimal PEIP policy parameters.
Observe that the expedited inventory after ordering is bounded from below by
the order-up-to level $S^{e}$. This implies that the projected expedited
inventory position equals $S^{e}$ plus the projected overshoot. A given
projected expedited inventory position level $U$ thus only scales $IP^{e}$ for
a given $S^{e}$, which suggests that order placement depends on $S^{e}$ and
$U$ only through their difference. We state this observation formally in the
lemma below, which is a special case of Lemma 4.2 of Sheopuri et al. (2010):

###### Lemma 4.3

The distributions of $O$, $q^{r}$, and $q^{e}$ depend on $U$ and $S^{e}$ only
through their difference $V=U-S^{e}$.

As our discussion preceding Lemma 4.3 already alludes to, the difference $V$
has an explicit meaning that allows for an alternative but equivalent
specification and operation of the PEIP policy. Rather than keeping the
projected expedited inventory position at a fixed level, this alternative
specification places regular orders such that the expected overshoot is kept
at a fixed level (while retaining an order-up-to level $S^{e}$ for the
expedited supplier). To state this equivalence relation formally, observe that
$\mathbb{E}[O_{t+l}|\mathbf{x}^{r}_{t}]$ denotes the expected overshoot $l$
periods into the future at time $t$ given the system state at time $t$
following ordering, $\mathbf{x}^{r}_{t}$. In any period $t$ after ordering, we
have
$\mathbb{E}[IP^{e}_{t+l}|\mathbf{x}^{r}_{t}]=S^{e}+\mathbb{E}[O_{t+l}|\mathbf{x}^{r}_{t}]$.
Hence, placing regular orders such that
$\mathbb{E}[IP^{e}_{t+l}|\mathbf{x}^{r}_{t}]$ equals the projected expedited
inventory position level $U$ is equivalent to placing regular orders such that
$\mathbb{E}[O_{t+l}|\mathbf{x}^{r}_{t}]$ equals what we henceforth refer to as
the projected overshoot level $V=U-S^{e}$.

While the original specification of the PEIP policy has intuitive appeal, the
alternative specification outlined in the previous paragraph allows us to
decompose the optimization of the policy parameters into two simple uni-
variate optimization problems. Indeed, letting $O^{V}$ denote the steady state
overshoot random variable for a given $V$, the optimal order-up-to level
$S^{e*}$ for a given $V$ has a simple form:

###### Lemma 4.4

The optimal order-up-to level $S^{e*}$ for a given $V$ equals

$S^{e*}=\inf\left\\{S^{e}\in\mathbb{R}:\mathbb{P}\left(\mathbf{D}^{l^{e}+1}-O^{V}\leq
S^{e}\right)\geq\frac{p}{p+h}\right\\}.$

The result above implies that a simple search procedure over the projected
overshoot level $V$ suffices to find the globally optimal PEIP policy.

Lemma 4.4 is a special case of Lemma 4.3 of Sheopuri et al. (2010). Sheopuri
et al. (2010) show that this result holds in general for all policies that
have an order-up-to rule for the expedited supplier and operate some given
regular ordering rule that uses only the information contained in
$\mathbf{x}^{r}_{t}$. For all such policies, the optimal order-up-to level for
the expedited supplier can be interpreted as a standard Newsvendor model with
one additional feature. The ordering rule for the regular supplier essentially
dictates a return stream in the form of the overshoot which must therefore be
subtracted from the lead time demand to arrive at the net lead time demand
observed by the said Newsvendor. The PEIP policy has particular intuitive
appeal in the context of this Newsvendor with returns interpretation; it keeps
the expected amount to be returned $l$ periods into the future at a fixed
level.

##  5 Asymptotic optimality

In this section, we prove that the best PEIP policy is asymptotically optimal
when both the shortage cost and the cost premium for expedited units become
large, with their ratio held constant. We first elaborate on why it is
important and non-trivial to study this asymptotic regime. We then present the
asymptotic optimality result itself, and we subsequently show that this result
is robust in the sense that it holds true for a broad class of policies.

###  5.1 Regime of interest

We know from Xin and Goldberg (2018) that a simple TBS policy is
asymptotically optimal as the lead time difference between the regular
supplier and the expedited supplier approaches infinity. Unfortunately, the
policy performs poorly outside this asymptotic regime, particularly when
either the cost for a unit in backlog or the price charged by the expedited
supplier is large. When these costs grow large simultaneously, the performance
of the TBS drops precipitously (Klosterhalfen et al. 2011). It is however
exactly this latter asymptotic regime that is prevalent in practice, and thus
establishing asymptotic performance guarantees of the PEIP policy in this
regime has important practical implications. In the capital goods industry,
for instance, backordering a critical part comes at a high cost while
expediting shipments from an emergency supplier are expensive too (see, e.g.,
Westerweel et al. 2021).

In this section, we thus focus on the asymptotic regime where the unit
expediting cost $c^{e}$ and the shortage cost $p$ grow large simultaneously.
We do, however, need the assumption that their ratio is held fixed at a
constant strictly smaller than $l$ (i.e. $c^{e}<p\cdot l$). Recall from
Section 3 that if we would not impose this assumption, then ordering from the
expedited supplier over the regular supplier would never be beneficial. That
is, the dual-sourcing inventory problem would reduce to a trivial single
supplier inventory problem if $c^{e}\geq p\cdot l$.

We remark that, following a reasoning similar to the above, the asymptotic
regime where both $l$ and $c^{e}$ grow large with their ratio held fixed at a
constant strictly smaller than $p$ is, at least theoretically, interesting as
well. Indeed, this too is a non-trivial regime in which the optimal policy
does not reduce to a trivial single supplier inventory problem. Xin (2022) has
recently made advances on this latter regime by showing that for the
continuous time variant of the problem, the CDI policy has a worst-case
performance guarantee of 1.79.

###  5.2 Main results

To facilitate our analysis, we first introduce additional notation. Let
$C^{PEIP^{*}}(p,h,c^{e},l^{r},l^{e})$ and $C^{\pi^{*}}(p,h,c^{e},l^{r},l^{e})$
denote the long run average cost per period of the dual-sourcing inventory
system under the best PEIP policy and the optimal policy, respectively, as
functions of the problem specific input parameters. We may occasionally omit
certain input parameters when there is no ambiguity. We define the functions
$p(n)=p\cdot n$ and $c^{e}(n)=c^{e}\cdot n$, and we are hence interested in
the asymptotic regime where $n\to\infty$ with $\frac{c^{e}(n)}{p(n)}$ fixed at
a constant strictly smaller than $l$. For a given $n>0$, we further define
$C^{PEIP^{*}}(n)=C^{PEIP^{*}}(p(n),c^{e}(n))$ and
$C^{\pi^{*}}(n)=C^{\pi^{*}}(p(n),c^{e}(n))$ to denote the cost as we scale $p$
and $c^{e}$ proportionally with $n$.

Let $\mathcal{L}(p,h,l)$ and $\mathcal{B}(p,h,l)$ denote the canonical single
supplier inventory systems with lost sales and backlogged demand,
respectively, as defined in Janakiraman et al. (2007), Huh et al. (2009), and
Bijvank et al. (2014). Following their notation, let
$C^{\mathcal{L}^{*}}(p,h,l)$ denote the long run average cost per period under
an optimal policy in $\mathcal{L}(p,h,l)$ as a function of the lost sales
penalty cost $p$, the holding cost $h$, and the lead time $l$. Similarly, let
$C^{\mathcal{B}^{*}}(p,h,l)$ denote the long run average cost per period under
the optimal policy in $\mathcal{B}(p,h,l)$, with $p$ now denoting the penalty
cost for backlogged demand. It is well-known that the optimal policy for
$\mathcal{B}(p,h,l)$ is a simple order-up-to rule. It is equally well-known
that the optimal policy for $\mathcal{L}(p,h,l)$ has a complex structure and
depends in general on the entire vector of outstanding orders, very much akin
to the present dual-sourcing inventory system.

We first establish a lower bound on the long run average cost per period of
the optimal policy, i.e. $C^{\pi^{*}}(p,c^{e},l^{r},l^{e})$, in terms of both
the long run average cost per period of the optimal policy for
$\mathcal{B}(p,h,l)$, i.e. $C^{\mathcal{B}^{\star}}(p,h,l)$, and the optimal
policy for $\mathcal{L}(p,h,l)$, i.e. $C^{\mathcal{L}^{*}}(p,h,l)$.

###### Lemma 5.1

$C^{\mathcal{B}^{*}}(c^{e}/(l^{r}+1),h,l^{r})\leq
C^{\mathcal{L}^{*}}(c^{e},l^{r})\leq C^{\pi^{*}}(p,h,c^{e},l^{r},l^{e})$

###### Proof 5.2

Proof. Observe that a lower bound on the long run average cost per period of
the optimal policy is given by the long run average cost per period cost of an
optimal policy for a system identical to the present inventory system but in
which any backlogged demand at the end of a period is satisfied instantly by
the expedited supplier at unit price $c^{e}$, where we assume without loss of
generality that $c^{e}<p$. According to Theorem 3.1 of Sheopuri et al. (2010),
this system is exactly $\mathcal{L}$, where the lost sales penalty cost equals
$c^{e}$, i.e. $C^{\mathcal{L}^{*}}(c^{e},l^{r})$. Hence, we have
$C^{\pi^{*}}(p,c^{e},l^{r},l^{e})\geq C^{\mathcal{L}^{*}}(c^{e},l^{r})$. We
further know from Theorem 5 of Janakiraman et al. (2007) that
$C^{\mathcal{L}^{*}}(c^{e},l^{r})\geq
C^{\mathcal{B}^{*}}(c^{e}/(l^{r}+1),l^{r})$, and thus
$C^{\pi^{*}}(p,c^{e},l^{r},l^{e})\geq
C^{\mathcal{B}^{*}}(c^{e}/(l^{r}+1),l^{r})$.

We note in passing that easily computable lower bounds for the optimal cost of
dual-sourcing systems are relatively scarce. In fact, we are aware of only one
such lower bound in terms of the optimal policy for an equivalent dual-
sourcing system where the lead time difference is 1 (Sheopuri et al. 2010).
For this equivalent system, the optimal policy is myopic in that both
suppliers use an order-up-to level. In this respect, the lower bound in terms
of $\mathcal{B}(c^{e}/(l^{r}+1),l^{r})$ in Lemma 5.1 is of independent
interest as it is easy to compute and leads to an upper bound on the
optimality gap for any given policy.

Our main result requires the following technical assumption regarding the
cumulative demand over $l^{r}+1$ periods: The random variable
$\mathbf{D}^{l_{r}+1}$ has a positive and finite mean, i.e.
$0<\mathbb{E}[\mathbf{D}^{l_{r}+1}]<\infty$, and satisfies one of the
following conditions:

  1. i.

$\mathbf{D}^{l_{r}+1}$ is bounded, or

  2. ii.

$\mathbf{D}^{l_{r}+1}$ is unbounded and
$\lim_{d\to\infty}\mathbb{E}[\mathbf{D}^{l_{r}+1}-d|\mathbf{D}^{l_{r}+1}>d]/d=0$.

This assumption first appeared in Huh et al. (2009). They show that many
commonly used distributions in inventory models satisfy this assumption,
including Poisson distributions, geometric distributions, negative binomial
distributions with parameters $r>0$ and $0<p<1$, and (log-)normal
distributions. A sufficient condition for this assumption to be satisfied is
that the demand distribution has an increasing failure rate.

We are now in the position to state the main result of this section.

###### Theorem 5.3

Let the backorder penalty cost $p$ and the expedited cost premium $c^{e}$ be
such that $c^{e}/p<l$. Then, under Assumption 5.2, the best PEIP policy is
asymptotically optimal as $c^{e}$ and $p$ approach infinity simultaneously,
that is

$\lim\nolimits_{n\to\infty}\frac{C^{PEIP^{*}}(n)}{C^{\pi^{*}}(n)}=1.$

###### Proof 5.4

Proof. Observe that single sourcing from the regular supplier is a feasible
PEIP policy by setting $S^{e}$ equal to $\infty$. This observation implies
that the numerator is bounded from above by the long run average cost per
period of an optimal policy in a single supplier inventory system with
backlogged demand whose lead time is equal to the lead time of the regular
supplier, i.e. $C^{\mathcal{B}^{*}}(p,h,l^{r})\geq
C^{PEIP^{*}}(p,h,c^{e},l^{r},l^{e})$. Combining this observation with Lemma
5.1, we have

$\frac{C^{PEIP^{*}}(n)}{C^{\pi^{*}}(n)}\leq\frac{C^{\mathcal{B}^{*}}(p(n),h,l^{r})}{C^{\mathcal{B}^{*}}(c^{e}(n)/(l^{r}+1),h,l^{r})}.$

By Theorem 2b of Huh et al. (2009), we know that under Assumption 5.2

$\lim\nolimits_{n\to\infty}\frac{C^{\mathcal{B}^{*}}(p(n),h,l^{r})}{C^{\mathcal{B}^{*}}(c^{e}(n)/(l^{r}+1),h,l^{r})}=1,$

which gives the desired result.

Define the subset
$\tilde{\Pi}=\\{\pi\in\Pi|C^{\pi^{\star}}(p,h,c^{e},l^{r},l^{e})\leq
C^{\mathcal{B}^{*}}(p,h,l^{r})\\}$. Note that it readily follows from the
definition of $\tilde{\Pi}$ and the proof of Theorem 5.3, that any policy
$\pi\in\tilde{\Pi}$ is asymptotically optimal in the regime under our
consideration. This is an important observation that generalizes our result to
a wide class of policies. We therefore state it as a theorem.

###### Theorem 5.5

Let the backorder penalty cost $p$ and the expedited cost premium $c^{e}$ be
such that $c^{e}/p<l$. Then, under Assumption 5.2, any policy
$\tilde{\pi}\in\tilde{\Pi}$ is asymptotically optimal as $c^{e}$ and $p$
approach infinity simultaneously, that is

$\lim\nolimits_{n\to\infty}\frac{C^{\tilde{\pi}^{*}}(n)}{C^{\pi^{*}}(n)}=1,$

where $C^{\tilde{\pi}^{*}}(n)$ is defined in a way similar as
$C^{\pi^{*}}(n)$.

We conclude this section by noting that the CDI, DI, and SI policy are all
contained in the set $\tilde{\Pi}$. They are thus asymptotically optimal when
both $c^{e}$ and $p$ grow large with their ratio held fixed at a constant
strictly smaller than $l$.

##  6 Numerical investigation

The theoretical results of the previous section are important as they provide
performance guarantees for the PEIP policy in high service regimes where
expedited orders are expensive. While this is particularly useful for
practitioners operating in those regimes, it does not imply that the PEIP
policy consistently performs well, especially outside those asymptotic
regimes. In this section, we therefore undertake an extensive numerical
investigation to examine the overall effectiveness of the PEIP policy, thereby
complementing the theory of the previous section. This investigation mainly
revolves around the comparison of the performance of the PEIP policy with the
performance of several existing heuristic polices.

We first describe the benchmark heuristic policies in Section 6.1. We then
continue with the numerical investigation itself, which consists of two parts.
The first part, Section 6.2, compares the performance of the PEIP policy with
the performance of the benchmark heuristic policies based on a full factorial
test bed of industrial size. The second part, Section 6.3, analyzes the
performance of the PEIP policy as well as the benchmark heuristic policies as
the lead time difference between both suppliers grows large. It is exactly
this regime where a simple TBS policy is asymptotically optimal (Xin and
Goldberg 2018).

###  6.1 Benchmark heuristic policies and computational aspects

The following five heuristic policies will serve as benchmarks: (i) The DI
policy, (ii) the CDI policy, (iii) the VBS policy, (iv) the BWB policy, and
(v) the TBS policy. Although we have discussed these five heuristic policies
in our literature review, we revisit a few points here that are important to
bear in mind while considering the results of the numerical investigation.

First, the CDI policy and the BWB policy are the current best performing
heuristic policies. Their computational requirements are however significantly
higher than the PEIP policy. Indeed, while the PEIP policy requires only a
one-dimensional search to find the optimal policy parameters, both the CDI
policy and the BWB policy require a search over two dimensions to arrive at
their best policy parameters. By contrast, the DI policy, VBS policy, and the
TBS policy have the same computational requirements as the PEIP policy.
Second, the CDI policy is a generalization of the DI policy, and it is
therefore to be expected that the former policy outperforms the latter. The
same holds for the BWB policy and the VBS policy – the latter being a special
case of the former. Third, all five benchmark heuristic policies use an order-
up-to rule for the expedited supplier. As such, echoing our discussion after
Lemma 4.4, the optimal order-up-to level under each policy for given regular
ordering rule parameters follows a Newsvendor type equation. This is
convenient numerically as it only requires us to simulate the steady state
overshoot distribution for given regular ordering rule parameters to arrive at
the corresponding optimal order-up-to level. We describe this simulation-based
optimization scheme in detail next.

For all problem instances in this numerical investigation, we find the best
policy parameters for the PEIP policy as well as for the benchmark heuristic
policies via golden-section searches over their respective regular ordering
rule parameters. In each iteration of this search procedure, we first compute
the steady state overshoot distribution via simulation, we then determine the
optimal order-up-to level via the Newsvendor equation, and we finally compute
the corresponding long run average cost per period. We use common random
numbers across all policies per problem instance, and we continue simulating
the steady state overshoot distribution until the width of the 95 percent
confidence intervals for the mean and for the standard deviation of the
overshoot are less than 1 percent of their respective point estimates. After
we find the best control policy parameters for all heuristic policies for a
given problem instance, we compute the long run average cost per period for
each heuristic policy under its best policy parameters via simulation. As in
the simulation-based optimization scheme, this simulation uses common random
numbers across policies, and it continues until the width of the 95 percent
confidence intervals for the long run average cost per period is less than 1
percent of its point estimate.

###  6.2 Full factorial experiment

We start our numerical investigation by comparing the performance of the PEIP
policy with the performance of the heuristic policies described in the
previous section. We do so based on a large test bed of industrial size. Note
that the optimal policy cannot be computed for such large instances due to the
complexity of the corresponding dynamic program. We therefore exclude the
optimal policy in this investigation.

In all instances of the test bed, the one period demand has a negative
binomial distribution with mean 50 and the holding cost $h$ is fixed at 1. We
further keep the price of the regular supplier $c^{r}$ fixed at 0 since only
the cost difference between the suppliers affects the relative cost rate. The
expedited lead time $l^{e}$ is kept fixed at 0 periods so that the focus is on
the lead time difference $l=l^{r}-l^{e}=l^{r}$. The remaining input parameters
are varied over multiple levels. We vary the backorder penalty cost over five
levels ($p\in\\{4,9,19,49,99\\}$), the coefficient of variation of the one
period demand over five levels
($\sigma_{\text{D}}/\mathbb{E}[\text{D}]\in\\{0.15,0.25,0.5,1,1.5,2\\}$), and
the regular lead time over four levels ($l^{r}\in\\{2,3,4,5\\}$). We set the
price of the expedited supplier $c^{e}$ equal to a fraction of the backorder
penalty cost multiplied by the lead time difference of the specific instance,
that is, $c^{e}=\delta pl$ for $\delta\in\\{0.1,0.2,0.4\\}$. While this
approach is different from most numerical studies on dual-sourcing inventory
systems, it does ensure that there is no instance in the test bed for which
exclusively sourcing from the regular supplier is optimal. Table 1 summarizes
all levels for each input parameter in our test bed that is not kept fixed.
Permuting over all these levels leads to a large test bed of 360 instances.

Table 1: Input parameter values for our test bed |  Input parameter | No. of choices | Values
---|---|---|---
1 |  Backorder penalty cost, $p$ | 5 | 4, 9, 19, 49, 99
2 |  Regular lead time, $l^{r}$ | 4 | 2, 3, 4, 5
3 |  Coefficient of variation of demand, $\sigma_{\text{D}}/\mathbb{E}[\text{D}]$ | 6 | 0.15, 0.25, 0.5, 1, 1.5, 2
4 |  Price of the expedited supplier, $c^{e}$ | 3 |  $\delta pl$ for $\delta$ = 0.1, 0.2, 0.4

We are interested in the performance of the PEIP policy in comparison with the
performance of the benchmark heuristics. To that end, we compute for each
instance of the test bed the percentage gap in the long run average cost per
period of each benchmark heuristic policy
$\pi\in\\{\text{DI,CDI,VBS,BWB,TBS}\\}$ relative to the PEIP policy:
$100\cdot\frac{C^{\pi^{\star}}-C^{\text{PEIP}^{\star}}}{C^{\text{PEIP}^{\star}}}$.

Table 2 summarizes the numerical results of the full factorial experiment. The
table presents the average, maximum, and minimum gap percentages for each
benchmark heuristic policy computed over all instances as well as the
percentage of test instances in which the PEIP policy outperforms the specific
benchmark heuristic policy. (A positive gap percentage implies that the PEIP
policy outperforms the specific benchmark heuristic policy.) Detailed results
are relegated to Appendix 9. Based on this table, we conclude that the PEIP
policy outperforms the TBS, DI, CDI, and VBS policy. The performance of the
PEIP policy seems to be comparable with the BWB policy, though on average the
PEIP policy outperforms this policy as well. It is also interesting to note
that the PEIP policy can outperform the BWB and CDI policy by up to 2.67% and
4.67%, respectively. The opposite never holds. Indeed, when the PEIP policy is
outperformed by the BWB or CDI policy, it only occurs by much smaller margins
of up to 0.29% and 0.08%, respectively. Note that these gaps are smaller than
the confidence interval around the estimated performance for any single
instance. This is an interesting observation, especially in view of the fact
that the BWB and CDI policy are the current best performing heuristic
policies, and have considerably higher computational requirements than the
PEIP policy. Furthermore, these policies have more parameters and the BWB
policy is arguably difficult to communicate to practitioners.

Table 2: Summary of full factorial experiment Heuristic | Avg | Max | Min | %
---|---|---|---|---
VBS | 0.15 | 3.15 | -0.05 | 90
BWB | 0.03 | 2.67 | -0.29 | 42
DI | 0.71 | 4.97 | 0.00 | 100
CDI | 0.19 | 4.67 | -0.08 | 94
TBS | 55.11 | 373.88 | 1.68 | 100

###  6.3 Long lead time difference regime

We will now examine the performance of the PEIP policy as well as the
benchmark heuristic policies for increasingly larger lead time differences
$l$. To that end, we will study a test instance in which we only vary $l$. The
cost parameters in this test instance are fixed as follows: $h=1$, $p=19$, and
$c^{e}=5$. As in the previous section, the one period demand has a negative
binomial distribution with mean 50, with
$\sigma_{\text{D}}/\mathbb{E}[\text{D}]$ now fixed at 0.25.

Since the TBS policy is asymptotically optimal as the lead time difference $l$
grows large (Xin and Goldberg 2018), we will now use the relative difference
between the long run average cost per period of each heuristic policy with the
long run average cost per period of the TBS policy as the main performance
measure. To that end, we compute the percentage improvement/reduction in the
long run average cost per period of each heuristic policy
$\pi\in\\{\text{PEIP,BWB,VBS,CDI,DI}\\}$ relative to the TBS policy:
$\%\mathit{RED}=100\cdot\frac{C^{\text{TBS}^{\star}}-C^{\pi^{\star}}}{C^{\text{TBS}^{\star}}}$.
Note that the long run average cost of a TBS policy is insensitive to $l$
(see, e.g., Klosterhalfen et al. 2011). The long run average cost per period
of the best TBS policy, i.e. $C^{\text{TBS}^{\star}}$, thus remains constant
as we vary $l$.

Table 3 provides the gap percentages for increasingly larger values of $l$,
along with the variability of the orders placed with the regular supplier
computed through simulation. Based on this table, we can draw three main
conclusions. First, the PEIP policy has the best relative improvement over the
TBS policy for each value of $l$. Second, even for values of $l$ that would be
considered large in practice, the PEIP, BWB, CDI, and VBS policy outperform
the TBS policy. Third, the variability of the orders placed with the regular
supplier under the PEIP policy decreases in $l$. This suggests that the PEIP
policy will increasingly mimic the TBS policy as the lead time difference
grows. (Note that the TBS policy has zero variability in its regular orders.)
The same holds for the BWB, CDI, and VBS policy. Whether these four heuristic
policies are asymptotically optimal when $l$ grows large is an open question.

Table 3: Long lead times regime |  | PEIP |  | BWB |  | VBS |  | CDI |  | DI
---|---|---|---|---|---|---|---|---|---|---
$l$ |  | $\%\mathit{RED}$ |  Var[Qr] |  | $\%\mathit{RED}$ |  Var[Qr] |  | $\%\mathit{RED}$ |  Var[Qr] |  | $\%\mathit{RED}$ |  Var[Qr] |  | $\%\mathit{RED}$ |  Var[Qr]
2 |  | 21.81 | 104.02 |  | 21.80 | 100.03 |  | 21.75 | 113.03 |  | 21.76 | 110.57 |  | 21.53 | 132.25
4 |  | 12.03 | 59.90 |  | 11.98 | 48.97 |  | 11.78 | 73.87 |  | 11.95 | 46.98 |  | 10.30 | 127.67
6 |  | 7.50 | 33.64 |  | 7.37 | 34.61 |  | 6.86 | 51.23 |  | 7.32 | 24.62 |  | 4.06 | 125.51
8 |  | 5.18 | 21.27 |  | 4.97 | 24.97 |  | 4.23 | 36.49 |  | 5.09 | 15.72 |  | 0.17 | 125.45
10 |  | 3.81 | 14.42 |  | 3.52 | 18.24 |  | 3.06 | 19.86 |  | 3.66 | 9.03 |  | -2.53 | 124.25
12 |  | 3.05 | 9.23 |  | 2.72 | 14.85 |  | 2.55 | 11.38 |  | 2.84 | 8.81 |  | -4.60 | 124.05
14 |  | 2.43 | 6.97 |  | 2.04 | 12.08 |  | 2.00 | 9.89 |  | 2.09 | 2.55 |  | -6.26 | 122.81
16 |  | 2.06 | 5.29 |  | 1.78 | 10.47 |  | 1.78 | 3.63 |  | 1.83 | 2.74 |  | -7.63 | 123.37
18 |  | 1.68 | 3.84 |  | 1.61 | 4.26 |  | 1.56 | 2.95 |  | 1.57 | 2.51 |  | -8.57 | 123.48
20 |  | 1.45 | 3.01 |  | 1.36 | 2.79 |  | 1.34 | 2.50 |  | 0.09 | 0.02 |  | -9.25 | 122.61

##  7 Concluding remarks

In this paper, we have proposed the PEIP policy for dual-sourcing inventory
systems. This policy uses an order-up-to rule for the expedited supplier, and
places regular orders such that the expected expedited inventory position at
the time of the regular order entering the expedited inventory position is
raised to a target level. In doing so, the PEIP policy leverages all the
information contained in the pipeline – as does the optimal policy. This is in
contrast with existing heuristic policies that either aggregate all
outstanding orders or ignore them entirely and place a constant order every
period regardless. We have further established a separability result that
reduces the optimization of the PEIP policy to two simple one-dimensional
optimization problems. An extensive numerical investigation has indicated that
the PEIP policy outperforms the current best performing heuristic policies,
even the ones that employ more control parameters than the PEIP policy. The
PEIP policy is thus vastly more advanced than existing heuristic policies, and
yet retains an intuitive appeal for practitioners, has superior performance,
and can be optimized efficiently.

We have shown that the PEIP policy is asymptotically optimal when the unit
shortage cost and the unit price charged by the expedited supplier approach
infinity simultaneously with their ratio held fixed at a constant. This result
is useful for practice as it implies that the PEIP policy has asymptotic
performance guarantees in high service regimes where utilizing an expedited
source is expensive. We have further illustrated that this asymptotic
optimality result is robust in the sense that it holds true for a wide class
of dual-sourcing heuristic policies, including the CDI, DI, and SI policy. Our
proof technique in itself has merit too since it can serve as a template that
is readily applicable to future heuristic policies. As such, we have extended
the literature on asymptotic optimality results for dual-sourcing inventory
systems.

Our numerical investigation also poses an interesting question: Is the PEIP
policy asymptotically optimal as the lead time difference between both
suppliers grows large? Our numerical results provide strong evidence that this
may be the case. An answer to this question for the PEIP and other policies is
left for future research.

The research of the first author is supported by the National Research Fund of
Luxembourg through AFR grant 12451704.

## References

  * Allon and Van Mieghem (2010) Allon G, Van Mieghem J (2010) Global dual sourcing: Tailored base-surge allocation to near-and offshore production. _Management Science_ 56(1):110–124.
  * Arts et al. (2016) Arts J, Basten R, Van Houtum G (2016) Repairable stocking and expediting in a fluctuating demand environment: Optimal policy and heuristics. _Operations Research_ 64(6):1285–1301.
  * Arts et al. (2011) Arts J, Van Vuuren M, Kiesmüller G (2011) Efficient optimization of the dual-index policy using markov chains. _IIE Transactions_ 43(8):604–620.
  * Barankin (1961) Barankin E (1961) A delivery-lag inventory model with an emergency provision (the single-period case). _Naval Research Logistics (NRL)_ 8(3):285–311.
  * Bijvank et al. (2014) Bijvank M, Huh WT, Janakiraman G, Kang W (2014) Robustness of order-up-to policies in lost-sales inventory systems. _Operations Research_ 62(5):1040–1047.
  * Boute and Van Mieghem (2015) Boute R, Van Mieghem J (2015) Global dual sourcing and order smoothing: The impact of capacity and lead times. _Management Science_ 61(9):2080–2099.
  * Drent and Arts (2021) Drent M, Arts J (2021) Expediting in two-echelon spare parts inventory systems. _Manufacturing & Service Operations Management_ 23(6):1431–1448.
  * Feng et al. (2006) Feng Q, Sethi S, Yan H, Zhang H (2006) Are base-stock policies optimal in inventory problems with multiple delivery modes? _Operations Research_ 54(4):801–807.
  * Fu et al. (2019) Fu K, Gong X, Liang G (2019) Managing perishable inventory systems with product returns and remanufacturing. _Production and Operations Management_ 28(6):1366–1386.
  * Fukuda (1964) Fukuda Y (1964) Optimal policies for the inventory problem with negotiable leadtime. _Management Science_ 10(4):690–708.
  * Gijsbrechts et al. (2022) Gijsbrechts J, Boute R, van Mieghem J, Zhang D (2022) Can deep reinforcement learning improve inventory management? performance on dual sourcing, lost sales and multi-echelon problems. _Manufacturing & Service Operations Management_ 24(3):1349–1368.
  * Goldberg et al. (2016) Goldberg D, Katz-Rogozhnikov D, Lu Y, Sharma M, Squillante M (2016) Asymptotic optimality of constant-order policies for lost sales inventory models with large lead times. _Mathematics of Operations Research_ 41(3):898–913.
  * Goldberg et al. (2021) Goldberg DA, Reiman MI, Wang Q (2021) A survey of recent progress in the asymptotic analysis of inventory systems. _Production and Operations Management_ 30(6):1718–1750.
  * Gong et al. (2014) Gong X, Chao X, Zheng S (2014) Dynamic pricing and inventory management with dual suppliers of different lead times and disruption risks. _Production and Operations Management_ 23(12):2058–2074.
  * Hua et al. (2015) Hua Z, Yu Y, Zhang W, Xu X (2015) Structural properties of the optimal policy for dual-sourcing systems with general lead times. _IIE Transactions_ 47(8):841–850.
  * Huh et al. (2009) Huh T, Janakiraman G, Muckstadt JA, Rusmevichientong P (2009) Asymptotic optimality of order-up-to policies in lost sales inventory systems. _Management Science_ 55(3):404–420.
  * Janakiraman et al. (2018) Janakiraman G, Nagarajan M, Veeraraghavan S (2018) Simple policies for managing flexible capacity. _Manufacturing & Service Operations Management_ 20(2):333–346.
  * Janakiraman et al. (2007) Janakiraman G, Seshadri S, Shanthikumar G (2007) A comparison of the optimal costs of two canonical inventory systems. _Operations Research_ 55(5):866–875.
  * Janakiraman et al. (2015) Janakiraman G, Seshadri S, Sheopuri A (2015) Analysis of tailored base-surge policies in dual sourcing inventory systems. _Management Science_ 61(7):1547–1561.
  * Janssen and de Kok (1999) Janssen F, de Kok T (1999) A two-supplier inventory model. _International journal of production economics_ 59(1):395–403.
  * Klosterhalfen et al. (2011) Klosterhalfen S, Kiesmüller G, Minner S (2011) A comparison of the constant-order and dual-index policy for dual sourcing. _International Journal of Production Economics_ 133(1):302 – 311.
  * Minner (2003) Minner S (2003) Multiple-supplier inventory models in supply chain management: A review. _International Journal of Production Economics_ 81:265–279.
  * Neuts (1964) Neuts M (1964) An inventory model with an optional time lag. _Journal of the Society for Industrial and Applied Mathematics_ 12(1):179–185.
  * Rao et al. (2000) Rao U, Scheller-Wolf A, Tayur S (2000) Development of a rapid-response supply chain at caterpillar. _Operations Research_ 48(2):189–204.
  * Rong et al. (2017) Rong Y, Atan Z, Snyder L (2017) Heuristics for base‐stock levels in multi‐echelon distribution networks. _Production and Operations Management_ 26(9):1760–1777.
  * Rosenshine and Obee (1976) Rosenshine M, Obee D (1976) Analysis of a standing order inventory system with emergency orders. _Operations Research_ 24(6):1143–1155.
  * Sapra (2017) Sapra A (2017) Dual sourcing in a serial system. _Production and Operations Management_ 26(12):2163–2174.
  * Scheller-Wolf et al. (2007) Scheller-Wolf A, Veeraraghavan S, van Houtum G (2007) Effective dual sourcing with a single index policy, working paper.
  * Sheopuri et al. (2010) Sheopuri A, Janakiraman G, Seshadri S (2010) New policies for the stochastic inventory control problem with two supply sources. _Operations Research_ 58(3):734–745.
  * Song et al. (2017) Song J, Xiao L, Zhang H, Zipkin P (2017) Optimal policies for a dual-sourcing inventory problem with endogenous stochastic lead times. _Operations Research_ 65(2):379–395.
  * Sun and Van Mieghem (2018) Sun J, Van Mieghem J (2018) Robust dual sourcing inventory management: Optimality of capped dual index policies and smoothing. _Manufacturing & Service Operations Management_ Forthcoming.
  * Svoboda et al. (2021) Svoboda J, Minner S, Yao M (2021) Typology and literature review on multiple supplier inventory control models. _European Journal of Operational Research_ 293(1):1–23.
  * Threatte and Graves (2002) Threatte K, Graves S (2002) Tactical shipping and scheduling at polaroid with dual lead-times (Proceedings SMA Conference).
  * Van Jaarsveld and Arts (2021) Van Jaarsveld W, Arts J (2021) Projected inventory level policies for lost sales inventory systems: Asymptotic optimality in two regimes. _arXiv preprint arXiv:2101.07519_ .
  * Veeraraghavan and Scheller-Wolf (2008) Veeraraghavan S, Scheller-Wolf A (2008) Now or later: A simple policy for effective dual sourcing in capacitated systems. _Operations Research_ 56(4):850–864.
  * Westerweel et al. (2021) Westerweel B, Basten R, den Boer J, van Houtum GJ (2021) Printing spare parts at remote locations: Fulfilling the promise of additive manufacturing. _Production and Operations Management_ 30(6):1615–1632.
  * Whittemore and Saunders (1977) Whittemore A, Saunders S (1977) Optimal inventory under stochastic demand with two supply options. _SIAM Journal on Applied Mathematics_ 32(2):293–305.
  * Xin (2021) Xin L (2021) Understanding the performance of capped base-stock policies in lost-sales inventory models. _Operations Research_ 69(1):61–70.
  * Xin (2022) Xin L (2022) 1.79-approximation algorithms for continuous review single-sourcing lost-sales and dual-sourcing inventory models. _Operations Research_ 70(1):111–128.
  * Xin and Goldberg (2016) Xin L, Goldberg D (2016) Optimality gap of constant-order policies decays exponentially in the lead time for lost sales models. _Operations Research_ 64(6):1556–1565.
  * Xin and Goldberg (2018) Xin L, Goldberg D (2018) Asymptotic optimality of tailored base-surge policies in dual-sourcing inventory systems. _Management Science_ 64(1):437–452.

##  8 Proof of Proposition 4.2

###### Proof 8.1

Proof of Proposition 4.2 Following our discussion after Lemma 4.3, it suffices
to prove that in any period $t\in\mathbb{N}$, we can place a non-negative
regular order so that $\mathbb{E}[O_{t+l}|\mathbf{x}^{r}_{t}]$ equals the
projected overshoot level $V$. For ease of exposition, we will now denote the
regular order placed in period $t$ with $q^{r}_{t+l}$ such that the order
entering the expedited inventory position in period $t$ is denoted
$q^{r}_{t}$.

Due to our assumption on the initial state, i.e. $\mathbf{x}_{0}=\mathbf{0}$,
we have that $\exists q^{r}_{l}\geq 0$ such that
$\mathbb{E}[O_{l}|\mathbf{x}^{r}_{0}]=\mathbb{E}[(O_{l-1}+q^{r}_{l}-D_{l-1})^{+}|\mathbf{x}^{r}_{0}]=V$.
We define ${Y}_{t}=(O_{t}-D_{t})^{+}$. It suffices now to show that
$\mathbb{E}[Y_{l}|\mathbf{x}^{r}_{0},D_{0}=0]\leq\mathbb{E}[O_{l}|\mathbf{x}^{r}_{0}]=V$
because $\mathbb{E}[Y_{l}|\mathbf{x}^{r}_{0},D_{t}=0]$ is the minimum
projected overshoot level as seen in period $1$ before a regular order is
placed. Observe that

$Y_{l}|(\mathbf{x}^{r}_{0},D_{0}=0)=(((\ldots((O_{0}+q^{r}_{1})^{+}+q_{2}^{r}-D_{1})^{+}\ldots)^{+}+q^{r}_{l}-D_{l-1})^{+}-D_{l})^{+},$

and

$O_{l}|\mathbf{x}^{r}_{0}=((\ldots((O_{0}+q^{r}_{1}-D_{0})^{+}+q_{2}^{r}-D_{1})^{+}\ldots)^{+}+q^{r}_{l}-D_{l-1})^{+}.$

It is easy to verify through exhaustion and the fact that $(x)^{+}$ is
monotone increasing that $Y_{l}|(\mathbf{x}^{r}_{0},D_{0}=0)\leq
O_{l}|\mathbf{x}^{r}_{0}$ state-wise and thus
$\mathbb{E}[Y_{l}|\mathbf{x}^{r}_{0},D_{0}=0]\leq\mathbb{E}[O_{l}|\mathbf{x}^{r}_{0}]=V$.

##  9 Detailed results numerical investigation

Table 4 presents the percentage gap in the long run average cost per period of
each benchmark heuristic policy relative to the PEIP policy. In this table, we
first distinguish between subsets of instances with the same value for a
specific input parameter of Table 1 and then present the results for all
instances.

Table 4: Detailed result full factorial experiment |  | VBS |  | BWB |  | DI |  | CDI |  | TBS
---|---|---|---|---|---|---|---|---|---|---
Parameter | Value | Avg | Max | Min | % |  | Avg | Max | Min | % |  | Avg | Max | Min | % |  | Avg | Max | Min | % |  | Avg | Max | Min | %
$p$ | 4 | 0.32 | 0.65 | 0.08 | 100 |  | 0.09 | 0.45 | -0.11 | 78 |  | 1.76 | 4.97 | 0.23 | 100 |  | 0.36 | 4.19 | 0.06 | 100 |  | 10.73 | 30.99 | 1.68 | 100
9 | 0.20 | 0.62 | 0.02 | 100 |  | 0.01 | 0.27 | -0.21 | 47 |  | 1.01 | 3.27 | 0.11 | 100 |  | 0.28 | 4.32 | 0.02 | 100 |  | 21.74 | 58.51 | 4.48 | 100
19 | 0.08 | 0.33 | -0.05 | 96 |  | -0.04 | 0.66 | -0.29 | 22 |  | 0.50 | 1.73 | 0.04 | 100 |  | 0.15 | 3.10 | 0.01 | 100 |  | 38.35 | 90.34 | 9.34 | 100
49 | 0.12 | 3.15 | -0.03 | 83 |  | -0.03 | 0.46 | -0.18 | 26 |  | 0.17 | 0.61 | 0.00 | 100 |  | 0.04 | 0.43 | -0.07 | 92 |  | 76.82 | 199.62 | 23.71 | 100
99 | 0.02 | 0.09 | -0.02 | 72 |  | 0.12 | 2.67 | -0.13 | 35 |  | 0.11 | 2.81 | 0.00 | 100 |  | 0.12 | 4.67 | -0.08 | 79 |  | 127.90 | 373.88 | 32.34 | 100
$l^{r}$ | 2 | 0.07 | 0.29 | 0.00 | 94 |  | 0.08 | 2.67 | -0.05 | 51 |  | 0.27 | 1.36 | 0.00 | 100 |  | 0.05 | 0.29 | -0.01 | 90 |  | 48.75 | 235.21 | 1.75 | 100
3 | 0.15 | 2.64 | -0.01 | 92 |  | 0.02 | 0.73 | -0.10 | 42 |  | 0.58 | 2.80 | 0.01 | 100 |  | 0.17 | 4.32 | -0.02 | 96 |  | 54.35 | 286.08 | 1.68 | 100
4 | 0.15 | 0.54 | -0.01 | 90 |  | 0.02 | 0.85 | -0.18 | 38 |  | 0.85 | 3.86 | 0.00 | 100 |  | 0.26 | 4.67 | -0.07 | 97 |  | 57.45 | 334.64 | 1.76 | 100
5 | 0.21 | 3.15 | -0.05 | 84 |  | 0.00 | 1.31 | -0.29 | 36 |  | 1.14 | 4.97 | 0.01 | 100 |  | 0.27 | 4.19 | -0.08 | 94 |  | 59.87 | 373.88 | 1.70 | 100
$\frac{\sigma_{D}}{\mathbb{E}[D]}$ | 0.15 | 0.24 | 3.15 | -0.02 | 97 |  | 0.09 | 2.67 | -0.14 | 52 |  | 0.81 | 4.97 | 0.00 | 100 |  | 0.28 | 4.67 | -0.08 | 92 |  | 76.50 | 373.88 | 4.29 | 100
0.25 | 0.15 | 0.61 | 0.00 | 100 |  | 0.09 | 2.47 | -0.18 | 42 |  | 0.81 | 4.87 | 0.01 | 100 |  | 0.13 | 1.46 | -0.02 | 92 |  | 63.18 | 240.11 | 3.85 | 100
0.5 | 0.12 | 0.62 | 0.00 | 98 |  | -0.03 | 0.85 | -0.20 | 30 |  | 0.79 | 4.39 | 0.01 | 100 |  | 0.24 | 4.32 | -0.01 | 95 |  | 60.73 | 292.31 | 3.38 | 100
1 | 0.10 | 0.60 | -0.01 | 83 |  | -0.03 | 0.44 | -0.18 | 25 |  | 0.72 | 3.37 | 0.02 | 100 |  | 0.13 | 0.79 | -0.01 | 92 |  | 49.06 | 228.77 | 2.68 | 100
1.5 | 0.11 | 0.44 | -0.02 | 78 |  | 0.00 | 0.20 | -0.21 | 43 |  | 0.61 | 2.62 | 0.01 | 100 |  | 0.15 | 0.52 | 0.00 | 98 |  | 43.74 | 214.23 | 2.11 | 100
2 | 0.15 | 0.55 | -0.05 | 85 |  | 0.05 | 0.45 | -0.29 | 58 |  | 0.54 | 2.81 | 0.01 | 100 |  | 0.19 | 2.79 | 0.00 | 97 |  | 37.43 | 177.20 | 1.68 | 100
$c^{e}=\delta pl$ | 0.1 | 0.20 | 0.65 | -0.02 | 93 |  | 0.02 | 0.45 | -0.18 | 51 |  | 1.15 | 4.97 | 0.03 | 100 |  | 0.27 | 4.67 | -0.08 | 90 |  | 24.68 | 88.41 | 1.70 | 100
0.2 | 0.15 | 0.62 | -0.03 | 89 |  | 0.02 | 2.67 | -0.20 | 37 |  | 0.78 | 3.39 | 0.02 | 100 |  | 0.21 | 4.19 | -0.01 | 94 |  | 48.60 | 182.03 | 4.48 | 100
0.4 | 0.11 | 3.15 | -0.05 | 89 |  | 0.06 | 2.47 | -0.29 | 44 |  | 0.43 | 2.81 | 0.00 | 100 |  | 0.15 | 2.79 | -0.01 | 97 |  | 89.73 | 373.88 | 9.82 | 100
Total |  | 0.15 | 3.15 | -0.05 | 90 |  | 0.03 | 2.67 | -0.29 | 42 |  | 0.71 | 4.97 | 0.00 | 100 |  | 0.19 | 4.67 | -0.08 | 94 |  | 55.11 | 373.88 | 1.68 | 100