Open access

Stochastic Control and Improvement of Statistical Decisions in Revenue Optimization Systems

Written By

Nicholas A. Nechval and Maris Purgailis

Published: 28 November 2012

DOI: 10.5772/46153

From the Edited Volume

Stochastic Modeling and Control

Edited by Ivan Ganchev Ivanov

Chapter metrics overview

1,907 Chapter Downloads

View Full Metrics

1. Introduction

A large number of problems in production planning and scheduling, location, transportation, finance, and engineering design require that decisions be made in the presence of uncertainty. From the very beginning of the application of optimization to these problems, it was recognized that analysts of natural and technological systems are almost always confronted with uncertainty. Uncertainty, for instance, governs the prices of fuels, the availability of electricity, and the demand for chemicals. A key difficulty in optimization under uncertainty is in dealing with an uncertainty space that is huge and frequently leads to very large-scale optimization models. Decision-making under uncertainty is often further complicated by the presence of integer decision variables to model logical and other discrete decisions in a multi-period or multi-stage setting.

Approaches to optimization under uncertainty have followed a variety of modeling philosophies, including expectation minimization, minimization of deviations from goals, minimization of maximum costs, and optimization over soft constraints. The main approaches to optimization under uncertainty are stochastic programming (recourse models, robust stochastic programming, and probabilistic models), fuzzy programming (flexible and possibilistic programming), and stochastic dynamic programming.

This paper is devoted to improvement of statistical decisions in revenue management systems. Revenue optimization – or revenue management as it is also called – is a relatively new field currently receiving much attention of researchers and practitioners. It focuses on how a firm should set and update pricing and product availability decisions across its various selling channels in order to maximize its profitability. The most familiar example probably comes from the airline industry, where tickets for the same flight may be sold at many different fares throughout the booking horizon depending on product restrictions as well as the remaining time until departure and the number of unsold seats. Since the tickets for a flight have to be sold before the plane takes off, the product is perishable and cannot be stored for future use. The use of the above strategies has transformed the transportation and hospitality industries, and has become increasingly important in retail, telecommunications, entertainment, financial services, health care and manufacturing. In parallel, pricing and revenue optimization has become a rapidly expanding practice in consulting services, and a growing area of software and IT development, where the revenue optimization systems are tightly integrated in the existing Supply Chain Management solutions.

Most stochastic models, which are used in revenue optimization systems, are developed under the assumptions that the parameter values of the models are known with certainty. When these models are applied to solve real-world problems, the parameters are estimated and then treated as if they were the true values. The risk associated with using estimates rather than the true parameters is called estimation risk and is often ignored. When data are limited and/or unreliable, estimation risk may be significant, and failure to incorporate it into the model design may lead to serious errors. Its explicit consideration is important since decision rules which are optimal in the absence of uncertainty need not even be approximately optimal in the presence of such uncertainty.

In this paper, we consider the cases where it is known that the underlying probability distributions belong to a parameterized family of distributions. However, unlike in the Bayesian approach, we do not assume any prior knowledge on the parameter values. The primary purpose of the paper is to introduce the idea of embedding of sample statistics (say, sufficient statistics or maximum likelihood estimators) in a performance index of revenue optimization problem. In this case, we find the optimal stochastic control policy directly. We demonstrate the fact that the traditional approach, which separates the estimation and the optimization tasks in revenue optimization systems (i.e., when we use the estimates as if they were the true parameters) can often lead to pure results. It will be noted that the optimal statistical decision rules depend on data availability.

For constructing the improved statistical decisions, a new technique of invariant embedding of sample statistics in a performance index is proposed (Nechval et al., 1999; 2004; 2008; 2010a; 2010b; 2010c; 2010d; 2010e; 2011a; 2011b). This technique represents a simple and computationally attractive statistical method based on the constructive use of the invariance principle in mathematical statistics. Unlike the Bayesian approach, an invariant embedding technique is independent of the choice of priors, i.e., subjectivity of investigator is eliminated from the problem. The technique allows one to eliminate unknown parameters from the problem and to find the improved invariant statistical decision rules, which has smaller risk than any of the well-known traditional statistical decision rules.

In order to obtain improved statistical decisions for revenue management under parametric uncertainty, it can be considered the three prediction situations: “new-sample” prediction, “within-sample” prediction, and “new-within-sample” prediction. For the new-sample prediction situation, the data from a past sample are used to make predictions on a future unit or sample of units from the same process or population. For the within-sample prediction situation, the problem is to predict future events in a sample or process based on early data from that sample or process. For the new-within-sample prediction situation, the problem is to predict future events in a sample or process based on early data from that sample or process as well as on a past data sample from the same process or population. Some mathematical preliminaries for the within-sample prediction situation are given below.

Advertisement

2. Mathematical preliminaries for the within-sample prediction situation

Theorem 1. Let X1 ... Xk be the first k ordered observations (order statistics) in a sample of size m from a continuous distribution with some probability density function f (x) and distribution function F (x), where is a parameter (in general, vector). Then the joint probability density function of X1 ... Xk and the lth order statistics Xl (1 k < l m) is given by

fθ(x1, ..., xk, xl)=fθ(x1, ..., xk)gθ(xl|xk),E1

where

fθ(x1,..., xk)
=m!(mk)!i=1kfθ(xi)[1Fθ(xk)]mk,E2
gθ(xl|xk)=(mk)!(lk1)!(ml)![Fθ(xl)Fθ(xk)1Fθ(xk)]lk1[1Fθ(xl)Fθ(xk)1Fθ(xk)]mlfθ(xl)1Fθ(xk)=(mk)!(lk1)!(ml)!j=0lk1(lk1j)(1)j[1Fθ(xl)1Fθ(xk)]ml+jfθ(xl)1Fθ(xk)=(mk)!(lk1)!(ml)!j=0ml(mlj)(1)j[Fθ(xl)Fθ(xk)1Fθ(xk)]lk1+jfθ(xl)1Fθ(xk)E3

represents the conditional probability density function of Xl given Xk=xk.

Proof. The joint density of X1 ... Xk and Xl is given by

fθ(x1, ..., xk, xl)=m!(lk1)!(ml)!i=1kfθ(xi)[Fθ(xl)Fθ(xk)]lk1fθ(xl)[1Fθ(xl)]ml=fθ(x1, ..., xk)gθ(xl|xk).E4

It follows from (4) that

fθ(xl|x1, ..., xk)=fθ(x1, ..., xk, xl)fθ(x1, ..., xk)=gθ(xl|xk),E5

i.e., the conditional distribution of Xl, given Xi = xi for all i = 1,…, k, is the same as the conditional distribution of Xl, given only Xk = xk. This ends the proof. □

Corollary 1.1. The conditional probability distribution function of Xl given Xk=xk is

Pθ{Xlxl|Xk=xk}=1(mk)!(lk1)!(ml)!×j=0lk1(lk1j)(1)jml+1+j[1Fθ(xl)1Fθ(xk)]ml+1+j=(mk)!(lk1)!(ml)!j=0ml(mlj)(1)jlk+j[Fθ(xl)Fθ(xk)1Fθ(xk)]lk+j.E6

Corollary 1.2. If l = k + 1,

gθ(xk+1|xk)=(mk)[1Fθ(xk+1)1Fθ(xk)]mk1fθ(xk+1)1Fθ(xk)=(mk)j=0mk1(mk1j)(1)j[Fθ(xk+1)Fθ(xk)1Fθ(xk)]jfθ(xk+1)1Fθ(xk),1km1,E7
and
Pθ{Xk+1xk+1|Xk=xk}=1[1Fθ(xk+1)1Fθ(xk)]mk=(mk)j=0mk1(mk1j)(1)j1+j[Fθ(xk+1)Fθ(xk)1Fθ(xk)]1+j,1km1.E8

Corollary 1.3. If l = m,

gθ(xm|xk)=(mk)j=0mk1(mk1j)(1)j×[1Fθ(xm)1Fθ(xk)]jfθ(xm)1Fθ(xk)=(mk)[Fθ(xm)Fθ(xk)1Fθ(xk)]mk1fθ(xm)1Fθ(xk),1km1,E9
and
Pθ{Xmxm|Xk=xk}=1(mk)j=0mk1(mk1j)(-1)j1+j[1-Fθ(xm)1-Fθ(xk)]1+j=[Fθ(xm)Fθ(xk)1Fθ(xk)]mk, 1km1.E10

2.1. Exponential distribution

In order to use the results of Theorem 1, we consider, for illustration, the exponential distribution with the probability density function

fθ(x)=1θexp(xθ), x0, θ>0,E11

and the probability distribution function

Fθ(x)=1exp(xθ), x0, θ>0.E12

Theorem 2. Let X1 ... Xk be the first k ordered observations (order statistics) in a sample of size m from the exponential distribution (11). Then the conditional probability density function of the lth order statistics Xl (1 k < l m) given Xk = xk is

gθ(xl|xk)=1Β(lk,(ml+1)j=0lk1(lk1j)(1)j1θexp((ml+1+j)(xlxk)θ)=1Β(lk,(ml+1)j=0ml(mlj)(1)j1θ[1exp(xlxkθ)]lk1+jexp(xlxkθ), xlxk,E13

and the conditional probability distribution function of the lth order statistics Xl given Xk = xk is

Pθ{Xlxl|Xk=xk}=11Β(lk,(ml+1)j=0lk1(lk1j)×(1)jml+1+jexp((ml+1+j)(xlxk)θ) =1Β(lk,(ml+1)j=0ml(mlj)(1)jlk+j[1exp(xlxkθ)]lk+j.E14

Proof. It follows from (3) and (6), respectively. □

Corollary 2.1. If l = k + 1,

gθ(xk+1|xk)=(mk)1θexp((mk)(xk+1xk)θ)=(mk)j=0mk1(mk1j)(1)j1θ[1exp(xk+1xkθ)]jexp(xk+1xkθ), xk+1xk, 1km1,E15
and
Pθ{Xk+1xk+1|Xk=xk}=1exp((mk)(xk+1xk)θ)=(mk)j=0mk1(mk1j)(1)j1+j[1exp(xk+1xkθ)]1+j,1km1.E16

Corollary 2.2. If l = m,

gθ(xm|xk)=(mk)×j=0mk1(mk1j)(1)j1θexp((1+j)(xmxk)θ)=(mk)1θ[1exp(xmxkθ)]mk1exp(xmxkθ),xmxk, 1km1,E17
and
Pθ{Xmxm|Xk=xk}=1(mk)j=0mk1(mk1j)(1)j1+jexp((1+j)(xmxk)θ)=[1exp(xmxkθ)]mk, 1km1.E18

Theorem 3. Let X1 ... Xk be the first k ordered observations (order statistics) in a sample of size m from the exponential distribution (11), where the parameter is unknown. Then the predictive probability density function of the lth order statistics Xl (1 k < l m) is given by

gsk(xl|xk)=kΒ(lk,(ml+1)j=0lk1(lk1j)(1)j×[1+(ml+1+j)xlxksk](k+1)1sk, xlxk,E19

where

Sk=i=1kXi+(mk)XkE20

is the sufficient statistic for , and the predictive probability distribution function of the lth order statistics Xl is given by

Psk{Xlxl|Xk=xk}=11Β(lk,(ml+1)j=0lk1(lk1j)(1)jml+1+j×[1+(ml+1+j)xlxksk]k.E21

Proof. Using the technique of invariant embedding (Nechval et al., 1999; 2004; 2008; 2010a; 2010b; 2010c; 2010d; 2010e; 2011a; 2011b), we reduce (13) to

gθ(xl|xk)=1Β(lk,(ml+1)j=0lk1(lk1j)(1)j×vexp((ml+1+j)(xlxk)skv)1sk=gsk(xl|xk,v),E22

where

V=Sk/θE23

is the pivotal quantity, the probability density function of which is given by

f(v)=1Γ(k)vk1exp(v), v0.E24
Then
gsk(xl|xk)=E{gsk(xl|xk,v)}=0gsk(xl|xk,v)f(v)dv=gsk(xl|xk).E25

This ends the proof. □

Corollary 3.1. If l = k + 1,

gsk(xk+1|xk)=k(mk)[1+(mk)xk+1xksk](k+1)1sk,xk+1xk, 1km1,E26
and
Psk{Xk+1xk+1|Xk=xk}=1[1+(mk)xk+1xksk]k,1km1.E27

Corollary 3.2. If l = m,

gsk(xm|xk)=k(mk)j=0mk1(mk1j)(1)j[1+(1+j)xmxksk](k+1)1sk,xmxk, 1km1,E28
and
Psk{Xmxm|Xk=xk}=1(mk)j=0mk1(mk1j)(1)j1+j[1+(1+j)xmxksk]k=j=0mk(mkj)(1)j[1+jxmxksk]k,1km1.E29

2.2. Cumulative customer demand

The primary purpose of this paper is to introduce the idea of cumulative customer demand in inventory control problems to deal with the order statistics from the underlying distribution. It allows one to use the above results to improve statistical decisions for inventory control problems under parametric uncertainty.

Assumptions. The customer demand at the ith period represents a random variable Yi, i{1, …, m}. It is assumed (for the cumulative customer demand) that the random variables

X1=Y1, ..., Xk=i=kYi, ..., Xl=i=1lYi, ..., Xm=i=1mYiE30

represent the order statistics (X1 … Xm) from the exponential distribution (11).

Inferences. For the above case, we have the following inferences.

Conditional probability density function of Yk+1, k{1, …, m 1}, is given by

gθ(yk+1|k)=mkθexp((mk)yk+1θ), yk+10;E31

Conditional probability distribution function of Yk+1, k{1, …, m 1}, is given by

Gθ{yk+1|k}=1exp((mk)yk+1θ) .E32

Conditional probability density function of Zm=i=k+1mYiis given by

gθ(zm|k)=(mk)1θ[1exp(zmθ)]mk1exp(zmθ),zm0, 1km1;E33

Conditional probability distribution function of Zm=i=k+1mYiis given by

Gθ(zm|k)=[1exp(zmθ)]mk, 1km1.E34

Predictive probability density function of Yk+1, k{1, …, m 1}, is given by

gsk(yk+1|k)=k(mk)[1+(mk)yk+1sk](k+1)1sk,yk+10;E35

Predictive probability distribution function of Yk+1, k{1, …, m 1}, is given by

Gsk(yk+1|k)=1[1+(mk)yk+1sk]k.E36

Predictive probability density function of Zm is given by

gsk(zm|k)=k(mk)j=0mk1(mk1j)(1)j[1+(1+j)zmsk](k+1)1sk,zm0, 1km1;E37

Predictive probability distribution function of Zm is given by

Gsk(zm|k)=j=0mk(mkj)(1)j[1+jzmsk]k,1km1.E38
Advertisement

3. Stochastic inventory control problem

Most of the inventory management literature assumes that demand distributions are specified explicitly. However, in many practical situations, the true demand distributions are not known, and the only information available may be a time-series of historic demand data. When the demand distribution is unknown, one may either use a parametric approach (where it is assumed that the demand distribution belongs to a parametric family of distributions) or a non-parametric approach (where no assumption regarding the parametric form of the unknown demand distribution is made).

Under the parametric approach, one may choose to estimate the unknown parameters or choose a prior distribution for the unknown parameters and apply the Bayesian approach to incorporating the demand data available. Scarf (1959) and Karlin (1960) consider a Bayesian framework for the unknown demand distribution. Specifically, assuming that the demand distribution belongs to the family of exponential distributions, the demand process is characterized by the prior distribution on the unknown parameter. Further extension of this approach is presented in (Azoury, 1985). Application of the Bayesian approach to the censored demand case is given in (Ding et al., 2002; Lariviere & Porteus, 1999). Parameter estimation is first considered in (Conrad, 1976) and recent developments are reported in (Agrawal & Smith, 1996; Nahmias, 1994). Liyanage & Shanthikumar (2005) propose the concept of operational statistics and apply it to a single period newsvendor inventory control problem.

This section deals with inventory items that are in stock during a single time period. At the end of the period, leftover units, if any, are disposed of, as in fashion items. Two models are considered. The difference between the two models is whether or not a setup cost is incurred for placing an order. The symbols used in the development of the models include:

c = setup cost per order,

c1= holding cost per held unit during the period,

c2= penalty cost per shortage unit during the period,

g (yk+1|k) = conditional probability density function of customer demand, Yk+1, during the (k+1)th period,

= parameter (in general, vector),

u = order quantity,

q = inventory on hand before an order is placed.

3.1. No-setup model (Newsvendor model)

This model is known in the literature as the newsvendor model (the original classical name is the newsboy model). It deals with stocking and selling newspapers and periodicals. The assumptions of the model are:

  1. Demand occurs instantaneously at the start of the period immediately after the order is received.

  2. No setup cost is incurred.

The model determines the optimal value of u that minimizes the sum of the expected holding and shortage costs. Given optimal u (= u*), the inventory policy calls for ordering u* q if q < u*; otherwise, no order is placed.

If Yk+1 u, the quantity u Yk+1 is held during the (k+1)th period. Otherwise, a shortage amount Yk+1 u will result if Yk+1> u. Thus, the cost per the (k+1)th period is

C(u)={c1uYk+1θ if Yk+1u,c2Yk+1uθ if Yk+1>u.E39

The expected cost for the (k+1)th period, E{C(u)}, is expressed as

Eθ{C(u)}=1θ(c10u(uyk+1)gθ(yk+1|k)dyk+1+c2u(yk+1u)gθ(yk+1|k)dyk+1).E40

The functionEθ{C(u)}can be shown to be convex in u, thus having a unique minimum. Taking the first derivative of Eθ{C(u)} with respect to u and equating it to zero, we get

1θ(c10ugθ(yk+1|k)dyk+1c2ugθ(yk+1|k)dyk+1)=0E41
or
c1Pθ{Yk+1u}c2(1Pθ{Yk+1u})=0E42
or
Pθ{Yk+1u}=c2c1+c2.E43

It follows from (31), (32), (40), and (43) that

u=θmkln(1+c2c1)E44
and
Eθ{C(u)}=1θ(c2Eθ{Yk+1}(c1+c2)0uyk+1gθ(yk+1|k)dyk+1)=c1mkln(1+c2c1).E45

Parametric uncertainty. Consider the case when the parameter is unknown. To find the best invariant decision ruleuBI, we use the invariant embedding technique (Nechval et al., 1999; 2004; 2008; 2010a; 2010b; 2010c; 2010d; 2010e; 2011a; 2011b) to transform (39) to the form, which is depended only on the pivotal quantities V, V1, and the ancillary factor . In statistics, a pivotal quantity or pivot is a function of observations and unobservable parameters whose probability distribution does not depend on unknown parameters. Note that a pivotal quantity need not be a statistic—the function and its value can depend on parameters of the model, but its distribution must not. If it is a statistic, then it is known as an ancillary statistic.

Transformation of C(u) based on the pivotal quantities V, V1 is given by

C(1)(η )={c1(ηVV1) if V1ηV,c2(V1ηV) if V1>ηV,E46

where

η=uSk,E47
V1=Yk+1θ~g(v1|k)=(mk)exp[(mk)v1], v10.E48

Then E{C(1)()} is expressed as

E{C(1)(η)}=0(c10ηv(η vv1)g(v1|k)dv1+c2ηv(v1ηv)g(v1|k)dv1)f(v)dv.E49

The function E{C(1)()} can be shown to be convex in , thus having a unique minimum. Taking the first derivative of E{C(1)()} with respect to and equating it to zero, we get

0v(c10ηvg(v1|k)dv1c2ηvg(v1|k)dv1)f(v)dv=0E50
or
0vP(V1ηv)f(v)dv0vf(v)dv=c2c1+c2.E51

It follows from (47), (49), and (51) that the optimum value of is given by

η=1mk[(1+c2c1)1/(k+1)1],E52

the best invariant decision rule is

uBI=ηSk=Skmk[(1+c2c1)1/(k+1)1],E53

and the expected cost, if we use uBI, is given by

Eθ{C(uBI)}=c1(k+1)mk[(1+c2c1)1/(k+1)1]=E{C(1)(η)}.E54

It will be noted that, on the other hand, the invariant embedding technique (Nechval et al., 1999; 2004; 2008; 2010a; 2010b; 2010c; 2010d; 2010e; 2011a; 2011b) allows one to transform equation (40) as follows:

Eθ{C(u)}=1θ(c10u(uyk+1)gθ(yk+1|k)dyk+1+c2u(yk+1u)gθ(yk+1|k)dyk+1)=1sk(c10u(uyk+1)v2(mk)exp(v(mk)yk+1sk)1skdyk+1+c2u(yk+1u)v2(mk)exp(v(mk)yk+1sk)1skdyk+1).E55

Then it follows from (55) that

E{Eθ{(C(u)}}=0Eθ{C(u)}f(v)dv=Esk{C(1)(u)},E56

where

Esk{C(1)(u)}=ksk(c10u(uyk+1)gsk(yk+1|k)dyk+1+c2u(yk+1u)gsk(yk+1|k)dyk+1)E57

represents the expected prediction cost for the (k+1)th period. It follows from (57) that the cost per the (k+1)th period is reduced to

C(2)(u)={c1uYk+1sk/k if Yk+1u,c2Yk+1usk/k if Yk+1>u,E58

and the predictive probability density function of Yk+1 (compatible with (40)) is given by

gsk(yk+1|k)=(k+1)(mk)[1+(mk)yk+1sk](k+2)1sk, yk+10.E59

Minimizing the expected prediction cost for the (k+1)th period,

Esk{C(2)(u)}=ksk(c10u(uyk+1)gsk(yk+1|k)dyk+1+c2u(yk+1u)gsk(yk+1|k)dyk+1),E60

with respect to u, we obtain uBI immediately, and

Esk{C(2)(uBI)}=c1(k+1)mk[(1+c2c1)1/(k+1)1].E61

It should be remarked that the cost per the (k+1)th period, C(2)(u),can also be transformed to

C(3)(η)={c1k(uskYk+1sk) if Yk+1skuskc2k(Yk+1skusk) if Yk+1sk>usk={c1k(ηW) if Wηc2k(Wη) if W>η,E62

where the probability density function of the ancillary statistic W (compatible with (40)) is given by

gsk(w|k)=(k+1)(mk)[1+(mk)w](k+2),w0.E63

Then the best invariant decision rule uBI=ηSk,where ηminimizes

E{C(3)(η)}=k(c10η(ηw)g(w|k)dw+c2η(wη)g(w|k)dw).E64

Comparison of statistical decision rules. For comparison, consider the maximum likelihood decision rule that may be obtained from (44),

uML=θmkln(1+c2c1)=ηjMLSkE65
,

where θ=Sk/k is the maximum likelihood estimator of ,

ηML=1mkln(1+c2c1)1/k.E66

Since uBIand uML belong to the same class,

C={u:u=ηSk},E67

it follows from the above that uML is inadmissible in relation touBI. If, say, k=1 andc2/c1=100, we have that

Rel.eff.{uML, uBI,q}= Eθ{C(uBI)}/Eθ{C(uML)}=0.838.E68

Thus, in this case, the use of uBIleads to a reduction in the expected cost of about 16.2 % as compared withuML. The absolute expected cost will be proportional to and may be considerable.

3.2. Setup model (s-S policy)

The present model differs from the one in Section 3.1 in that a setup cost c is incurred. Using the same notation, the total expected cost per the (k+1)th period is

Eθ{C¯(u)}=c+Eθ{C(u)}=c+1θ(c10u(uyk+1)gθ(yk+1|k)dyk+1+c2u(yk+1u)gθ(yk+1|k)dyk+1).E69

As shown in Section 3.1, the optimum value u* must satisfy (43). Because c is constant, the minimum value of Eθ{C¯(u)} must also occur at u*. In Fig.1,

Figure 1.

(sS) optimal ordering policy in a single-period model with setup cost

Eθ{C(s)}=Eθ{C¯(S)}=c+Eθ{C(S)}, s<S.E70

The equation yields another value s1 (> S), which is discarded.

Assume that q is the amount on hand before an order is placed. How much should be ordered? This question is answered under three conditions: 1) q < s; 2) s q S; 3) q > S.

Case 1 (q < s). Because q is already on hand, its equivalent cost is given by Eθ{C(q)}.If any additional amount u q (u > q) is ordered, the corresponding cost given u isEθ{C¯(u)}, which includes the setup cost c. From Fig. 1, we have

minu > qEθ{C¯(u)}=Eθ{C¯(S)}<Eθ{C(q)}.E71

Thus, the optimal inventory policy in this case is to order S q units.

Case 2 (s q S). From Fig. 1, we have

Eθ{C(q)}minu > qEθ{C¯(u)}=Eθ{C¯(S)}.E72

Thus, it is not advantageous to order in this case and u* = q.

Case 3 (q > S). From Fig. 1, we have for u > q,

Eθ{C(q)}<Eθ{C¯(u)}.E73

This condition indicates that, as in case (2), is not advantageous to place an order that is, u* = q.

The optimal inventory policy, frequently referred to as the s S policy, is summarized as

If x<S, order Sx,If xs, do not order.E74

The optimality of the s S policy is guaranteed because the associated cost function is convex.

Parametric uncertainty. In the case when the parameter is unknown, the total expected prediction cost for the (k+1)th period,

Esk{C¯(1)(u)}=c+Esk{C(1)(u)}=c+ksk(c10u(uyk+1)gsk(yk+1|k)dyk+1+c2u(yk+1u)gsk(yk+1|k)dyk+1),E75

is considered in the same manner as above.

Advertisement

4. Airline revenue management problem

The process of revenue management has become extremely important within the airline industry. It consists of setting fares, setting overbooking limits, and controlling seat inventory to increase revenues. It has allowed the airlines to survive deregulation by allowing them to respond to competitors' deep discount fares on a rational basis.

An airline, typically, offers tickets for many origin–destination itineraries in various fare classes. These fare classes not only include business and economy class, which are settled in separate parts of the plane, but also include fare classes for which the difference in fares is explained by different conditions regarding for example cancellation options or overnight stay arrangements. Therefore the seats on a flight are products, which can be offered to different customer segments for different prices. Since the tickets for a flight have to be sold before the plane takes off, the product is perishable and cannot be stored for future use. The same is true for most other service industries, such as hotels, hospitals and schools.

4.1. Airline seat inventory control

At the heart of airline revenue management lies the airline seat inventory control problem. It is common practice for airlines to sell a pool of identical seats at different prices according to different booking classes to improve revenues in a very competitive market. In other words, airlines sell the same seat at different prices according to different types of travelers (first class, business and economy) and other conditions. The question then arises whether to offer seats at a relatively low price at a given time with a given number of seats remaining or to wait for the possible arrival of a higher paying customer. Assigning seats in the same compartment to different fare classes of passengers in order to improve revenues is a major problem of airline seat inventory control. This problem has been considered in numerous papers. For details, the reader is referred to a review of yield management, as well as perishable asset revenue management, by Weatherford et al. (1993), and a review of relevant mathematical models by Belobaba (1987).

The problem of finding an optimal airline seat inventory control policy for multi-leg flight with multiple fare classes, which allows one to maximize the expected profit of this flight, is one of the most difficult problems of air transport logistics. On the one hand, one must have reasonable assurance that the requirements of customers for reservations will be met under most circumstances. On the other hand, one is confronted with the limitation of the capacity of the cabin, as well as with a host of other less important constraints. The problem is normally solved by the application of judgment based on past experience. The question arises whether or not it is possible to construct a simple mathematical theory of the above problem, which will allow one better to use the available data based upon airline statistics. Two models (dynamic model and static one) of airline data may be considered. In the dynamic model, the problem is formulated as a sequential decision process. In this case, an optimal dynamic reservation policy is used at each stage prior to departure time for multi-leg flights with several classes of passenger service. The essence of determining the optimal dynamic reservation policy is maximization of the expected gain of the flight, which is carried out at each stage prior to departure time using the available data. The term (dynamic reservation policy) is used in this paper to mean a decision rule, based on the available data, for determining whether to accept a given reservation request made at a particular time for some future date. An optimal static reservation policy is based on the static model. The models proposed here contain a simple and natural treatment of the airline reservation process and may be appropriate in practice.

4.2. Expected marginal seat revenue model (EMSR)

Different approaches were developed for solving the airline seat inventory control problem. The most important and widely used model – EMSR – was originally proposed by Littlewood (1972). To explain the basic ideas of the Littlewood model, we will consider the seat allocation problem on a nonstop flight with two airfares. We denote by U the number of seats in the aircraft, by uL the number of seats reserved for passengers with a lower fare and by p the probability that a passenger who would pay the higher fare cannot find a seat because it was sold to a passenger paying a lower fare. A rise in variable uL means a rise in probability p. A rise in the number of seats for passengers with the lower fare, i.e. a rise in variable p, decreases the number of seats for passengers with the higher fare, i.e., variable U – uL decreases. A reduction in variable U – uL increases the probability that a passenger paying the higher fare cannot find a vacant seat on their desired flight because it has been sold to a passenger with a lower fare. Probability p is given by

p=UuLfθ(x)dx,E76

where the fθ(x)is the underlying probability density function for the total number of requests X of passengers who would pay the higher fare, is the parameter (in general, vector). Littlewood (1972) proposed the following way to determine the reservation level uL to which reservations are accepted for passengers with the lower fare. We denote by c1 the revenue from passengers with the lower fare and by c2 the revenue from passengers with the higher fare. Let uL seats be reserved for low fare passengers. The revenue per lower fare seat is c1. Expected revenue from a potential high fare passenger is c2p. Passengers with lower fares should be accepted until

c1c2p,E77

i.e.,

pc1c2.E78

Reservation level uL is determined by solving the following equality:

Pr{ X>h}=γ,E79

where

h=UuL,E80
γ=c1c2.E81

Richter (1982) gave a marginal analysis, which proved that (77) gives an optimal allocation (assuming certain continuity conditions). Optimal policies for more than two classes have been presented independently by Curry (1990), Wollmer (1992), Brumelle & McGill (1993), and Nechval et al. (2006).

Parametric uncertainty. In order to solve (79) under parametric uncertainty, it can be used, for example, the following results.

Theorem 4. Let X1 ... Xr be the first r ordered past observations from a previous sample of size n from the two-parameter Weibull distribution

f(x|β,δ)=δβ(xβ)δ1exp[(xβ)δ] (x>0),E82

where both distribution parameters (β – scale, - shape) are positive. Then a lower one-sided conditional prediction limit h on the lth order statistic Xlf in a set of m future ordered observations also from the distribution (82) is given by

h=zh1/δβ,E83

where zh satisfies the equation

Pr{Xlf>h|z(r)}=Pr{Xlf>zh1/δβ|z(r)}=[0v2r2i=1rziv2k=0l1(mk) j=0k(kj)(1)j((mk+j)zhv2+i=1rziv2+(nr)zrv2)rdv2]0v2r2i=1rziv2(i=1rziv2+(nr)zrv2)rdv2=γ,E84
z(r)=(z1, z2, ..., zr)E85
,
Zi=(Xiβ)δ, i=1, ..., r,E86

are ancillary statistics, any r2 of which form a functionally independent set (for notational convenience we include all of z1, …, zr in (85); zr-1 and zr can be expressed as function of z1, …, zr-2 only), βand δ are the maximum likelihood estimators of and based on the first r ordered past observations (X1 … Xr) from a sample of size n from the two-parameter Weibull distribution, which can be found from solution of

β=([i=1rxiδ+(nr)xrδ]/r)1/δ,E87
and
δ=[(i=1rxiδlnxi+(nr)xrδlnxr)(i=1rxiδ+(nr)xrδ)11ri=1rlnxi]1,E88

(Observe that an upper one-sided conditional prediction limit h on the lth order statistic Xlf from a set of m future ordered observations X1fXmfmay be obtained from a lower one-sided conditional prediction limit by replacing by 1.)

Proof. The joint density of X1 ... Xr is given by

f(x1, ..., xr|β,δ)=n!(nr)!i=1rδβ(xiβ)δ1exp((xiβ)δ)exp((nr)(xrβ)δ).E89
Letβ, δbe the maximum likelihood estimates of , , respectively, based on X1 … Xr from a complete sample of size n, and let
V1=(ββ)δ, V2=δδ, and Zi=(Xiβ)δ, i=1, ..., r,E90

Parameters and in (90) are scale and shape parameters, respectively, and it is well known that if β and δ are estimates of and , possessing certain invariance properties, then V1 and V2 are the pivotal quantities whose distributions depend only on n. Most, if not all, proposed estimates of and possess the necessary properties; these include the maximum likelihood estimates and various linear estimates.

Using (90) and the invariant embedding technique (Nechval et al., 1999; 2004; 2008; 2010a; 2010b; 2010c; 2010d; 2010e; 2011a; 2011b), we then find in a straightforward manner, that the joint density of V1, V2, conditional on fixedz=(z1, z2, ..., zr), is

f(v1,v2|z(r))=ϑ(z(r))v2r2i=1rziv2v1r1exp(v1[i=1rziv2+(nr)zrv2]),v1(0,),  v2(0,),E91

where

ϑ(z(r))=[0Γ(r)v2r2i=1rziv2(i=1rziv2+(nr)zrv2)rdv2]1,E92

is the normalizing constant. Writing

Pr{Xlf>h|β,δ}=k=0l1(mk) [F(h|β,δ)]k[1F(h|β,δ)]mk=k=0l1(mk)[1exp((hβ)δ)]k[exp((hβ)δ)]mk=k=0l1(mk) j=0k(kj)(1)jexp[v1(mk+j)zhv2]=Pr{Xlf>h|v1,v2},E93

where

zh=(hβ)δ,E94

we have from (91) and (93) that

Pr{Xlf>h|z(r)}=00Pr{Xlf>h|v1,v2}f(v1,v2|z(r))dv1dv2.E95

Now v1 can be integrated out of (95) in a straightforward way to give

Pr{Xlf>h|z(r)}=[0v2r2i=1rziv2k=0l1(mk) j=0k(kj)(1)j((mk+j)(hβ)δv2+i=1rziv2+(nr)zrv2)rdv2]0v2r2i=1rziv2(i=1rziv2+(nr)zrv2)rdv2.E96

This completes the proof. □

Remark 1. If l=m=1, then the result of Theorem 4 can be used to construct the static policy of airline seat inventory control.

Theorem 5. Let X1 ... Xk be the first k ordered early observations from a sample of size m from the two-parameter Weibull distribution (82). Then a lower one-sided conditional prediction limit h on the lth order statistic Xl (l > k) in the same sample is given by

h=wh1/δXk,E97

where wh satisfies the equation

Pr{Xl>h|z(k)}=Pr{(Xl/Xk)δ>(h/Xk)δ| z(k)}=Pr{W>wh|z(k)}=[0v2k2i=1kziv2j=0lk1(lk1j)(1)lk1jmkj((mkj)(whzk)v2+jzkv2+i=1kziv2)kdv2]×[0v2k2i=1kziv2j=0lk1(lk1j)(1)lk1jmkj((mk)zkv2+i=1kziv2)kdv2]1=γ,E98
z(k)=(z1, ...zk),E99
Zi=(Yiβ)δ, i=1, ..., k,E100
wh=(hYk)δ,E101

where β and δare the maximum likelihood estimates of and based on the first k ordered past observations X1 ... Xk from a sample of size m from the two-parameter Weibull distribution (82), which can be found from solution of

β=([i=1kxiδ+(mk)xkδ]/k)1/δ,E102
and
δ=[(i=1kxiδlnxi+(mk)xkδlnxk)(i=1kxiδ+(mk)xkδ)11ki=1klnxi]1,E103

(Observe that an upper one-sided conditional prediction limit h on the lth order statistic Xl based on the first k ordered early-failure observations X1 ... Xk, where l > k, from the same sample may be obtained from a lower one-sided conditional prediction limit by replacing by 1)

Proof. The joint density of X1 ... Xk and Xl is given by

f(x1, ..., xk,xl|β,δ)=m!(lk1)!(ml)!i=1kδβ(xiβ)δ1exp((xiβ)δ)×[exp((xkβ)δ)exp((xlβ)δ)]lk1δβ(xlβ)δ1exp((xlβ)δ)×exp((ml)(xlβ)δ)E104
.Letβ, δbe the maximum likelihood estimates of , , respectively, based on X1 ... Xk from a complete sample of size m, and let
V1=(ββ)δ,V2=δδ,W=(YlYk)δ,E105
andZi=(Yi/β)δ,i=1(1)k. Using the invariant embedding technique (Nechval et al., 1999; 2004; 2008; 2010a; 2010b; 2010c; 2010d; 2010e; 2011a; 2011b), we then find in a straightforward manner, that the joint density of V1, V2, W, conditional on fixedz(k)=(z1, ..., zk), is
f(v1,v2,w|z(k))=ϑ(z(k))v2k1i=1kziv2(wzk)v2v1kj=0lk1(lk1j)(1)lk1j×exp[v1((mkj)(wzk)v2+jzkv2+i=1kziv2)],v1(0,),  v2(0,),  w(1,),E106

where

ϑ(z(k))=[0v2k2i=1kziv2j=0lk1(lk1j)(1)lk1jΓ(k)mkj((mk)zkv2+i=1kziv2)kdv2]1E107

is the normalizing constant. Using (106), we have that

Pr{Yl>h|z(k)}=Pr{(YlYk)δ>(hYk)δ| z(k)}=Pr{W>wh|z(k)}=0wh0f(v1,v2,w|z(k))dv1dwdv2=[0v2k2i=1kziv2j=0lk1(lk1j)(1)lk1jmkj((mkj)(whzk)v2+jzkv2+i=1kziv2)kdv2]×[0v2k2i=1kziv2j=0lk1(lk1j)(1)lk1jmkj((mk)zkv2+i=1kziv2)kdv2]1,E108

and the proof is complete. □

Remark 2. If l=m, then the result of Theorem 5 can be used to construct the dynamic policy of airline seat inventory control.

Advertisement

5. Conclusions and directions for future research

In this paper, we develop a new frequentist approach to improve predictive statistical decisions for revenue optimization problems under parametric uncertainty of the underlying distributions for the customer demand. Frequentist probability interpretations of the methods considered are clear. Bayesian methods are not considered here. We note, however, that, although subjective Bayesian prediction has a clear personal probability interpretation, it is not generally clear how this should be applied to non-personal prediction or decisions. Objective Bayesian methods, on the other hand, do not have clear probability interpretations in finite samples.

For constructing the improved statistical decisions, a new technique of invariant embedding of sample statistics in a performance index is proposed. This technique represents a simple and computationally attractive statistical method based on the constructive use of the invariance principle in mathematical statistics. The method used is that of the invariant embedding of sample statistics in a performance index in order to form pivotal quantities, which make it possible to eliminate unknown parameters (i.e., parametric uncertainty) from the problem. It is especially efficient when we deal with asymmetric performance indexes and small data samples

More work is needed, however, to obtain improved or optimal decision rules for the problems of unconstrained and constrained optimization under parameter uncertainty when: (i) the observations are from general continuous exponential families of distributions, (ii) the observations are from discrete exponential families of distributions, (iii) some of the observations are from continuous exponential families of distributions and some from discrete exponential families of distributions, (iv) the observations are from multiparametric or multidimensional distributions, (v) the observations are from truncated distributions, (vi) the observations are censored, (vii) the censored observations are from truncated distributions.

Advertisement

Acknowledgement

This research was supported in part by Grant No. 06.1936, Grant No. 07.2036, Grant No. 09.1014, and Grant No. 09.1544 from the Latvian Council of Science and the National Institute of Mathematics and Informatics of Latvia.

References

  1. 1. AgrawalN.SmithS. A. 1996 Estimating Negative Binomial Demand for Retail Inventory Management with Unobservable Lost Sales. Naval Res. Logist., 43 839 861
  2. 2. AzouryK. S. 1985 Bayes Solution to Dynamic Inventory Models under Unknown Demand Distribution. Management Sci., 31 1150 1160
  3. 3. BelobabaP. P. 1987 Survey Paper: Airline Yield Management- an Overview of Seat Inventory Control. Transportation Science, 21 6373
  4. 4. BrumelleS. L.Mc GillJ. I. 1993 Airline Seat Allocation with Multiple Nested Fare Classes. Operations Research, 41 127137
  5. 5. ConradS. A. 1976 Sales Data and the Estimation of Demand. Oper. Res. Quart., 27 123 127
  6. 6. CurryR. E. 1990 Optimal Airline Seat Allocation with Fare Classes Nested by Origins and Destination. Transportation Science, 24 193204
  7. 7. DingX.PutermanM. L.BisiA. 2002 The Censored Newsvendor and the Optimal Acquisition of Information. Oper. Res., 50 517 527
  8. 8. KarlinS. 1960 Dynamic Inventory Policy with Varying Stochastic Demands. Management Sci., 6 231 258
  9. 9. LariviereM. A.PorteusE. L. 1999 Stalking Information: Bayesian Inventory Management with Unobserved Lost Sales. Management Sci., 45 346 363
  10. 10. LittlewoodK. 1972 Forecasting and Control of Passenger Bookings. In: Proceedings of the Airline Group International Federation of Operational Research Societies, 12 95117
  11. 11. LiyanageL. H.ShanthikumarJ. G. 2005 A Practical Inventory Control Policy Using Operational Statistics. Oper. Res. Lett., 33 341 348
  12. 12. NahmiasS. 1994 Demand Estimation in Lost Sales Inventory Systems. Naval Res. Logist., 41 739 757
  13. 13. NechvalN. A.PurgailisM. 2010e Improved State Estimation of Stochastic Systems via a New Technique of Invariant Embedding. In: Stochastic Control, Chris Myers (ed.), 167 193. Publisher: Sciyo, Croatia, India
  14. 14. NechvalN. A.VasermanisE. K. 2004 Improved Decisions in Statistics. SIA “Izglitibas soli”, Riga
  15. 15. NechvalN. A.NechvalK. N. 1999 Invariant Embedding Technique and Its Statistical Applications. In: Conference Volume of Contributed Papers of the 52nd Session of the International Statistical Institute, Finland, Helsinki: ISIInternational Statistical Institute,Availqable from http://www.stat.fi/isi99/procee-dings/arkisto/varasto/ nech0902.pdf
  16. 16. NechvalN. A.BerzinsG.PurgailisM.NechvalK. N. 2008 Improved Estimation of State of Stochastic Systems via Invariant Embedding Technique. WSEAS Transactions on Mathematics, 7 141 159
  17. 17. NechvalN. A.NechvalK. N.PurgailisM. 2011b Statistical Inferences for Future Outcomes with Applications to Maintenance and Reliability. In: Lecture Notes in Engineering and Computer Science: Proceedings of the World Congress on Engineering (WCE 2011), 865871 . London, U.K.
  18. 18. NechvalN. A.PurgailisM.BerzinsG.CiksteK.KrastsJ.NechvalK. N. 2010a Invariant Embedding Technique and Its Applications for Improvement or Optimization of Statistical Decisions. In: Analytical and Stochastic Modeling Techniques and Applications, Al-Begain, K., Fiems, D., Knottenbelt, W. (eds.),. LNCS, 6148 306 320. Springer, Heidelberg
  19. 19. NechvalN. A.PurgailisM.CiksteK.NechvalK. N. 2010d Planning Inspections of Fatigued Aircraft Structures via Damage Tolerance Approach. In: Lecture Notes in Engineering and Computer Science: Proceedings of the World Congress on Engineering (WCE 2010), 2470 2475. London, U.K.
  20. 20. NechvalN. A.PurgailisM.CiksteK.BerzinsG.NechvalK. N. 2010c Optimization of Statistical Decisions via an Invariant Embedding Technique. In: Lecture Notes in Engineering and Computer Science: Proceedings of the World Congress on Engineering (WCE 2010), 1776 1782. London, U.K.
  21. 21. NechvalN. A.PurgailisM.CiksteK.BerzinsG.RozevskisU.NechvalK. N. 2010b Prediction Model Selection and Spare Parts Ordering Policy for Efficient Support of Maintenance and Repair of Equipment. In: Analytical and Stochastic Modeling Techniques and Applications, Al-Begain, K., Fiems, D., Knottenbelt, W. (eds.). LNCS, 6148 321 338. Springer, Heidelberg
  22. 22. NechvalN. A.PurgailisM.NechvalK. N.RozevskisU. 2011a Optimization of Prediction Intervals for Order Statistics Based on Censored Data. In: Lecture Notes in Engineering and Computer Science: Proceedings of the World Congress on Engineering (WCE 2011), 63 69. London, U.K.
  23. 23. NechvalN. A.RoziteK.StrelchonokV. F. 2006 Optimal Airline Multi-Leg Flight Seat Inventory Control. In: Computing Anticipatory Systems, Daniel M. Dubois (ed.), Melville, New York: AIP (American Institute of Physics) Proceedings, 839 591600
  24. 24. RichterH. 1982 The Differential Revenue Method to Determine Optimal Seat Allotments by Fare Type. In: Proceedings of the XXII AGIFORS Symposium, American Airlines, New York, 339 362
  25. 25. ScarfH. 1959 Bayes Solutions of Statistical Inventory Problem. Ann. Math. Statist. 30 490 508
  26. 26. WeatherfordL. R.BodilyS. E.PferiferP. E. 1993 Modeling the Customer Arrival Process and Comparing Decision Rules in Perishable Asset Revenue Management Situations. Transportation Science, 27 239251
  27. 27. WollmerR. D. 1992 An Airline Seat Management Model for a Single Leg Route when Lower Fare Classes Book First. Operations Research, 40 2637

Written By

Nicholas A. Nechval and Maris Purgailis

Published: 28 November 2012