# Airline Overbooking Problem with Uncertain No-Shows

Authors: Chunxiao Zhang; Congrong Guo; Shenghui Yi
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper considers an airline overbooking problem of a new single-leg flight with discount fare. Due to the absence of historical data of no-shows for a new flight, and various uncertain human behaviors or unexpected events which causes that a few passengers cannot board their aircraft on time, we fail to obtain the probability distribution of no-shows. In this case, the airlines have to invite some domain experts to provide belief degree of no-shows to estimate its distribution. However, human beings often overestimate unlikely events, which makes the variance of belief degree much greater than that of the frequency. If we still regard the belief degree as a subjective probability, the derived results will exceed our expectations. In order to deal with this uncertainty, the number of no-shows of new flight is assumed to be an uncertain variable in this paper. Given the chance constraint of social reputation, an overbooking model with discount fares is developed to maximize the profit rate based on uncertain programming theory. Finally, the analytic expression of the optimal booking limit is obtained through a numerical example, and the results of sensitivity analysis indicate that the optimal booking limit is affected by flight capacity, discount, confidence level, and parameters of the uncertainty distribution significantly.


---

## Body

## 1. Introduction

Overbooking is a strategy that airlines accept the booking reservations of customers more than flight capacity in order to make up for the vacancy loss caused by no-shows who do not show up for check-in without canceling their booking requests before the flight takes off or are late for their scheduled flights. A lot of examples can reflect that overbooking strategy contributes to huge profits for airlines. Smith et al. [1] estimated that 15 percent of seats on sold-out flights would be lost if overbooking were not practiced and that the benefit of overbooking at America in 1990 exceeded $225 million. Overbooking can reduce the waste of seats and maximize airlines' profits, but it also brings potential risk. When the number of arrival passengers exceeds flight capacity, it might cause that some arrival passengers cannot board flight (denied boarding); thus, airlines need to compensate this part of passengers (denied-boarding compensation), which lead to losses on both social reputation and profits of airlines.Overbooking is one of the oldest problems and most effective revenue management practices and was officially sanctioned and published by the American Civil Aeronautics Board in 1965 [2]. In 1958, Beckmann [3] established a single period static model on overbooking, and a booking-limit policy, which instructed the manager to set a certain limit to accept reservations up to the limit, was proved to be optimal. Rothstein [4] formulated the problem as a nonhomogenous Markovian decision process and solved it by a dynamic programming method in 1971. Alstrup et al. [5] in 1986 as well proposed a dynamic programming formulation of a problem with two cabins, in which the terminal conditions allowed for upgrading and downgrading. Chatwin [6] in 1993 considered a multiperiod overbooking problem relating to a single-leg flight and a single fare class, gave conditions that ensure a booking-limit policy to be optimal, and described the continuous model with stationary fares and refunds as a birth and death process. Robert [7] in 2005, on the assumption that passengers' arriving obeyed the binomial distribution, established a single-fare-class overbooking model and then extended to the conditions of multiple-fare classes and dynamic.In the previous researches on overbooking problem, the arrival rate of customers is an important element and is usually assumed to be a random variable, and probability theory plays a great important character in the optimization of the overbooking strategy. We will consider an airline overbooking problem of a new single-leg flight with discount fare in this paper. Due to the absence of demand data for a new flight and various uncertain human behaviors or unexpected events which causes that a few passengers cannot board their aircraft on time, we have to invite some domain experts to provide belief degree to estimate the distribution of no-shows. However, human beings often overestimate unlikely events, which makes the variance of belief degree much greater than that of the frequency (Kahneman and Tversky [8]). In this case, if we regard the belief degree as a subjective probability, the derived results will exceed our expectations. In order to deal with the involved human uncertainty, uncertainty theory was founded by Liu [9] in 2007 and was refined by Liu [10] in 2010 based on normality, duality, subadditivity, and product axioms.Nowadays, uncertainty theory has become a branch of axiomatic mathematics for modelling human uncertainty, and a lot of applications can be found in various fields such as uncertain programming [11], uncertain statistics [10], uncertain risk analysis [12], uncertain reliability analysis [12], uncertain logic [13], uncertain inference [14], uncertain process [15], uncertain calculus [15], and uncertain finance [16]. Based on the theory of uncertain renewal process, Yao and Ralescu [17] investigated the uncertain age replacement policy and obtained the long-run average replacement cost. Zhang and Guo [18] applied the uncertain renewal process to the ordering problem of spare parts for aircrafts assuming the interarrival times to be uncertainty variables. With uncertainty theory, Liu and Yao [19] presented an uncertain expected value model for multilevel programming with equivalent crisp form.In this paper, we consider the airline overbooking problem of new flight in uncertain environment and assume the number of no-shows as an uncertain variable. The rest of this paper is organized as follows. Section2 recalls some basic concepts and properties about uncertainty theory which will be used throughout the paper. In Section 3, we build the model of airline overbooking in uncertain environment and get some theorems. We apply our model to practical overbooking system, and sensitivity analysis is given in Section 4. Finally, conclusions are drawn in Section 5.


## 2. Preliminaries

LetΓ be a nonempty set. A collection ℒ of Γ is called a σ-algebra if (a) Γ
∈
ℒ; (b) if Λ
∈
ℒ, then Λ
c
∈
ℒ; and (c) if Λ
1
,
Λ
2
,
…
,
∈
ℒ, then Λ
1
∪
Λ
2
∪
⋯
∈
ℒ. Each element Λ in the σ-algebra ℒ is called an event. Uncertain measure is a function from ℒ to [
0,1
]. In order to present an axiomatic definition of uncertain measure, it is necessary to assign to each event Λ a number ℳ
{
Λ
} which indicates the belief degree that the event Λ will occur. In order to ensure that the number ℳ
{
Λ
} has certain mathematical properties, Liu [9] proposed the following axioms.Axiom 1 (normality axiom).
ℳ
{
Γ
}
=
1 for the universal set Γ.Axiom 2 (duality axiom).
ℳ
{
Λ
}
+
ℳ
{
Λ
c
}
=
1 for any event Λ.Axiom 3 (subadditivity axiom).
For every countable sequence of eventsΛ
1
,
Λ
2
,
…, we have
(1)
ℳ
{
⋃
i
=
1
∞
‍
Λ
i
}
≤
∑
i
=
1
∞
‍
ℳ
{
Λ
i
}
.Definition 1 (Liu [9]).
The set functionℳ is called an uncertain measure if it satisfies the normality, duality, and subadditivity axioms.The triplet (Γ
,
ℒ
,
ℳ) is calledan uncertainty  space. Besides, in order to provide the operational law, Liu [20] defined the product uncertain measure on the product σ-algebre ℒ as follows.Axiom 4 (product axiom).
Let(
Γ
k
,
ℒ
k
,
ℳ
k
) be uncertainty spaces for k
=
1,2
,
…. Then the product uncertain measure ℳ is an uncertain measure satisfying
(2)
ℳ
{
∏
i
=
1
∞
‍
Λ
k
}
=
⋀
k
=
1
∞
ℳ
k
{
Λ
k
}
,
where Λ
k are arbitrarily chosen events from ℒ
k for k
=
1,2
,
…, respectively.Definition 2 (Liu [9]).
An uncertain variable is a measurable functionξ from an uncertainty space (
Γ
,
ℒ
,
ℳ
) to the set of real numbers; that is, for any Borel set B of real numbers, the set
(3)
{
ξ
∈
B
}
=
{
γ
∈
Γ
ξ
(
γ
)
∈
B
}
is an event.Definition 3 (Liu [9]).
The uncertainty distributionΦ of an uncertain variable ξ is defined by
(4)
Φ
(
x
)
=
ℳ
{
ξ
≤
x
}
,
for any real number x.Definition 4 (Liu [10]).
Letξ be an uncertain variable with regular uncertainty distribution Φ
(
x
). Then the inverse function Φ
-
1
(
α
) is called the inverse uncertainty distribution of ξ.Theorem 5 (Liu [9]).
Letξ be an uncertain variable with uncertainty distribution Φ. If the expected value exists, then
(5)
E
[
ξ
]
=
∫
0
+
∞
‍
(
1
-
Φ
(
x
)
)
d
x
-
∫
-
∞
0
‍
Φ
(
x
)
d
x
.Uncertain programming is a type of mathematical programming involving uncertain variables [9]. Assume that x is a decision vector, ξ is an uncertain vector, and f
(
x
,
ξ
) is an uncertain objective function. Liu [11] proposed the following uncertain programming model:
(6)
min
⁡
x
E
[
f
(
x
,
ξ
)
]
subject
to
:
ℳ
{
g
j
(
x
,
ξ
)
≤
0
}
≥
α
j
,
j
=
1,2
,
…
,
p
,
where ℳ
{
g
j
(
x
,
ξ
)
≤
0
}
≥
α
j
(
j
=
1,2
,
…
,
p
) are a set of chance constraints. It is naturally desired that the uncertain constraints g
i
(
x
,
ξ
)
≤
0
(
j
=
1,2
,
…
,
p) hold with confidence levels α
1
,
α
2
,
…
,
α
p.Theorem 6 (Liu [11]).
Assume that the constraint functiong
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
) is strictly increasing with respect to ξ
1
,
ξ
2
,
…
,
ξ
k and strictly decreasing with respect to ξ
k
+
1
,
ξ
k
+
2
,
…
,
ξ
n. If ξ
1
,
ξ
2
,
…
,
ξ
n are independent uncertain variables with uncertainty distributions Φ
1
,
Φ
2
,
…
,
Φ
n, respectively, then the chance constraint
(7)
ℳ
{
g
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
)
≤
0
}
≥
α
holds if and only if
(8)
g
(
x
,
Φ
1
-
1
(
α
)
,
…
,
Φ
k
-
1
(
α
)
,
Φ
k
+
1
-
1
(
1
-
α
)
,
…
,
Φ
n
-
1
(
1
-
α
)
)
≤
0
.


## 3. Mathematical Formulation

First of all, some notations are made as follows for the mathematical formulation:m: Booking limit of a new flight
n: Capacity of an aircraft
ξ: The number of no-shows with uncertainty distribution Φ
g: Price of a new flight ticket
r: Total cost of a flight
p: Penalty cost which is paid to each crowed-out customer who is denied boarding because the number of arrival passengers exceeds flight capacity
β: A discount of fare, 0
≤
β
≤
1
s
(
m
,
ξ
): Profit rate function of the new flight when booking limit is m and the number of no-shows is ξ
j: The maximum permissible number of crowed-out customers.We suppose that an airline is planning to open up a new single-leg flight with discount fares and a booking limit should be decided to match the new flight. Due to the absence of historical data, the airline cannot obtain the probability distribution of no-shows. In this case, the numberξ of no-shows is assumed to be a positive uncertain variable, and its uncertainty distribution Φ can be obtained by the belief degree of the invited experts. We suppose that the airline provides no refunds for the no-shows, and compensates those crowed-out customers. Our objective function is the profit rate that is the profit divided by the total cost of a new flight; then it is expressed as
(9)
s
(
m
,
ξ
)
=
{
m
g
β
r
-
1
,
if
m
-
ξ
≤
n
m
g
β
r
-
(
m
-
ξ
-
n
)
p
r
-
1
,
if
m
-
ξ
≥
n
.Since the numberξ of no-shows is an uncertain variable, the profit rate function s
(
m
,
ξ
) is an uncertain variable as well. As s
(
m
,
ξ
) cannot be directly maximized, we may maximize its expected value; that is,
(10)
max
⁡
m
E
[
s
(
m
,
ξ
)
]
.The purpose of decision-maker of airline is to find the optimal booking limit that maximizes the profit. However, if the number of arrival passengers exceeds flight capacity when the flight takes off, it will cause that some arrival passengers could not board flight, which lead to not only profit losses but also bad social reputation. For reducing the negative impact on the airline, a chance constraint is given that the uncertain measure of the event that the number of crowded-out customers is less thanj is greater than a given confidence level of α; that is,
(11)
ℳ
{
m
-
n
-
ξ
≤
j
}
≥
α
.In order to find the optimal booking limitm
*, we present the following theorems.Theorem 7.
Letξ be a positive uncertain variable with an uncertainty distribution Φ. Given that
(12)
s
(
m
,
ξ
)
=
{
m
g
β
r
-
1
,
i
f
m
-
ξ
≤
n
m
g
β
r
-
(
m
-
ξ
-
n
)
p
r
-
1
,
i
f
m
-
ξ
≥
n
,
the uncertain variable s
(
m
,
ξ
) has an uncertainty distribution
(13)
Ψ
(
x
)
=
{
0
,
i
f
x
<
m
g
β
r
-
(
m
-
n
)
p
r
-
1
Φ
(
r
x
+
r
-
m
g
β
p
+
m
-
n
)
,
m
m
l
i
f
m
g
β
r
-
(
m
-
n
)
p
r
-
1
≤
x
<
m
g
β
r
-
1
1
,
i
f
x
≥
m
g
β
r
-
1
.Proof.
It is easy to know thats
(
m
,
ξ
)
≥
m
g
β
/
r
-
(
m
-
n
)
p
/
r
-
1; therefore,
(14)
Ψ
(
x
)
=
ℳ
{
s
(
m
,
ξ
)
≤
x
}
=
0
,
for any x
∈
(
-
∞
,
m
g
β
/
r
-
(
m
-
n
)
p
)
/
r
-
1. If x
∈
[
m
g
β
/
r
-
(
m
-
n
)
p
/
r
-
1
,
m
g
β
/
r
-
1
), then
(15)
Ψ
(
x
)
=
ℳ
{
s
(
m
,
ξ
)
≤
x
}
=
ℳ
{
m
g
β
r
-
(
m
-
ξ
-
n
)
p
r
-
1
≤
x
}
=
ℳ
{
ξ
≤
r
x
+
r
-
m
g
β
p
+
m
-
n
}
=
Φ
(
r
x
+
r
-
m
g
β
p
+
m
-
n
)
.
Since s
(
m
,
ξ
)
≤
m
g
β
/
r
-
1, we have
(16)
Ψ
(
x
)
=
ℳ
{
s
(
m
,
ξ
)
≤
x
}
=
1
,
for any x
∈
[
m
g
β
/
r
-
1
,
+
∞
). The theorem is verified.Theorem 8.
Letξ be a positive uncertain variable with an uncertainty distribution Φ. Given that
(17)
s
(
m
,
ξ
)
=
{
m
g
β
r
-
1
,
i
f
m
-
ξ
≤
n
m
g
β
r
-
(
m
-
ξ
-
n
)
p
r
-
1
,
i
f
m
-
ξ
≥
n
,
then
(18)
E
[
s
(
m
,
ξ
)
]
=
m
g
β
r
-
p
r
∫
0
m
-
n
‍
Φ
(
x
)
d
x
-
1
.Proof.
The expected value of the uncertain variables
(
m
,
ξ
) is
(19)
E
[
s
(
m
,
ξ
)
]
=
∫
0
+
∞
‍
[
1
-
Ψ
(
x
)
]
d
x
-
∫
-
∞
0
‍
Ψ
(
x
)
d
x
=
∫
0
m
g
β
/
r
-
(
m
-
n
)
p
/
r
-
1
‍
1
d
x
+
∫
m
g
β
/
r
-
(
m
-
n
)
p
/
r
-
1
m
g
β
/
r
-
1
‍
[
(
r
x
+
r
-
m
g
β
p
+
m
-
n
)
1
-
Φ
m
m
m
m
m
m
m
m
m
m
m
l
l
×
(
r
x
+
r
-
m
g
β
p
+
m
-
n
)
]
d
x
+
∫
m
g
β
/
r
-
1
+
∞
‍
0
d
x
-
∫
-
∞
0
‍
0
d
x
=
∫
0
m
g
β
/
r
-
1
‍
1
d
x
-
∫
m
g
β
/
r
-
(
m
-
n
)
p
/
r
-
1
m
g
β
/
r
-
1
‍
Φ
(
r
x
+
r
-
m
g
β
p
+
m
-
n
)
d
x
=
m
g
β
r
-
p
r
∫
0
m
-
n
‍
Φ
(
x
)
d
x
-
1
.
The theorem is verified.Since the constraint function(
m
-
n
-
ξ
≤
j
) is strictly decreasing with respect to the uncertain variable ξ, the chance constraint (11) can be converted to crisp formula according to Theorem 6; then
(20)
m
≤
n
+
j
+
Φ
-
1
(
1
-
α
)
.Therefore, the uncertain programming model is developed as follows:(21)
max
⁡
m
[
m
g
β
r
-
p
r
∫
0
m
-
n
‍
Φ
(
x
)
d
x
-
1
]
subject
to
:
m
≤
n
+
j
+
Φ
-
1
(
1
-
α
)
.


## 4. Application

In this section, we will present a numerical case to illustrate the aforementioned model. Suppose that the overbooking problem is considered for a new single-leg flight of an airline. Assume that the numberξ of no-shows is a positive uncertain variable with linear uncertainty distribution ℒ
(
a
,
b
)  (
a
≥
0
) (Liu [21]); that is,
(22)
Φ
(
x
)
=
{
0
,
if
x
≤
a
(
x
-
a
)
(
b
-
a
)
,
if
a
≤
x
≤
b
1
,
if
x
≥
b
.
Then, the inverse uncertainty distribution of linear uncertain variable ℒ
(
a
,
b
) (Liu [21]) is
(23)
Φ
-
1
(
α
)
=
(
1
-
α
)
a
-
α
b
.
From the uncertain programming model (21), we can obtain that the optimal booking limit with discount fare is
(24)
m
*
=
{
(
g
β
(
b
-
a
)
p
+
a
+
n
)
∧
(
n
+
j
+
α
a
+
(
1
-
α
)
b
)
,
m
m
m
m
m
m
m
m
m
m
l
l
l
l
l
l
l
if
g
β
≤
p
n
+
j
+
α
a
+
(
1
-
α
)
b
,
if
g
β
>
p
.We consider two familiar types of aircraft A320-200 and B747-300 with capacity of 150 and 416, respectively. We give thata
=
0 and the price of the flight ticket g
= RMB 960 yuan. According to the general provision set by the airline, we suppose that the penalty cost p is 30
% of the face value of the ticket and p will be counted by RMB 200 yuan if it is less than RMB 200 yuan; that is,
(25)
p
=
max
⁡
{
1.3
g
β
,
g
β
+
200
}
.
For instance, if the upper limit of no-shows b
=
8, the permissible maximum of crowed-out passages j
=
5, aircraft capacity n
=
150, the chance constraint α
=
0.95, the discount β
=
0.4, then the optimal booking limit m
* is 155.Figure1 shows the optimal booking limit m
* changing with discount β for b
=
8, j
=
5. On the whole, with a gradually reduced slope, the optimal booking limit m
* increases in discount β till β reaches a certain value. The optimal booking limit m
* does not increase in the confidence level α, and, when β
≤
0.4, α has no effect on m
*. By the comparison of Figures 1(a) and 1(b), we can see that the increase of m
* caused by the increase of flight capacity n is distinct.Optimal booking limitm
* under the changes of α and β when b
=
8, j
=
5.
(a)
n
=
150
(b)
n
=
416Figure2 shows the optimal booking limit m
* changing with discount β for b
=
8, j
=
8. Compared with Figure 1, due to a little increase of j, m
* increases still in β and n, while the variation trend of m
* with β has nearly nothing to do with α. As can be seen from the comparison between Figures 1 and 2, the turning point of the slope of the optimal booking limit curve increases in j.Optimal booking limitm
* under the changes of α and β when b
=
8, j
=
8.
(a)
n
=
150
(b)
n
=
416Figures3 and 4 show the optimal booking limit m
* changing with the parameter b for j
=
5 and j
=
8, respectively. The optimal booking limit m
* increases in b, and, when b reaches a certain value, the slope becomes smaller. In the case of α
=
1.0, when b is bigger than a certain value, m
* remains the same. We also observe that m
* still does not increase in the confidence level α, and the closer α gets to 1, the less sensitive m
* is to b. The flight capacity n still has a great influence on m
*.Optimal booking limitm
* under the changes of α and b when β
=
0.8, j
=
5.
(a)
n
=
150
(b)
n
=
416Optimal booking limitm
* under the changes of α and b when β
=
0.8, j
=
8.
(a)
n
=
150
(b)
n
=
416As can be seen from the comparison between Figures3 and 4, the turning point of the slope of the optimal booking limit curve increases in j.


## 5. Conclusions

Overbooking problem is an important strategy for airline revenue management. For a new flight, there is no historical date to obtain the probability distribution of the number of no-shows; therefore, stochastic method is not suitable. This paper introduced an uncertain variable to describe the number of no-shows. An airline overbooking model with discount fare was developed with chance constraint, and it was converted to a crisp programming based on uncertain programming theory. Through a numerical case, we obtained the analytic expression of the optimal booking limit to maximize the profit rate function of the new flight. The results of sensitivity analysis indicated that flight capacity, discount, confidence level, and parameters of the uncertainty distribution significantly affected the optimal booking limit.However, there is still a lot of work to be done in the future research. The dynamic nature of the booking process can be taken into account. Furthermore, randomness and uncertainty may coexist in practical situation; thus an uncertain random overbooking model might be our future research.



---

*Source: 304217-2014-03-16.xml*