# Uncertain Programming for Network Revenue Management

Authors: Deyi Mou; Xiaoxin Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The mathematical model for airline network seat inventory control problem is usually investigated to maximize the total revenue under some constraints such as capacities and demands. This paper presents a chance-constrained programming model based on the uncertainty theory for network revenue management, in which the fares and the demands are both uncertain variables rather than random variables. The uncertain programming model can be transformed into a deterministic form by taking expected value on objective function and confidence level on the constraint functions. Based on the strategy of nested booking limits, a solution method of booking control is developed to solve the problem. Finally, this paper gives a numerical example to show that the method is practical and efficient.


---

## Body

## 1. Introduction

After the deregulations in the airline industry, the revenue management techniques have become indispensable for airline seat inventory control. A central problem in airline revenue management is determining optimal decision rules for sequentially accepting or denying itinerary requests. So it is necessary to develop mathematical models to determine complex booking control strategies.The optimization methods on seat inventory control problem with multiple-fare classes can be separated into the single-leg optimization method and the network optimization method. Based on the optimized frequency, each optimization method can be sorted out the static method and the dynamic method. In brief, the dynamic nature of the arrivals of the requests over time is not explicitly considered in the static method, whereas the mutability in the demand is taken into account in the dynamic method as the end of the reservation period approaches and the seat capacity diminishes.The single-leg optimization method firstly appeared in the research of Littlewood [1]. He studied a seat inventory control problem with two-fare classes on a single leg and proposed a marginal seat revenue rule applied into a two-price, single-leg model. Belobaba [2, 3] extended this idea to a multiclass problem and introduced the expected marginal seat revenue heuristic for the general approach. Wollmer [4], Brumelle and McGill [5], and Robinson [6] further studied the single-leg problem with multiple-fare classes. They developed algorithms to find the optimal booking control policy under the assumption that the probability distributions of the demands for different fare classes were known. Lee and Hersh [7] developed a discrete-time dynamic programming model to find an optimal booking control policy without requiring any assumptions about the arrival mode for the manifold booking classes. Liang [8] proposed a continuous-time, stochastic, dynamic programming model and showed that a threshold control policy was optimal. Feng and Xiao [9] presented a stochastic control model to dynamically tackle with seat inventory control problem.For the network optimization method, Glover et al. [10] initially described a minimum cost network flow formulation with deterministic demand without focusing on the stochastic elements. After that, a solution method for the sequential allocation of seats under the assumption of stochastic demand was provided by Wang [11]. Wollmer [12] proposed a linear programming model that considered stochastic demand. Dror et al. [13] proposed a similar deterministic network minimum cost flow formulation that allowed for cancellations as deterministic losses on arcs in the network. Curry [14] developed a combined mathematical model for a multiclass seat inventory control problem. Williamson [15] studied two network-based mathematical programming models. The first model incorporated probabilistic demand and the second model simplified the problem by substituting stochastic demand by its expectation. Wong et al. [16] applied nesting techniques into a multiclass seat inventory control problem. de Boer et al. [17] proposed stochastic linear programming for network revenue management and developed the nesting technique of Williamsion. Bertsimas and De Boer [18] and van Ryzin and Vulcano [19] used simulation-based optimization methods that also investigated nesting over the network. Cooper and Homem-De-Mello [20] proposed a decomposition method combining mathematical programming methods and Markov decision process. Recently, İlker Birbil et al. [21] proposed a framework for solving airline revenue management problems on large networks.With the fast development of civil aviation industry, many airlines often create new routes. Due to lacking reliable data and accurate information, the methods in the literature above become invalid for these new routes. On the other hand, when unconventional sudden events such as war, atrocious weather, and earthquake, happen, the cumulative data of computer reservation system is no longer trustworthy. There are some limitations when the traditional stochastic models above deal with such problems at this situation. In the two cases, we have to invite some experts to evaluate their degree of belief that each event will occur. However, humans tend to overweigh unlikely events (Kahnema and Tversky [22]); thus, the degree of belief may have a much larger range than the real frequency. In this situation, if we insist on dealing with the degree of belief using the probability theory, some counterintuitive results will be obtained (Liu [23]). In revenue management of the above two cases, as we stated before, the domain experts invited are likely to overrate the market demand on the new routes and underestimate the market demand under the circumstances of unconventional sudden events. If the belief degree of the market demand is treated as probability, we have no choice but to increase the capacity on the new routes and reduce the capacity under the circumstances of unconventional sudden events. This will cause great losses in revenue for airlines. This conclusion seems unacceptable and then the belief degree cannot be treated as probability.In order to deal with the experts' degree of belief, the uncertainty theory was founded by Liu [24] and refined by Liu [25] in 2013. Many researchers have contributed to this area. The uncertainty theory has been applied to uncertain programming, uncertain risk analysis, uncertain game, uncertain inference, uncertain logic, uncertain finance, and uncertain optimal control (Liu [25]). Nowadays, the uncertainty theory has become a branch of axiomatic mathematics to model human uncertainty (Liu [26]).Depending on the analysis as mentioned above, we think that it is necessary to apply the uncertainty theory as a basic approach to model the uncertainty in the revenue management of the two cases above. In this paper, we propose the chance-constrained programming model based on the uncertainty theory to deal with the uncertain factors. The rest of this paper is structured as follows. In Section2, some basic concepts and properties in uncertainty theory used throughout this paper are introduced. In Section 3, an uncertain programming model is constructed. According to inverse uncertainty distribution, the model can be transformed to its deterministic form. In Section 4, we present a solution method of booking control on the basis of the strategy of nested booking limits. After that, a numerical example is given in Section 5. At last, a brief summary is presented in Section 6.


## 2. Preliminaries

In this section, some basic definitions and arithmetic operations of uncertainty theory needed throughout this paper are presented.Definition 1 (Liu [24]).
LetΓ be a nonempty set and L a σ-algebra over Γ. Each element Λ
∈
L is called an event. The set function M is called an uncertain measure if it satisfies the following four axioms:
Axiom 1 (Normality). M
{
Γ
}
=
1;
Axiom 2 (Monotonicity). M
{
Λ
1
}
≤
M
{
Λ
2
} whenever Λ
1
⊂
Λ
2;
Axiom 3 (Self-Duality). M
{
Λ
}
+
M
{
Λ
c
}
=
1 for any event Λ;
Axiom 4 (Countable Subadditivity). For every countable sequence of events {
Λ
i
}, we have(1)
M
{
⋃
i
=
1
∞
‍
Λ
i
}
≤
∑
i
=
1
∞
‍
M
{
Λ
i
}
.Definition 2 (Liu [24]).
LetΓ be a nonempty set, L a σ-algebra over Γ, and M an uncertain measure. Then the triple (
Γ
,
L
,
M
) is called on uncertainty space.Definition 3 (Liu [24]).
An uncertain variableξ is a measurable function from an uncertainty space (
Γ
,
L
,
M
) to the set of real numbers; that is, for any Borel set B of real numbers, the set
(2)
{
ξ
∈
B
}
=
{
γ
∈
Γ
∣
ξ
(
γ
)
∈
B
}
is an event.For a sequence of uncertainty variablesξ
1
,
ξ
2
,
…
,
ξ
n and a measurable function f, Liu [24] proved that ξ
=
f
(
ξ
1
,
ξ
2
,
…
,
ξ
n
) defined as ξ
(
γ
)
=
f
(
ξ
1
(
γ
)
,
ξ
2
(
γ
)
,
…
,
ξ
n
(
γ
)
),∀
γ
∈
Γ is also an uncertain variable. In order to describe an uncertain variable, a concept of uncertainty distribution is introduced as follows.Definition 4 (Liu [24]).
The uncertainty distributionΦ of an uncertain variable ξ is defined by
(3)
Φ
(
x
)
=
M
{
ξ
≤
x
}
,
for any real number x.Peng and Iwamura [27] proved that a function Φ
:
R
→
[
0,1
] is an uncertainty distribution if and only if it is a monotone increasing function except for Φ
(
x
)
≡
0 or Φ
(
x
)
≡
1. The inverse function Φ
-
1 is called the inverse uncertainty distribution of ξ. Inverse uncertainty distribution is an important tool in the operation of uncertain variables.Theorem 5 (Liu [24]).
Letξ
1
,
ξ
2
,
…
,
ξ
n be independent uncertain variables with regular uncertainty distributions Φ
1
,
Φ
2
,
…
,
Φ
n, respectively. If f
(
x
1
,
x
2
,
…
,
x
n
) is strictly increasing with respect to x
1
,
x
2
,
…
,
x
m and strictly decreasing with respect to x
m
+
1
,
x
m
+
2
,
…
,
x
n, then
(4)
ξ
=
f
(
ξ
1
,
ξ
2
,
…
,
ξ
n
)
is an uncertain variable with inverse uncertainty distribution
(5)
Ψ
-
1
(
α
)
=
f
(
Φ
1
-
1
(
α
)
,
…
,
Φ
m
-
1
(
α
)
,
Φ
m
+
1
-
1
(
1
-
α
)
,
…
,
m
m
m
m
m
l
m
l
Φ
n
-
1
(
1
-
α
)
)
.Expected value is the average of an uncertain variable in the sense of uncertain measure. It is an important index to rank uncertain variables.Definition 6 (Liu [24]).
Letξ be an uncertain variable. Then the expected value of ξ is defined by
(6)
E
[
ξ
]
=
∫
0
∞
‍
M
{
ξ
≥
r
}
d
r
-
∫
-
∞
0
‍
M
{
ξ
≤
r
}
d
r
,
provided that at least one of the two integrals is finite.In order to calculate the expected value via inverse uncertainty distribution, Liu and Ha [28] proved that
(7)
E
[
ξ
]
=
∫
0
1
‍
f
(
Φ
1
-
1
(
α
)
)
,
…
,
Φ
m
-
1
(
α
)
,
Φ
m
+
1
-
1
(
1
-
α
)
,
…
,
m
m
m
m
m
l
Φ
n
-
1
(
1
-
α
)
d
α
under the condition described in Theorem 5. Generally, the expected value operator E has no linearity property for arbitrary uncertain variables. But, for independent uncertain variables ξ and η with finite expected values, we have
(8)
E
[
a
ξ
+
b
η
]
=
a
E
[
ξ
]
+
b
E
[
η
]
,
for any real numbers a and b.


## 3. Uncertain Programming Model for Multiple-Leg Network Seat Inventory Control

### 3.1. Problem Description

Because an airline wants to maximize revenue from the whole network, the researchers on this field focus on the network-based models now. Airlines usually provide thousands of such combinations of origin, destination and fare class (ODF). Therefore determining a comprehensive booking control strategy for the entire network is crucially important.The objective of network seat inventory control is to maximize the airline's expected revenue from its supply of ODF combinations. Each ODF in the network is constitutive of one or more flight legs. The limited capacity on each flight leg has to be made full use of in the most profitable way. This can be achieved by limiting the number of seats available to the less lucrative classes. So the problem is to allocate all seats of each flight leg to the related ODF in the most profitable way. Due to its economic importance in the airline, the problem has been extensively studied.In this paper, the network seat inventory control problem will be modeled by the chance-constrained programming based on the uncertainty theory in which the fare and the demand of each ODF are assumed to be uncertain variables with given uncertainty distributions.


### 3.2. Model Development

At first, we introduce the following notations to represent the mathematical formulation throughout the remainder of this paper:x
ODF
: the number of seats reserved for each separate ODF;
N
: the total number of flight legs in the ODF network;
S
l
: the set of ODF combinations available on flight leg;
C
l
: the seat capacity on legl;
D
ODF
: the deterministic aggregated demand for each ODF;
f
ODF
: the fare required for an ODF.In order to facilitate the analysis, we make some reasonable assumptions as follows.(a)
The flight market demand exceeds its capacity supply.
(b)
Overbooking is not considered by the model discussed here.Next, based on the analysis of the decision making process, the general problem is formulated as follows [15]:
(9)
max
⁡
∑
ODF
‍
f
ODF
x
ODF
s
.
t
.
l
l
∑
ODF
∈
S
l
‍
x
ODF
≤
C
l
∀
flight
legs
l
=
1
,
…
,
N
,
l
mmvli
l
x
ODF
≤
D
ODF
∀
ODF
,
l
mmml
l
x
ODF
≥
0
integer
∀
ODF
.In the above model, the quantitiesf
ODF and D
ODF are all assumed to be crisp numbers. However, when there are new routes created by the airlines or the emergency takes place sometimes, the quantities generally are not fixed but obtained from experience evaluation or expert knowledge. In this case, we may assume the quantities are uncertain variables. Then the model (9) is only a conceptual model rather than a mathematical model because there does not exist a natural ordership in an uncertain world. Here we take expected value criterion on the objective function and confidence level on the constraint functions (Liu [25]). Then the model (9) turns into the following mathematical model:
(10)
max
⁡
E
[
∑
ODF
‍
f
ODF
x
ODF
]
s
.
t
.
l
∑
ODF
∈
S
l
‍
x
ODF
≤
C
l
∀
flight
legs
l
=
1
,
…
,
N
,
mmm
l
l
m
m
l
M
{
x
ODF
≤
D
ODF
}
≥
β
ODF
∀
ODF
,
ml
m
m
l
x
ODF
≥
0
integer
∀
ODF
,
where β
ODF are some predetermined confidence levels for all ODF.In practical applications, the uncertainty distributions of uncertain variablesf
ODF and D
ODF and the confidence levels β
ODF are determined by linear interpolation method, the principle of least squares, the method of moments, and the Delphi method from expert's experimental data (Liu [25]). How do we obtain expert's experimental data? Liu [25] proposed a questionnaire survey for collecting expert’s experimental data. In this paper, we assume that the uncertainty distributions of uncertain variables f
ODF and D
ODF and the confidence levels β
ODF have been determined.In order to solve model (10), firstly, we introduce two corollaries which were from the uncertainty theory (Liu [25]).Corollary 7.
Assume the objective functionf
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
) is strictly increasing with respect to ξ
1
,
ξ
2
,
…
,
ξ
m and strictly decreasing with respect to ξ
m
+
1
,
ξ
m
+
2
,
…
,
ξ
n. If ξ
1
,
ξ
2
,
…
,
ξ
n are independent uncertain variables with uncertainty distributions Φ
1
,
Φ
2
,
…
,
Φ
n, respectively, then the expected objective function E
[
f
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
)
] is equal to
(11)
∫
0
1
‍
f
(
x
,
Φ
1
-
1
,
…
,
Φ
m
-
1
,
Φ
m
+
1
-
1
,
…
,
Φ
n
-
1
)
d
α
.Corollary 8.
Assume the constraint functiong
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
) is strictly increasing with respect to ξ
1
,
ξ
2
,
…
,
ξ
k and strictly decreasing with respect to ξ
k
+
1
,
ξ
m
k
2
,
…
,
ξ
n. If ξ
1
,
ξ
2
,
…
,
ξ
n are independent uncertain variables with uncertainty distributions Φ
1
,
Φ
2
,
…
,
Φ
n, respectively, then the chance constrain
(12)
M
{
g
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
)
≤
0
}
≥
α
holds if and only if
(13)
g
(
x
,
Φ
1
-
1
(
α
)
,
…
,
Φ
k
-
1
(
α
)
,
Φ
k
+
1
-
1
(
1
-
α
)
,
…
,
Φ
n
-
1
(
1
-
α
)
)
≤
0
.Secondly, the next theorem shows that the model (10) is equivalent to a deterministic model, for which many efficient algorithms have been designed.Theorem 9.
Assume thatf
O
D
F and D
O
D
F are independent uncertain variables with uncertainty distributions ϕ
O
D
F and ψ
O
D
F. Then the model (10) is equivalent to the following model:
(14)
max
⁡
∑
O
D
F
‍
x
O
D
F
∫
0
1
‍
ϕ
O
D
F
-
1
(
α
)
d
α
s
.
t
.
0000
∑
O
D
F
∈
S
l
‍
x
O
D
F
≤
C
l
∀
f
l
i
g
h
t
l
e
g
s
l
=
1
,
…
,
N
,
ll
00000
m
m
x
O
D
F
≤
ψ
O
D
F
-
1
(
1
-
β
O
D
F
)
∀
O
D
F
,
ll
00000
m
m
x
O
D
F
≥
0
i
n
t
e
g
e
r
∀
O
D
F
.Proof.
The function∑
ODF
f
ODF
x
ODF is strictly increasing with respect to f
ODF and f
ODF are independent uncertain variables with uncertainty distributions ϕ
ODF, respectively. By using Corollary 7, we obtain
(15)
E
[
∑
ODF
‍
f
ODF
x
ODF
]
=
∑
ODF
‍
x
ODF
∫
0
1
‍
ϕ
-
1
ODF
(
α
)
d
α
.
Since that(16)
M
{
x
ODF
≤
D
ODF
}
≥
β
ODF
is equivalent to
(17)
M
{
-
D
ODF
+
x
ODF
≤
0
}
≥
β
ODF
and the function -
D
ODF
+
x
ODF is strictly decreasing with respect to D
ODF with uncertainty distribution ψ
ODF, it follows from Corollary 8 that we have
(18)
-
ψ
ODF
-
1
(
1
-
β
ODF
)
+
x
ODF
≤
0
,
that is,
(19)
x
ODF
≤
ψ
ODF
-
1
(
1
-
β
ODF
)
.
The theorem is thus verified.


## 3.1. Problem Description

Because an airline wants to maximize revenue from the whole network, the researchers on this field focus on the network-based models now. Airlines usually provide thousands of such combinations of origin, destination and fare class (ODF). Therefore determining a comprehensive booking control strategy for the entire network is crucially important.The objective of network seat inventory control is to maximize the airline's expected revenue from its supply of ODF combinations. Each ODF in the network is constitutive of one or more flight legs. The limited capacity on each flight leg has to be made full use of in the most profitable way. This can be achieved by limiting the number of seats available to the less lucrative classes. So the problem is to allocate all seats of each flight leg to the related ODF in the most profitable way. Due to its economic importance in the airline, the problem has been extensively studied.In this paper, the network seat inventory control problem will be modeled by the chance-constrained programming based on the uncertainty theory in which the fare and the demand of each ODF are assumed to be uncertain variables with given uncertainty distributions.


## 3.2. Model Development

At first, we introduce the following notations to represent the mathematical formulation throughout the remainder of this paper:x
ODF
: the number of seats reserved for each separate ODF;
N
: the total number of flight legs in the ODF network;
S
l
: the set of ODF combinations available on flight leg;
C
l
: the seat capacity on legl;
D
ODF
: the deterministic aggregated demand for each ODF;
f
ODF
: the fare required for an ODF.In order to facilitate the analysis, we make some reasonable assumptions as follows.(a)
The flight market demand exceeds its capacity supply.
(b)
Overbooking is not considered by the model discussed here.Next, based on the analysis of the decision making process, the general problem is formulated as follows [15]:
(9)
max
⁡
∑
ODF
‍
f
ODF
x
ODF
s
.
t
.
l
l
∑
ODF
∈
S
l
‍
x
ODF
≤
C
l
∀
flight
legs
l
=
1
,
…
,
N
,
l
mmvli
l
x
ODF
≤
D
ODF
∀
ODF
,
l
mmml
l
x
ODF
≥
0
integer
∀
ODF
.In the above model, the quantitiesf
ODF and D
ODF are all assumed to be crisp numbers. However, when there are new routes created by the airlines or the emergency takes place sometimes, the quantities generally are not fixed but obtained from experience evaluation or expert knowledge. In this case, we may assume the quantities are uncertain variables. Then the model (9) is only a conceptual model rather than a mathematical model because there does not exist a natural ordership in an uncertain world. Here we take expected value criterion on the objective function and confidence level on the constraint functions (Liu [25]). Then the model (9) turns into the following mathematical model:
(10)
max
⁡
E
[
∑
ODF
‍
f
ODF
x
ODF
]
s
.
t
.
l
∑
ODF
∈
S
l
‍
x
ODF
≤
C
l
∀
flight
legs
l
=
1
,
…
,
N
,
mmm
l
l
m
m
l
M
{
x
ODF
≤
D
ODF
}
≥
β
ODF
∀
ODF
,
ml
m
m
l
x
ODF
≥
0
integer
∀
ODF
,
where β
ODF are some predetermined confidence levels for all ODF.In practical applications, the uncertainty distributions of uncertain variablesf
ODF and D
ODF and the confidence levels β
ODF are determined by linear interpolation method, the principle of least squares, the method of moments, and the Delphi method from expert's experimental data (Liu [25]). How do we obtain expert's experimental data? Liu [25] proposed a questionnaire survey for collecting expert’s experimental data. In this paper, we assume that the uncertainty distributions of uncertain variables f
ODF and D
ODF and the confidence levels β
ODF have been determined.In order to solve model (10), firstly, we introduce two corollaries which were from the uncertainty theory (Liu [25]).Corollary 7.
Assume the objective functionf
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
) is strictly increasing with respect to ξ
1
,
ξ
2
,
…
,
ξ
m and strictly decreasing with respect to ξ
m
+
1
,
ξ
m
+
2
,
…
,
ξ
n. If ξ
1
,
ξ
2
,
…
,
ξ
n are independent uncertain variables with uncertainty distributions Φ
1
,
Φ
2
,
…
,
Φ
n, respectively, then the expected objective function E
[
f
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
)
] is equal to
(11)
∫
0
1
‍
f
(
x
,
Φ
1
-
1
,
…
,
Φ
m
-
1
,
Φ
m
+
1
-
1
,
…
,
Φ
n
-
1
)
d
α
.Corollary 8.
Assume the constraint functiong
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
) is strictly increasing with respect to ξ
1
,
ξ
2
,
…
,
ξ
k and strictly decreasing with respect to ξ
k
+
1
,
ξ
m
k
2
,
…
,
ξ
n. If ξ
1
,
ξ
2
,
…
,
ξ
n are independent uncertain variables with uncertainty distributions Φ
1
,
Φ
2
,
…
,
Φ
n, respectively, then the chance constrain
(12)
M
{
g
(
x
,
ξ
1
,
ξ
2
,
…
,
ξ
n
)
≤
0
}
≥
α
holds if and only if
(13)
g
(
x
,
Φ
1
-
1
(
α
)
,
…
,
Φ
k
-
1
(
α
)
,
Φ
k
+
1
-
1
(
1
-
α
)
,
…
,
Φ
n
-
1
(
1
-
α
)
)
≤
0
.Secondly, the next theorem shows that the model (10) is equivalent to a deterministic model, for which many efficient algorithms have been designed.Theorem 9.
Assume thatf
O
D
F and D
O
D
F are independent uncertain variables with uncertainty distributions ϕ
O
D
F and ψ
O
D
F. Then the model (10) is equivalent to the following model:
(14)
max
⁡
∑
O
D
F
‍
x
O
D
F
∫
0
1
‍
ϕ
O
D
F
-
1
(
α
)
d
α
s
.
t
.
0000
∑
O
D
F
∈
S
l
‍
x
O
D
F
≤
C
l
∀
f
l
i
g
h
t
l
e
g
s
l
=
1
,
…
,
N
,
ll
00000
m
m
x
O
D
F
≤
ψ
O
D
F
-
1
(
1
-
β
O
D
F
)
∀
O
D
F
,
ll
00000
m
m
x
O
D
F
≥
0
i
n
t
e
g
e
r
∀
O
D
F
.Proof.
The function∑
ODF
f
ODF
x
ODF is strictly increasing with respect to f
ODF and f
ODF are independent uncertain variables with uncertainty distributions ϕ
ODF, respectively. By using Corollary 7, we obtain
(15)
E
[
∑
ODF
‍
f
ODF
x
ODF
]
=
∑
ODF
‍
x
ODF
∫
0
1
‍
ϕ
-
1
ODF
(
α
)
d
α
.
Since that(16)
M
{
x
ODF
≤
D
ODF
}
≥
β
ODF
is equivalent to
(17)
M
{
-
D
ODF
+
x
ODF
≤
0
}
≥
β
ODF
and the function -
D
ODF
+
x
ODF is strictly decreasing with respect to D
ODF with uncertainty distribution ψ
ODF, it follows from Corollary 8 that we have
(18)
-
ψ
ODF
-
1
(
1
-
β
ODF
)
+
x
ODF
≤
0
,
that is,
(19)
x
ODF
≤
ψ
ODF
-
1
(
1
-
β
ODF
)
.
The theorem is thus verified.


## 4. Solution Method of Booking Control

### 4.1. The Strategy of Nested Booking Limits

In the model (14), we use f
¯
ODF to denote ∫
0
1
‍
ϕ
ODF
-
1
(
α
)
d
α and D
¯
ODF to denote ψ
ODF
-
1
(
1
-
β
ODF
). Then the relaxation of the model (14) is
(20)
max
⁡
∑
ODF
‍
f
¯
ODF
x
ODF
s
.
t
.
mmll
l
l
∑
ODF
∈
S
l
‍
x
ODF
≤
C
l
∀
flight
legs
l
=
1
,
…
,
N
,
mmm
mmll
l
l
i
x
ODF
≤
D
¯
ODF
∀
ODF
,
mml
mmml
m
x
ODF
≥
0
∀
ODF
.The whole booking time should be partitioned into a few time periods of reservation; for example, a day is a time period of reservation. In order to facilitate the analysis, we describe the model (20) in the form of the matrix and the vector considering the time period of reservation. For this, we introduce the following notations:I: the total number of flight legs in the ODF network;
i: index for set of flight legs;
J: the total number of the ODF;
j: index for set of the ODF;
t: index for the time period of reservation;
C
t
=
[
C
1
t
,
C
2
t
,
…
,
C
i
t
,
…
,
C
I
t
]
T: the seat capacity on each flight leg in the reservation time period t;
F
t
=
[
f
-
1
t
,
f
-
2
t
,
…
,
f
-
j
t
,
…
f
-
J
t
]
T: the corresponding f
¯
ODF for each separate ODF in the reservation time period t;
D
t
=
[
D
-
1
t
,
D
-
2
t
,
…
,
D
-
j
t
,
…
,
D
-
J
t
]
T: the corresponding D
¯
ODF for each separate ODF in the reservation time period t;
X
t
=
[
x
1
t
,
x
2
t
,
…
,
x
j
t
,
…
,
x
J
t
]
T: the number of seats reserved for each separate ODF in the reservation time period t;
A
=
(
a
i
j
)
I
×
J: the matrix denotation of flight legs that each ODF travels, where if the ODF j travels the flight leg i, then a
i
j
=
1, otherwise a
i
j
=
0;
A
j: the jth column of the matrix A, denoting the flight legs that the ODF j travels.The model (20) is described as follows in the form of the matrix and the vector:
(21)
LP
(
C
t
,
D
t
)
=
max
⁡
(
F
t
)
T
X
t
ml
s
.
t
.
m
m
m
m
v
A
X
t
≤
C
t
,
mmlmm
v
0
≤
X
t
≤
D
t
.The dual problem of the model above can be described as follows:(22)
DLP
(
C
t
,
D
t
)
=
min
⁡
[
(
P
t
)
T
C
t
+
(
Q
t
)
T
D
t
]
ml
s
.
t
.
m
m
m
m
m
A
T
P
t
+
Q
t
≥
F
t
,
m
m
m
m
l
v
P
t
,
Q
t
≥
0
,
where P
t
=
[
P
1
t
,
P
2
t
,
…
,
P
i
t
,
…
,
P
I
t
]
T denotes the shadow prices corresponding to each flight leg and Q
t
=
[
Q
1
t
,
Q
2
t
,
…
,
Q
j
t
,
…
,
Q
J
t
]
T denotes the shadow prices corresponding to each D
¯
ODF.Bid price control method is one of the prevalent methods of network seat inventory control. The bid price of each ODF is equal to the sum of shadow prices of the flight legs that the ODF crosses. A booking request for a passenger from the ODF is rejected if the bid price of the ODF exceeds the fare for the ODF and is accepted otherwise. Although bid price control method has been used in the actual operations of the airlines, it has a few shortcomings as follows.(a)
Each ODF’s contribution to network revenue is not considered in the bid price control method.
(b)
When calculating shadow prices using the relevant models, the solution of the model may be degenerate solution. This will cause the multiple bid prices of an ODF.
(c)
The fares of most of the passengers on the flight just exceed the bid prices so that airlines suffer losses.For this, we present a nesting control method based on the network contribution value for the above uncertain programming model.First, we define an ODF’s net contribution value to network revenue in the reservation time periodt as the expected fare for the ODF in the reservation time period t minus the opportunity cost of the ODF in the reservation time period t, that is,
(23)
NC
V
j
t
=
f
-
j
t
-
O
C
j
t
,
where NC
V
j
t denotes the net contribution value of the ODF j to network revenue in the reservation time period t and O
C
j
t denotes the opportunity cost of the ODF j in the reservation time period t.The opportunity costO
C
j
t of the ODF j in the reservation time period t is calculated based on the DLP model as follows:
(24)
O
C
j
t
=
(
P
t
)
T
A
j
for 1
≤
j
≤
J.Now the opportunity cost of the ODF in the reservation time periodt is known, so we figure up the net contribution value of the ODF to network revenue in the reservation time period t. However, the solution of the model DLP may be degenerate solution and this phenomenon will cause multiple net contribution values of the ODF to network revenue. In this case, we will use the following method to calculate the net contribution value of the ODF to network revenue in the reservation time period t. If C
t
-
A
j
≥
0, then NC
V
j
t
=
f
-
j
t
-
[
LP
(
C
t
,
D
t
)
-
LP
(
C
t
-
A
j
,
D
t
)
]. Otherwise,NC
V
j
t
=
-
∞ where ∞ denotes a large enough number.Finally, we rank the ODF on the basis of their net contribution value to network revenue to determine the nesting level. If some of the ODFs have the same net contribution value to network revenue, we can rank the ODF on the basis of their expected fare.


### 4.2. The Algorithm for Nested ODF-Based Booking Control

Every time a booking request arrives for any ODF in the network, a quick decision should be made whether or not to accept the request. We have to specify a booking control strategy for the decision. We propose the algorithm for nested ODF-based booking control.The notations used in the following algorithm are given as below:X
t
=
[
x
t
1
,
x
t
2
,
…
,
x
t
j
,
…
,
x
t
J
]
T: the number of seats reserved for each separate ODF in the reservation time period t after ranking the elements of X
t according to the nesting level;
P
L
t
=
[
P
L
t
1
,
P
L
t
2
,
…
,
P
L
t
j
,
…
,
P
L
t
J
]
T: seat protect level for each ranked ODF in the reservation time period t;
M
k
(
1
≤
k
≤
j
): the set of flight legs that the kth ODF travels;
b
t
=
[
b
t
1
,
b
t
2
,
…
,
b
t
j
,
…
,
b
t
J
]: the number of booking requests for the ranked ODF that have already been accepted in the reservation time period t;
B
L
t
j: seat booking limit for the jth ODF.The heuristic algorithm for nested ODF-based booking control is as follows.Step 1.
Calculate each ODF's net contribution value to network revenue in the reservation time periodt and determine the nesting level. By solving the model above, we can obtain X
t
=
[
x
1
t
,
x
2
t
,
…
,
x
j
t
,
…
,
x
J
t
]
T.Step 2.
Determine seat protect level for each ODF. According to ranking results of Step1, we rank the elements of X
t and obtain X
t
=
[
x
t
1
,
x
t
2
,
…
,
x
t
j
,
…
,
x
t
J
]
T. Seat protect level is determined as P
L
t
=
[
P
L
t
1
,
P
L
t
2
,
…
,
P
L
t
j
,
…
,
P
L
t
J
]
=
[
x
t
1
,
x
t
2
,
…
,
x
t
j
,
…
,
x
t
J
]
T.Step 3.
At the beginning of the reservation time periodt, it is obvious that b
t
=
0. Determine seat booking limit for the ranked ODF as follows.
For the first ODF,(25)
B
L
t
1
=
min
⁡
{
N
i
t
∣
1
≤
i
≤
I
,
i
∈
M
1
}
;
for the jth ODF (
2
≤
j
≤
J
), on the flight leg i (
1
≤
i
≤
I
), the total number of the seats protected for the lower level ODF than the jth ODF is Π
i
t
=
∑
k
=
1
j
-
1
P
R
k
t, where the kth ODF travels the flight leg i and the number of the seats available on the flight leg i is (
C
i
t
-
Π
i
t
). So we have
(26)
B
L
t
j
=
min
⁡
{
C
i
t
-
Π
i
t
∣
1
≤
i
≤
I
,
i
∈
M
j
}
.Step 4.
IfB
L
t
j
>
b
t
j, then accept the booking request, let b
t
j
=
b
t
j
+
1; if B
L
t
j
=
b
t
j, then decline the request.Step1 determines the nesting level for each separate ODF; Step 2 determines seat protect level for each ranked ODF; Step 3 determines seat booking limit for the ranked ODF; Step 4 develops the standard of accepting or rejecting the booking requests.When entering the next reservation time period, let(27)
C
t
=
C
t
-
b
t
T
[
A
1
A
2
⋯
A
j
⋯
A
J
]
T
,
t
=
t
-
1
,
b
t
=
0
,
and then go into the algorithm above.


## 4.1. The Strategy of Nested Booking Limits

In the model (14), we use f
¯
ODF to denote ∫
0
1
‍
ϕ
ODF
-
1
(
α
)
d
α and D
¯
ODF to denote ψ
ODF
-
1
(
1
-
β
ODF
). Then the relaxation of the model (14) is
(20)
max
⁡
∑
ODF
‍
f
¯
ODF
x
ODF
s
.
t
.
mmll
l
l
∑
ODF
∈
S
l
‍
x
ODF
≤
C
l
∀
flight
legs
l
=
1
,
…
,
N
,
mmm
mmll
l
l
i
x
ODF
≤
D
¯
ODF
∀
ODF
,
mml
mmml
m
x
ODF
≥
0
∀
ODF
.The whole booking time should be partitioned into a few time periods of reservation; for example, a day is a time period of reservation. In order to facilitate the analysis, we describe the model (20) in the form of the matrix and the vector considering the time period of reservation. For this, we introduce the following notations:I: the total number of flight legs in the ODF network;
i: index for set of flight legs;
J: the total number of the ODF;
j: index for set of the ODF;
t: index for the time period of reservation;
C
t
=
[
C
1
t
,
C
2
t
,
…
,
C
i
t
,
…
,
C
I
t
]
T: the seat capacity on each flight leg in the reservation time period t;
F
t
=
[
f
-
1
t
,
f
-
2
t
,
…
,
f
-
j
t
,
…
f
-
J
t
]
T: the corresponding f
¯
ODF for each separate ODF in the reservation time period t;
D
t
=
[
D
-
1
t
,
D
-
2
t
,
…
,
D
-
j
t
,
…
,
D
-
J
t
]
T: the corresponding D
¯
ODF for each separate ODF in the reservation time period t;
X
t
=
[
x
1
t
,
x
2
t
,
…
,
x
j
t
,
…
,
x
J
t
]
T: the number of seats reserved for each separate ODF in the reservation time period t;
A
=
(
a
i
j
)
I
×
J: the matrix denotation of flight legs that each ODF travels, where if the ODF j travels the flight leg i, then a
i
j
=
1, otherwise a
i
j
=
0;
A
j: the jth column of the matrix A, denoting the flight legs that the ODF j travels.The model (20) is described as follows in the form of the matrix and the vector:
(21)
LP
(
C
t
,
D
t
)
=
max
⁡
(
F
t
)
T
X
t
ml
s
.
t
.
m
m
m
m
v
A
X
t
≤
C
t
,
mmlmm
v
0
≤
X
t
≤
D
t
.The dual problem of the model above can be described as follows:(22)
DLP
(
C
t
,
D
t
)
=
min
⁡
[
(
P
t
)
T
C
t
+
(
Q
t
)
T
D
t
]
ml
s
.
t
.
m
m
m
m
m
A
T
P
t
+
Q
t
≥
F
t
,
m
m
m
m
l
v
P
t
,
Q
t
≥
0
,
where P
t
=
[
P
1
t
,
P
2
t
,
…
,
P
i
t
,
…
,
P
I
t
]
T denotes the shadow prices corresponding to each flight leg and Q
t
=
[
Q
1
t
,
Q
2
t
,
…
,
Q
j
t
,
…
,
Q
J
t
]
T denotes the shadow prices corresponding to each D
¯
ODF.Bid price control method is one of the prevalent methods of network seat inventory control. The bid price of each ODF is equal to the sum of shadow prices of the flight legs that the ODF crosses. A booking request for a passenger from the ODF is rejected if the bid price of the ODF exceeds the fare for the ODF and is accepted otherwise. Although bid price control method has been used in the actual operations of the airlines, it has a few shortcomings as follows.(a)
Each ODF’s contribution to network revenue is not considered in the bid price control method.
(b)
When calculating shadow prices using the relevant models, the solution of the model may be degenerate solution. This will cause the multiple bid prices of an ODF.
(c)
The fares of most of the passengers on the flight just exceed the bid prices so that airlines suffer losses.For this, we present a nesting control method based on the network contribution value for the above uncertain programming model.First, we define an ODF’s net contribution value to network revenue in the reservation time periodt as the expected fare for the ODF in the reservation time period t minus the opportunity cost of the ODF in the reservation time period t, that is,
(23)
NC
V
j
t
=
f
-
j
t
-
O
C
j
t
,
where NC
V
j
t denotes the net contribution value of the ODF j to network revenue in the reservation time period t and O
C
j
t denotes the opportunity cost of the ODF j in the reservation time period t.The opportunity costO
C
j
t of the ODF j in the reservation time period t is calculated based on the DLP model as follows:
(24)
O
C
j
t
=
(
P
t
)
T
A
j
for 1
≤
j
≤
J.Now the opportunity cost of the ODF in the reservation time periodt is known, so we figure up the net contribution value of the ODF to network revenue in the reservation time period t. However, the solution of the model DLP may be degenerate solution and this phenomenon will cause multiple net contribution values of the ODF to network revenue. In this case, we will use the following method to calculate the net contribution value of the ODF to network revenue in the reservation time period t. If C
t
-
A
j
≥
0, then NC
V
j
t
=
f
-
j
t
-
[
LP
(
C
t
,
D
t
)
-
LP
(
C
t
-
A
j
,
D
t
)
]. Otherwise,NC
V
j
t
=
-
∞ where ∞ denotes a large enough number.Finally, we rank the ODF on the basis of their net contribution value to network revenue to determine the nesting level. If some of the ODFs have the same net contribution value to network revenue, we can rank the ODF on the basis of their expected fare.


## 4.2. The Algorithm for Nested ODF-Based Booking Control

Every time a booking request arrives for any ODF in the network, a quick decision should be made whether or not to accept the request. We have to specify a booking control strategy for the decision. We propose the algorithm for nested ODF-based booking control.The notations used in the following algorithm are given as below:X
t
=
[
x
t
1
,
x
t
2
,
…
,
x
t
j
,
…
,
x
t
J
]
T: the number of seats reserved for each separate ODF in the reservation time period t after ranking the elements of X
t according to the nesting level;
P
L
t
=
[
P
L
t
1
,
P
L
t
2
,
…
,
P
L
t
j
,
…
,
P
L
t
J
]
T: seat protect level for each ranked ODF in the reservation time period t;
M
k
(
1
≤
k
≤
j
): the set of flight legs that the kth ODF travels;
b
t
=
[
b
t
1
,
b
t
2
,
…
,
b
t
j
,
…
,
b
t
J
]: the number of booking requests for the ranked ODF that have already been accepted in the reservation time period t;
B
L
t
j: seat booking limit for the jth ODF.The heuristic algorithm for nested ODF-based booking control is as follows.Step 1.
Calculate each ODF's net contribution value to network revenue in the reservation time periodt and determine the nesting level. By solving the model above, we can obtain X
t
=
[
x
1
t
,
x
2
t
,
…
,
x
j
t
,
…
,
x
J
t
]
T.Step 2.
Determine seat protect level for each ODF. According to ranking results of Step1, we rank the elements of X
t and obtain X
t
=
[
x
t
1
,
x
t
2
,
…
,
x
t
j
,
…
,
x
t
J
]
T. Seat protect level is determined as P
L
t
=
[
P
L
t
1
,
P
L
t
2
,
…
,
P
L
t
j
,
…
,
P
L
t
J
]
=
[
x
t
1
,
x
t
2
,
…
,
x
t
j
,
…
,
x
t
J
]
T.Step 3.
At the beginning of the reservation time periodt, it is obvious that b
t
=
0. Determine seat booking limit for the ranked ODF as follows.
For the first ODF,(25)
B
L
t
1
=
min
⁡
{
N
i
t
∣
1
≤
i
≤
I
,
i
∈
M
1
}
;
for the jth ODF (
2
≤
j
≤
J
), on the flight leg i (
1
≤
i
≤
I
), the total number of the seats protected for the lower level ODF than the jth ODF is Π
i
t
=
∑
k
=
1
j
-
1
P
R
k
t, where the kth ODF travels the flight leg i and the number of the seats available on the flight leg i is (
C
i
t
-
Π
i
t
). So we have
(26)
B
L
t
j
=
min
⁡
{
C
i
t
-
Π
i
t
∣
1
≤
i
≤
I
,
i
∈
M
j
}
.Step 4.
IfB
L
t
j
>
b
t
j, then accept the booking request, let b
t
j
=
b
t
j
+
1; if B
L
t
j
=
b
t
j, then decline the request.Step1 determines the nesting level for each separate ODF; Step 2 determines seat protect level for each ranked ODF; Step 3 determines seat booking limit for the ranked ODF; Step 4 develops the standard of accepting or rejecting the booking requests.When entering the next reservation time period, let(27)
C
t
=
C
t
-
b
t
T
[
A
1
A
2
⋯
A
j
⋯
A
J
]
T
,
t
=
t
-
1
,
b
t
=
0
,
and then go into the algorithm above.


## 5. Numerical Experiment

In this section, we apply the model and the algorithm of the former two sections to airline seat inventory control and give an optimal policy.An airline prepares to open a new route, which is from A to C through B. So there are two legs and three segments. Every segment has two fare classes with Y and T, so there are six ODFs. These are shown in Figure1.Figure 1
Schematic.That is,(28)
N
=
2
,
l
=
1,2
,
S
1
=
{
ABY
,
ABT
,
ACY
,
ACT
}
,
S
2
=
{
BCY
,
BCT
,
ACY
,
ACT
}
.Furthermore, there are 140 seats available in the flight and the booking period is partitioned into 11 time intervals.In order to simulate the booking process, some simulated reservation data about each time interval are given in Table1.Table 1
Simulated reservation data.
ODF
t = 10
t = 9
t = 8
t = 7
t = 6
t = 5
t = 4
t = 3
t = 2
t = 1
t = 0
ABY
3
3
3
5
4
1
3
7
8
11
8
ABT
13
5
8
7
1
2
6
2
5
5
2
BCY
0
2
1
5
4
8
6
4
7
7
4
BCT
15
5
11
9
9
8
2
3
4
2
0
ACY
2
0
0
1
2
9
1
7
5
3
5
ACT
10
2
5
6
2
4
7
4
3
1
1Whent
=
10, there is C
1
=
C
2
=
140.According to experts' experience, the demands for ABY, ABT, BCY, BCT, ACY, and ACT follow a normal uncertainty distributionN
(
e
i
,
σ
i
), i
=
1,2
,
3,4
,
5,6, respectively. The fare f
i for ABY, ABT, BCY, BCT, ACY, and ACT follows a normal uncertainty distribution N
(
e
i
′
,
σ
i
′
),  i
=
1,2
,
3,4
,
5,6, respectively. Tables 2 and 3 give the value of the quantities.Table 2
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(42, 2)
(66, 2)
(41, 3)
(71, 4)
(35, 1)
(50, 3)Table 3
Parameters of normal distribution of fare.
N
(
e
i
′
,
σ
i
′
)
1
2
3
4
5
6
(1000, 80)
(800, 40)
(400, 20)
(320, 10)
(1200, 90)
(960, 50)Note that the normal uncertain variableN
(
e
,
σ
) has an expected value e and an inverse uncertainty distribution
(29)
Φ
-
1
(
x
)
=
e
+
3
σ
π
ln
⁡
1
-
x
x
.Furthermore,β
=
0.9.According to Section3 and Section 4, the result of the seat inventory control for t
=
10 is obtained in Table 4.Table 4
The seat inventory control fort = 10.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 10
ABY
1000
200
42
140
3
3
ABT
800
0
63
63
13
13
BCY
400
80
41
105
0
0
BCT
320
0
64
64
15
15
ACY
1200
80
35
98
2
2
ACT
960
−160
10
0
10
0Whent
=
9,8
,
7,6
,
5,4
,
3,2
,
1,0, the results of the seat inventory control are listed in Appendix.Finally, the result of simulation is listed as Table5.Table 5
The seat inventory control result.
The combination of the ODF
The total number of accepted seats
ABY
52
ABT
54
BCY
48
BCT
58
ACY
30
ACT
4
The total expected revenue
172800The numerical experiment shows that the computation time of the algorithm is 0.4–0.8 seconds.We use bid price control method for the above simulation data and the result is listed as Table6.Table 6
The seat inventory control result of the bid price control method.
The combination of the ODF
The total number of accepted seats
ABY
48
ABT
54
BCY
45
BCT
57
ACY
30
ACT
8
The total expected revenue
171120Table 7
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(40, 2)
(56, 2)
(39, 3)
(61, 4)
(34, 1)
(42, 3)Table 8
The seat inventory control fort = 9.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 9
ABY
1000
200
40
122
3
3
ABT
800
0
48
48
5
5
BCY
400
80
39
89
2
2
BCT
320
0
50
50
5
5
ACY
1200
80
34
82
0
0
ACT
960
−160
0
0
2
0Table 9
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(38, 2)
(47, 2)
(36, 3)
(51, 4)
(32, 1)
(36, 3)Table 10
The seat inventory control fort = 8.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 8
ABY
1000
200
38
114
3
3
ABT
800
0
44
44
8
8
BCY
400
80
36
84
1
1
BCT
320
0
48
48
11
11
ACY
1200
80
32
76
0
0
ACT
960
−160
0
0
5
0Table 11
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(36, 2)
(39, 2)
(33, 3)
(42, 4)
(30, 1)
(30, 3)Table 12
The seat inventory control fort = 7.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 7
ABY
1000
200
36
103
5
5
ABT
800
0
37
37
7
7
BCY
400
80
33
74
5
5
BCT
320
0
41
41
9
9
ACY
1200
80
30
67
1
1
ACT
960
−160
0
0
6
0Table 13
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(33, 2)
(32, 2)
(30, 3)
(34, 4)
(28, 1)
(24, 3)Table 14
The seat inventory control fort = 6.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 6
ABY
1000
200
23
90
4
4
ABT
800
0
29
29
1
1
BCY
400
80
30
61
4
4
BCT
320
0
31
31
9
9
ACY
1200
80
28
57
2
2
ACT
960
−160
0
0
2
0Table 15
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(30, 2)
(25, 2)
(27, 3)
(26, 4)
(25, 1)
(19, 3)Table 16
The seat inventory control fort = 5.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 5
ABY
1000
200
30
83
1
1
ABT
800
0
25
28
2
2
BCY
400
80
27
49
8
8
BCT
320
0
19
19
8
8
ACY
1200
80
25
53
9
9
ACT
960
−160
3
3
4
3Table 17
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(27, 2)
(20, 2)
(23, 3)
(20, 4)
(22, 1)
(15, 3)Table 18
The seat inventory control fort = 4.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 4
ABY
1000
200
27
68
3
3
ABT
800
0
19
19
6
6
BCY
400
80
23
24
6
6
BCT
320
0
1
1
2
1
ACY
1200
80
22
41
1
1
ACT
960
−160
0
0
7
0Table 19
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(23, 2)
(15, 2)
(19, 3)
(14, 4)
(19, 1)
(11, 3)Table 20
The seat inventory control fort = 3.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 3
ABY
1000
440
23
58
7
7
ABT
800
240
15
16
2
2
BCY
400
0
18
18
4
4
BCT
320
−80
0
0
3
0
ACY
1200
240
19
35
7
7
ACT
960
0
1
1
4
1Table 21
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(19, 2)
(11, 2)
(15, 3)
(10, 4)
(16, 1)
(8, 3)Table 22
The seat inventory control fort = 2.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 2
ABY
1000
200
19
41
8
8
ABT
800
0
6
6
5
5
BCY
400
0
10
10
7
7
BCT
320
−80
0
0
4
0
ACY
1200
0
16
22
5
5
ACT
960
−240
0
0
3
0Table 23
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(14, 2)
(8, 2)
(10, 3)
(6, 4)
(12, 1)
(5, 3)Table 24
The seat inventory control fort = 1.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 1
ABY
1000
200
14
23
11
11
ABT
800
0
5
5
5
5
BCY
400
0
10
10
7
7
BCT
320
−80
0
0
2
0
ACY
1200
0
4
9
3
3
ACT
960
−240
0
0
1
0Table 25
Parameters of normal distribution of demand.
N
(
e
i
,
σ
i
)
1
2
3
4
5
6
(9, 2)
(3, 2)
(5, 3)
(2, 1)
(7, 1)
(2, 1)Table 26
The seat inventory control fort = 0.
ODF
f
j
t
-
NCV
j
t
x
j
t
BL
t
j
Simulated reservation data
The number of accepted seats
t = 0
ABY
1000
0
4
4
8
4
ABT
800
200
0
0
2
0
BCY
400
0
4
4
4
4
BCT
320
−80
0
0
0
0
ACY
1200
−200
0
0
5
0
ACT
960
−440
0
0
1
0Comparing Tables5 and 6, we can see that the total expected revenue using the bid price control method is 171120 RMB, while the total expected revenue using the proposed method in this paper is 172800 RMB. Numerical simulation results show that the proposed method in this paper is effective for improving the airline's revenue.


## 6. Conclusions

To consider network revenue management problem under conditions of new routes and unconventional sudden events, we established an uncertain programming model. Based on the strategy of nested booking limits, a heuristic algorithm for booking control was developed. Numerical test was performed to evaluate the model and the solution algorithm. The test results show that the model and the solution are all effective. There are some suggestions for future research:(i)
the impact of the nesting heuristics on total revenue;
(ii)
more complex hub-spoke network;
(iii)
considering dynamic factors such as the arrival order of the requests;
(iv)
integrated uncertain and stochastic model.



---

*Source: 187275-2014-06-09.xml*