Inventory Management

STUDIES OF INVENTORY CONTROL AND CAPACITY PLANNING
WITH MULTIPLE SOURCES

A Dissertation
Presented to
The Academic Faculty

By

Frederick Craig Zahrn

In Partial Fulﬁllment
Of the Requirements for the Degree
Doctor of Philosophy in Industrial Engineering

Georgia Institute of Technology
August 2009

STUDIES OF INVENTORY CONTROL AND CAPACITY PLANNING
WITH MULTIPLE SOURCES

Approved by:
Dr. Shi-Jie Deng, Advisor
School of Industrial and Systems
Engineering
Georgia Institute of Technology
Dr. John H. Vande Vate, Advisor
School of Industrial and Systems
Engineering
Georgia Institute of Technology
Dr. Hayriye Ayhan
School of Industrial and Systems
Engineering
Georgia Institute of Technology

Dr. Mark E. Ferguson
College of Management
Georgia Institute of Technology
Dr. Anton J. Kleywegt
School of Industrial and Systems
Engineering
Georgia Institute of Technology

Date Approved: July 6, 2009

ACKNOWLEDGMENTS

I thank my advisors, Dr. Shi-Jie Deng and Dr. John H. Vande Vate, for their guidance of my research. I am particularly indebted to them—Prof. Vande Vate especially— for technical and expository advice in the portion of the dissertation on capacity planning. I also thank Dr. R. Gary Parker for his support of my graduate studies.

iii

TABLE OF CONTENTS

Acknowledgments

iii

Summary

v

Chapter 1: Average optimal control in an inventory model with multiple sources
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Inventory control with a convex ordering cost function .
1.2.2 Inventory control under average cost criteria . . . . . . .
1.3 Formal problem statement and proof strategy . . . . . . . . . .
1.4 Technical arguments . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Preliminary analytical results . . . . . . . . . . . . . . .
1.4.2 Relaxed model, ﬁnite-horizon discounted setting . . . . .
1.4.3 Relaxed model, inﬁnite-horizon discounted setting . . . .
1.4.4 Average optimality in the relaxed and unrelaxed models
1.4.5 Extension to the discrete case . . . . . . . . . . . . . . .
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

Chapter 2: Optimal composition of a retail distribution ﬂeet when spot capacity is available
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Fleet composition and related problems . . . . . . . . . . . .
2.2.2 Capacity investment . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Our model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Relation to other newsvendor-type models . . . . . . . . . .
2.4 An algorithm facilitating solution of our model . . . . . . . . . . . .
2.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Eﬃcient generation of “deﬁnitive” collections for our model .
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iv

.
.
.
.
.
.
.
.
.
.
.
.
.

1
1
3
3
7
8
15
15
21
28
35
45
48
50

.
.
.
.
.
.
.
.
.
.
.
.
.

53
53
57
57
60
64
66
66
71
75
75
79
85
86

SUMMARY

This dissertation consists of two self-contained studies.
The ﬁrst study, in the domain of stochastic inventory theory, addresses the structure of optimal ordering policies in a periodic review setting. We take multiple sources of a single product to imply an ordering cost function that is nondecreasing, piecewise linear, and convex. Our main contribution is a proof of the optimality of a ﬁnite generalized base stock policy under an average cost criterion. Our inventory model is formulated as a Markov decision process with complete observations. Orders are delivered immediately. Excess demand is fully backlogged, and the function describing holding and backlogging costs is convex. All parameters are stationary, and the random demands are independent and identically distributed across periods. The
(known) distribution function is subject to mild assumptions along with the holding and backlogging cost function. Our proof uses a vanishing discount approach. We extend our results from a continuous environment to the case where demands and order quantities are integral.
The second study is in the area of capacity planning. Our overarching contribution is a relatively simple and fast solution approach for the ﬂeet composition problem faced by a retail distribution ﬁrm, focusing on the context of a major beverage distributor. Vehicles to be included in the ﬂeet may be of multiple sizes; we assume that spot transportation capacity will be available to supplement the ﬂeet as needed. We aim to balance the ﬁxed costs of the ﬂeet against exposure to high variable costs due to reliance on spot capacity.
We propose a two-stage stochastic linear programming model with ﬁxed recourse.
The demand on a particular day in the planning horizon is described by the total quantity to be delivered and the total number of customers to visit. Thus, daily demand throughout the entire planning period is captured by a bivariate probability v distribution. We present an algorithm that eﬃciently generates a “deﬁnitive” collection of bases of the recourse program, facilitating rapid computation of the expected cost of a prospective ﬂeet and its gradient. The equivalent convex program may then be solved by a standard gradient projection algorithm.
The two investigations making up this dissertation are united by a concern with multiple sources within their respective contexts. The ﬁrst study posits multiple sources of a single product (for example, multiple suppliers or production technologies) within an inventory control context. The second study considers multiple sources of transportation capacity, in the form of vehicles of diﬀering sizes and the alternative of ﬂeet versus spot capacity. For each of the two investigations, our focus on multiple sources entails a richer analysis than that arising from a single-source setting.

vi

CHAPTER 1: AVERAGE OPTIMAL CONTROL IN AN INVENTORY
MODEL WITH MULTIPLE SOURCES

1.1 Introduction
Consider a periodic review inventory control context in which there are multiple suppliers or production technologies for a single product, each source being subject to a ﬁxed short-term capacity. On the premise that the cheapest source should be used ﬁrst, a convex and piecewise linear ordering cost function—associating each source with a constant marginal ordering cost—may be an appropriate model element. In this chapter, we investigate the structure of optimal ordering policies for a class of models with this type of ordering cost function. In deﬁning optimal policies, our focus is on an average cost criterion. While this type of cost criterion is relatively familiar in the ﬁeld of stochastic processes, it is often regarded as more technically forbidding in comparison to ﬁnite-horizon or discounted cost criteria. Thus, our method of analysis may be of some interest as well as the structural result.
Our inventory model is formulated as a Markov decision process with complete observations. The ordering cost for any period is a nondecreasing, piecewise linear, and convex function of the order quantity for a single product. Here we assume that there is no upper limit on the order quantity in a given period; the most expensive source is modeled as uncapacitated. We are also assuming that there is no significant ﬁxed cost to be incurred by ordering a positive quantity as against ordering nothing. Furthermore, we are assuming that all sources have nonnegative marginal cost. Orders are delivered immediately. Excess demand is fully backlogged, and the function describing holding and backlogging costs is convex. All parameters are stationary, and the random demands are independent and identically distributed across periods; the (known) distribution function is subject to mild assumptions along with the holding and backlogging cost function. We prove that a ﬁnite generalized base
1

stock policy is optimal under a long-run average expected cost criterion. We focus on the case of a continuous state space in which demands and order quantities might take any nonnegative real value, and we extend our argument to the discrete case in which these quantities may take only nonnegative integral values.
Though convex ordering cost functions appeared early in the literature on stochastic inventory theory, and though there has been considerable eﬀort directed at understanding optimal inventory control policies under average cost criteria, we are not aware of any prior work establishing our precise conclusions. Our result is not surprising, however, as ﬁnite generalized base stock policies have been claimed to be optimal in discounted cost settings when the ordering cost function is piecewise linear and convex. Furthermore, average cost results consistent with ours have been claimed for the special case when the convex cost function is composed of two linear pieces.
Moreover, important work of Huh et al. (2008) aims to greatly facilitate proofs of optimal policy structures, under an average cost criterion, for a wide class of inventory control models very nearly encompassing ours (as well as models that are more complex than ours in fundamental ways).
A possibly unique element of our argument centers around an observation that, in a relaxed version of our model under a discounted cost criterion, the one-sided derivatives (with respect to the inventory level) of the optimal value functions are nonincreasing in the discount factor. This observation may be useful for further results, and it is not present in the paper by Huh et al. (2008). In its broad outlines, our method of proof is more familiar: it is based on the well-known vanishing discount strategy, and it incorporates a relaxation technique used before by Zheng (1991).
In Section 1.2, we review relevant literature. In Section 1.3, we precisely deﬁne our model and state our desired results, and we then summarize our proof. Section
1.4 contains our technical arguments. We conclude the chapter brieﬂy in Section 1.5, and we give references in Section 1.6.

2

1.2 Literature review
In reviewing related literature, we focus on work featuring periodic review inventory models with a convex (and nonlinear) ordering cost function or with an average cost criterion. Broader coverage of the subject of inventory theory may be found in Veinott
(1966), Porteus (1990), Zipkin (2000), and Porteus (2002). References on Markov decision process (MDP) models more generally, including models under average cost criteria, include Heyman and Sobel (1984), Puterman (1994), Arapostathis et al.
(1993), Hern´ndez-Lerma and Lasserre (1996), Sennott (1999), and Feinberg and a Shwartz (2002).

1.2.1 Inventory control with a convex ordering cost function
Convex ordering cost functions appeared early in the literature on inventory control and production planning. Several studies in this area consider deterministic models, unlike our framework which features stochastic demand. For example, Veinott (1964) studies a production and inventory model with a convex ordering cost function (or rather a convex production cost function) in a ﬁnite-horizon setting with deterministic future demand; here, uncertainty is dealt with by sensitivity analysis. In a subsequent survey of inventory theory, Veinott (1966) discusses other work with convex ordering cost functions in a deterministic setting, much of which was published in the 1950s.
A few additional references along these lines are given in Sethi et al. (2005, p. 11).
In a stochastic and dynamic setting, Karlin (1958) considers basic inventory control models featuring three types of ordering cost functions, associating each type of function with an optimal decision rule having a particular structure:
1. A linear ordering cost function is associated with what are now widely known as base stock rules, which have the form: order up to meet a target inventory level s∗ when the current period’s inventory level is below s∗ ; i.e., order the quantity (s∗ − I) if the current inventory level is I < s∗ , and otherwise order
3

nothing.
2. An ordering cost function involving a ﬁxed set-up cost incurred for all positive order quantities, in addition to a linear cost component, is associated with (s, S) rules: order up to a target level S ∗ when we see inventory below a critical level s∗ , where s∗ ≤ S ∗ ; i.e., order the quantity (S ∗ − I) if the current inventory level is I < s∗ , and otherwise order nothing.
3. A convex ordering cost function is associated with what have been called (in
Porteus 1990) generalized base stock rules, which have the property that the order-up-to level is a nondecreasing function of the current inventory level, while the order quantity is a nonincreasing function of the current inventory level. Here, Karlin’s criterion for evaluating a given policy is the discounted expected cost incurred, which by nature diminishes the emphasis on the (perhaps very) long term.
By contrast, we are concerned with the structure of optimal policies under an average cost criterion, which is intended to ignore the short-term, transient behavior of the system and focus on the steady state. Also notable is that Karlin assumes strict convexity of the ordering cost function, apparently making extensive further speciﬁcation of optimal policies cumbersome in general. We instead assume a piecewise linear form that implies an intuitive and relatively simple optimal policy structure.
Further results for stochastic inventory control with a strictly convex ordering cost function under a discounted cost criterion may be found in Bulinskaya (1967).
The case of a piecewise linear and convex ordering cost function is discussed in the survey of stochastic inventory theory by Porteus (1990). He describes the structure of a ﬁnite generalized base stock rule by reference to a hypothetical situation involving alternative production technologies. Each technology has a linear cost and a ﬁxed per-period capacity—except the most expensive technology, which is uncapacitated.
4

This leads to a convex and piecewise linear ordering cost function, as in our setting, on the assumption that a particular technology is utilized only if all cheaper technologies are being used to capacity. The decision rule is then deﬁned by a nonincreasing set of base stock levels corresponding to the technologies in increasing order of marginal cost.
There may therefore be a range of inventory levels for which we do not utilize a given technology, though we utilize all cheaper technologies to capacity. Porteus asserts the optimality of a ﬁnite generalized base stock policy under a discounted expected cost criterion, but he oﬀers no proof or reference for this proposition. The only optimality proof we have found that allows an ordering cost function with any number of linear pieces is in Bensoussan et al. (1983), under the ﬁnite-horizon total expected cost criterion. Unlike Bensoussan et al., we deal with an average cost criterion, and we also allow unbounded marginal holding and backlogging costs—as well as a marginal ordering cost equal to zero for the cheapest source.
Considerable attention has been given to stochastic models with piecewise linear and convex ordering cost functions for the special case with two linear pieces. Sobel
(1970) studies such a model in which the location of the kink in the function is chosen at the outset and thereafter is ﬁxed from period to period. He argues for the optimality of a ﬁnite generalized base stock policy when the location of the kink is given—under discounted cost criteria, and also under an average cost criterion for the case of discrete demand. His ﬁnite-horizon results are used in Kleindorfer and
Kunreuther (1978). Henig et al. (1997) consider a similar model with an ordering cost function equal to zero for up to R units, with a cost of c per additional unit.
(This is in the context of supply and transportation contracts, in which the available volume R per period may be speciﬁed by a long-term agreement; like Sobel, they aim to optimally choose R.) They argue for the optimality of a ﬁnite generalized base stock policy speciﬁed by two base stock levels (and the parameter R) with respect to the discounted expected cost. They conjecture that the same type of policy is

5

optimal with respect to an average cost criterion. This conjecture is repeated in
Geunes (1999) and in Serel et al. (2001). Yang et al. (2005) consider a model with capacitated “in-house” production and an uncapacitated “outsourcing” option. In their default setting, the capacity level ﬂuctuates randomly and there is a ﬁxed cost of outsourcing as well as a per-unit cost. These complexities aside, they oﬀer in eﬀect an argument for average optimality, in a discrete setting, of a ﬁnite generalized base stock policy when the ordering cost function is nondecreasing, convex, and piecewise linear with two linear pieces. Our argument accommodates a cost function with any
(ﬁnite) number of linear pieces, and we also allow non-discrete demand distributions.
Stochastic production smoothing models such as that of Beckmann (1961) are also relevant here. Beckmann’s model incorporates a linear cost of production along with per-unit costs of increasing and decreasing the production level relative to the level chosen for the preceding period. Thus we have in eﬀect an inventory model in which the ordering cost function is convex and piecewise linear with two linear pieces, such that the location of the kink in the function may change from period to period. It is even allowed that the function may decrease up to the kink, signifying that it is very costly to reduce production. (This characteristic is also allowed in Sobel 1970.)
Later work on production smoothing models in this vein includes Sobel (1969) and
Sobel (1971). In our model, by contrast, the ordering cost function is nondecreasing and ﬁxed across periods, while we allow any number of linear pieces.
Huh et al. (2008) is a study aimed at developing a framework under which the optimality of particular inventory control policy structures may be immediately extended from ﬁnite-horizon to inﬁnite-horizon (including average cost) settings. Their framework includes the possibility of a nondecreasing, piecewise linear and convex ordering cost, though they do not discuss the speciﬁc structure of optimal policies for this situation. Their framework also requires bounds on the marginal holding and backlogging costs, whereas our arguments do not require such bounds. Further-

6

more, in the course of our technical argument we oﬀer some structural insight for our problem that may be of wider use and that is not present in their paper.

1.2.2 Inventory control under average cost criteria
As observed in the general treatments of Markov decision processes in Heyman and
Sobel (1984, p. 171) and Puterman (1994, p. 331), an average cost criterion may be appropriate for modeling systems in which decisions are made frequently. These authors also note the complexity of technical analysis under average cost criteria; problematic characteristics of inventory models in particular include the possibility of state spaces and feasible action sets that are unbounded (and perhaps continuous), as well as unbounded cost functions.
In Section 1.2.1 above, we have discussed work on inventory control under an average cost criterion when the ordering cost function is convex (and nonlinear).
Here, we mention work on stochastic inventory control models with other types of ordering cost functions.
The case of an inventory model with a linear ordering cost function (as in the ﬁrst case examined in Karlin 1958, mentioned above) is studied in Vega-Amaya and
Montes-de-Oca (1998). They argue that the base stock structure remains optimal under an average cost criterion. Our model encompasses linear (nondecreasing) ordering cost functions, but we assume backlogging of unmet demand while they assume lost sales. Literature on average optimality in models with a ﬁxed cost of ordering in addition to a linear component (as in the second case examined in Karlin 1958) is brieﬂy reviewed in Feinberg and Lewis (2006). They cite several papers arguing that the
(s, S) structure remains optimal. One such paper of particular signiﬁcance for us is Zheng (1991), which employs a relaxation technique that we use as well. Other studies cited include Iglehart (1963), Veinott and Wagner (1965), Beyer and Sethi

7

(1999), and Chen and Simchi-Levi (2004). The forthcoming volume of Beyer et al.
(2009) also promises to discuss this case.
The work by Huh et al. (2008) mentioned above stands to establish average optimality of policy structures, for a wide class of cost functions and other model parameters, whenever the structures are known to be optimal in a ﬁnite-horizon setting.

1.3 Formal problem statement and proof strategy
We deﬁne our inventory model as a Markov decision process. Let I ∈ R represent the inventory level at a particular decision point. Excess demand is backlogged, so this quantity may be negative. Knowing I, we must choose the order quantity for the current period; we order so as to bring the inventory level up to some level Z ≥ I, delivery being instantaneous. The cost of the order is C(Z −I) according to a function
C : R+ → R+ . After our decision is made, the demand level X for the current period is revealed. The demand level in each period is a nonnegative, real-valued random variable with known distribution; it is independent of the history of the process, which here consists of all past inventory levels and order-up-to levels, including those of the current period. In particular, the demand levels are independent and identically distributed across periods. The period inventory level net of demand is (Z − X). An inventory holding cost (or backlogging penalty cost, if net inventory is negative) for the current period is incurred in the amount of L(Z − X) according to a function
L : R → R+ . The quantity (Z − X) will be observed as the inventory level at the next decision point.
In our setting, C(Q) is a convex, nondecreasing, piecewise linear function of the order quantity Q = (Z − I). The m sources of our product are numbered in order of marginal cost, with the cheapest source ﬁrst and the most expensive source last.
(We assume that m is ﬁnite.) Without loss of generality, we assume that no two sources have identical marginal cost, and that each source has nonzero capacity. The

8

ordering cost function is deﬁned by parameters as follows:

0 = c0 ≤ c1 < c2 < . . . < cm−1 < cm < +∞

0 = r0 < r1 < r2 < . . . < rm−1 < rm = +∞
Here, ri is the cumulative capacity of the ﬁrst i sources. On the premise that the cheapest source(s) should be used ﬁrst, the marginal cost of increasing the order quantity is ci when the order quantity satisﬁes ri−1 ≤ Q < ri . For order quantity Q, then, we have: m (ci − ci−1 )(Q − ri−1 )+

C(Q) = i=1 We impose the following additional conditions on the holding and backlogging cost function and the distribution of demand variables:
Assumption 1. L : R → R+ is a convex function.
Assumption 2. L(I) → +∞ as |I| → +∞.
Assumption 3. E[L(Z − X)] < +∞ for all Z ∈ R.
Assumption 4. P (X = 0) < 1.
The property E[X] < +∞ is implicit in Assumptions 1–3, and we prove this later on. Our assumption of convexity of the holding and backlogging cost function is fairly typical—encompassing the straightforward case of two linear functions that are zero when the net inventory level is zero—though it is not universal. Given convexity, our additional assumption that this function approaches +∞ for increasing or decreasing inventory levels is reasonable: the violation of this assumption would imply an incentive to pursue arbitrarily great inventory or backlog quantities. Furthermore, given Assumptions 1 and 2 and our optimality criterion, our assumption that L ≥ 0 is without loss of generality. Similarly, it is without loss of generality that we assume C(0) = 0. Assumption 4 is imposed to eliminate a relatively trivial special
9

case. Finally, note that our framework allows mixed demand distributions as well as distributions having a probability density or mass function.
Given the characteristics of our model as just described, we seek to understand the structure of optimal control policies under an average cost criterion. We now deﬁne the particular criterion we adopt.
Deﬁnition 1. For a general Markov decision process, let φ(y, a) be the cost incurred in any given period when the state is observed to be y and the action a is taken. An admissible policy π ∗ is average optimal if for all admissible policies π and all initial states y0 , we have
1
∗
Eπ0
lim sup y n→+∞ n + 1

n

t=0

1 φ(yt , at ) ≤ lim sup
Eπ0
y n→+∞ n + 1

n

φ(yt , at ) t=0 Above, a policy prescribes the decision rule to be used at all decision points; a decision rule speciﬁes an action at a particular decision point. (Our usage of these terms follows Puterman 1994 and is not universal.) An admissible policy consists of rules that are allowed to depend on any information in the history of the process; in our case, the history includes (in sequence) all inventory levels I observed and all order-up-to levels Z chosen. Furthermore, randomized selection of actions may be employed. However, an admissible policy may not use rules depending on demand levels not yet realized. There is a further requirement that all policies under consideration satisfy certain measurability requirements. In general (and beyond the issue of policies) we take measurability for granted in the course of our arguments; to the best of our knowledge, our constructions do not run afoul of such technical subtleties at the foundations of fully rigorous treatments of probabilistic models.
Deﬁnitions of average optimality similar to ours are given Heyman and Sobel
(1984) and Arapostathis et al. (1993). Our deﬁnition is equivalent to the “lim inf” average optimality of Puterman (1994, p. 129, in the context of maximizing rewards).

10

Our use of the limit superior instead of the plain limit is reasonable because it is possible in our framework to specify an inventory control model and policy for which the desired limit does not exist. We will, however, ﬁnd that a plain limit is attained by the policy we establish as average optimal. (There is also a related “sample path average cost” criterion which we do not discuss; see Arapostathis et al. 1993.)
Our primary goal is to show that there exists a ﬁnite generalized base stock policy that is average optimal for our inventory model as described. In particular, we will show that there is such an optimal policy that is expressible in terms of the parameters
{r0 , . . . , rm } along with certain critical values {s0 , . . . , sm }. The following deﬁnition makes this goal precise.
Deﬁnition 2. Given our model parameters {r0 , . . . , rm }, and given critical values

sm ≤ sm−1 ≤ . . . ≤ s2 ≤ s1 < s0 = +∞

the corresponding ﬁnite generalized base stock policy (“FGB policy”) prescribes an order-up-to level as a function of the inventory level at any decision point:
• If si −ri ≤ I < si −ri−1 (equivalently, ri−1 < si −I ≤ ri ) for some i ∈ {1, . . . , m}, choose Z = si . Here we are able to reach the ith base stock level by utilizing the ith source, while using the ﬁrst (i − 1) sources to their capacities.
• If si − ri−1 ≤ I < si−1 − ri−1 (equivalently, si ≤ I + ri−1 < si−1 ) for some i ∈ {1, . . . , m}, choose Z = I + ri−1 . We are in a range where we use the ﬁrst
(i − 1) sources to their capacities, but we do not use source i. Our use of the ﬁrst (i − 1) sources alone brings us above the ith base stock level.
Note that the cases above are mutually exclusive and exhaustive. Also note that if si = si−1 for some i, the second type of condition above becomes vacuous for that
i. We allow for the possibility that si = −∞ for some i = 0, which would imply
11

that source i and any more expensive sources are never utilized. However, we will establish that si is ﬁnite for all i = 0 characterizing our particular average optimal
FGB policy. (Our deﬁnition may be compared with Bensoussan et al. 1983, p. 332,
Porteus 1990, p. 622, and Liu and Esogbue 1999, p. 43.)
Our proof strategy involves studying a relaxed version of the inventory model in which the inventory level may be reduced by an arbitrary amount at no cost. Note that by expanding the domain of the function C to be R, our given formula for
C(Q) remains valid. This relaxed model will be associated with a relaxed FGB policy structure, which we now deﬁne.
Deﬁnition 3. A relaxed ﬁnite generalized base stock policy (“rFGB policy”) is the same as an FGB policy, except that for s1 − r0 ≤ I < s0 − r0 (that is, I ≥ s1 ), we choose Z = min{I, s∗ } instead of Z = I + r0 = I. Here s∗ is an additional parameter satisfying s1 ≤ s∗ < +∞.
In addition to the average cost criterion deﬁned above, we will in the course of our arguments make use of (rather standard) ﬁnite- and inﬁnite-horizon discounted cost optimality criteria for Markov decision processes, which we deﬁne below.
Deﬁnition 4. For an MDP, let φ(y, a) be the cost incurred in period t when the state is y and action a is taken. Let φn (y) be the cost incurred for ﬁnal state y in the terminal period n ∈ Z+ . Let β ∈ (0, 1) be the discount factor. An admissible policy π ∗ is discount optimal if for all admissible policies π and all initial states y0 ,
∗

Eπ0 y n−1 t=0 β t φ(yt , at ) + β n φn (yn ) ≤ Eπ0 y n−1 t=0 β t φ(yt , at ) + β n φn (yn )

If we take β = 1, the above becomes a total expected cost criterion. We will ﬁnd it convenient to reverse the numbering of periods, so that subscript ‘0’ is associated with the terminal period.

12

Deﬁnition 5. For an MDP, let φ(y, a) be the cost incurred when the state is y and action a is taken. Let β ∈ (0, 1) be the discount factor. An admissible policy π ∗ is discount optimal if for all admissible policies π and all initial states y0 ,
+∞
∗

Eπ0 y +∞

β t φ(yt , at ) ≤ Eπ0 y t=0

β t φ(yt , at ) t=0 In our case, φ(y, a) ≥ 0. By the monotone convergence theorem, then, it is equivalent for us to take the limits outside of the expectations in the deﬁnition above.
Our technical arguments run as follows. In Section 1.4.1, we establish some notation and several analytical results that we will use later. In Section 1.4.2, we begin our study of the relaxed model. We ﬁnd that rFGB decision rules are discount optimal in a ﬁnite-horizon setting with discount factor β. Speciﬁcally, given n ≥ 1 decision points remaining and terminal cost equal to zero, critical values {s∗ , s1 , . . . , sm } deﬁned in n n n terms of the optimal cost function (also called the “value function”) fn−1 (I), which is convex, correspond to an optimal rFGB decision rule. Upon further examination, we ﬁnd that the one-sided derivatives of fn−1 (I) with respect to I are nonincreasing in n as well as in the discount factor β. As a consequence, the critical values si are n nondecreasing in n and in β (provided that we choose the greatest possible critical values at each step, in cases where there are multiple optimizers). Finally, we show that the critical values {s∗ , s1 , . . . , sm } are ﬁnite for suﬃciently large n and β. n n n In Section 1.4.3, we turn to the inﬁnite-horizon setting, considering the situation as n → +∞. We observe for the ﬁnite-horizon model that we may restrict attention to a compact interval of actions in any given state, and we also establish fn

f . After

seeing its role in a solution of the discounted cost optimality equation, this function f turns out to be the optimal cost function for the inﬁnite-horizon setting. Based on the convex structure of f , we ﬁnd that rFGB policies are discount optimal. We also establish that the one-sided derivatives of f (I) with respect to I are nonincreasing

13

in β, and that the critical values si derived from f are nondecreasing in β (again provided that we choose the greatest possible critical values).
In Section 1.4.4, we use the above results to construct and validate average optimal policies. In the inﬁnite-horizon discounted setting, for β close to 1 we ﬁnd that we may restrict attention to a compact interval of actions that does not vary with β. We
¯
¯ also establish for a (convex) relative value function f that f

¯ f1 as β → 1. These

¯ facts are used to show the role of f1 , along with a scalar ρ, in solving the average cost optimality equation. We then argue that an rFGB policy with critical values
¯
si deﬁned by reference to the convex function f1 is average optimal for the relaxed
1
problem, having cost ρ. Finally, we show that this implies that an FGB policy (with the same critical values, absent s∗ ) must be average optimal for the unrelaxed model.
1
In Section 1.4.5, we aim to attain our secondary goal: extension of our main result to the discrete case in which demands and order quantities may take only nonnegative integral values. We show how our main argument in the preceding sections may be used to establish that an average optimal FGB policy exists in this case as well.
Our arguments are fairly self-contained, making use of many ideas from prior work. Some notable examples of prior literature that inspired our argument in various ways include: Heyman and Sobel (1984, Theorems 8-14 and 8-15 and proofs), Zheng
(1991, Section 4), Arapostathis et al. (1993, Theorem 5.1 and proof), Puterman (1994,
Theorems 6.2.2 and 8.10.7 and proofs), Henig et al. (1997, Lemma 1 and Theorem 1 and proofs), and Yang et al. (2005, Lemmas 7 and 8 and proofs). It is also clear that our argument has elements in common with Sobel (1970) and Sch¨l (1993, Lemma a 1.2 and Proposition 1.3).

14

1.4 Technical arguments
1.4.1 Preliminary analytical results
In the rest of the chapter, we will denote left and right derivatives with ‘−’ and ‘+’ superscripts, respectively. In Section 1.4.2 and after, these derivatives will always be taken with respect to I or Z. We deﬁne the left and right derivatives so that they are equal when the conventional derivative exists. We take the existence of a one-sided derivative to mean that the corresponding limit is ﬁnite.
The following lemma is essentially the same as Theorem 5.1.3 in Webster (1994):
Lemma 1. If a ﬁnite-valued, convex function g is deﬁned on an open interval of R, then g − (x) and g + (x) exist for all x in this interval. Given x1 < x2 in this interval, we also have

g − (x1 ) ≤ g + (x1 ) ≤

g(x2 ) − g(x1 )
≤ g − (x2 ) ≤ g + (x2 ) x2 − x1

In particular, if g : R → R is convex then it is continuous. Sums, positive scalar multiples, and pointwise limits of convex functions are themselves convex. A convex, ﬁnite-valued function g achieves a local (and therefore global) minimum over R at x∗ if and only if g − (x∗ ) ≤ 0 ≤ g + (x∗ ). For a convex, ﬁnite-valued function g, we also deﬁne g − (−∞) := lim g − (x) x→−∞ g + (+∞) := lim g + (x) x→+∞ and we note that these are monotone limits (by convexity) that may be inﬁnite.
Lemma 2. Let g : R → R be convex, and let Y be a real-valued random variable such that E[g(x − Y )] is ﬁnite for all x ∈ R. E[g(x − Y )] is a convex, ﬁnite-valued function of x over R.

15

Proof. Given reals x1 < x2 and λ ∈ (0, 1), we have

g((1 − λ)x1 + λx2 − Y ) ≤ (1 − λ)g(x1 − Y ) + λg(x2 − Y )

for any realized value of Y by the convexity of g. Since E[g(x − Y )] is ﬁnite for all x ∈ R, we may apply linearity of expectation (Wheeden and Zygmund 1977, Theorem
10.23) as well as monotonicity of expectation (Wheeden and Zygmund 1977, p. 170) to this inequality, establishing convexity.
The following lemma is essentially contained in Sobel (1970) and Heyman and
Sobel (1984, p. 527):
Lemma 3. Given the premises of Lemma 2, the left and right derivatives with respect to x of E[g(x − Y )] are equal to the ﬁnite quantities E[g − (x − Y )] and E[g + (x − Y )] respectively for all x ∈ R.
Proof. Let us consider the left derivative case. For any particular x and realized value of Y , convexity implies that δ −1 (g(x − Y ) − g(x − δ − Y ))

g − (x − Y ) as δ → 0+ .

By our premises and linearity of expectation, E[δ −1 (g(x − Y ) − g(x − δ − Y ))] is ﬁnite for all real δ > 0. Using the monotone convergence theorem (Wheeden and Zygmund
1977, Theorem 10.27), we conclude that

δ −1 (E[g(x − Y )] − E[g(x − δ − Y )]) → E[g − (x − Y )]

By Lemmas 1 and 2, the left derivative of E[g(x − Y )] must exist. By the convergence above, then, E[g − (x − Y )] is equal to this left derivative and is ﬁnite as desired. A similar argument may be applied for the case of right derivatives.

16

Lemma 4. Given the premises of Lemma 2, we have:
• limx→−∞ E[g − (x − Y )] =: E[g − (−∞ − Y )] = g − (−∞)
• limx→+∞ E[g + (x − Y )] =: E[g + (+∞ − Y )] = g + (+∞)
Proof. For any realized value of Y , we have g − (x − Y ) g + (x − Y )

g − (−∞) as x → −∞ and

g + (+∞) as x → +∞. By Lemma 3, E[g − (x − Y )] and E[g + (x − Y )]

are ﬁnite for every x ∈ R. Using the monotone convergence theorem, we obtain limx→−∞ E[g − (x − Y )] = g − (−∞) and limx→+∞ E[g + (x − Y )] = g + (+∞).
Rolle’s theorem (Bartle 1976, p. 196) may be modiﬁed for one-sided derivatives:
Lemma 5. Let g : R → R be continuous on the closed interval [x1 , x2 ] with g + existing on the open interval (x1 , x2 ), and suppose g(x1 ) = g(x2 ) = 0. There exist x and x in (x1 , x2 ) such that g + (x ) ≤ 0 and g + (x ) ≥ 0.
1
Proof. If g(x) = 0 for all x ∈ (x1 , x2 ), we may choose x = x = 2 (x1 + x2 ). Suppose

that g(x) > 0 for some x ∈ (x1 , x2 ). There must exist a maximizer x of the continuous function g over the compact set [x1 , x2 ]. By our supposition x1 = x = x2 , and since x is a maximizer we must have g + (x ) ≤ 0. Now there must be some x ∈ (x1 , x ) such that g(x ) = 1 g(x ) and 1 g(x ) < g(x) for all x ∈ (x , x ). (By the intermediate
2
2 value theorem, there exists x satisfying g(ˆ) = 1 g(x ) between x and x whenever
ˆ
x
2
1 g(x) < 2 g(x ). If for every such x the function g goes below g(ˆ) inside (ˆ, x ), x
ˆ
x x ˆ

may be taken inﬁnitely close to x and so g cannot be continuous on the left at x , a contradiction.) We conclude that g + (x ) ≥ 0. Finally, in the last remaining case we must have g(x) < 0 for some x ∈ (x1 , x2 ), and we may employ a similar argument.
Lemma 5 may be used in a form analogous to the mean value theorem (Bartle
1976, p. 196) to prove, by contradiction, the following condition for convexity; cf.
Theorem 5.3.1 in Hiriart-Urruty and Lemar´chal (1993, p. 34). e 17

Lemma 6. If g : R → R is continuous with right derivatives for all x ∈ R and g + (x) is nondecreasing in x, then g is convex.
The following is implied by Theorem 24.1 in Rockafellar (1970):
Lemma 7. If g : R → R is convex and x ∈ R, then limx→¯− g + (x) = g − (¯) and
¯
x x limx→¯+ g + (x) = g + (¯). Similarly, x x
The following is a slight modiﬁcation of Lemma 8-5 in Heyman and Sobel (1984); cf. Lemma 3 of Sobel (1971).
Lemma 8. If on an open interval of R we have a sequence of ﬁnite-valued convex functions gn such that gn

g, the limit also being ﬁnite-valued, then for all x on this

interval we have:

−
+
g − (x) ≤ lim inf gn (x) ≤ lim sup gn (x) ≤ g + (x) n→+∞ n→+∞

+
−
Proof. Let x be an element of the given interval. By Lemma 1, gn (x) and gn (x) exist

for all n. The limiting function g is ﬁnite and inherits convexity, so Lemma 1 implies that g − (x) and g + (x) exist also.
Suppose that the ﬁrst desired inequality does not hold. This means that there
−
− exists ε > 0 and a subsequence of elements gn (x) such that gn (x) < g − (x) − ε

for all n. But there also exists δ > 0 such that (x − δ) lies in the given interval and also δ −1 (g(x) − g(x − δ)) > g − (x) − ε/2. Furthermore, there exists n in our subsequence of indices such that gn (x) > g(x) − δε/2. We may now bring out a
−
contradiction. By Lemma 1, gn (x − δ) ≥ gn (x) − δgn (x). By our deﬁnitions of ε
−
and n , we have gn (x) − δgn (x) > g(x) − δg − (x) + δε/2. By our deﬁnition of δ,

g(x) − δg − (x) + δε/2 > g(x − δ). Putting these together, the implication is that gn (x − δ) > g(x − δ), which contradicts the fact that gn

g.

−
+
The second desired inequality follows from noting that gn (x) ≤ gn (x) for all n,

18

which is a consequence of Lemma 1. To obtain the third inequality, we may use an argument symmetrical with that given for the ﬁrst inequality.
A consequence of Lemma 8 is that any sequence of minimizers of such a sequence of functions gn will become inﬁnitely close to the set of minimizers of g. (This is not to say that the sequence of minimizers necessarily converges to a point.) For observe that if a given x is less than the interval of minimizers of g, we have g + (x) < 0,
+
and Lemma 8 implies that gn (x) < 0 for suﬃciently large n, which implies that

minimizers of gn are eventually greater than x. We may argue similarly that, if a given x is greater than the interval of minimizers of g, then minimizers of gn are eventually less than x.
The following is given as Dini’s theorem in Bartle (1976, p. 173, without proof).
Lemma 9. If a monotone sequence of continuous functions fn converges at each point of a compact set K in Rp to a function f which is continuous on K, then the convergence is uniform on K.
The next lemma is implied by the primary result 1.4.3 in Flett (1980, p. 22).
Lemma 10. Let g : R → R be continuous, and suppose that g has right derivatives for all x ∈ R, such that g + (x) ≥ 0 for all x ≥ x . The function g is nondecreasing over [x , +∞).
Note that Lemma 10 may be “turned around” to imply that a function g having left derivatives is nonincreasing over (−∞, x ] if g − (x) ≤ 0 for all x ≤ x .
Lemma 11. For all n ≥ 1, let gn : R → R be continuous with right derivatives for all x ∈ R; let g : R → R have right derivatives for all x ∈ R, and assume that gn → g.
+
If for some x ∈ R we have gn (x) ≥ 0 for all x ≥ x and all n ≥ 1, then g + (x ) ≥ 0.

Proof. Suppose instead that we have g + (x ) < 0 for some x as described. There exists δ > 0 small enough so that δ −1 (g(x + δ) − g(x )) < 0. Since gn → g, there exists n
19

large enough so that gn (x ) and gn (x +δ) are each strictly less than ε away from their limiting values as n → +∞, where we deﬁne ε := (g(x ) − g(x + δ))/2, noting that by our supposition ε > 0. It follows that gn (x ) > gn (x + δ). Lemma 10, however, implies that gn must be nondecreasing over [x , +∞), so we have a contradiction.
Turning around the preceding result yields g − (x ) ≤ 0, if we are instead given
−
gn (x) ≤ 0 for all x ≤ x and the existence of left derivatives. These statements may

also be applied to functions −gn with −g to show the preservation of inequalities in
+
the other direction, i.e., g + (x ) ≤ 0 if gn (x) ≤ 0 for all x ≥ x , and g − (x ) ≥ 0 if
−
gn (x) ≥ 0 for all x ≤ x .

Lemma 12. Let g : R → R be a nondecreasing function, let Y be a real-valued random variable such that E[g(Y )] is ﬁnite, and let y1 and y2 be real with y1 < y2 .
If P (Y > y2 ) > 0, then E[g(Y ) | Y > y2 ] ≥ E[g(Y ) | Y > y1 ].
Proof. Deﬁne α := E[g(Y ) | Y > y2 ]. Deﬁne g ∗ (y) := g(y)1(y > y2 ) + α1(y ≤ y2 ), where 1 is the indicator function. Using monotonicity of expectation and the fact that g is nondecreasing, for y ≤ y2 we obtain g(y) ≤ g(y2 ) = E[g(y2 ) | Y > y2 ] ≤ α.
Hence g ≤ g ∗ , and by another application of monotonicity of expectation we ﬁnd that
E[g(Y ) | Y > y1 ] ≤ E[g ∗ (Y ) | Y > y1 ]. Now we may observe
E[g(Y )1(Y > y2 )] + E[α1(y1 < Y ≤ y2 )]
P (Y > y1 ) αP (Y > y2 ) + αP (y1 < Y ≤ y2 )
=
P (Y > y1 )

E[g ∗ (Y ) | Y > y1 ] =

Simplifying, E[g ∗ (Y ) | Y > y1 ] = α, and the desired result follows.
For a nonincreasing function g, the above result may be applied to the function
−g, from which we conclude instead E[g(Y ) | Y > y2 ] ≤ E[g(Y ) | Y > y1 ].
The following is a Tauberian theorem relating the inﬁnite-horizon discounted and average cost criteria. A proof of an analogous statement for nonpositive sequences is
20

oﬀered after Lemma 8.10.6 in Puterman (1994).
Lemma 13. Suppose we are given a nonnegative sequence of elements at (e.g., expected costs in successive decision periods) with discount factor β ∈ (0, 1). We have
+∞

1 lim sup(1 − β) β aj ≤ lim sup t→+∞ t + 1 β→1 j=0

t

j

aj j=0 Lastly, we may bring out an implicit assumption of our framework which we will take for granted in the arguments ahead.
Lemma 14. Given our deﬁnition of X and Assumptions 1–3, E[X] < +∞ must hold.
Proof. By Assumption 1, Assumption 2, and Lemma 1, there exists Z ∈ R such that
L− (Z ) < 0. Using Lemma 1, we ﬁnd that L(Z ) − L(Z − X) ≤ XL− (Z ) for all realized values of X. By linearity and monotonicity of expectation,

E[X] ≤

E[L(Z − X)] − L(Z )
−L− (Z )

Using Assumption 3, we have a ﬁnite upper bound on E[X].

1.4.2 Relaxed model, ﬁnite-horizon discounted setting
We begin our formal argument by stating the dynamic programming recursion for the relaxed model in a ﬁnite-horizon discounted setting. For n ≥ 1:

fn (I) := min{C(Z − I) + E[L(Z − X)] + βE[fn−1 (Z − X)]}
Z∈R

Here β ∈ (0, 1) is a discount factor; we deﬁne the terminal cost function f0 (I) := 0. fn (I) represents the minimum possible total discounted expected cost, to be incurred between the present (with n decision points remaining) and the terminal period, if the current inventory level is I. This fact is implied by the dynamic programming theorem
21

in Hern´ndez-Lerma and Lasserre (1996, p. 24, as generalized for discounted costs on a p. 32). To be more precise, their theorem concludes that fn (I) is the minimal cost if we take the (undiscounted) one-stage cost function to be C(Z − I) + E[L(Z − X)].
Using the tower property (Grimmett and Stirzaker 2001, p. 336), we ﬁnd that this characterization of the one-stage cost is equivalent to C(Z − I) + L(Z − X) as far as our optimality criteria are concerned.
Our ﬁrst results in this section will show that the minimum in the recursion above is achieved by a decision rule of the rFGB type. In this eﬀort, we will make use of the following function, deﬁned for n ≥ 1:

Gn (Z) := E[L(Z − X)] + βE[fn−1 (Z − X)]

Theorem 1. Let n ≥ 1 be given. Suppose that Gn (Z) is convex and ﬁnite-valued, with G− (−∞) < 0 and G+ (+∞) > 0. Deﬁne s0 := +∞. For all i ∈ {∗, 1, . . . , m}, n n n choose si minimizing ci Z + Gn (Z) over R (we deﬁne c∗ := 0). If the minimum does n not exist, deﬁne si := −∞. Then for all I ∈ R, the rFGB decision rule corresponding n to parameters {r0 , . . . , rm } and critical values {s0 , . . . , sm } along with s∗ achieves the n n n minimum in the dynamic programming recursion for fn (I).
Proof. (In this proof, we drop all subscripts n from Gn and the critical values si .) By n the given properties of G(Z), we may make three comments immediately. First, to say that the minimum of ci Z + G(Z) does not exist is to imply that this function is nondecreasing everywhere (since ci ≥ 0); it is therefore natural in this case to deﬁne si = −∞. Second, we may be assured that s∗ is ﬁnite. Third, we have:

sm ≤ sm−1 ≤ . . . ≤ s2 ≤ s1 ≤ s∗ < s0 = +∞

For ﬁnite si , we know in particular that G− (si ) ≤ −ci and G+ (si ) ≥ −ci . Notice that for any particular I ∈ R, the dynamic programming recursion is the problem of
22

minimizing the convex, ﬁnite-valued objective function C(Z − I) + G(Z) over Z ∈ R.
For a given I, an optimal Z ∗ is therefore one that satisﬁes

C − (Z ∗ − I) + G− (Z ∗ ) ≤ 0 ≤ C + (Z ∗ − I) + G+ (Z ∗ )

We proceed with an analysis of the possible cases for I ∈ R:
• If si − ri ≤ I < si − ri−1 for some i ∈ {1, . . . , m}, let Z ∗ = si . This case only applies if si is ﬁnite, so G− (Z ∗ ) and G+ (Z ∗ ) exist. Moreover, the order quantity is in (ri−1 , ri ]. We have C − (Z ∗ − I) = ci and G− (Z ∗ ) ≤ −ci , so decreasing Z ∗ does not improve the total cost. Similarly, C + (Z ∗ − I) ≥ ci and G+ (Z ∗ ) ≥ −ci , so increasing Z ∗ does not improve the total cost, either.
• If si − ri−1 ≤ I < si−1 − ri−1 for some i ∈ {2, . . . , m}, let Z ∗ = I + ri−1 .
This case only applies if si−1 is ﬁnite, so Z ∗ is some ﬁnite number in [si , si−1 ).
C − (Z ∗ − I) = ci−1 and G− (Z ∗ ) ≤ −ci−1 , so decreasing Z ∗ does not improve the total cost. Similarly, C + (Z ∗ − I) = ci and G+ (Z ∗ ) ≥ −ci , so increasing Z ∗ also fails to improve the total cost.
• If s1 ≤ I < s∗ , let Z ∗ = I. C − (Z ∗ − I) = 0 and G− (Z ∗ ) ≤ 0, so decreasing
Z ∗ does not improve the total cost; C + (Z ∗ − I) = c1 and G+ (Z ∗ ) ≥ −c1 , so increasing Z ∗ cannot improve the total cost.
• If s∗ ≤ I, let Z ∗ = s∗ . (We know that s∗ is ﬁnite.) C − (Z ∗ − I) = 0 and
G− (Z ∗ ) ≤ 0, so decreasing Z ∗ will not improve the total cost; C + (Z ∗ − I) ≥ 0 and G+ (Z ∗ ) ≥ 0, so increasing Z ∗ does not improve the total cost.
In each case above, we see that the rFGB decision rule according to the given parameters achieves the minimum in the dynamic programming recursion.

23

Theorem 2. For all n ≥ 1,
• Gn (Z) is convex and ﬁnite-valued with G− (−∞) < 0 and G+ (+∞) > 0. n n
−
+
• fn (I) is convex and ﬁnite-valued with fn (−∞) ≥ −cm and fn (I) = 0 for I

suﬃciently large.
Proof. Our proof will be by induction on n. First, by our deﬁnition that f0 (I) = 0, we see that f0 (I) satisﬁes the required conditions. Assume that these conditions are valid for fn−1 (I) for some particular n ≥ 1.
By the induction hypothesis, fn−1 (Z) is ﬁnite for any Z ∈ R and fn−1 (Z − X) is ﬁnite for any realized value of X. The conditions on the derivatives of fn−1 imply that fn−1 (Z) ≤ fn−1 (Z −X) ≤ fn−1 (Z)+cm X. Since we know that E[X] < +∞, by taking expectations we ﬁnd that E[fn−1 (Z − X)] is a ﬁnite-valued function of Z. Now by
Lemmas 2 and 3 we may also conclude that E[fn−1 (Z −X)] is convex in Z and that its
−
+ left and right derivatives are equal to E[fn−1 (Z −X)] and E[fn−1 (Z −X)] respectively.

Lemmas 2 and 3 may be similarly applied to E[L(Z − X)] using Assumption 3.
By Assumption 2 and Lemma 4, E[L− (−∞ − X)] < 0 and E[L+ (+∞ − X)] > 0.
−
Similarly, by the induction hypothesis we may argue that E[fn−1 (−∞ − X)] ≤ 0 and
+
E[fn−1 (+∞ − X)] = 0. We conclude that Gn (Z) is a convex, ﬁnite-valued function

with G− (−∞) < 0 and G+ (+∞) > 0, and so we may apply Theorem 1 to obtain n n
∗
∗ fn (I) = C(Zn (I) − I) + Gn (Zn (I))

∗ where Zn (I) prescribes an optimal action for inventory level I according to an rFGB

decision rule with critical values {s0 , . . . , sm } and s∗ satisfying the conditions of n n n ∗ the theorem. Zn (I) is a continuous function of I, and the functions C and Gn are

continuous, so fn (I) is continuous. Similarly, fn (I) is ﬁnite-valued. We now analyze the right derivatives of fn (I):

24

∗
• If si − ri ≤ I < si − ri−1 for some i ∈ {1, . . . , m}, then Zn (I) = si . Increasing n n n I decreases the order quantity, but does not change the order-up-to level. The
+
order quantity is in (ri−1 , ri ], so fn (I) = −ci here.
∗
• If si − ri−1 ≤ I < si−1 − ri−1 for some i ∈ {2, . . . , m}, Zn (I) = I + ri−1 . n n
+
Increasing I does not change the order quantity, so fn (I) = G+ (I + ri−1 ) here. n Over [si , si−1 ), G+ (Z) is a nondecreasing function with values in [−ci , −ci−1 ]. n n n ∗
• If s1 ≤ I < s∗ , Zn (I) = I. Increasing I does not change the order quantity, n n
+
so fn (I) = G+ (I) here. Over [s1 , s∗ ), G+ (Z) is a nondecreasing function with n n n n values in [−c1 , 0].
∗
• If s∗ ≤ I, Zn (I) = s∗ . Increasing I does not cause any change in ordering cost, n n
+
and the order-down-to level is ﬁxed, so fn (I) = 0 here.

We observe that fn (I) has nondecreasing right derivatives; we may now invoke Lemma
6 to conclude that fn (I) is convex. Furthermore, by our analysis above we must have
−
fn (I) ≥ −cm for all I, and fn (I) is constant over [s∗ , +∞) where s∗ has been shown n n

to be ﬁnite.
By the dynamic programming theorem in Hern´ndez-Lerma and Lasserre (1996), a Theorems 1 and 2 establish that a policy consisting of rFGB decision rules as deﬁned in Theorem 1 is discount optimal in our ﬁnite-horizon setting.
In preparation for our later arguments, we will study properties that depend on
β. To make this dependence explicit, we may add a subscript ‘β’ to symbols already deﬁned. The two theorems below have implications for limiting cases as n → +∞ and β → 1.
Theorem 3. For all n ≥ 1:
+
−
+
−
• fn (I) ≤ fn−1 (I) and fn (I) ≤ fn−1 (I) for all I. (These are derivatives with

respect to I.)
25

i
• si n+1 ≥ sn if these values are chosen to be the greatest minimizers deﬁned in

Theorem 1, for all i ∈ {∗, 1, . . . , m}.
+
+
−
−
• fβ2 ,n (I) ≤ fβ1 ,n (I) and fβ2 ,n (I) ≤ fβ1 ,n (I), for β1 < β2 , for all I.

• si 2 ,n ≥ si 1 ,n for β1 < β2 , if these values are chosen to be the greatest minimizers β β deﬁned in Theorem 1, for all i ∈ {∗, 1, . . . , m}.
Proof. (We prove the ﬁrst two statements ﬁrst.) Our proof will be by induction on
+
+
n. First, by our deﬁnition that f0 (I) = 0 and by Theorem 2, we have f1 ≤ f0 and
−
−
+
−
+
− f1 ≤ f0 . Assume henceforth that fn ≤ fn−1 and fn ≤ fn−1 for some particular

n ≥ 1.
Using Lemmas 2 and 3 as in the proof of Theorem 2 and applying monotonicity of expectation with the induction hypothesis, we ﬁnd that G+ ≤ G+ and G− ≤ G− . n+1 n+1 n n
From Theorem 2, we know that Gn−1 and Gn are convex and ﬁnite-valued. For any i ∈ {∗, 1, . . . , m}, if si minimizes ci Z + Gn (Z) then we have G− (si ) ≤ −ci . n n n We conclude that G− (si ) ≤ −ci also, so si n+1 n n+1 may be chosen to be greater than si as desired. (If si = −∞ then we have nothing to prove.) Choosing the greatest n n minimizers at every step is therefore one way to make sure that si ≥ si . (Convexity n n+1 implies that the set of minimizers is a closed interval, and it follows in our situation that the greatest minimizer exists whenever a minimizer exists.)
Choosing the greatest minimizers as indicated, we may now use facts from the
+
+ proof of Theorem 2 to verify that fn+1 (I) ≤ fn (I) for all I ∈ R:
+
• If si − ri ≤ I < si − ri−1 for some i ∈ {1, . . . , m}, then fn+1 (I) = −ci . n+1 n+1
+
Meanwhile, since si − ri ≤ si − ri , we have fn (I) ≥ −ci . n n+1
+
• If si − ri−1 ≤ I < si−1 − ri−1 for some i ∈ {2, . . . , m}, then fn+1 (I) = n+1 n+1

G+ (I + ri−1 ) ≤ −ci−1 . At the same time, since si − ri−1 ≤ si − ri−1 , we n+1 n n+1 + have fn (I) ≥ min{G+ (I + ri−1 ), −ci−1 } ≥ G+ (I + ri−1 ). n+1 n

26

+
• If s1 ≤ I < s∗ , then fn+1 (I) = G+ (I) ≤ 0. Since s1 ≤ s1 , we also have n+1 n+1 n+1 n n+1 + fn (I) = min{G+ (I), 0} ≥ G+ (I). n+1 n
+
+
• If s∗ ≤ I, then fn+1 (I) = 0. Since s∗ 1 ,n ≤ s∗ , fn (I) = 0 also. n+1 n+1 β −
−
In each case above, we see that the desired inequality holds. That fn+1 (I) ≤ fn (I)

for all I follows by Lemma 7. For if this inequality were invalid for some inventory level I , then any increasing sequence of inventory levels Ik approaching I would see
+
+ fn+1 (Ik ) > fn (Ik ) eventually.

(We now prove the last two statements of the theorem.) Let β1 and β2 be given
+
+
−
− such that β1 < β2 . We will argue by induction on n that fβ2 ,n ≤ fβ1 ,n and fβ2 ,n ≤ fβ1 ,n .
+
−
In the base case, by our deﬁnition fβ,0 = fβ,0 = 0 for all β, and the desired inequalities

are satisﬁed. Henceforth, let n be given and assume that the case for n − 1 is settled.
For any β and Z, we have, as suggested in the ﬁrst half of this proof:

+
G+ (Z) = E[L+ (Z − X)] + βE[fβ,n−1 (Z − X)] β,n The ﬁrst term on the right side above is independent of the discount factor. Regarding the second term: the induction hypothesis and the fact (from Theorem 2)
+
+ that fβ,n−1 ≤ 0 imply, via monotonicity of expectation, that β2 E[fβ2 ,n−1 (Z − X)] ≤
+
β1 E[fβ1 ,n−1 (Z − X)]. Thus G+2 ,n ≤ G+1 ,n , and essentially the same argument yields β β

G−2 ,n ≤ G−1 ,n . By reasoning as in the ﬁrst half of this proof, it follows that choosing β β the greatest minimizers gives us si 2 ,n ≥ si 1 ,n . Continuing with analogous reasoning, β β
−
+
+
− we ﬁnd that fβ2 ,n ≤ fβ1 ,n and fβ2 ,n ≤ fβ1 ,n .

Theorem 4. If L− (−∞)/(1 − β) < −ci , then the critical values {s∗ , s1 , . . . , si } n n n deﬁned according to Theorem 1 will be ﬁnite for n suﬃciently large.
Proof. Since the critical values in question are in [si , s∗ ] (see the proof of Theorem n n
1) and we are assured by Theorem 2 that G+ (+∞) > 0, a suﬃcient condition for the n 27

desired ﬁniteness is G− (−∞) < −ci . Since f0 (I) = 0 we have G1 (Z) = E[L(Z − X)], n and by Lemma 4 we see that G− (−∞) = L− (−∞). Now if si = −∞, through the
1
n−1 deﬁnition of Gn and an analysis of the derivatives of fn−1 as in the proof of Theorem
2, we obtain G− (−∞) = L− (−∞) + βG− (−∞). Summing this geometric series, we n−1 n ﬁnd that si will be ﬁnite for some n if L− (−∞)/(1 − β) < −ci . By Theorem 3, si n n
(and the other, greater critical values) will remain ﬁnite for all n > n as well.
Since L− (−∞) < 0 by Assumptions 1–3, the condition in Theorem 4 is satisﬁed for any particular i ∈ {1, . . . , m} when β is suﬃciently close to 1.

1.4.3 Relaxed model, inﬁnite-horizon discounted setting
We now build a case for the optimality of an rFGB policy for the relaxed model with respect to the inﬁnite-horizon discounted expected cost. In this eﬀort, we will make use of results proved for the ﬁnite-horizon case. The ﬁrst two theorems here will facilitate our solution of the discounted cost optimality equation.
Theorem 5. Let I ∈ R be given. There exist real numbers ZI and ZI with ZI < ZI such that the compact interval [ZI , ZI ] contains the minimizer(s) of the dynamic programming recursion for fn (I), for all n ≥ 1.
Proof. Consider the policy that always chooses Z = 0. The inﬁnite-horizon discounted expected cost of this policy, given that the initial state is I, is

χ(I) := C(−I) + E[L(−X)] + β

E[C(X)] + E[L(−X)]
1−β

which is ﬁnite for any given β ∈ (0, 1) under our assumptions. Any ﬁnite-horizon problem with initial state I will have an optimal discounted expected cost no greater than this quantity.
Let n ≥ 1 and I ∈ R be given. We deﬁne ZI such that E[L(Z − X)] > χ(I) for all Z ≤ Z , and we deﬁne ZI such that E[L(Z − X)] > χ(I) for all Z ≥ Z .
28

By Assumptions 1–3 and Lemmas 2–4, ZI and ZI may be chosen to be ﬁnite with
ZI < ZI . C ≥ 0 and L ≥ 0 by deﬁnition, and by induction we may argue that fn−1 ≥ 0, so we have C(Z − I) + βE[fn−1 (Z − X)] ≥ 0 for all Z ∈ R. Therefore, for each Z ∈ [ZI , ZI ] it is the case that
/

C(Z − I) + E[L(Z − X)] + βE[fn−1 (Z − X)] > χ(I)

But by the dynamic programming theorem and Theorems 1 and 2, fn (I) is the cost of a discount optimal policy, so we must have

C(Z − I) + E[L(Z − X)] + βE[fn−1 (Z − X)] ≤ χ(I)

for any minimizer of the recursive expression for fn (I).
Theorem 6. As n → +∞, 0 ≤ fn

f where f : R → R is convex with f − (−∞) ≥

−cm and f + (I) = 0 for I suﬃciently large.
Proof. By our deﬁnitions of the functions C and L and the terminal cost f0 , the cost incurred in any period in our ﬁnite-horizon setting is nonnegative. By Theorems
1 and 2 together with the dynamic programming theorem, then, for each n ≥ 0 the optimal cost function fn must be nonnegative. Furthermore, the optimal cost for our ﬁnite-horizon problem with (n + 1) decision points cannot be less than the optimal cost for the problem with n decision points, given a common initial state.
The sequence {fn (I) : n ≥ 0} is therefore nondecreasing for any given I. Additionally, continuing with notation introduced in the proof of Theorem 5, for any given I we have fn (I) ≤ χ(I) for all n ≥ 0 where χ(I) is a ﬁnite quantity. Thus the sequence
{fn (I) : n ≥ 0} converges to a ﬁnite value as n → +∞.
As a pointwise limit, f inherits the convexity of the functions fn established in
Theorem 2. Since f is also ﬁnite-valued, its left and right derivatives exist. The

29

property f − (−∞) ≥ −cm is inherited from the analogous property established for the functions fn in Theorem 2, as may be seen by using Lemma 11.
It remains to argue that f + (I) = 0 for I suﬃciently large. Consider again the proof of Theorem 5. If I = 0, we may deﬁne Z0 such that E[L(Z − X)] > χ(0) for all Z ≥ Z0 . Now observe that χ(I) = χ(0) for all I ≥ 0. By Theorem 5, then, a minimizer of the dynamic programming recursion for fn (I) cannot be greater than
Z0 for any I ≥ 0 and n ≥ 1. It follows that critical values s∗ as deﬁned in Theorem n +
1 cannot exceed Z0 . This implies through the proof of Theorem 2 that fn (I) = 0 for

I ≥ Z0 , for all n ≥ 1. Using Lemma 11, we conclude that f + (I) = 0 for I ≥ Z0 .
Following the ﬁnite-horizon case, we deﬁne G(Z) := E[L(Z − X)] + βE[f (Z − X)].
We also deﬁne Jn (I, Z) := C(Z − I) + Gn (Z) and J(I, Z) := C(Z − I) + G(Z).
Theorem 7. For all I ∈ R, f satisﬁes the discounted cost optimality equation:

f (I) = min{C(Z − I) + E[L(Z − X)] + βE[f (Z − X)]}
Z∈R

Proof. Theorem 6 implies that 0 ≤ fn (Z − X)

f (Z − X) for any given Z ∈ R and

any realized value of X. The properties of the derivatives of f established there along with the fact that E[X] < +∞ yields that E[f (Z − X)] is ﬁnite for all Z, as argued in the proof of Theorem 2 for E[fn−1 (Z − X)]. We may now invoke the monotone convergence theorem to establish that Gn

G as n → +∞ (by monotonicity of

expectation the convergence is monotone). We may also use Lemma 2 to see that
E[f (Z − X)] is a ﬁnite-valued convex function of Z. It follows that, given I ∈ R,
J(I, Z) as well as Jn (I, Z) are ﬁnite-valued convex functions of Z. Moreover, that
Gn

G implies Jn (I, Z)

J(I, Z) as n → +∞ for all real I and Z.

Let I ∈ R be given. By Theorem 5, there is a compact interval ϕ(I) := [ZI , ZI ] such that any minimizer of Jn (I, Z) over Z ∈ R must be in ϕ(I). By the development above, Lemma 9 implies that Jn (I, Z) converges uniformly to J(I, Z) on the
30

compact interval ϕ(I). Letting ε > 0 be given, there exists N such that n ≥ N implies both minZ∈ϕ(I) Jn (I, Z) ≤ minZ∈ϕ(I) J(I, Z) + ε and minZ∈ϕ(I) Jn (I, Z) ≥ minZ∈ϕ(I) J(I, Z) − ε. Since ε can be arbitrarily small and fn (I) = minZ∈ϕ(I) Jn (I, Z), we may take n → +∞ to conclude that f (I) = minZ∈ϕ(I) J(I, Z).
We may now brieﬂy argue that minZ∈ϕ(I) J(I, Z) = minZ∈R J(I, Z). Again, let
I ∈ R be ﬁxed. By the convexity of Jn and our selection of ϕ(I), it follows that
−
+
Jn (I, ZI ) ≤ 0 and Jn (I, ZI ) ≥ 0, where these derivatives are taken with respect to

Z, for all n ≥ 1. By Lemma 11, we ﬁnd that J − (I, ZI ) ≤ 0 and J + (I, ZI ) ≥ 0, so a minimizer of J(I, Z) over Z ∈ R will be found in ϕ(I). This establishes that f (I) = minZ∈R J(I, Z) as desired.
Our next result uses our solution to the discounted cost optimality equation to establish the optimality of an rFGB policy.
Theorem 8. Deﬁne s0 = +∞. For all i ∈ {∗, 1, . . . , m}, choose si minimizing ci Z + G(Z) over R. (Again, we deﬁne c∗ = 0.) If the minimum does not exist, deﬁne si = −∞. Then for all I ∈ R, the rFGB decision rule corresponding to parameters
{r0 , . . . , rm } and critical values {s0 , . . . , sm } along with s∗ achieves the minimum in the functional equation solved by f (I). Moreover, the rFGB policy with these parameters is discount optimal in the inﬁnite-horizon setting, and its cost is f (I) given initial state I.
Proof. In the proof of Theorem 7, we argue that E[f (Z − X)] is ﬁnite-valued and convex over Z ∈ R. In this context we may invoke Lemma 3 to the eﬀect that the left and right derivatives of this funtion are E[f − (Z − X)] and E[f + (Z − X)] respectively. Furthermore, Lemma 4 and the properties of the derivatives of f imply that E[f − (−∞ − X)] ≤ 0 and E[f + (+∞ − X)] = 0. Argument as in the proof of
Theorem 2 shows that, in addition to G being ﬁnite-valued and convex, G satisﬁes
G− (−∞) < 0 and G+ (+∞) > 0. Theorem 1 (with Gn replaced by G) now implies
31

that s∗ is ﬁnite, that this and the other critical values specify a valid rFGB decision rule, and that this rule achieves the minimum in the functional equation. Adjusting the functional equation, we have:

f (I) ≤ min{E[C(Z − I) + L(Z − X)] + βE[f (Z − X)]}
Z∈R

for any I ∈ R. Let π be any admissible policy. Treating I0 as an initial state implies by the above that

f (I0 ) ≤ Eπ0 [C(Z0 − I0 ) + L(Z0 − X0 )] + βEπ0 [f (I1 )]
I
I where the next state is I1 = Z0 − X0 . The history of the process at decision point n, which we call Hn , consists of (I0 , Z0 , . . . , In−1 , Zn−1 , In ). Using the above inequality as a base for induction, suppose for given n ≥ 1 that n−1 β t Eπ0 [C(Zt − It ) + L(Zt − Xt )] + β n Eπ0 [f (In )]
I
I

f (I0 ) ≤ t=0 Now for any history Hn with present state In , we also have from our functional equation that

f (In ) ≤ Eπ n [C(Zn − In ) + L(Zn − Xn )] + βEπ n [f (In+1 )]
H
H

In the induction hypothesis we may therefore apply monotonicity of expectation and the tower property, obtaining: n β t Eπ0 [C(Zt − It ) + L(Zt − Xt )] + β n+1 Eπ0 [f (In+1 )]
I
I

f (I0 ) ≤ t=0 The above holds for any I0 ∈ R and any n ≥ 1 by induction. A small adjustment to our argument shows that the above holds with equality for π = π ∗ , where π ∗
32

represents the speciﬁed rFGB policy that achieves the minimum in the functional equation. In the remainder of this proof, we will argue that any policy that does not satisfy β n+1 Eπ0 [f (In+1 )] → 0 cannot be optimal. Taking n → +∞, we may then
I
obtain: n f (I0 ) =
≤

∗

β t Eπ0 [C(Zt − It ) + L(Zt − Xt )]
I

lim

n→+∞

t=0 n β t Eπ0 [C(Zt − It ) + L(Zt − Xt )]
I

lim

n→+∞

t=0

for every policy π worth considering and for every I0 ∈ R. This will then establish the discount optimality of the rFGB policy π ∗ and validate the treatment of f as an optimal cost function.
For what kind of policy π would we see the condition β n+1 Eπ0 [f (In+1 )] → 0
I
fail? Consider Theorem 6. Since f is nonnegative, such a policy would have to see lim supn→+∞ Eπ0 [f (In+1 )] = +∞. Since f is convex and ﬁnite-valued with f − (−∞) ≥
I
−cm and f + (+∞) = 0, such a policy would have to see lim inf n→+∞ Eπ0 [In+1 ] = −∞.
I
Due to the geometric rate of decrease in β n+1 , a merely linear rate of decrease in a subsequence of {Eπ0 [In+1 ] : n ≥ 0} will not suﬃce to violate the condition. We will
I
argue below that only a non-optimal policy could sustain a faster-than-linear rate of decrease in a subsequence of {Eπ0 [In+1 ] : n ≥ 0}.
I
Recall from the proof of Theorem 5 that we need not consider policies with inﬁnitehorizon expected discounted cost greater than the cost incurred by a policy of setting
Z = 0 in every step. The cost of the Z = 0 policy with initial state I is, continuing with notation deﬁned previously, χ(I) = χ(0) + C(−I). As in Theorem 5, there exists some I low enough so that Z ≤ I implies E[L(Z − X)] > χ(0). Assumptions 1–3 and Lemmas 2 and 3 imply that the left derivative of E[L(Z − X)] is E[L− (Z − X)] and is no greater than δ := E[L− (I − X)] < 0 for Z ≤ I . For any given initial state

33

I, then,
E L I + δ −1 cm (−I)+ − X

> χ(0) + cm (−I)+ ≥ χ(I)

Therefore, in state I we need not consider choosing Z below I +δ −1 cm (−I)+ . When I decreases by one unit, this is to say that our lower bound on the order level Z decreases by (at most) the ﬁxed quantity |δ −1 cm |. For any sequence of realized demands, the most rapid drop in inventory within our bounds would result from always ordering to this lower bound; call this policy π . After our initial order dictated by π , this lower bound will decrease after each step by |δ −1 cm | times the latest realized demand.
Suppose that the initial state is I0 , that the initial action according to π is Z0 , and that for n ≥ 1 we have In = Zn−1 − Xn−1 . Given any ﬁnite sequence of realized demands, we have for n ≥ 1 that Zn = Zn−1 + δ −1 cm Xn−1 , and so
In+1 = Z0 + δ −1 cm (X0 + . . . + Xn−1 ) − Xn

Given any initial state and a sequence of realized demands up to a given period, the above state calculated for π may be taken as a lower bound on the state for any policy π we have not ruled out. Taking expectations,

Eπ0 [In+1 ] = Eπ0 [Z0 + δ −1 cm (X0 + . . . + Xn−1 ) − Xn ] = Z0 + nδ −1 cm E[X] − E[X]
I
I

and so the expected inventory level under π falls linearly in n. By monotonicity of expectation we conclude that, for those policies π we have not ruled out, the expected inventory level decreases at most at a linear rate (in any subsequence of the decision points). To complete this section, we study the eﬀect of β on our solution to the functional equation. The following result is an inﬁnite-horizon counterpart to Theorem 3.

34

+
−
Theorem 9. fβ (I) and fβ (I) are nonincreasing in β for all I. Consequently: if si β are chosen to be the greatest minimizers in Theorem 8, then these critical values are nondecreasing in β for all i ∈ {∗, 1, . . . , m}.
Proof. Let β1 , β2 ∈ (0, 1) be given with β1 < β2 . Via Theorems 3 and 6, we may
+
+
−
− invoke Lemma 11 to conclude that fβ1 (I) − fβ2 (I) ≥ 0 and fβ1 (I) − fβ2 (I) ≥ 0 for all

I. That the critical values are nondecreasing in β follows by an argument analogous to that used for Theorem 3.

1.4.4 Average optimality in the relaxed and unrelaxed models
We will now develop an argument for the average optimality of an rFGB policy in the relaxed model. In this eﬀort, we will make use of results proved for the ﬁnite-horizon and inﬁnite-horizon discounted cases. As before, we use subscripts ‘β’ to explicitly indicate dependence on the discount factor. Theorems 10 and 11 function in this context similarly to Theorem 5 in its context.
Theorem 10. s∗ , as deﬁned in Theorem 8, is bounded above by a ﬁnite quantity β independent of β.
Proof. We will show that there exists I ∗ ∈ R and β < 1 such that β ≥ β implies s∗ < I ∗ . Since by Theorem 9 the greatest candidate for s∗ is nondecreasing in β, we β β may then conclude that s∗ < I ∗ for all β ∈ (0, 1). β Let π ∗ denote an optimal rFGB policy as specifed in Theorem 8. Suppose that the initial state is I0 = s∗ , and consider the operation of π ∗ on our model. Given a β ∗∗ real parameter ∆ ≥ 0, we deﬁne a history-dependent policy π∆ by reference to its

control of a second model, operating in parallel and subject to the same initial state
I0 and the same sequence of demand variables Xt (and the same cost functions C and
L). At the initial decision point t = 0, the order quantity (Z0 − I0 ) is chosen to be one unit less in the second model than the quantity chosen at t = 0 by π ∗ in the ﬁrst
35

∗∗ model. (Given the initial state I0 = s∗ , this means that π∆ chooses Z0 = I0 − 1 while β π ∗ selects Z0 = I0 .) In subsequent decision points t ≥ 1, the order quantity (Zt − It ) is chosen in the second model to be the same as the quantity chosen at t by π ∗ in the ﬁrst model—with a single exception. In the ﬁrst decision point t at which the inventory level is observed to be strictly below s∗ −∆ in the ﬁrst system (equivalently, β strictly below s∗ − ∆ − 1 in the second system), the order quantity (Zt − It ) is chosen β to be one unit more in the second system than in the ﬁrst. We call this special decision point the “transitional step.” To sum up from another perspective: after the initial step, the inventory level in the second system tracks exactly one unit below the level in the ﬁrst system; then, after the inventory levels fall enough to trigger the transitional step, the inventory levels in the two systems match exactly. Note that
∗∗
the policy π∆ controlling the second system is admissible, with the proviso that we

have only deﬁned its behavior when the initial state is I0 = s∗ . β ∗∗
Except for the transitional step, in which one more unit is ordered under π∆ than

under π ∗ , the ordering cost C(Zt − It ) is the same for both policies at all decision points t. Meanwhile, if for all I ≥ s∗ − ∆ − 1 we have L+ (I) > 0, then the costs β L(Zt −Xt ) are lower for the second system in every step before the transitional step— excepting possibly the step immediately prior. In the transitional step and after, the costs L(Zt − Xt ) are equal for the two systems. We will show that, if s∗ ≥ I ∗ and β β ≥ β , then for the initial state I0 = s∗ the discounted expected cost of the policy β ∗∗ π∆ is less than that of π ∗ . Since we know that π ∗ is discount optimal, we may then

conclude that s∗ ≥ I ∗ is false for all β ≥ β . β By Assumptions 1 and 2, there exists ε > 0 and Imin ∈ R such that L+ (I) ≥ ε for all I ≥ Imin − 1. We deﬁne ∆ := 3kE[X] and β := (3/4)1/(k−1) for some integral value k ≥ 2 to be speciﬁed. By Assumption 4, we may focus on the nontrivial case where
P (X = 0) < 1, so we have 0 < E[X] < +∞. By Markov’s inequality (Grimmett and

36

Stirzaker 2001, p. 311), we have

P(

k−1 t=0 k−1 t=0 Xt > ∆) ≤ E[ n t=0

Deﬁning T∆ := min{n :

Xt ]/∆ = kE[X]/∆ =

1
3

Xt > ∆}, we then have k−1 t=0

P (T∆ ≥ k) = P (

Xt ≤ ∆) ≥

2
3

By the structure of rFGB policies and our choice of initial state I0 = s∗ , the time β index of the transitional step must be (strictly) greater than T∆ . If we posit I0 =
∗∗
s∗ ≥ Imin + ∆ and β ≥ β , then the expected discounted savings under π∆ (relative β to π ∗ ), before we ﬁrst see Zt − Xt < I0 − ∆ − 1, is at least

E[

T∆ −1 t=0 T∆ −1 t=0 β t ε] ≥ E[
≥ ε(

k−2 t=0 β t ε | T∆ ≥ k]P (T∆ ≥ k)

β t )( 2 )
3

≥ εk(β )k−1 ( 2 )
3
= kε/2

We may now ﬁx k to be some integral value large enough so that kε/2 > cm .
Here, cm serves as an upper bound on the expected discounted excess in ordering cost
∗∗
incurred by π∆ (relative to π ∗ ) in the transitional step. (The bound remains valid in

expectation even though we have not proved that the transitional step must occur.)
It remains to account for the possible diﬀerence between the expected discounted costs incurred in the period immediately before the transitional step. We use T to denote the time index of the transitional step.
Suppose the random variable X is bounded above by some real quantity Xmax .
∗∗
By requiring I ∗ ≥ Imin + Xmax + ∆, we ensure that L+ (ZT −1 − XT −1 ) > 0 under π∆ if

the transitional step occurs. In this case of bounded demand, we may then infer that
37

∗∗ the expected discounted savings under π∆ (relative to π ∗ ) in the period immediately

before the transitional step is nonnegative. In total, then, we have a positive net
∗∗
savings in expected discounted cost by using π∆ .

Suppose the random variable X is not bounded above. If the transitional step
∗∗
occurs, then under π∆ we have I0 − ∆ − 1 ≤ ZT −1 ≤ I0 − 1. Given ZT −1 = Z,
∗∗
the expected discounted savings under π∆ (relative to π ∗ ) in the period immediately

before the transitional step is at least

E[L+ (Z − X) | X > (Z − I0 − ∆ − 1)]
Since L+ is nondecreasing, the quantity above is at least

E[L+ (I0 − ∆ − 1 − X) | X > (Z − I0 − ∆ − 1)]

By Assumption 3 and Lemma 12 (as applied to nonincreasing functions), the quantity above is at least
E[L+ (I0 − ∆ − 1 − X) | X > ∆]
We are to take I0 ≥ I ∗ , and as I ∗ → +∞ we ﬁnd E[L+ (I ∗ − ∆ − 1 − X) | X > ∆] →
L+ (+∞) > 0. This may be seen by applying the monotone convergence theorem to the function L+ (I ∗ − ∆ − 1 − X)1(X > ∆), where 1 is the indicator function, much as was done for Lemma 4. Thus we may ﬁx I ∗ suﬃciently high so that the expected discounted savings in the period of concern is nonnegative. In total, we again have a
∗∗
positive net savings by using π∆ .

In the following theorem we deﬁne the critical values that will play a role in the optimal solution to the unrelaxed problem. From this point on, we use a subscript
‘1’ instead of ‘β’ to identify functions and critical values relevant to the undiscounted case. These functions and critical values are not to be confused with their ﬁnite-

38

horizon counterparts when there is one decision period remaining.
Theorem 11. For all i ∈ {∗, 1, . . . , m}, choose si to be the greatest minimizer deﬁned β in Theorem 8. We have si β si where si is some ﬁnite value, for all i as β → 1
1
1

for β ∈ (0, 1). (We deﬁne s0 := +∞.) Furthermore, there exists a compact interval
1
containing minimizers of the functional equation in Theorem 7 for all β ∈ (0, 1) suﬃciently large.
Proof. By Theorem 4, there exists β0 < 1 such that sm ,n is ﬁnite for some n ≥ 1. β0 −
By the analysis of the derivatives of fβ,n in Theorem 2, we have fβ0 ,n (I) = −cm

for all I < sm ,n − rm−1 . Since sm ,n ≤ sm ,n for all n > n (by Theorem 3), the β0 β0 β0 − convergence of fβ0 ,n to fβ0 (by Theorem 6) implies via Lemma 11 that fβ0 (I) = −cm

for all I < sm ,n − rm−1 . It follows that G−0 (Z) < −cm for suﬃciently low Z, so sm β0 β0 β as deﬁned above is ﬁnite.
By Theorem 9, the values si deﬁned above are all nondecreasing in β. By the β structure of our rFGB policies and Theorem 10, there exists I ∗ such that, for all β ≥ β0
−∞ < sm ≤ sm ≤ sm−1 ≤ . . . ≤ s2 ≤ s1 ≤ s∗ < I ∗ < +∞ β0 β β β β β
Monotonicity and boundedness show the desired ﬁnite limits exist with sm ≤ sm−1 ≤
1
1
. . . ≤ s2 ≤ s1 ≤ s∗ . By the structure of our rFGB policies and Theorem 8, it also
1
1
1
follows that, for each state I, a minimizer of the functional equation lies in [sm , s∗ ] β0 1 for all β ≥ β0 .

¯
For β ∈ (0, 1), we deﬁne the relative cost function fβ (I) := fβ (I) − fβ (s∗ ). The
1
following theorem may be compared with Theorem 6 in the previous part.
¯
Theorem 12. As β → 1 for β ∈ (0, 1), 0 ≤ fβ
¯−
¯ with f1 (−∞) ≥ −cm and f1 (I) = 0 for I ≥ s∗ .
1
39

¯
¯
f1 where f1 : R → R is convex

¯
Proof. By Theorem 11, s∗ is ﬁnite; by Theorem 6, so is fβ (s∗ ) and hence fβ . Therefore,
1
1
+
−
¯+
¯− we may directly obtain fβ (I) = fβ (I) and fβ (I) = fβ (I) for all I. From Theorem
−
¯−
¯
6, then, fβ (−∞) = fβ (−∞) ≥ −cm . Moreover, fβ inherits convexity from fβ . Using

the properties of Gβ shown in the proof of Theorem 8, an analysis of the derivatives
+
of fβ as in the proof of Theorem 2 yields fβ (I) = 0 for I ≥ s∗ . Since (via Theorem β −
¯
11) s∗ ≤ s∗ we have fβ (I) = 0 for all I ≥ s∗ . We also have fβ (I) ≤ 0 for I ≤ s∗
1
1
1
β

by convexity, so Lemma 10 may be used to show that fβ (I) ≥ fβ (s∗ ) for all I < s∗ .
1
1
¯
Putting the preceding two comments together, we conclude that fβ ≥ 0. All of the foregoing holds for all β ∈ (0, 1).
¯
¯
We may now argue by Theorem 9 that fβ1 ≤ fβ2 for β1 < β2 . To see this,
¯
¯
¯−
¯−
¯
observe that fβ1 = fβ2 = 0 over [s∗ , +∞) and fβ1 ≥ fβ2 over (−∞, s∗ ], each fβ being
1
1
¯− ¯− ¯ continuous, and apply Lemma 10 (in its “turned around” form) to fβ2 − fβ1 . fβ is also
¯
bounded above, since by the preceding paragraph we may write f (I) ≤ cm (s∗ − I)+ .
1
This establishes the desired monotone convergence to the limiting function we call
¯
¯−
¯−
¯ f1 . Using Lemma 11, fβ (−∞) ≥ −cm implies that f1 (−∞) ≥ −cm . Also, fβ (I) = 0
¯
implies f1 (I) = 0 for I ≥ s∗ .
1

¯
¯
Following the discounted case, we deﬁne Gβ (Z) := E[L(Z − X)] + βE[fβ (Z − X)]
¯
¯ and Jβ (I, Z) := C(Z − I) + Gβ (Z) for β ∈ (0, 1). Similarly, we deﬁne the functions
¯
¯
¯
¯
G1 (Z) := E[L(Z − X)] + E[f1 (Z − X)] and J1 (I, Z) := C(Z − I) + G1 (Z).
By adding fβ (s∗ ) to both sides of the functional equation in Theorem 7, we obtain
1
for all I ∈ R and all β ∈ (0, 1) the modiﬁed functional equation
¯
¯
(1 − β)fβ (s∗ ) + fβ (I) = min{C(Z − I) + E[L(Z − X)] + βE[fβ (Z − X)]}
1
Z∈R

which we will use to prove the following result.

40

Theorem 13. For all I ∈ R:
• (1 − β)fβ (I) → ρ as β → 1 for some ρ ∈ R.
¯
• ρ and f1 satisfy the average cost optimality equation:
¯
¯ ρ + f1 (I) = min{C(Z − I) + E[L(Z − X)] + E[f1 (Z − X)]}
Z∈R

Proof. We will substantially follow the proof of Theorem 7. Using Theorem 12 as
¯
a basis instead of Theorem 6, we obtain Gβ

¯
¯
G1 and Jβ

¯
J1 as β → 1, where

¯
¯
G1 (Z) and J1 (I, Z) are ﬁnite-valued and convex in Z for ﬁxed I. Let I ∈ R be given.
¯
By Theorem 11, there is a compact interval ϕ such that a minimizer of Jβ (I, Z) over
Z ∈ R must exist in ϕ for β suﬃciently large. By the convergences just noted, Lemma
¯
¯
9 implies that Jβ (I, Z) converges uniformly to J1 (I, Z) on ϕ as β → 1. Letting
¯
ε > 0 be given, there exists β such that β ≥ β implies both minZ∈ϕ Jβ (I, Z) ≤
¯
¯
¯
minZ∈ϕ J1 (I, Z) + ε and minZ∈ϕ Jβ (I, Z) ≥ minZ∈ϕ J1 (I, Z) − ε. Since ε can be
¯
¯ arbitrarily small, we have limβ→1 minZ∈ϕ Jβ (I, Z) = minZ∈ϕ J1 (I, Z), the latter term being ﬁnite, as it is the minimum of a continuous function over a compact interval.
¯
As we argued for Theorem 7, using the convexity of Jβ and its minimization over ϕ
¯
¯ along with Lemma 11 implies that minZ∈ϕ J1 (I, Z) = minZ∈R J1 (I, Z).
¯
¯
By our modiﬁed functional equation, (1−β)fβ (s∗ ) = minZ∈R Jβ (I, Z)− fβ (I) for β
1
¯
¯
suﬃciently large. Taking β → 1, we see (1 − β)fβ (s∗ ) → minZ∈R J1 (I, Z) − f1 (I) =: ρ.
1
This limit is ﬁnite, and it establishes the solution to the average cost optimality
¯
equation. Observe from Theorem 12 that 0 ≤ (1 − β)fβ (I) ≤ (1 − β)cm (s∗ − I)+ , and
1
¯ so (1 − β)fβ (I) → 0 as β → 1, which means that ((1 − β)fβ (I) − (1 − β)fβ (s∗ )) → 0.
1
Given our deﬁnition of ρ, this implies that (1 − β)fβ (I) → ρ as desired.
The following theorem uses our solution of the average cost optimality equation to show the average optimality of an rFGB policy.

41

Theorem 14. The critical values {s0 , . . . , sm } and s∗ deﬁned in Theorem 11, together
1
1
1
with the given parameters {r0 , . . . , rm }, characterize an rFGB policy π ∗ that is average optimal for the relaxed model. Also, for any initial inventory level I0 ∈ R, we have
1
n→+∞ n + 1

n
∗

Eπ0 [C(Zt − It ) + L(Zt − Xt )] = ρ
I

lim

t=0

Proof. We ﬁrst argue that π ∗ satisﬁes the average cost optimality equation of Theorem
¯
¯
13 along with ρ and f1 . Observe from the proof of Theorem 13 that G1 is ﬁnitevalued and convex. From Theorem 12, Lemmas 2–4, and Assumptions 1–3, we can
¯1
¯1 see (similar to the proofs of Theorems 2 and 8) that G− (Z) < 0 and G+ (Z) > 0.
The proof of Theorem 1 still works if we take β = 1, so an rFGB decision rule with
¯
critical values minimizing ci Z + G1 (Z) for i ∈ {∗, 1, . . . , m} will achieve the minimum
¯
in the average cost optimality equation. Since Gβ

¯
G1 as β → 1 (from the proof

¯ of Theorem 13), Lemma 8 implies that minimizers of ci Z + Gβ (Z) will converge to
¯
minimizers of ci Z + G1 (Z) if they converge at all. By Theorem 11, then, si minimizes
1
¯ ci Z + G1 (Z) for all i ∈ {∗, 1, . . . , m}.
Consider any admissible policy π. Given initial state I0 , by Theorem 8 we have for all β ∈ (0, 1) that:
+∞

β t Eπ0 [C(Zt − It ) + L(Zt − Xt )] ≥ fβ (I0 )
I
t=0

Multiplying both sides of the above by (1 − β), it follows from Theorem 13 that
+∞

β t Eπ0 [C(Zt − It ) + L(Zt − Xt )] ≥ lim sup(1 − β)fβ (I0 ) = ρ
I

lim sup(1 − β) β→1 β→1

t=0

Applying Lemma 13,

lim sup t→+∞ 1 t+1 +∞

Eπ0 [C(Zt − It ) + L(Zt − Xt )] ≥ ρ
I
t=0

42

This means that ρ is a lower bound on the (lim sup) average expected cost. Now given our argument at the outset, we have for all t:
∗

∗

¯
¯
ρ + f1 (It ) = Eπ t [C(Zt − It ) + L(Zt − Xt )] + Eπ t [f1 (It+1 )]
H
H

where Ht represents the information available at the point of decision in period t
(deﬁned in the proof of Theorem 8). Given any initial state I0 , we may sum the equations corresponding to t ∈ {0 . . . n}, divide the resulting equation by (n + 1), and take expectations on both sides (based on π ∗ and I0 ) to obtain
1
n+1

n
∗

Eπ0 [C(Zt − It ) + L(Zt − Xt )] = ρ +
I
t=0

1
1 ¯
∗
¯ f1 (I0 ) −
Eπ0 f1 (In+1 )
I
n+1 n+1 Consider the right side of this equation as n → +∞. The ﬁrst term is a constant.
¯
¯
Since f1 is ﬁnite-valued, the second term converges to 0. Given the form of f1 (from
¯
¯
Theorem 12) and π ∗ , we note that f1 (In+1 ) is nonnegative and less than f1 (sm − Xn )
1
for all realized Xn . Hence the expectation in the third term is nonnegative and less
¯
than E[f1 (sm − Xn )], which is ﬁnite by Theorem 12 and the fact that E[X] < +∞.
1
The third term therefore converges to 0. We conclude that the desired limit indeed holds, and this establishes the average optimality of π ∗ .
We now relate our relaxed model with Z ∈ R to the unrelaxed model with the constraint Z ≥ I, given what we have proved in Theorem 14. This accomplishes the primary mathematical goal of the chapter.
Theorem 15. The critical values {s0 , . . . , sm } deﬁned in Theorem 11 (where all
1
1 but s0 := +∞ were identiﬁed to be ﬁnite), together with the given parameters
1
{r0 , . . . , rm }, characterize an FGB policy π that is average optimal for the relaxed
¯
model, and is therefore average optimal for the unrelaxed model as well.
Proof. The FGB policy π speciﬁed diﬀers from the average optimal rFGB policy of
¯
43

Theorem 14 (which we again call π ∗ ) only in that Z = I is chosen when the inventory level is observed to be I > s∗ , rather than choosing Z = s∗ . Observe that for initial
1
1 states I0 ≤ s∗ , the two policies will behave equivalently at every decision point as
1
the system operates. This is because an inventory level I > s∗ will never be seen
1
given such an initial state, since Z > s∗ is never chosen by these policies for observed
1
inventory levels I ≤ s∗ . The long-run average expected cost of π for initial states
¯
1
I0 ≤ s∗ is therefore ρ, the same as the long-run average expected cost of π ∗ identiﬁed
1
in Theorem 14.
We now argue that, for any given initial state I0 > s∗ , the long-run average
1
expected cost of π is also ρ. Deﬁne T to be a random variable indicating the ﬁrst
¯
¯ decision period for which It < s∗ under policy π . Since Zt = It for all t < T under this
1
T −2 t=0 policy, T is determined by the properties

Xt ≤ (I0 −s∗ ) and
1

T −1 t=0 Xt > (I0 −s∗ ).
1

Because Assumption 4 tells us that P (X = 0) < 1, a standard theorem of renewal theory (Grimmett and Stirzaker 2001, p. 412) implies that T is ﬁnite with probability one. Furthermore, IT will be ﬁnite with probability one. Given T and IT , both ﬁnite, the cost incurred in periods 0 through T − 1 is bounded above by T M , where
M := max{L(I) : I ∈ [IT , I0 ]}. By Assumption 1, M is ﬁnite, and we also have a lower bound of 0 on the cost incurred through period T − 1. Given T and IT , both ﬁnite, because the action of π depends only on the current inventory level, the cost
¯
incurred in any period t ≥ T is probabilistically the same as the cost incurred T steps earlier in a system with initial state IT . Therefore, given T and IT as noted, the sequence of averages

1 n+1 n t=0 ¯
Eπ0 [C(Zt − It ) + L(Zt − Xt )] is bounded above for all
I

n ≥ T by the sequence

1
TM
n+1

+

n−T +1 n+1 1 n−T +1

n−T t=0 ¯
EπT [C(Zt − It ) + L(Zt − Xt )] → ρ
I

44

and bounded below for all n ≥ T by the sequence

n−T +1 n+1 1 n−T +1

n−T t=0 ¯
EπT [C(Zt − It ) + L(Zt − Xt )] → ρ
I

where in taking limits we have used the fact that IT < s∗ . We conclude that the
1
long-run average expected cost of the policy π must be ρ as desired.
¯
We may now conclude that the FGB policy π is average optimal for the relaxed
¯
model: it performs as well as the average optimal rFGB policy π ∗ with respect to our optimality criterion. Furthermore, π is feasible for the unrelaxed model, as it
¯
never chooses a negative order quantity. Since any admissible policy that is feasible for the unrelaxed model is also feasible for the relaxed model, there cannot exist an admissible policy outperforming π in the unrelaxed model with respect to our
¯
optimality criterion. Such a policy would have to outperform π ∗ in the relaxed model, which by Theorem 14 is impossible.

1.4.5 Extension to the discrete case
In this section, we extend our main result to the discrete case in which demands and order quantities may take only nonnegative integral values.
First, we may assume without loss of generality that the initial inventory level is an integer. Consequently, we may posit that the state of the process is always integral. This assumption is justiﬁed because we can shift our holding and backlogging cost function L by the same amount required to shift a fractional initial inventory level to reach an integral value. Policies in this “shifted” model then have the same cost characteristics as “unshifted” policies in the original model, and furthermore an
“unshifted” FGB policy is still of the FGB type (featuring “unshifted” critical values).
We may also assume without loss of generality that the source capacity parameters {r1 , . . . , rm−1 } take integral values. This is because, if some parameters ri

45

are fractional, we can replace the ordering cost function C with another function
¯
C : R+ → R+ which is equal to C for integral order quantities, but which is linear on the interval [Q, Q + 1] for each nonnegative Q ∈ Z. By the nature of the discrete
¯
case, this substitution makes no diﬀerence to the cost incurred by a given policy. (C may, however, have a larger or smaller number of linear pieces than C.)
Given our assumption that the initial inventory level is integral, we may similarly
¯
replace the holding and backlogging cost function L by L : R → R+ , which is deﬁned to be equal to L for integral inventory levels, but which is linear on the interval
[I, I + 1] for each I ∈ Z. By the nature of the discrete case, this substitution likewise
¯
makes no diﬀerence to the cost incurred by a given policy. Furthermore, L inherits the satisfaction of Assumptions 1–3 from L. In particular, Assumption 1 may be justiﬁed
¯
¯ by Lemma 6: it is clear that L is continuous and that L+ is constant on [I, I + 1) for
¯
¯ each I ∈ Z; furthermore, by Lemma 1 we have L+ (I − 1) ≤ L− (I) ≤ L+ (I) ≤ L+ (I).
Given this, Assumption 2 follows from noting that, as with L, there must exist reals
¯
¯
I and I such that L− (I ) < 0 and L+ (I ) > 0. It remains to deal with Assumption
3. Let Z ∗ ∈ R be given. Using Assumption 2 just shown, deﬁne Z to be the greatest
¯
¯
¯
integer less than or equal to min{Z : L(Z) = L(Z ∗ )}. Using the convexity of L, we
¯
¯ ﬁnd for any (integral) realized demand X that L(Z ∗ − X) ≤ L(Z − X) = L(Z − X).
¯
That E[L(Z ∗ − X)] < +∞ follows by monotonicity of expectation.
¯
Let us designate by F the class of functions R → R exempliﬁed by L, deﬁning the class to consist of those continuous functions that are linear on the interval [x, x + 1]
¯
for each x ∈ Z. Observe that the ordering cost function C belongs to F when we extend its domain to the negative real line, where it is deﬁned to be equal to zero in the context of our relaxed model (i.e., the model allowing negative order quantities).
Key facts about F are as follows. The class is closed with respect to addition, addition of real constants being a special case. Multiplication by real constants also preserves membership in F, as does shifting of functions (left or right) by ﬁxed integral

46

amounts. Finite limits of sequences of functions in F are also in F. Given g, h ∈ F, we may conclude that g(h(x)) ∈ F, if h maps integers to integers and the linear pieces of h have slopes among {−1, 0, 1} only. If a function in F has a greatest minimizer, then the greatest minimizer is an integer.
Consider now the main argument of Sections 1.4.2–1.4.4, when we are assured
C, L ∈ F as justiﬁed above, ignoring the requirement that order quantities be integral.
In Theorem 1, we ﬁnd if Gn ∈ F that ci Z + Gn (Z) is in F for each i ∈ {∗, 1, . . . , m}, and when any of these functions has a minimum its greatest minimizer is integral.
In Theorem 2, we may argue that Gn ∈ F and fn ∈ F for all n ≥ 1. We ﬁrst argue that Gn ∈ F if fn−1 ∈ F. We ﬁnd that L(Z − X) ∈ F for all realized X, and so
E[L(Z − X)] belongs to F as a sum of functions in F or as a ﬁnite limit of such sums.
Similarly, by hypothesis E[fn−1 (Z − X)] must be in F, and now Gn ∈ F follows. We next argue that fn ∈ F if Gn ∈ F. Observe that
∗
∗ fn (I) = C(Zn (I) − I) + Gn (Zn (I))

∗ where Zn (I) is a function of I assigning order-up-to levels in accordance with the

rFGB policy speciﬁed by the critical values si that are integral (whenever ﬁnite) n ∗ as we have established. We ﬁnd that Zn (I) ∈ F, that this function maps integers

to integers, and that its linear pieces have slopes among {0, 1} only. Additionally,
∗
(Zn (I) − I) ∈ F maps integers to integers and its linear pieces have slopes among

{−1, 0} only. Since C ∈ F, and since Gn ∈ F by hypothesis, we may conclude that fn ∈ F as desired. Now, since our terminal value function f0 := 0 is in F, the desired memberships in F follow for all n ≥ 1.
We turn to the inﬁnite-horizon setting. By Theorem 6, fn

f where f is ﬁnite-

valued, so we have f ∈ F. Since G is deﬁned in terms of f in the same way that Gn is deﬁned in terms of fn−1 , the fact that G ∈ F follows by an argument analogous

47

to that indicated for the ﬁnite-horizon setting. Also like the ﬁnite-horizon setting, we ﬁnd in Theorem 8 that, by choosing the greatest minimizer of ci Z + G(Z) where possible, the critical values si are integral (whenever ﬁnite). From the perspective of the vanishing discount approach, these critical values si deﬁne a discount optimal β rFGB policy when the discount factor is β ∈ (0, 1). By Theorem 11, for each i ∈
{∗, 1, . . . , m} we have si β si as β → 1, each limit being ﬁnite. By the integrality
1

of each si for i ∈ {∗, 1, . . . , m}, each of these limiting values si must be integral. In
1
β
Theorem 15, then, the FGB policy that is average optimal for the unrelaxed model is speciﬁed by the integral critical values {s1 , . . . , sm } as well as the integral parameters
1
1
{r0 , . . . , rm−1 } (and, by deﬁnition, s0 = rm = +∞). Since we are assured that the
1
initial inventory level is integral (as justiﬁed above), it follows that the order quantity chosen by this FGB policy will be integral at each decision point. Since this policy is average optimal in the absence of the constraint mandating integral order quantities, this same policy is also average optimal when the constraint is imposed.

1.5 Conclusion
In this chapter, we have proved the existence of a ﬁnite generalized base stock policy that is optimal under an average cost criterion, for an inventory control model involving multiple sources of a single product. Our main argument concentrated on a continuous setting; we subsequently indicated how this argument can also be used to establish the result in a discrete case. Building on this work, one potentially interesting research direction would involve integration of our methods with other mathematical work on average optimal control in Markov decision processes (particularly including other inventory models). Such integration may enable streamlining of our main argument. Relatedly, methods we have employed (such as examination of the derivatives of discounted value functions within a vanishing discount approach) may also ﬁnd wider use in proving new results or simplifying proofs of known re-

48

sults. Research establishing the degree to which our work is relevant for practical applications would also be most welcome. Such research may warrant investigation of methods for computing the critical values we have shown to exist.

49

1.6 References
Arapostathis, A., V. S. Borkar, E. Fern´ndez-Gaucherand, M. K. Ghosh, S. I. a Marcus. 1993. Discrete-time controlled Markov processes with average cost criterion: A survey. SIAM Journal on Control and Optimization 31(2) 282–344.
Bartle, R. G. 1976. The Elements of Real Analysis, 2nd ed. Wiley, New York.
Beckmann, M. J. 1961. Production smoothing and inventory control. Operations
Research 9(4) 456–467.
Bensoussan, A., M. Crouhy, J.-M. Proth. 1983. Mathematical Theory of Production
Planning. Elsevier Science, Amsterdam.
Beyer, D., S. P. Sethi. 1999. The classical average-cost inventory models of Iglehart and Veinott-Wagner revisited. Journal of Optimization Theory and Applications
101(3) 523–555.
Beyer, D., F. Cheng, S. P. Sethi, M. Taksar. 2009. Markovian Demand Inventory
Models. Springer, Secaucus, NJ. Forthcoming.
Bulinskaya, E. V. 1967. Optimum inventory policies with a convex ordering cost function. Theory of Probability and its Applications 12(1) 9–21.
Chen, X., D. Simchi-Levi. 2004. Coordinating inventory control and pricing strategies with random demand and ﬁxed ordering cost: The inﬁnite horizon case. Mathematics of Operations Research 29(3) 698–723.
Feinberg, E. A., A. Shwartz, eds. 2002. Handbook of Markov Decision Processes:
Methods and Applications. Kluwer, Boston, MA.
Feinberg, E. A., M. E. Lewis. 2006. Optimality inequalities for average cost Markov decision processes and the optimality of (s, S) policies. Technical Report
TR1442, Cornell University, Ithaca, NY. http://legacy.orie.cornell.edu/~melewis/pubs/mdp-ss-tech-report.pdf Accessed May 23, 2009.
Flett, T. M. 1980. Diﬀerential Analysis: Diﬀerentiation, Diﬀerential Equations, and
Diﬀerential Inequalities. Cambridge University Press, Cambridge, UK.
Geunes, J. 1999. Models to Optimize Multi-Stage Linkages in Manufacturing and
Distribution Operations. Ph.D. dissertation, Smeal College of Business
Administration, Pennsylvania State University, University Park, PA.
Grimmett, G. R., D. R. Stirzaker. 2001. Probability and Random Processes, 3rd ed.
Oxford University Press, Oxford, UK.
Henig, M., Y. Gerchak, R. Ernst, D. F. Pyke. 1997. An inventory model embedded in designing a supply contract. Management Science 43(2) 184–189.
50

Hern´ndez-Lerma, O., J. B. Lasserre. 1996. Discrete-Time Markov Control a Processes: Basic Optimality Criteria. Springer, New York.
Heyman, D. P., M. J. Sobel. 1984. Stochastic Models in Operations Research,
Volume II: Stochastic Optimization. McGraw-Hill, New York.
Hiriart-Urruty, J.-B., C. Lemar´chal. 1993. Convex Analysis and Minimization e Algorithms I: Fundamentals. Springer, Berlin.
Huh, W. T., G. Janakiraman, M. Nagarajan. 2008. Average cost inventory models:
An analysis using a vanishing discount approach. Working paper dated
September 15, 2008.
Iglehart, D. L. 1963. Dynamic programming and stationary analysis of inventory problems. H. E. Scarf, D. M. Gilford, M. W. Shelly, eds. Multistage Inventory
Models and Techniques, Stanford University Press, Stanford, CA, 1–31.
Karlin, S. 1958. Optimal inventory policy for the Arrow-Harris-Marschak dynamic model. K. J. Arrow, S. Karlin, H. Scarf, eds. Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, Stanford, CA, 135–154.
Kleindorfer, P., H. Kunreuther. 1978. Stochastic horizons for the aggregate planning problem. Management Science 24(5) 485–497.
Liu, B., A. O. Esogbue. 1999. Decision Criteria and Optimal Inventory Processes.
Kluwer Academic, Boston, MA.
Porteus, E. L. 1990. Stochastic inventory theory. D. P. Heyman, M. J. Sobel, eds.
Stochastic Models, Elsevier Science, Amsterdam, 605–652.
Porteus, E. L. 2002. Foundations of Stochastic Inventory Theory. Stanford
University Press, Stanford, CA.
Puterman, M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic
Programming. Wiley, New York.
Rockafellar, R. T. 1970. Convex Analysis. Princeton University Press, Princeton,
NJ.
Sch¨l, M. 1993. Average optimality in dynamic programming with general state a space. Mathematics of Operations Research 18(1) 163–172.
Sennott, L. I. 1999. Stochastic Dynamic Programming and the Control of Queueing
Systems. Wiley, New York.
Serel, D. A., M. Dada, H. Moskowitz. 2001. Sourcing decisions with capacity reservation contracts. European Journal of Operational Research 131 635–648.
Sethi, S., H. Zhang, Q. Zhang. 2005. Average-Cost Control of Stochastic
Manufacturing Systems. Springer, New York.
51

Sobel, M. J. 1969. Production smoothing with stochastic demand I: Finite horizon case. Management Science 16(3) 195–207.
Sobel, M. J. 1970. Making short-run changes in production when the employment level is ﬁxed. Operations Research 18(1) 35–51.
Sobel, M. J. 1971. Production smoothing with stochastic demand II: Inﬁnite horizon case. Management Science 17(11) 724–735.
Vega-Amaya, O., R. Montes-de-Oca. 1998. Application of average dynamic programming to inventory systems. Mathematical Methods of Operations
Research 47 451–471.
Veinott, A. F. 1964. Production planning with convex costs: A parametric study.
Management Science 10(3) 441–460.
Veinott, A. F., H. M. Wagner. 1965. Computing optimal (s, S) inventory policies.
Management Science 11(5) 525–552.
Veinott, A. F. 1966. The status of mathematical inventory theory. Management
Science 12(11) 745–777.
Webster, R. 1994. Convexity. Oxford University Press, Oxford, UK.
Wheeden, R. L., A. Zygmund. 1977. Measure and Integral: An Introduction to Real
Analysis. Marcel Dekker, New York.
Yang, J., X. Qi, Y. Xia. 2005. A production-inventory system with Markovian capacity and outsourcing option. Operations Research 53(2) 328–349.
Zheng, Y.-S. 1991. A simple proof for optimality of (s, S) policies in inﬁnite-horizon inventory systems. Journal of Applied Probability 28 802–810.
Zipkin, P. H. 2000. Foundations of Inventory Management. McGraw-Hill, Boston,
MA.

52

CHAPTER 2: OPTIMAL COMPOSITION OF A RETAIL
DISTRIBUTION FLEET WHEN SPOT CAPACITY IS AVAILABLE

2.1 Introduction
We address the ﬂeet composition problem faced by a retail distribution ﬁrm, with particular attention to a major distributor of beverage products. Every working day, the distributor transports merchandise from a distribution center to a great number of customer sites using trucks of several sizes. Demand becomes known to the distributor just before the requested day of delivery, and the ﬁrm strives for a consistently high service level in which deliveries are not delayed. Vehicle routes are not ﬁxed. The distributor experiences daily demand that is variable in terms of the total cubic volume as well as the average drop size. Customers are heterogeneous, ranging from large hypermarkets to small shops or restaurants. A customer’s demand on a given day generally does not necessitate a particular size of vehicle to satisfy the demand. Common carriers can be hired on a spot basis to supplement the ﬂeet as needed on a given day. We take the planning horizon to be one year in length for illustrative purposes. The goal is to balance the ﬁxed cost of vehicles to be owned through the planning horizon against exposure to a high variable cost due to reliance on spot capacity. (We streamline our discussion in this chapter by referring to “owned” vehicles, though our reasoning is intended to apply similarly to typical leasing arrangements.)
To assist the distributor’s decision of the proper ﬂeet size and mix for next year, we propose an optimization model. The model revolves around the description of a day’s demand in terms of the total cubic volume to be delivered and the total number of customers to visit. We submit that this compact characterization is useful for capturing the capabilities of diﬀerent sizes of vehicles. Consider a speciﬁc, substantial cubic volume of merchandise for delivery on a particular day. If this demand is concentrated
53

among only a few customer sites, then in the interest of minimizing variable cost we would tend to prefer utilizing a few large vehicles from our ﬂeet. (Large vehicles tend to be more eﬃcient than small vehicles in terms of variable cost, e.g. cost due to fuel and driver-hours, when moving a great volume of merchandise from one ﬁxed location to another.) If the same cubic volume of demand is instead scattered evenly across a great many customer sites, then we are inclined to “parallel process” the deliveries by utilizing many small vehicles. In this chapter, we introduce a two-stage stochastic linear program with ﬁxed recourse that is based on this two-dimensional characterization of demand, and we present an eﬃcient algorithm facilitating solution of this model by a standard gradient-based method for continuous optimization.
There is a substantial current of published research concerning ﬂeet composition decisions and the closely related problem of ﬂeet sizing, incorporating a great variety of application contexts and modeling approaches. Some researchers take a more detail-oriented approach to modeling the day-to-day operations underlying the strategic decision at hand (e.g. Dell’Amico et al. 2007, Sim˜o et al. 2008). Such moda els typically involve complex vehicle routing subproblems, and they are likely to be daunting in terms of computational eﬀort and data requirements—particularly when considering a large customer base for deliveries, for which routes are not ﬁxed from day to day, under a long planning horizon. Other models are less concerned with the intricacies of vehicle movements, likely making implementation easier (e.g. Wyatt
1961, Papier and Thonemann 2008).
In the wider context of capacity planning, there is a recent stream of literature introducing rather abstract capacity decision models whose applicability to ﬂeet composition problems has been little studied. Eberly and Van Mieghem (1997) study optimal adjustments of multiple factor levels in a multiperiod, stochastic setting. Van
Mieghem and Rudi (2002) introduce a multidimensional capacity investment model involving a more speciﬁc, but still quite general, model of resource processing. This

54

more speciﬁc model is a recourse linear program within a two-stage stochastic program involving uncertain demand variables in the right-hand side; following earlier work, the authors illustrate a solution approach for the investment problem based on a decomposition of the space of possible demands.
In the domain of two-stage stochastic linear programming with ﬁxed recourse, the decomposition just mentioned is fairly familiar (e.g. Birge and Louveaux 1997, pp.
170–171). The space of possible demands is dissected into regions such that the same basis is optimal throughout any given region. Such a construction facilitates various means of solution of the stochastic program; if the demand space has low dimension, then numerical integration might then be used to compute the ﬁrst-stage cost and its gradient (or a subgradient). Essentially the same kind of decomposition is sought in parametric linear programming (e.g. Jones 2005).
Our approach brings together two key elements that have appeared only separately in the literature on ﬂeet composition: the use of a two-stage stochastic programming formulation, and the description of a day’s demand by the total quantity to be delivered and the total number of customers to visit. This synthesis allows us to capture our distributor’s daily demand over an entire planning horizon by a bivariate probability distribution. In practice, this opens up the possibility of identifying a suitable distribution family, for present purposes reducing the task of forecasting a year’s worth of daily demand to the estimation of a handful of distribution parameters. In the context of capacity decision models, we oﬀer a specialized recourse structure for ﬂeet composition within the framework of Eberly and Van Mieghem (1997) and Van
Mieghem and Rudi (2002), and we oﬀer an eﬃcient algorithm producing a decomposition of the demand space given any number of vehicle types. This algorithm actually generates what we call a “deﬁnitive” collection of bases, which correspond to a dissection of the demand space facilitating solution of the stochastic program in the manner suggested above. In the context of stochastic linear programming and

55

parametric linear programming, we name and explicitly deﬁne (for our model) the concept of a deﬁnitive collection of bases—which seems to have been only implicit in prior work—and we provide a tailored algorithm generating such a collection when the
(recourse) linear program consists of minimization subject to two positive fractional covering constraints with variable upper bounds.
Our overarching contribution in this chapter, then, is a relatively simple and fast solution approach for the ﬂeet composition problem faced by our prototypical distributor. Our research contributions in support of this overarching goal pertain to the type of model we propose, which is new in the context of ﬂeet composition, and to our proposed method of solution. Our solution method, a standard gradientbased approach at surface level, relies on our specialized algorithm to facilitate rapid computation of the expected cost of a prospective ﬂeet composition and its gradient.
We articulate the concept of a “deﬁnitive” collection of bases, over whose feasible regions we perform double integration to obtain the expected second-stage cost or its gradient for any ﬂeet composition. Our recourse linear program has exponentially many bases, but our algorithm generates a deﬁnitive set of O(n2 ) bases in O(n3 ) time, where n is the number of vehicle types.
The rest of the chapter is organized as follows. In Section 2.2, we review relevant literature in the contexts of ﬂeet management, capacity planning, and optimization.
In Section 2.3, we present our model, we make explicit certain key propositions underlying our model, and we elaborate on our model’s relationship to newsvendor-type models in prior literature. In Section 2.4, we precisely deﬁne our concept of a deﬁnitive collection of bases, indicate the usefulness of such collections in solving our model, and present and validate our algorithm for generating deﬁnitive collections for our model. We oﬀer concluding remarks in Section 2.5 and list references in Section 2.6.

56

2.2 Literature review
2.2.1 Fleet composition and related problems
Fleet composition has been an object of study in the operations research and management science literature since at least the 1950s. Early published work on this subject includes Kirby (1959) and, arguably, Dantzig and Fulkerson (1954). Studies have addressed ﬂeets of cargo ships (Sigurd et al. 2005), warships (Crary et al. 2002), various classes of trucks (Gould 1969, Woods and Harris 1979, Ball et al. 1983, Wu et al.
2005), buses (Ceder 2005), locomotives (Nahapetyan et al. 2007, Godwin et al. 2008), cargo aircraft (Barnhart and Schneur 1996), airliners (Listes and Dekker 2005, Clark
2007), and automated guided vehicles (Hall et al. 2001, Vis et al. 2005), as well as rail freight cars (Papier and Thonemann 2008), diﬀerent kinds of containers (Turnquist and Jordan 1986, Imai and Rivera 2001), barges and tugboats (Richetta and Larson
1997), and more. Some, such as List et al. (2003), have proposed general approaches to the problem that do not specify a particular mode of transportation. Some researchers approach the problem from the standpoint of drivers (i.e., the number and type of vehicle operators to employ), for instance Sim˜o et al. (2008). Papers feaa turing substantial review and eﬀorts at classiﬁcation of literature in this area include
˙
Etezadi and Beasley (1983), Turnquist (1985), and Zak et al. (2008).
Key phrases in this current of research include “ﬂeet size” (or “ﬂeet sizing”), “ﬂeet mix,” “ﬂeet composition,” “ﬂeet size and mix,” “ﬂeet planning,” and “ﬂeet design.”
“Fleet composition,” the label that we adopt, has been inconsistently distinguished from “ﬂeet sizing” in the literature, but the following deﬁnitions are in accord with much published work. A ﬂeet composition problem is a decision problem where, for some set of vehicle types, we are to specify the number of vehicles of each type to include in the ﬂeet. A ﬂeet sizing problem or ﬂeet size problem is one where we are merely to specify the total number of vehicles in the ﬂeet. Fleet size and mix we take to be in the spirit of ﬂeet composition. The clearest example of a ﬂeet sizing

57

problem would be one where there is a single vehicle type under consideration, and in a mathematical sense such a problem is obviously a special case of ﬂeet composition.
Note that, for a given ﬂeet composition problem, it may well turn out that it is optimal to include no vehicles of a given type in the ﬂeet. (Our deﬁnitions may be contrasted with those oﬀered in Etezadi and Beasley 1983; cases where our classiﬁcations disagree
˙
with other authors’ self-classiﬁcations include Fagerholt 1999 and Zak et al. 2008.)
Many authors’ approaches to ﬂeet composition involve detailed modeling of the operational level, including the routing of vehicles. Recent projects of this kind include
Nahapetyan et al. (2007) for a major railroad company (involving rapid simulation of “trains, locomotives, terminals, and shops in an integrated framework” over many months of operation) and Sim˜o et al. (2008) for a major truckload carrier (simulata ing “at a high level of detail the movements of over 6,000 drivers”). There is also a fairly standard variant of the classic vehicle routing problem that is designed for ﬂeet composition, the ﬂeet size and mix vehicle routing problem. This model was introduced in Golden et al. (1984a), and work since then is surveyed in Renaud and
Boctor (2002). More recently, Dell’Amico et al. (2007) attack a generalization of this problem incorporating delivery time windows speciﬁc to each customer.
In our prototypical beverage distributor’s context, a detail-oriented, routing-based approach is a daunting proposition: the customer base is large; there are several vehicle types; the planning horizon is long; demand is uncertain, and exhibits seasonal as well as day-to-day variation; routes are not ﬁxed. Even though there are techniques aimed at lowering the computational burden in a routing-based approach (Etezadi and Beasley 1983, Golden et al. 1984b) or simplifying the spatial representation of demand (Klincewicz et al. 1990), the broad nature of the ﬁrm’s business concerns
(encompassing inventories and marketing as well as transportation of merchandise to customers) render simpler approaches especially attractive.
Our proposed model brings together two key elements that have appeared only

58

separately in the literature on ﬂeet composition. The ﬁrst element is the use of a two-stage stochastic programming formulation. List et al. (2003) and Couillard and
Martel (1990) are relatively recent examples of this type of model; the letter of Kirby
(1959) can be considered their ancestor. Kirby (1959) suggests, in essence, a classic newsvendor approach to the problem of ﬂeet sizing. He models demand by a random variable indicating the number of wagons (rail freight cars) required; wagons are hired when demand exceeds the ﬂeet size. Wyatt (1961) and Alsbury (1972) extend this approach and suggest ways of approaching the ﬂeet composition problem while keeping a one-dimensional characterization of demand. In our context, however, it not clear how to infer the individual utilization levels of the variously sized trucks given a scalar representation of demand. (Recall that our distributor’s demand is variable in terms of the average daily drop size as well as the total cubic volume, and that the customer base is heterogeneous.)
The second key element of our model is the description of a day’s demand by the total cubic volume to be delivered and the total number of customers to visit.
This perspective appears to originate in the ﬂeet composition approach of Eilon et al.
(1971a, pp. 234–236). Subsequent models suggested by Etezadi and Beasley (1983) feature similarly compact characterizations of demand. These two papers oﬀer deterministic mixed integer linear programming formulations that ask for a serial, dailylevel forecast of demand across the planning horizon. However, they do not explicitly recognize that the serial order of demand is immaterial under their assumptions.
Adopting a two-stage stochastic programming perspective, we open the door to an additional level of concision—capturing demand by a distribution function—while also accommodating uncertainty. We also simplify matters by dropping the requirement of integrality, which we believe to be justiﬁed considering factors such as the scale of our distributor’s demand and the strategic nature of the decision at hand.
In closing, we note that we are leaving aside discussion of approaches to ﬂeet com-

59

position and related problems based on certain continuous approximation methods
(Diana et al. 2006, Smilowitz and Daganzo 2007) and queueing theory (Papier and
˙
Thonemann 2008, Zak et al. 2008). Useful as these techniques may be to enable simple implementations in this problem domain, we are not aware of their use in the literature to address our prototypical distributor’s context. We leave elaboration of the usefulness of these techniques for our context as a direction for future research.

2.2.2 Capacity investment
This area of research is reviewed rather broadly in Van Mieghem (2003); we focus on a chain of literature originating with Eberly and Van Mieghem (1997). They introduce a model of investment in multiple resources in which the decisions concern the adjustment of resource levels across multiple periods in a stochastic environment. They argue that a particular type of control limit policy maximizes expected discounted proﬁt when the cost of adjusting each individual resource is a kinked piecewise linear convex function and the operating proﬁt function is concave in the resource levels
(given any realized state of the world).
Our model qualiﬁes as an instance of the Eberly and Van Mieghem (1997) model in which there is only one decision period, where the multiple resources at issue are the diﬀerent vehicle types under consideration for inclusion in the ﬂeet. In our beverage distributor’s context, business concerns beyond transportation distract attention from the problem of planning the composition of the ﬂeet multiple periods ahead, though future extension of our model to a multiperiod setting may nonetheless be useful.
According to the authors, the optimal control limit policy (in our case, the optimal number of vehicles of each type to purchase) may be deﬁned in terms of the gradient of the expected proﬁt function. However, the highly abstract nature of their resource processing model precludes detailed advice for our context. Under our assumptions, their characterization of the optimal policy essentially amounts to the usual ﬁrst-order

60

condition for gradient-based convex optimization, and they oﬀer no advice on how to calculate our gradient. Moreover, their focus on an abstract resource adjustment decision precludes detailed advice on modeling our resource processing mechanism.
(The only explicit multiperiod use of their framework in a ﬂeet-composition-related context appears to be a car rental ﬂeet sizing model in Angelus and Porteus 2002.)
Within the framework of this 1997 paper, Harrison and Van Mieghem (1999) study a model in which the operating proﬁt function is speciﬁed to be the solution of a linear program of the product mix type. This recourse program models production decisions taken on the basis of prior capacity investment decisions (i.e., available resources) and realized demand for multiple products. Given “kinked” linear resource adjustment cost functions, stationary parameters, and demand that is independent and identically distributed across periods, the problem collapses to a single-period problem in the same form. They classify this single-period problem, which is a twostage stochastic programming model, as a multidimensional newsvendor model. We believe that our model is not a special case of their model; neither is our model more general. (After developing additional notation, we will contrast our model with theirs in detail in Section 2.3.2.) For an example problem, Harrison and Van Mieghem
(1999) oﬀer a parametric analysis involving identiﬁcation of regions in the demand space throughout which there applies a constant optimal vector of shadow prices for capacity (degeneracy issues aside). They argue that the gradient of the expected operating proﬁt function is equal to the sum of these optimal shadow prices weighted by the probabilities of the associated regions (assuming a probability distribution of demand having no point mass). To facilitate the solution of our model by a gradientbased approach, we will introduce an algorithm that in eﬀect carries out this kind of decomposition of the demand space in our setting.
Van Mieghem and Rudi (2002) propose class of models called newsvendor networks. In their basic form, these models are single period capacity investment models

61

formulated as two-stage stochastic programs featuring random demand for multiple products. Their resource processing model (i.e., the second stage) is more general than that of Harrison and Van Mieghem (1999), but more speciﬁc than that of Eberly and
Van Mieghem (1997). Along with a capacity consumption matrix, the recourse linear program has a general input-output matrix translating input inventories (or stocks) into products. The authors show that this model captures several forms of production activities, including assembly, component commonality, input substitution or transshipment, resource ﬂexibility, and simultaneous resource requirements. For an example problem, they identify regions in the demand space involved in a characterization of the gradient of the expected operating proﬁt function as in Harrison and
Van Mieghem (1999). Beﬁtting the abstract nature of their model, they remark that particular instances may be substantially amenable to analytical solution, and they recommend optimization through simulation for other instances (i.e., estimating the gradient by solving the recourse linear program for a sample of demand vectors, as in
Kim 2006). At least in terms of its mathematical structure, our model qualiﬁes as a newsvendor network model. We show in Section 2.3.2 that our model (as we deﬁne it) can be transformed into the form of a newsvendor network; however, we argue that it is most natural to pose our recourse problem with two positive fractional covering constraints and some variables bounded above.
In the many published articles in this stream of capacity management research, one generally ﬁnds discussion of the structure of the decomposition of the demand space only for fairly speciﬁc cases. In particular, we are not aware of any substantial discussion of our type of recourse structure. This appears to be due largely to our perspective on demand for the service of transportation, highlighting two of its aggregate attributes that are simultaneously satisﬁed by a single activity. This perspective may be contrasted with a typical view of demand in terms of quantities of discrete products, in which a single activity produces a single product. (In our review of this

62

stream of capacity investment research, the only model we have found for ﬂeet composition is the model of Netessine et al. 2002, which also qualiﬁes as a newsvendor network. Their model is in a car rental context, and it does not share our perspective on demand.) Furthermore, our desire to abstract away from a speciﬁc number of vehicle types with ﬁxed characteristics invites a more generalized kind of analysis of a wide class of decompositions. By in eﬀect generating this kind of decomposition, our algorithm reduces the temptation to re-solve the recourse linear program from scratch many times as in the simulation optimization method recommended for general problems by Van Mieghem and Rudi (2002). Since our demand space is only two-dimensional, we are able to recommend straightforward numerical integration instead of simulation for calculating the desired gradient; the appropriate optimal dual vector (and an optimal basis matrix inverse) can be pre-calculated for each region of integration before the gradient search algorithm begins.
Finally, given the newsvendor-type models under discussion, it is warranted to relate our model to other descendents of the classic newsvendor model, which serves as a foundation for models in capacity planning as well as inventory control. In particular, newsvendor network models such as ours may be distinguished from the
“multi-product newsvendor” (or “multi-item newsvendor,” or “newsstand”) problems that appeared earlier in the literature. In these models, the focus is on dealing with complex ex-ante constraints (e.g. a budget constraint when selecting how many of each product to stock) while the ex-post constraints are trivial. For us, the main issue is a trivially constrained ex-ante capacity investment decision, which along with realized demand determines complex ex-post constraints on operations. Discussion of the basic newsvendor (or “newsboy”) problem and its many variants can be found in Porteus (1990) and Khouja (1999).

63

2.2.3 Optimization
Our proposed model falls under the general category of two-stage stochastic linear programs with ﬁxed and relatively complete recourse; a general reference on stochastic programming is Birge and Louveaux (1997). Our recourse program is a minimization problem with two positive fractional covering constraints, in which all coeﬃcients are assumed positive, with some (but not all) variables bounded above.
Our main contribution in the context of optimization is our algorithm in Section
2.4.2 generating a “deﬁnitive” collection of bases of our recourse problem. We deﬁne a deﬁnitive collection of bases in the context of the analysis of our recourse linear program, which has varying parameters in the right-hand side. Such a collection B must satisfy three conditions: Optimality (each basis in B must be optimal for those parameter values where it is feasible), Covering (for each possible parameter value, there must be a feasible basis in B), and Disjoint Interiors (for no pair of bases in B do the associated feasible regions have a common interior point). Having a deﬁnitive collection of bases of our model facilitates the rapid computation of the expected
(ﬁrst-stage or second-stage) cost and its gradient, so that one may then proceed with a standard gradient projection algorithm.
The usefulness of such collections as we generate, which goes beyond our present purpose of cost and gradient computation, is known to researchers in optimization.
The issue of degeneracy complicates matters of conceptualization, but it is clear that the same general idea comes up in many contexts. In stochastic programming, collections such as ours are intimately related to the technique of “full decomposition” of the space of right-hand sides discussed in Birge and Louveaux (1997, pp. 170–171).
“Bunching” techniques seek to employ in eﬀect a partial decomposition (Birge and
Louveaux 1997, pp. 169–174), and can be used to speed up the L-shaped method for solving stochastic linear programs with recourse (ibid., Chapter 5). These kinds of decompositions have been used to study the “distribution problem” of stochastic pro-

64

gramming, in which one seeks to understand the distribution of the optimal objective value of a (linear) program having random parameters with known joint distribution
(Foote 1980, Wets 1980). The same general kind of decomposition is sought in parametric linear programming (Jones 2005, from the perspective of optimal control). An early articulation of the theoretical underpinnings of such decompositions is the basis decomposition theorem of Walkup and Wets (1969).
As one would expect, algorithms producing these useful decompositions have been proposed. General algorithms are discussed in the studies of Foote (1980), Wets
(1980), and Jones (2005). (Dual simplex pivoting in particular is a useful algorithmic element in situations where the right-hand side varies.) Studies aimed at producing such decompositions for particular classes of structured linear programs include Wallace (1986) and Filippi and Romanin-Jacur (2002). We are not aware of any general or specialized algorithms in prior literature guaranteeing polynomial upper bounds on time complexity or the number of bases to be generated for our recourse model. Thus, it seems appropriate to oﬀer an algorithm tailored to our recourse structure and to identify its complexity. In Section 2.4.2, we oﬀer arguments for the correctness and eﬃciency of our algorithm, which identiﬁes O(n2 ) bases—out of exponentially many bases that can be deﬁned—in O(n3 ) time, given n vehicle types.
We expect that our conception of a “deﬁnitive” collection of bases can be widened past the context of the particular model we study here. While the facts giving rise to our conception are known, it seems that our concept is something of an implicit idea in the literature, not having a concise term.
In closing, we note that our recourse linear program is structurally related to the problem of set covering in combinatorial optimization, and also to continuous models studied in the context of approximation algorithms (e.g. Fleischer 2004).

65

2.3 Our model
In Section 2.3.1, we deﬁne our model and articulate points to consider in making an assessment of our model’s validity. In Section 2.3.2, we note that our model may be seen as a generalization of the classic newsvendor problem, and we show via a transformation that our model qualiﬁes as a newsvendor network.

2.3.1 Deﬁnition
A type i of vehicle under consideration for ownership for the duration of the planning horizon is distinguished by four parameters: a ﬁxed cost fi , a variable cost vi , a sites capacity si , and a cubic volume capacity ci . The ﬁxed cost is that cost incurred per working day due to including one vehicle of this type in the permanent ﬂeet through the planning horizon, whether or not the vehicle is used. This quantity takes into account elements such as the vehicle’s depreciation cost, taxes, ﬁxed components of drivers’ wages and insurance, the cost of parking, and the cost of maintenance performed at ﬁxed time intervals, all amortized equally across the working days in the planning horizon. The variable cost is that additional cost per working day incurred due to fully utilizing one owned vehicle of this type, as against leaving it unused for the day. This includes, for example, the cost of fuel, variable components of drivers’ wages, and the cost of maintenance performed at ﬁxed mileage intervals as well as non-routine maintenance. The cubic volume capacity is the greatest volume of merchandise that a vehicle of this type can reliably deliver in one working day. The sites capacity is the greatest number of customer sites that a vehicle of this type can reliably complete in one working day. Note that full utilization of a vehicle may entail multiple loads in a given day. More broadly, the parameters vi , si , ci are not intrinsic to the vehicle; they depend on factors such as the spatial distribution of customers relative to the distribution center, customers’ order sizes, and other factors.
A type i of vehicle available for hire on a daily (spot) basis during the planning

66

horizon is distinguished by three parameters: a variable cost vi , a cubic volume capacity ci , and a sites capacity si . Under our assumptions, what makes a hired or spot vehicle diﬀerent from an owned vehicle in our ﬂeet is that a third party (most likely a common carrier) assumes responsibility for the ﬁxed cost associated with long-term control of the vehicle. From the retail distributor’s perspective, then, the cost incurred when relying on a speciﬁc type of hired capacity is essentially a variable cost that depends on the degree to which the capacity is utilized. The deﬁnitions of vi , ci , and si given above still apply. The method of measuring vi in particular is likely to be diﬀerent in the context of a spot vehicle, however, since the separate components of this cost are probably hidden.
Let O be the set of vehicle types under consideration for ownership, and let H be the set of vehicle types available for hire on a spot basis. We assume that there are n1 vehicle types in O and n2 vehicle types in H, and we deﬁne n = n1 + n2 . (To clear up a possible confusion: if e.g. a particular make and model of vehicle is available both for ownership and for hire, this should be counted as two distinct vehicle “types” in the sense relevant here—due to the diﬀerent cost implications of the two means of access.) We allow a more compressed notation by deﬁning f ∈ Rn1 , v ∈ Rn , c ∈ Rn ,
+
+
+
and s ∈ Rn to be vectors consisting of the parameters introduced above.
+
Demand for transportation is characterized by two jointly distributed nonnegative random variables C and S, representing respectively the total cubic volume of merchandise to be delivered and the total number of distinct customer sites to be visited.
This distribution may be interpreted as describing demand on a working day picked uniformly at random from the planning horizon. (We elaborate on this interpretation below.) We deﬁne the two-dimensional demand D = (C, S).
We deﬁne the ﬂeet composition vector K ∈ Rn1 to indicate the number of vehicles
+
of each type we decide to include in our ﬂeet; selecting K is the ﬁrst-stage (or exante) decision to be made in our model. Once the day’s demand is known, we have

67

the recourse (or second-stage, or ex-post) decision concerning how best to utilize owned and hired capacity to fulﬁll demand. We deﬁne the utilization vector x ∈ Rn
+
indicating the number of vehicles of each type to utilize. Given a ﬂeet composition
K and realized demand D = (C, S), we deﬁne the (optimal) second-stage cost:

z(K, D) := min v x
s.t. c x ≥ C
(1)

sx≥S xi ≤ K i i ∈ O xi ≥ 0

i∈O∪H

Observe that we have deﬁned a continuous optimization problem. The constraint xi ≤ K for i ∈ O reﬂects simply that we cannot utilize more of these vehicles than we own. Hired vehicle types, by contrast, are taken to have unlimited availability.
The expected second-stage cost is

Z(K) := E[z(K, D)]

where the expectation is taken with respect to the bivariate probability distribution.
Finally, our formulation of the ﬁrst-stage decision is simply min f K + Z(K)
s.t. K ≥ 0 which we also treat as a continuous optimization problem. If demand is known but exhibits variation (said variation being captured by the bivariate probability distribution), this formulation is equivalent to a deterministic minimization of costs over the entire planning horizon; if demand is uncertain, this formulation minimizes expected costs over the planning horizon.

68

We elaborate on the interpretation of the model when demand is uncertain. Let t index the working days in the planning horizon, and suppose the number of working days in the horizon is T . Let the random vector D be distributed as the demand on a working day picked uniformly at random from the planning horizon. In this context, we abbreviate by P (t) the probability that day t is picked, which is by deﬁnition
T −1 . Let the random vector Dt be distributed as the demand on day t. Observe that the conditional distribution of D, given that day t was selected, is equal to the distribution of Dt . Now the expected total cost incurred over the planning horizon, as a function of the capacity vector K, is equal to:

T t=1 (f

K + E[z(K, Dt )])

by linearity of expectation. It is equivalent to minimize the function obtained by multiplying the above by the positive constant T −1 . The function so obtained is equal to: fK+ T t=1 E[z(K, D) | t]P (t)

which reduces to our objective function f K + E[z(K, D)] by appeal to the law of total expectation.
Throughout the rest of the chapter, we assume for the sake of simplicity that each of the parameters fi , vi , ci , and si is positive, and that n1 and n2 are positive. We also assume that the random variable D = (C, S) has a (known) joint probability density function with ﬁnite second moments.
We now articulate various propositions underlying our model that must be considered in making a full assessment of our model’s validity. A full defense of our model, considering further details of the application context, possible qualiﬁcations of certain propositions, mathematical properties of our model, and ways in which our model may be extended, is beyond the scope of this chapter. We do, however, oﬀer a

69

few comments on the propositions.
1. Our continuous, linear model of ﬁxed costs is valid.
2. Our continuous, linear model of resource processing costs, given realized demand, is valid.
Since in theory an optimal solution to our recourse problem might have only one demand constraint binding, we highlight the subtle proposition that we incur utilization cost for (optimal) “surplus production” as though demand matched the total capacities of the vehicles we utilized.
We comment on the ﬁrst two points. Regarding the general issue of the appropriateness of a continuous and linear modeling approach, we appeal to the large customer base of our prototypical beverage distributor, the strategic nature of the decision at hand, and the broad nature of the ﬁrm’s business concerns
(including inventories and marketing, for example, in addition to the transportation of merchandise to customers that is our focus in this study). In regard to our model more speciﬁcally, including the representation of demand by the total cubic volume and number of sites, we appeal to the intuitive considerations given in the introduction to this chapter, along with the distribution context described. Further research will be required to fully validate our proposed model.
3. The ﬂeet composition vector directly translates to the set of vehicles actually available for use day-to-day, independent of utilization decisions during the planning horizon.
4. Per-unit utilization costs and capacity parameters of owned vehicle types are constant throughout the planning horizon, and are independent of our ﬂeet composition and day-to-day utilization decisions.

70

5. Hired vehicle types may be utilized in (arbitrarily) great quantities; their per-unit utilization costs and capacity parameters are constant throughout the planning horizon, and are independent of our ﬂeet composition and day-to-day utilization decisions. 6. Deliveries are not delayed. To put it another way, there are no backlogs.
7. Demand is independent of the ﬂeet composition and day-to-day utilization decisions.
8. Variable costs incurred at opposite ends of the planning horizon need not be discounted diﬀerently.
9. Our parameters, and the distribution of demand, can be measured with a level of accuracy appropriate to the decision at hand, considering the eﬀort associated with this measurement.
In some situations (such as when the ﬂeet is to be leased rather than owned), contractual agreements might greatly simplify the process of parameter estimation.
For a published account of eﬀorts at estimating ﬁxed and variable cost parameters for three vehicle ﬂeets, see Eilon et al. (1971b), which informed the exposition of our cost parameters above. In our view, further studies of this nature would be valuable additions to the literature.

2.3.2 Relation to other newsvendor-type models
Having dealt with the relationship of our model to other newsvendor-type models to some extent in our literature review (speciﬁcally Section 2.2.2), and having introduced the notation of our model above, we are now in a position to compare and contrast the models under discussion with greater precision. For simplicity, we maintain our
71

assumption that each of our parameters fi , vi , ci , and si is positive, and that n1 and n2 are positive.
First, we illustrate a reduction of our model to the traditional newsvendor problem for a special case. Suppose that in our model there is a single vehicle type available for ownership, 1 ∈ O, and a single type that will be available for hire on a spot basis,
2 ∈ H. (Here, n1 = n2 = 1.) Furthermore, suppose that c1 = c2 and s1 = s2 . In this case, we can meaningfully view any given demand D = (C, S) in terms of the number of vehicles required, regardless of type. Let us deﬁne this transformed demand as
D∗ = max{C/c1 , S/s1 } = max{C/c2 , S/s2 }. The cost incurred by purchasing K vehicles, after demand is realized, may now be expressed as

(f1 + v1 )K + (−v1 )(K − D∗ )+ + v2 (D∗ − K)+

We recognize this as the form of a traditional newsvendor cost model with an ordering cost of (f1 + v1 ), a salvage value of v1 , and a lost-sales penalty of v2 . We assume that f1 + v1 < v2 , so there is some incentive to own vehicles. Accordingly, assuming a diﬀerentiable probability density function, the optimal K is the critical fractile K ∗ such that P (D∗ ≤ K ∗ ) = (v2 − f1 − v1 )/(v2 − v1 ). A similar reduction is possible if we have the more general condition c1 /s1 = c2 /s2 .
In the remainder of this section, we examine the relationship between our model and the multidimensional newsvendor model deﬁned by Harrison and Van Mieghem
(1999) as well as the newsvendor network model deﬁned by Van Mieghem and Rudi
(2002). We argue that our model qualiﬁes as a newsvendor network, but that it is most natural to use the formulation we introduced in Section 2.3.1. We also argue that our model is not a special case of the model deﬁned by Harrison and Van Mieghem
(1999), though their model is also a newsvendor network. We adjust the notation of
Van Mieghem and Rudi (2002) to avoid excessive conﬂict with our notation.

72

In the multidimensional newsvendor model of Harrison and Van Mieghem (1999), the second-stage cost is max{p x : Ax ≤ K, x ≤ D, x ≥ 0}, where K is the vector of chosen capacity levels and D is the vector of realized demand. In the more general newsvendor network model of Van Mieghem and Rudi (2002), the form of the recourse problem is:
¯
max (r − cA ) x − cP (D − RD x) − cH (S − RS x)
¯
s.t. RS x ≤ S
RD x ≤ D
Ax ≤ K x≥0 where RS , RD , and A are nonnegative matrices. (Though Harrison and Van Mieghem do not explicitly assume that A is nonnegative, it is reasonable to suppose that they
¯
did not intend for their model to be interpreted otherwise.) Here, S is a vector of
“input stocks” chosen along with K in the ﬁrst stage; each decision variable in the vector x corresponds to an “activity” that depletes input stocks and uses resources to produce demanded “outputs.” The ﬁrst-stage objective function to be maximized is the expected value of the optimal proﬁt deﬁned above, less the investment cost
¯
cS S + cK K. In terms of mathematical structure, the presence of “resources” adds nothing; observe that any constraint from the set Ax ≤ K could be subsumed into
¯
the set RS ≤ S with a corresponding “holding cost” (cH ) component equal to 0, moving the associated investment cost from cK to cS . (Van Mieghem and Rudi 2002 go on to extend their model, creating a “dynamic newsvendor network” in which the distinction between input stocks and resources is much more substantial.) We submit that the main question becomes whether our recourse problem can be phrased in the

73

form: max (r − cA ) x − cP (D − RD x) − cH (K − Ax)
s.t. RD x ≤ D
Ax ≤ K x≥0 where RD and A are nonnegative matrices. If we take the natural step of interpreting
D above as our two-dimensional demand D = (C, S), it is likewise natural to introduce an “activity” i for each of our vehicle types with corresponding decision variable xi and corresponding column (ci , si ) in RD . (Note that this structure, reﬂecting a vehicle’s ability to produce two “outputs” simultaneously, is not captured by the recourse problem of Harrison and Van Mieghem 1999.) Since we require that all demand be satisﬁed, but equality of utilized vehicle capacity and demand might not be optimal (or even feasible), we introduce for each vehicle type i additional “activities” with associated decision variables xc and xs ; the corresponding columns in RD are i i respectively (ci , 0) and (0, si ). For each owned vehicle type i, the corresponding row of A has 1 in the columns corresponding to xi , xc , and xs , and 0 elsewhere; K is i i again interpreted as the ﬂeet composition vector. We set cH = 0 and r = 0; we deﬁne the components of cA to be vi for those entries corresponding to xi , xc , and i xs ; and we deﬁne the entries of cP to be strictly greater than the least marginal cost i of fulﬁlling the corresponding dimension of demand by a spot vehicle type. Because the “penalty cost” is so severe, we are assured that both demand constraints will be binding at optimality—a spot vehicle type can always be used to pick up the slack while reducing the penalty. It can now be argued that any optimal solution to the newsvendor network recourse problem we have formulated can be translated into an optimal solution of the recourse problem in our model with the same cost (though the objective values have opposite signs). (To translate a solution from the newsvendor network, we set the utilization of vehicle type i in our model equal to xi + xc + xs i i

74

from the newsvendor network solution.) Of course, the vector f representing our linear capacity investment cost can be translated directly to cS or cK . We conclude that our model can be put into the form of a newsvendor network, though doing so seems to require a rather contrived mechanism.

2.4 An algorithm facilitating solution of our model
In Section 2.4.1, we ﬁrst reiterate our technical assumptions and note that our deterministic equivalent program is thereby assured of being a convex program, with the gradient deﬁned everywhere in the interior of the feasible set. We then deﬁne bases of our recourse program (as well as “optimal” bases) by reference to an alternative formulation of the recourse program with two surplus variables. We deﬁne the feasible regions of our bases in the space of possible demands, and we introduce notation for the optimal dual vectors associated with optimal bases. We deﬁne our notion of a
“deﬁnitive” collection of bases of our recourse program and elucidate the role of such a collection in a standard gradient search algorithm. In Section 2.4.2, we present our algorithm generating a deﬁnitive set of bases of our recourse program, and we argue for its correctness and polynomial complexity.

2.4.1 Preliminaries
We ﬁrst reiterate our technical assumptions, which we have imposed for simplicity.
Assumption 1. Each of the parameters fi , vi , ci , and si is positive, and n1 and n2 are positive.
Assumption 2. The nonnegative random variable D = (C, S) has a known joint probability density function with ﬁnite second moments.
By our ﬁrst assumption, our stochastic programming model has relatively complete recourse. Our optimization model, min f K + Z(K) subject to K ≥ 0, may
75

therefore be viewed as a deterministic equivalent program, pushing the stochasticity within Z(K) into the background of our attention; we do not need to add constraints on K to ensure that the second stage has an optimal solution for any possible demand vector. By our two assumptions together, we may invoke a result stated in Birge and
Louveaux (1997, Theorem 6, pp. 90–91) to conclude that our deterministic equivalent program is a convex program, with the gradient of f K + Z(K) deﬁned for all K in the interior of the feasible set.
The major work to be done involves construction of a special set of bases of our recourse problem, reformulated with two surplus variables xc and xs to produce equality constraints (rather than covering constraints). We identify a basis by partitioning the decision variables (formally, their indices) into three sets: (1) a set B comprised of two basic indices, (2) a set L of indices of variables held at their lower bounds (i.e., zero), and (3) a set U of indices of variables held at their upper bounds, chosen from
O. We describe a basis as optimal if (1) its associated solution is feasible (i.e., basic variables xi1 and xi2 are nonnegative and, where applicable, are bounded above by
Ki1 and Ki2 respectively), (2) the reduced cost vi is nonnegative for each i ∈ L, and
¯
(3) the reduced cost vi is nonpositive for each i ∈ U . (We deﬁne vi = vi − vB B −1 Ai ,
¯
¯ where B −1 is interpreted as the inverse of the square matrix composed of the two basic columns from the system of equalities in the formulation above, and Ai is the selected nonbasic column of that system. For the theory behind our deﬁnition of bases using variables with upper and lower bounds, see e.g. Bertsimas and Tsitsiklis
1997, especially the exercise on p. 135.) For each basis b we deﬁne the associated feasible regions in the space of possible demands:

Ωb = {(C, S, K) ∈ R2+n1 : b is feasible for (C, S, K)}
+
Ωb (K) = {(C, S) ∈ R2 : (C, S, K) ∈ Ωb }
+

76

A basis b that is optimal for some point in Ωb is optimal for every point in this region.
The dual of our recourse problem (as originally formulated) may be expressed as follows: max Cµ1 + Sµ2 + K λ
s.t. ci µ1 + si µ2 + λi ≤ vi i ∈ O ci µ1 + si µ2 ≤ vi

i∈H

µj ≥ 0

j ∈ {1, 2}

λi ≤ 0

(2)

i∈O

If b is optimal for Ωb , then a uniquely optimal dual vector λb obtains throughout the interior of Ωb . Whenever Ki = 0, the ith component of λb may be interpreted as the right partial derivative of the optimal cost with respect to Ki at demand points in the interior of Ωb (K).
We desire a set B of bases such that three key conditions are satisﬁed:
1. (Optimality) Each basis b ∈ B is optimal for Ωb .
2. (Covering)

b∈B

Ωb (K) = R2 for each K ≥ 0.
+

3. (Disjoint Interiors) For each K ≥ 0 and basis pair b1 , b2 ∈ B, the interiors of
Ωb1 (K) and Ωb2 (K) are disjoint.
We call a set satisfying these conditions a deﬁnitive collection of bases. The value, for our purposes, of a deﬁnitive set is due in large part to the following result. The result follows from Proposition 1 of Van Mieghem and Rudi (2002), but we provide our own proof.
Proposition. Let B be a deﬁnitive set of bases, suppose Assumptions 1 and 2 hold.
Then for each K ≥ 0, we have:

Z(K) =

λb P (Ωb (K)) b∈B 77

Whenever Ki = 0, the ith component of this sum should be interpreted as a right partial derivative.
Proof. Let K ≥ 0 be given. Consider a point D = (C, S) that lies in the interior of the region Ωb (K) for some b ∈ B. Supposing Ki > 0, let {δm : m ≥ 1} be a sequence of real numbers converging to zero; if Ki = 0, let the sequence be positive
−1
as well. Since b is an optimal basis, the sequence of elements δm [z(K + δm ei , D) −

z(K, D)] will eventually become constant and equal to its limit λb,i . (Here ei ∈ Rn1 is the unit vector with ith component equal to one, and λb,i is the ith component of λb .) Since z(·, ·) is Lipschitz continuous (in fact, piecewise linear), the family of functions gD (δ) = δ −1 [z(K + δei , D) − z(K, D)] is uniformly bounded. Because D has a probability density function, the set of boundary points of the regions Ωb (K) for all b ∈ B must have probability mass zero. Applying the bounded convergence theorem, ∂
E[z(K, D)]
∂Ki

∂
= E[ ∂Ki z(K, D)], where we understand

∂
∂Ki

as the right

∂ partial derivative if Ki = 0. Since B is deﬁnitive, we also have E[ ∂Ki z(K, D)] = b∈B λb,i P (Ωb (K)).

Having an algorithm for generating a deﬁnitive set of bases of our recourse problem, we may pursue a standard gradient projection method for optimization. (Provision for projection of the improving direction—and limitation of the maximum step size—are required merely due to our nonnegativity constraints on K.) Computation of the objective function and its gradient in this context may be facilitated as follows.
Before initiating the search algorithm, generate a deﬁnitive collection B using our algorithm. For each basis b ∈ B, store the corresponding basis matrix inverse B −1 and the vector λb along with the deﬁning sets B, L, and U . (The elements of λb are deﬁned for reference within the presentation of our algorithm below.) Now suppose in the course of our gradient search algorithm we are given K ≥ 0 and we require the gradient of the objective function. For each basis b ∈ B, we obtain P (Ωb (K)) through numerical integration of the density function over the appropriate region; the
78

desired gradient is then f +

b∈B

λb P (Ωb (K)), where the ith component is actually

the right partial derivative if Ki = 0. Finally, suppose we are given K ≥ 0 and we require the value of the objective function for our search algorithm. For this end, we perform numerical integration over the demand space to calculate the expectation of f K + z(K, D) with respect to the density function. In doing so, we evaluate the second-stage cost z(K, D) at a given point D = (C, S) using the sets B, L, and U and the stored matrix B −1 corresponding to a basis b ∈ B for which D ∈ Ωb (K).
We suggest performing this integration over the regions Ωb (K) in sequence, so that we always know immediately which basis parameters apply for a given demand point falling in the current region. For the purpose of numerical integration, we can reduce the (theoretically unbounded) demand space to a large bounded region, such that nearly all of the probability mass is captured. On determining the best way to perform the numerical integrations we suggest, one may ﬁnd some discussions and further references in the works by Foote (1980), Wets (1980), and Birge and Louveaux (1997, especially pp. 286–288). Due to the strategic nature of the decision of interest and the low dimension of the parameter space, we submit that sophisticated numerical integration methods may not be crucial.

2.4.2 Eﬃcient generation of “deﬁnitive” collections for our model
Below, we oﬀer our algorithm for generating a deﬁnitive set B. The algorithm takes the liberty of discarding from the formulation certain vehicle types that will not
(or need not) be present in an optimal ﬂeet composition. The algorithm is based on a representation of the variable-cost eﬃciency of a vehicle type by the vector
(ci /vi , si /vi ), which we will call φi . By Assumption 1, each of these vectors is welldeﬁned and has both components strictly positive.
Algorithm.
1. (Eliminate clearly uneconomical or unnecessary vehicle types.) For each vehicle
79

type i1 , determine whether there is a second vehicle type i2 such that φi1 ≤ φi2 , fi1 /ci1 ≥ fi2 /ci2 , and fi1 /si1 ≥ fi2 /si2 . If so, eliminate type i1 . In this context, spot vehicle types are understood to have fi = 0; ties may be broken arbitrarily.
(To fulﬁll a given quantity of demand with i2 instead of i1 , the variable cost and the prerequisite ﬁxed cost will both be lower. Once this step is complete, we are assured that no two eﬃciency vectors φi1 and φi2 are identical. We assume that n1 > 0 even after all possible eliminations have been performed; otherwise, the basic tradeoﬀ giving rise to our model does not apply.)
2. (Generate bases allowing for a surplus of sites capacity.) Order the vehicle types so that cik /vik ≥ cik+1 /vik+1 for all k ∈ {1, . . . , n−1}, where sik /vik > sik+1 /vik+1 if cik /vik = cik+1 /vik+1 . The types are now in decreasing order of variable-cost eﬃciency at handling cubic volume, with ties broken in favor of the type that is more eﬃcient at handling customer sites. For each from 1 to min{k : ik ∈ H}, generate the basis deﬁned by B = {i , s}, L = {ik : k > } ∪ {c}, and U = {ik : k < }.
The optimal dual vector we associate with any given basis generated here has µ1 = vi /ci , µ2 = 0, λi = 0 for all i ∈ O \ U , and λi = vi − ci µ1 for all i ∈ U .
3. (Generate bases allowing for a surplus of cubic volume capacity—this step is symmetrical with the preceding step.) Order the vehicle types so that sik /vik ≥ sik+1 /vik+1 for all k ∈ {1, . . . , n − 1}, where cik /vik > cik+1 /vik+1 if sik /vik = sik+1 /vik+1 . The types are now in decreasing order of variable-cost eﬃciency at handling customer sites, with ties broken in favor of the type that is more eﬃcient at handling cubic volume. For each

from 1 to min{k : ik ∈ H},

generate the basis deﬁned by B = {c, i }, L = {ik : k > } ∪ {s}, and U = {ik : k < }.
The optimal dual vector we associate with any given basis generated here has
80

µ1 = 0, µ2 = vi /si , λi = 0 for all i ∈ O \ U , and λi = vi − si µ2 for all i ∈ U .
4. (Generate bases featuring two basic vehicle types.) Perform the following for each pair of vehicle types {i1 , i2 }. If φi1 ≤ φi2 or φi1 ≥ φi2 , continue with the next pair to be considered. Otherwise, calculate the values µ1 and µ2 such that the line µ1 y1 + µ2 y2 = 1 in R2 intersects both φi1 and φi2 . Identify the set V
+
of vectors φi with i ∈ {i1 , i2 } such that µ1 (ci /vi ) + µ2 (si /vi ) > 1 or such that
/
φi is a convex combination of φi1 and φi2 . If V ∩ H is nonempty, continue with the next pair to be considered. Otherwise, generate the basis with B = {i1 , i2 },
U = V , and all remaining indices (including c and s) assigned to L.
The optimal dual vector we associate with any given basis generated here has λi = 0 for all i ∈ O \ U and λi = vi − ci µ1 − si µ2 for all i ∈ U .
Our main technical result is the following:
Theorem. Suppose Assumption 1 holds. Our algorithm generates a deﬁnitive set of no more than

n
2

+ 2n1 + 2 bases in O(n3 ) time.

Note that we are in eﬀect discarding an exponential number of bases, due to the structure of our recourse linear program. This theorem is proved by means of four lemmas. The ﬁrst lemma establishes the algorithm’s computational complexity. The other three lemmas establish the three key conditions deﬁning a deﬁnitive collection of bases of our model (given in Section 2.4.1 above).
Lemma 1. Suppose Assumption 1 holds. Our algorithm generates no more than n 2

+ 2n1 + 2 bases in O(n3 ) time.

Proof. We may quickly verify that Steps 1–3 of our algorithm require no more than
O(n2 ) time. A straightforward implementation of our algorithm requires O(n3 ) time due to Step 4, which may perform quadratically many linear-time operations. (For pairs of vectors φi , we may determine for each remaining vector which simply deﬁned
81

region it belongs to.) No bases are generated in Step 1. In Step 2, the greatest number of bases that may be generated is n1 + 1. For this bound to be reached, all owned vehicle types must have greater variable-cost eﬃciency at handling cubic volume than the best hired type by this measure. In Step 3, the focus is instead on customer sites, and similarly the greatest number of bases that may be generated is n1 + 1. In Step
4, we generate at most one basis for each pair of vehicle types, so an upper bound on the number of bases produced here is

n
2

.

Lemma 2. Suppose Assumption 1 holds. The bases generated by our algorithm satisfy the Optimality Condition.
Proof. Using our assumption that each ci and si is positive, we easily see that Ωb (1) has nonempty interior. Selecting (C, S) from this interior, the corresponding basic solution is primal nondegenerate, and it will suﬃce to show that this solution is also optimal. If b was generated in Step 2, then B = {i , s} for some vehicle type i , and we construct the dual solution with µ1 = vi /ci , µ2 = 0, λi = 0 for all i ∈ O \ U , and λi = vi −ci µ1 for all i ∈ U . We may easily verify that this dual solution is feasible and satisﬁes complementary slackness conditions with the primal solution corresponding to basis b, establishing optimality. If instead b was generated in Step 3, the situation is symmetrical with the previous case; here, B = {c, i } for some vehicle type i , and our dual solution has µ1 = 0, µ2 = vi /si , λi = 0 for all i ∈ O \ U , and λi = vi − si µ2 for all i ∈ U . Finally, if b was generated in Step 4, then B = {i1 , i2 } for some vehicle types i1 and i2 . We let µ1 and µ2 be those (unique) values calculated by our algorithm for this pair of vehicle types; we set λi = 0 for all i ∈ O \U and λi = vi −ci µ1 −si µ2 for all i ∈ U . Without much trouble, we may conﬁrm that this dual solution is feasible and the complementary slackness conditions hold.
Lemma 3. Suppose Assumption 1 holds. The bases generated by our algorithm satisfy the Covering Condition.
82

Proof. By positivity of n1 , n2 , and each ci and si , the second-stage program is feasible and admits an optimal basic solution for each (C, S, K) ∈ R2+n1 . By the theory of
+
linear programming, a basic solution to our recourse problem (2) has at most two variables that are not at their bounds. By our assumption that v is positive, an optimal basic solution will never have xc and xs away from their bounds. If (C, S, K) is such that an optimal basic solution exists with xs and xi away from their bounds for some vehicle type i , then complementary slackness dictates that µ1 = vi /ci , that vehicle types i with vi /ci < µ1 must be owned types with xi = Ki , and that vehicle types i with vi /ci > µ1 must have xi = 0. Here when we have multiple vehicle types with vi /ci = µ1 , optimality is maintained by utilizing them in decreasing order of variable-cost eﬃciency with respect to sites with the last type used designated basic; we also maintain optimality by ensuring for each type i with Ki = 0 that i ∈ U if vi /ci < µ1 and i ∈ L if vi /ci > µ1 , ending up with a basis we generated in Step 2. We may argue similarly that some basis generated in Step 3 is optimal when (C, S, K) is such that an optimal basic solution exists with xc and xi away from their bounds for some vehicle type i . Finally, if (C, S, K) is such that an optimal basic solution exists with xi1 and xi2 away from their bounds for the pair of vehicle types i1 and i2 , then complementary slackness dictates that µ1 and µ2 are as calculated in Step 4 for this basic pair, that vehicle types i with φi strictly above this line must be owned types with xi = Ki , and that vehicle types i with φi strictly below this line must have xi = 0. Here when we have more than two vehicle types with φi on this line, then we may arrive at a basic pair and corresponding optimal utilizations consistent with Step 4 by systematically decreasing the utilization of the “outermost” types on this line while increasing utilization of “inner” types on the line; we also maintain optimality by ensuring for each type i with Ki = 0 that i ∈ U if φi lies above the line and i ∈ L if φi lies below the line, ending up with a basis we generated in Step 4.
For each K ≥ 0, the foregoing cases establish for all but a set of Lebesgue measure

83

2 zero the covering of R+ by

b∈B

Ωb (K). Since this is a ﬁnite covering by closed sets,

it follows that this union in fact covers all of the demand space R2 .
+
Lemma 4. Suppose Assumption 1 holds. The bases generated by our algorithm satisfy the Disjoint Interiors Condition.
Proof. Let K ≥ 0 be given, and let (C, S) be an interior point of some region Ωb (K) for a basis b our algorithm has generated. If b was generated in Step 2, with B = {i , s} for some vehicle type i , by complementary slackness we must have µ1 = vi /ci > 0 and µ2 = 0 at dual optimality. If (C, S) is to be an interior point of Ωb∗ (K) for some other basis b∗ generated by our algorithm, these unique dual values imply that b∗ must have B ∗ = {i ∗ , s} with vi ∗ /ci ∗ = vi /ci . Without loss of generality, we may assume that type i comes before type i ∗ in the ordering of Step 2. But now any point in the interior of Ωb (K) involves strictly less than

i∈U

ci Ki + ci Ki units of

cubic volume, while any point in the interior of Ωb∗ (K) involves strictly more than this quantity of cubic volume since (U ∪ {i }) ⊆ U ∗ by construction. We may argue similarly for the case where b was generated in Step 3, where B = {c, i } for some vehicle type i and the uniquely optimal dual values are µ1 = 0 and µ2 = vi /si > 0.
To conclude, we consider the case where b was generated in Step 4, with B = {i1 , i2 } for some vehicle types i1 and i2 . Here, complementary slackness implies that the uniquely optimal dual values of µ1 and µ2 are as calculated for this basic pair in Step
4. If another basis b∗ generated in Step 4 has B = {i3 , i4 } and the interior points of
Ωb∗ (K) share the optimal values of µ1 and µ2 , then we must have φi1 , φi2 , φi3 , and φi4 colinear. To support the desired conclusion that (C, S) cannot be an interior point of Ωb∗ (K), we describe the geometric structure of the regions corresponding to all bases generated in Step 4 using these values of µ1 and µ2 . Given µ1 and µ2 , we may without loss of generality assume that the set of vectors falling on the critical line of
Step 4 is {φ1 , φ2 , . . . , φm } with these vectors appearing on the line in the given order from left to right. For more than one basis to be generated, we must have m > 2.
84

The “canonical” case involves {1, . . . , m} ⊆ O with Ki > 0 for i ∈ {1, . . . , m}, in which m
2

bases are generated; the corresponding regions are parallelograms arranged

adjacent to each other in a kind of modiﬁed binomial tree structure. Here, the “top level” region corresponding to B = {1, m} shares sides with the two regions in the next lower level corresponding to B = {1, m − 1} and B = {2, m}. These two regions share sides with the three regions in the next lower level (if one exists), and so on for (m − 1) levels total. At the lowest level, pairs of regions with B = {i, i + 1} and
B = {i + 1, i + 2} for i ∈ {1, . . . , m − 2} share a side; these adjacency relationships are in eﬀect added on to a binomial tree structure. Non-canonical cases may be seen as limiting cases, in which opposite sides of certain parallelograms take zero length
(when some i ∈ {1, . . . , m} have Ki = 0) or inﬁnite length (when some i ∈ {1, . . . , m} are in H).

2.5 Conclusion
In this chapter, we have introduced a relatively simple and fast solution approach for the ﬂeet composition problem faced by a retail distribution ﬁrm, focusing on the context of a major beverage distributor. In support of this overarching goal, we introduced a ﬂeet composition model with a novel combination of characteristics, and we performed technical analysis facilitating solution of the model.
We close by indicating a few logical avenues for further research. Our model’s validity could be examined more deeply in a study providing details of its practical implementation in a real-life trial. Such an investigation should clarify the degree to which certain extensions of our approach are necessary and feasible. It should also yield insights regarding the best methods of computing solutions to our model.
Another possible investigation would further illuminate the connection of the idea of a “deﬁnitive” collection of bases to the wider contexts of stochastic and parametric programming. 85

2.6 References
Alsbury, P. 1972. The vehicle ﬂeet mix. International Journal of Physical
Distribution 2(3) 123–125.
Angelus, A., E. L. Porteus. 2002. Simultaneous capacity and production management of short-life-cycle, produce-to-stock goods under stochastic demand. Management Science 48(3) 399–413.
Ball, M. O., B. L. Golden, A. A. Assad, L. D. Bodin. 1983. Planning for truck ﬂeet size in the presence of a common-carrier option. Decision Sciences 14(1)
103–120.
Barnhart, C., R. R. Schneur. 1996. Air network design for express shipment service.
Operations Research 44(6) 852–863.
Bertsimas, D., J. N. Tsitsiklis. 1997. Introduction to Linear Optimization. Athena
Scientiﬁc, Belmont, MA.
Birge, J. R., F. Louveaux. 1997. Introduction to Stochastic Programming. Springer,
New York.
Ceder, A. 2005. Estimation of ﬂeet size for variable bus schedules. Transportation
Research Record 1903 3–10.
Clark, P. 2007. Buying the Big Jets: Fleet Planning for Airlines, 2nd ed. Ashgate,
Aldershot, UK.
Couillard, J., A. Martel. 1990. Vehicle ﬂeet planning in the road transportation industry. IEEE Transactions on Engineering Management 37(1) 31–36.
Crary, M., L. K. Nozick, L. R. Whitaker. 2002. Sizing the U.S. destroyer ﬂeet.
European Journal of Operational Research 136 680–695.
Dantzig, G. B., D. R. Fulkerson. 1954. Minimizing the number of tankers to meet a ﬁxed schedule. Naval Research Logistics Quarterly 1 217–222.
Dell’Amico, M., M. Monaci, C. Pagani, D. Vigo. 2007. Heuristic approaches for the ﬂeet size and mix vehicle routing problem with time windows. Transportation
Science 41(4) 516–526.
Diana, M., M. M. Dessouky, N. Xia. 2006. A model for the ﬂeet sizing of demand responsive transportation services with time windows. Transportation Research
Part B 40 651–666
Eberly, J. C., J. A. Van Mieghem. 1997. Multi-factor dynamic investment under uncertainty. Journal of Economic Theory 75 345–387.

86

Eilon, S., C. D. T. Watson-Gandy, N. Christoﬁdes. 1971a. Distribution
Management: Mathematical Modelling and Practical Analysis. Charles Griﬃn &
Company Limited, London.
Eilon, S., C. D. T. Watson-Gandy, A. Heilbron. 1971b. A vehicle ﬂeet costs more.
International Journal of Physical Distribution 1 126–132.
Etezadi, T., J. E. Beasley. 1983. Vehicle ﬂeet composition. Journal of the
Operational Research Society 34 87–91.
Fagerholt, K. 1999. Optimal ﬂeet design in a ship routing problem. International
Transactions in Operational Research 6 453–464.
Filippi, C., G. Romanin-Jacur. 2002. Multiparametric demand transportation problem. European Journal of Operational Research 139 206–219.
Fleischer, L. 2004. A fast approximation scheme for fractional covering problems with variable upper bounds. Proceedings of the Fifteenth Annual ACM-SIAM
Symposium on Discrete Algorithms, New Orleans, LA. SIAM, Philadelphia, PA,
1001–1010.
Foote, B. L. 1980. A discussion of the properties of a basic simplex algorithm for generating the decision regions of Bereanu. M. A. H. Dempster, ed. Stochastic
Programming, Academic Press, London, 207–222.
Godwin, T., R. Gopalan, T. T. Narendran. 2008. Tactical locomotive ﬂeet sizing for freight train operations. Transportation Research Part E 44 440–454.
Golden, B., A. Assad, L. Levy, E. Gheysens. 1984a. The ﬂeet size and mix vehicle routing problem. Computers & Operations Research 11(1) 49–66.
Golden, B. L., F. J. Gheysens, A. A. Assad. 1984b. On solving the vehicle ﬂeet size and mix problem. J. P. Brans, ed. Operational Research ’84. North-Holland,
Amsterdam, 721–734.
Gould, J. 1969. The size and composition of a road transport ﬂeet. Operational
Research Quarterly 20 81–92.
Hall, N. G., C. Sriskandarajah, T. Ganesharajah. 2001. Operational decisions in
AGV-served ﬂowshop loops: Fleet sizing and decomposition. Annals of
Operations Research 107 189–209.
Harrison, J. M., J. A. Van Mieghem. 1999. Multi-resource investment strategies:
Operational hedging under demand uncertainty. European Journal of
Operational Research 113 17–29.
Imai, A., F. Rivera. 2001. Strategic ﬂeet size planning for maritime refrigerated containers. Maritime Policy and Management 28(4) 361–374.

87

Jones, C. N. 2005. Polyhedral Tools for Control. Ph.D. dissertation, Control Group,
Department of Engineering, University of Cambridge, Cambridge, UK.
Khouja, M. 1999. The single-period (news-vendor) problem: Literature review and suggestions for future research. Omega 27 537–553.
Kim, S. 2006. Gradient-based simulation optimization. L. F. Perrone, F. P.
Wieland, J. Liu, B. G. Lawson, D. M. Nicol, R. M. Fujimoto, eds. Proceedings of the 2006 Winter Simulation Conference, 159–167.
Kirby, D. 1959. Is your ﬂeet the right size? Operational Research Quarterly 10 252.
Klincewicz, J. G., H. Luss, M. G. Pilcher. 1990. Fleet size planning when outside carrier services are available. Transportation Science 24(3) 169–182.
List, G. F., B. W. Wood, L. K. Nozick, M. A. Turnquist, D. A. Jones, E. A.
Kjeldgaard, C. R. Lawton. 2003. Robust optimization for ﬂeet planning under uncertainty. Transportation Research Part E 39 209–227.
Listes, O., R. Dekker. 2005. A scenario aggregation-based approach for determining a robust airline ﬂeet composition for dynamic capacity allocation.
Transportation Science 39(3) 367–382.
Nahapetyan, A., R. K. Ahuja, F. Z. Sargut, A. John, K. Somani. 2007. A simulation/optimization framework for locomotive planning. C. Liebchen, R. K.
Ahuja, J. A. Mesa, eds. ATMOS 2007 – 7th Workshop on Algorithmic
Approaches for Transportation Modeling, Optimization, and Systems, IBFI,
Dagstuhl, Germany, 259–276.
Netessine, S., G. Dobson, R. A. Shumsky. 2002. Flexible service capacity: Optimal investment and the impact of demand correlation. Operations Research 50(2)
375–388.
Papier, F., U. W. Thonemann. 2008. Queuing models for sizing and structuring rental ﬂeets. Transportation Science 42(3) 302–317.
Porteus, E. L. 1990. Stochastic inventory theory. D. P. Heyman, M. J. Sobel, eds.
Stochastic Models, Elsevier Science, Amsterdam, 605–652.
Renaud, J., F. F. Boctor. 2002. A sweep-based algorithm for the ﬂeet size and mix vehicle routing problem. European Journal of Operational Research 140
618–628.
Richetta, O., R. C. Larson. 1997. Modeling the increased complexity of New York
City’s refuse marine transport system. Transportation Science 31(3) 272–293.
Sigurd, M. M., N. L. Ulstein, B. Nygreen, D. M. Ryan. 2005. Ship scheduling with recurring visits and visit separation requirements. G. Desaulniers, J. Desrosiers,
M. M. Solomon, eds. Column Generation, Springer, New York, 225–245.
88

Sim˜o, H. P., J. Day, A. P. George, T. Giﬀord, J. Nienow, W. B. Powell. 2008. An a approximate dynamic programming algorithm for large-scale ﬂeet management:
A case application. Transportation Science, published online before print August
15, 2008.
Smilowitz, K. R., C. F. Daganzo. 2007. Continuum approximation techniques for the design of integrated package distribution systems. Networks 50(3) 183–196.
Turnquist, M. A. 1985. Research opportunities in transportation system characteristics and operations. Transportation Research Part A 19(5–6) 357–366.
Van Mieghem, J. A., N. Rudi. 2002. Newsvendor networks: Inventory management and capacity investment with discretionary activities. Manufacturing & Service
Operations Management 4(4) 313–335.
Van Mieghem, J. A. 2003. Capacity management, investment, and hedging: Review and recent developments. Manufacturing & Service Operations Management
5(4) 269–302.
Vis, I. F. A., R. B. M. de Koster, M. W. P. Savelsbergh. 2005. Minimum vehicle ﬂeet size under time-window constraints at a container terminal. Transportation
Science 39(2) 249–260.
Walkup, D. W., R. J.-B. Wets. 1969. Lifting projections of convex polyhedra.
Paciﬁc Journal of Mathematics 28(2) 465–475.
Wallace, S. W. 1986. Decomposing the requirement space of a transportation problem into polyhedral cones. Mathematical Programming Study 28 29–47.
Wets, R. J.-B. 1980. The distribution problem and its relation to other problems in stochastic programming. M. A. H. Dempster, ed. Stochastic Programming,
Academic Press, London, 245–262.
Woods, D. G., F. C. Harris. 1979. Truck ﬂeet composition for concrete distribution.
International Journal of Physical Distribution and Materials Management 10
3–14.
Wu, P., J. C. Hartman, G. R. Wilson. 2005. An integrated model and solution approach for ﬂeet sizing with heterogeneous assets. Transportation Science
39(1) 87–103.
Wyatt, J. K. 1961. Optimal ﬂeet size. Operational Research Quarterly 12 186–187.
˙
Zak, J., A. Redmer, P. Sawicki. 2008. Multiple objective optimization of the ﬂeet sizing problem for road freight transportation. Journal of Advanced
Transportation 42(4) 379–427.

89

Inventory Management

Similar Documents

Inventory Management

Inventory Management

Inventory Management

Inventory Management

Chemical Inventory Management

Inventory Management and Control

Inventory Management of Costco

Inventory Management System

Inventory Management

Inventory Management

Inventory Management

Inventory Management

Inventory Management

Inventory Management

Inventory Management

Popular Essays