# An Optimization Model of the Single-Leg Air Cargo Space Control Based on Markov Decision Process

Authors: Chun-rong Qin; Li Luo; Yang You; Yong-xi Xiao
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Based on the single-leg air cargo issues, we establish a dynamic programming model to consider the overbooking and space inventory control problem. We analyze the structure of optimal booking policy for every kind of booking requests and show that the optimal booking decision is of threshold type (known as booking limit policy). Our research provides a theoretical support for the air cargo space control.


---

## Body

## 1. Introduction

For the air cargo carrier, the main purpose of implementing seat inventory control in the actual operation is to avoid cargo space being occupied by too many low-value goods, causing the lack of timely transportation of high-value goods and resulting in the loss of some potential gains. In fact, some customers (FITs or agents) who order the space through telephone or network temporarily cancel the booking or directly do not appear while the aircraft is taking off. It brings a lot of losses to the air cargo carrier. In order to reduce the losses caused by the empty cabin, decision makers tend to overbook. However, overbooking too much may lead to greater economic losses. For this reason, during the air cargo overbooking, it is necessary to consider freight revenue, but at the same time decision makers have to consider the cost of overbooking as well. Above all, the decision makers’ aim is to obtain the maximum profit of freight. Usually, most of the goods are transported by single legs (single routes). For some relatively tight (the market demand is greater than supply) segments (routes), it is more suitable for scientific space control and proper overbooking. The problem can be described in detail as follows: in some tight legs, if there are some booking requests, decision makers will decide whether to accept or not. If it is accepted, decision makers will have to set aside proper space to its customers in accordance with the cargo information. Simply put, in the case of implementing overbooking, the goal is to maximize air cargo revenue by properly accepting customers' booking requests.


## 2. Related Literature Review

Based on the analysis of the characteristics of the products, Kasilingam  [1] establishes the air cargo overbooking decision-making model on the case of space capacity random, discusses the production capacity in discrete case and continuous case, and identifies the optimal overbooking for each situation. Kleywegt and Papastavrou [2] use dynamic random backpack model to discuss air cargo revenue management problem. The above-mentioned method can be used to describe the multidimensional problems, but the model is too difficult to solve easily. Luo et al. [3] establish a two-dimensional air cargo overbooking model and then determine the approximate optimal overbooking level. In this model, both the weight attributes and volume attributes are taken into account, and the objective is to minimize freight costs. Moussawi and Cakanyildrima [4] further study the two-dimensional air cargo overbooking model. The objective is to maximize freight revenue. What they do is different from Luo et al. [3]. Considering the benefits of passengers and cargo, Sandhu and Klabjan [5] establish space inventory control model with the static method. On the assumption of fixed volume, using the method of reducing dimension, they get the model’s approximate solution and gain the maximum revenue. Considering the freight forwarders and the delay of cargo transportation, Chew et al. [6] establish a stochastic dynamic programming model of short-term space inventory control, and the objective is to minimize transportation costs. Amaruchkul et al. [7] consider a single-leg air cargo space control problem. Under the random cargo volume and weight, they build a Markov decision process model and take a heuristic algorithm to analyze the model. Considering protocol sale customers and free sale customers, Levin and Nediak [8] build a space inventory control model by using dynamic programming methods, and the purpose is to make maximum total income rooted in the receipt of the goods. Under uncertain environment, Wang and Kao [9] establish an air cargo overbooking model and solve it by the fuzzy systems approach. Taking into account the two different demands of customers, Modarres and Sharifyazdi [10] build a random capacity space inventory control model and get the optimal decision. By analyzing the expected revenue function in dynamic programming model, combining the randomness of cargo volume and weight, Huang and Chang [11] establish a more efficient algorithm in air cargo revenue management problem. Supposing the cargo volume, weight and the yields of the air cargo are random and the cargo space booking process has no aftereffect, Han et al. [12] set up a single-leg air cargo revenue management space allocation model and take the bid control strategy to determine the goods receiving. Amaruchkul and Lorchirachoonkul [13] study the allocation of air transport capacity for the number of freight forwarders, get the probability distribution of the actual use of the transport capacity through discrete Markov chain, and solve the model by dynamic programming methods.By contrast, our work is to consider a single-leg air cargo overbooking and space inventory control problem by dynamic programming. We analyze the structure of optimal booking policy for every kind of booking requests and show that the optimal booking decision is of booking limit policy.


## 3. Model Description

Next we will study the single-leg air cargo space inventory control and overbooking under the conditions of shipping season (the demand is greater than supply). Because of the complexity of the actual situation, in order to abstract practical problems to theoretical issues, we need some basic assumptions.(i)
Aircraft total capacity is fixed (cargo size is unchanged);(ii)
customers’ booking requests are sufficient, namely, the supply is adequate;(iii)
the booking requests are divided into multiple classes;(iv)
each class’s arrival is independent;(v)
there is at most one booking request at any time;(vi)
on the condition that the aircraft is due to take off, whether or not to show up for each booking request is independent;(vii)
each booking request’s weight (volume) is identically independently distributed;(viii)
during whole booking period, accepted booking requests will not be free to cancel.Based on the above assumptions, we will establish mathematical model and make decisions on air cargo. In our model, the main parameters and variables are as follows:t: decision time, 0≤t≤T, where T is a booking period;j: jth class booking request, j=1,2,…,n, where n is the number of booking classes;pjt: the arrival probability of  jth class booking request in time t;p0t=1-∑j=1npjt: probability of no booking request in time t;rj: unit tariff of jth class booking request;ρ: penalty cost because of overbooking resulting in denying a booking  request;yj: cumulative number of the accepted jth class booking request in time t;y=∑j=1nyj: cumulative number of all accepted booking requests in time t;θ: the show-up rate of each accepted booking request near the takeoff;Cw: the maximum available load of the aircraft;Cv: the maximum available volume of the aircraft;W: weight of each booking request in time t;V: volume of each booking request in time t;w-: expected weight of each booking request in time t, namely, E(W);v-: expected volume of each booking request in time t, namely, E(V);λ: IATA required standard density, value of 0.006m3/kg.In order to meet up only one request in a period, we will divide booking lead time into a number of small discrete booking periods.t=0 means that air cargo carrier begins to accept the booking; t=T marks the end of booking, then the air cargo carrier should consider the DB (denying booking) problem.When0<t<T, Ut(y) is the maximum total expected profit given state y in time t. Given t and y, the dynamic programming optimality equation can be written as
(3.1)Ut(y)=∑j=1npjtmax{Ut+1(y+1)+rjmax{w-,v-λ},Ut+1(y)}+p0tUt+1(y)(3.1)’=Ut+1(y)+∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y),0},
where ΔUt(y)=Ut+1(y)-Ut+1(y+1) is the opportunity cost of accepting some class request in time  t. From (3.1)’, it is optimal to accept  jth class booking request in time t if  rjmax{w-,v-/λ}-ΔUt(y)≥0.Obviously,U0(0) is the maximum total expected profit from the beginning of booking to the end of booking. In  t=T, the penalty cost of overbooking is
(3.2)UT(y)=-ρE[(yθW-Cw)++(yθV-Cvλ)+]∀y.The boundary condition (3.2) shows that because of overbooking and relatively fixed capacity, air cargo carrier needs to deny some accepted requests at the end of booking.


## 4. Structural Properties

In (3.2), there exist continuous random variables W and V. The cumulative distribution function and probability density function are  FW(·), FV(·) and fW(·), fV(·), respectively.Next, we will prove thatUt(y) satisfies the following first-order and second-order properties as follows.Property 1.
Δ
U
t
(
y
)
≥
0, namely, Ut(y) is decreasing in y.Proof.
Whent=T,
(4.1)UT(y)=-ρE[(yθW-Cw)++(yθV-Cvλ)+]UT(y)=-ρ[∫Cw/yθ+∞(yθw-Cw)fW(w)dw+∫Cv/yθ+∞(yθv-Cvλ)fV(v)dv]UT(y)=-ρ[yθ∫Cw/yθ+∞wfW(w)dw-Cw∫Cw/yθ+∞fW(w)dwUT(y)+yθλ∫Cv/yθ+∞vfV(v)dv-Cvλ∫Cv/yθ+∞fV(v)dv],∴dUT(y)dy=-ρθ[∫Cw/yθ+∞wfW(w)dw+1λ∫Cv/yθ+∞vfV(v)dv]≤0.
Then,  UT(y) is decreasing in y.
Suppose thatUt+1(y) is decreasing in y. Next, we will show that Ut(y) is decreasing in y.
From (3.1), we can get the conclusion easily. This completes the proof.Property 2.
U
t
(
y
) is concave in  y,  that is, for each given t, ΔUt(y) is increasing in y.Proof.
Whent=T,
(4.2)d2UT(y)dy2=-ρθ[CwyθfW(Cwyθ)Cwθ1y2+1λCvyθfW(Cvyθ)Cvθ1y2]≤0.
ThenΔUT(y) is increasing in y, namely, UT(y) is concave in y.
Suppose thatΔUt(y) is increasing in y. Next, we will show that  ΔUt-1(y)  is increasing in y.
By (3.1)’, we have
(4.3)ΔUt-1(y)=ΔUt(y)+∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y),0}-∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y+1),0}.
Let
(4.4)A=ΔUt(y)+∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y),0},B=-∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y+1),0},∴ΔUt-1(y)=A+B.
ForB, by the above assumption, ΔUt(y+1) is increasing in y, then B is increasing in y.
ForA, suppose that there are m=0,1,…,n classes booking requests satisfying rjmax{w-,v-/λ}≥ ΔUt(y), n-m classes booking requests meeting rjmax{w-,v-/λ}≤ΔUt(y). We may assume that the first m classes in total n satisfy rjmax{w-,v-/λ}≥ΔUt(y), and the last n-m classes satisfy rjmax{w-,v-/λ}≤ΔUt(y). Then,
(4.5)A=ΔUt(y)+∑j=1mpjt(rjmax{w-,v-λ}-ΔUt(y))=ΔUt(y)+∑j=1mpjtrjmax{w-,v-λ}-ΔUt(y)∑j=1mpjt=(1-∑j=1mpjt)ΔUt(y)+∑j=1mpjtrjmax{w-,v-λ}.
By above hypothesis, we know thatΔUt(y) is increasing in y, then A is increasing in y.
From above, we can get:ΔUt-1(y) is increasing in y. This completes the proof.Property 3.
Δ
U
t
(
y
) is decreasing in t, that is,  ΔUt-1(y)≥ΔUt(y).Proof.
From (4.3), we have
(4.6)ΔUt-1(y)-ΔUt(y)=∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y),0}-∑j=1npjtmax{rjmax{w-,v-λ}-ΔUt(y+1),0}=∑j=1npjt{max{rjmax{w-,v-λ}-ΔUt(y),0}-max{rjmax{w-,v-λ}-ΔUt(y+1),0}}.
By Property2, we have ΔUt(y)≤ΔUt(y+1), then ΔUt-1(y)≥ΔUt(y). This completes the proof.Definenjt*=max{y|rjmax{w-,v-/λ}≥ΔUt(y)}, combining Property 3, we have at any time t, as long as y≤njt*, air cargo carrier will accept jth class booking request. And then, we have the following optimal control policy.Theorem 4.1.
The optimal control policy of then classes booking requests is a booking limit policy: it is optimal to accept jth class booking request in time t if y≤njt*, or reject it. Furthermore, the threshold njt* has the following properties:(1)
Ifr1≥r2≥⋯≥rn, njt* is decreasing in j, that is, n1t*≥n2t*≥⋯≥nnt*;(2)
njt* is increasing in t, that is, nj1*≤nj2*≤⋯≤njn*.Proof.
From Properties2 and 3, we can have the conclusions easily. This theorem is verified.The theorem shows that the optimal booking limits are time-dependent and nested in classes. Furthermore, the unit tariff is higher, the optimal booking control policy is more relaxed; the optimal booking limit policy of each class is increasing in time.


## 5. Conclusions

In this paper, we consider a single-leg air cargo overbooking and space inventory control problem. Based on actual problem, we discrete the booking time into small pieces and establish the dynamic space inventory control model of considering overbooking. After some powerful proofs, we get the optimal booking-limit policy for each class of goods.



---

*Source: 235706-2012-11-26.xml*