A single-resource revenue management problem with random resource consumptions

Abstract

We study a single-resource multi-class revenue management problem where the resource consumption for each class is random and only revealed at departure. The model is motivated by cargo revenue management problems in the airline and other shipping industries. We study how random resource consumption distribution affects the optimal expected profit and identify a preference acceptance order on classes. For a special case where the resource consumption for each class follows the same distribution, we fully characterize the optimal control policy. We then propose two easily computable heuristics: (i) a class-independent heuristic through parameter scaling, and (ii) a decomposition heuristic that decomposes the dynamic programming formulation into a collection of one-dimensional problems. We conduct extensive numerical experiments to investigate the performance of the two heuristics and compared them with several widely studied heuristic policies. Our results show that both heuristics work very well, with class-independent heuristic slightly better between the two. In particular, they consistently outperform heuristics that ignore demand and/or resource consumption uncertainty. Our results demonstrate the importance of considering random resource consumption as another problem dimension in revenue management applications.

Appendix

Proof of Theorem 1

• We only show the proof for convex order. The proof for usual stochastic order follows similarly. (a) We first show that v _T+1(x̃)⩽v _T+1(x) if Y _x̃ ⩾ _cx Y _x . Note that

  

  where the inequality follows from the facts that Y _x̃ ⩾ _cx Y _x and h(·) is convex.

  Assume that v _t+1(x̃)⩽v _t+1(x) if Y _x̃ ⩾ _cx Y _x , and we need to show that v _t (x̃)⩽v _t (x). By (5), the key is to show that T _k v _t+1(x̃)⩽T _k v _t+1(x), ie,

  

  Note that and , thus by the closure property of convex order and v _t+1(x̃+e _k )⩽v _t+1(x+e _k ) by induction assumption. Therefore (A.1) holds true, ie, T _k v _t+1(x̃)⩽T _k v _t+1(x) given Y _x̃ > _cx Y _x . It follows that

  

  and we have shown that v _t (x̃)⩽v _t (x) if Y _x̃ ⩾ _cx Y _x .

  (b) The result follows from (a) immediately as Y _x +A _i ⩾ _cx Y _x +A _j given A _i ⩾ _cx A _j . Therefore, v _t (x+e _i )⩽v _t (x+e _j ) and Δ _i v _t (x)⩾Δ _j v _t (x).

  (c) Suppose A _i ⩾ _cx A _j and r _j ⩾r _i , that is, class-j is ranked higher than class-i. By (b), we have Δ _i v _t (x)⩾Δ _j v _t (x) if A _i ⩾ _cx A _j . Therefore the result follows directly from

  

  that is, if it is optimal to accept a class-i request at state (x, t), then it is also optimal to accept a class-j request which is ranked higher than class-i. □

Proof of Lemma 2

• First we use coupling arguments to prove that the terminal function v _T+1(x)=−E[h(Y _x )] preserves submodularity for any nondecreasing and convex h(·).

  Let f(x)=−v _T+1(x) represent the penalty cost given the state x at period T+1. Submodularity of v _T+1(x) is equivalent to

  

  which says that the marginal cost of accepting a class-1 request at state x is lower than that of at state x+e ₂. Consider two systems with system 1 at state x and system 2 at state x+e ₂; and the arrival processes and random resource requirements of the two systems are coupled. We compare the marginal cost of accepting a class-1 request for the two systems. There are three cases: (1) both the total resource requirement of accepting a class-1 demand at state x and that of accepting another class-1 at state x+e ₂ do not exceed the capacity; (2) the total resource requirement of accepting a class-1 demand at state x is within the capacity, while that of accepting a class-1 at state x+e ₂ exceeds the capacity; (3) both have exceeded the capacity. In the first case, the marginal costs of system 1 and system 2 are the same; while in the second and third case, the marginal cost of system 1 is less than that of system 2 for the linear cost function. Therefore (A.2) is true and submodularity holds for v _T+1(x).

  Now assume that Δ₁ v _t+1(x ₁, x ₂)⩽Δ₁ v _t+1(x ₁, x ₂+1) and we need to show that submodularity holds for v _t (x ₁, x ₂), which is essentially reduced to show that Δ₁ T _i v _t+1(x ₁, x ₂)⩽Δ₁ T _i v _t+1(x ₁, x ₂+1), i=1, 2. We will adopt an approach introduced by Zhuang and Li (Lemma 2, 2010) to prove the propagation of structural properties on the control operator T _i .

  (a) T ₁ v _t+1(x ₁, x ₂)−T ₁ v _t+1(x ₁+1, x ₂)⩽T ₁ v _t+1(x ₁, x ₂+1)−T ₁ v _t+1(x ₁+1, x ₂+1), ie,

  

  Since

  

  where the inequalities follow from submodularity of v _t+1 (x ₁, x ₂) that

  

  Therefore (A.3) holds true by Lemma 2 (Zhuang and Li, 2010).

  (b) T ₂ v _t+1(x ₁, x ₂)−T ₂ v _t+1(x ₁+1, x ₂)⩽T ₂ v _t+1(x ₁, x ₂+1)−T ₂ v _t+1(x ₁+1, x ₂+1), ie,

  

  Since

  

  where the inequalities follow from submodularity of v _t+1(x ₁, x ₂) that

  

  hence (A.4) holds true. Therefore submodularity holds for v _t (x ₁, x ₂), ie, Δ₁ v _t (x ₁, x ₂)⩽Δ₁ v _t (x ₁, x ₂+1). □

Proof of Theorem 2

• The structure of the optimal control policy presented in Theorem 2 follows directly from the submodularity of v _t (x ₁, x ₂), which is proved in Lemma 2. □

Proof of Lemma 3

• (a) First we show that Δṽ _T+1(x)⩽Δṽ _T+1(x+1), ie,

  

  Note that (A.5) is equivalent to

  

  which is true since h(·) is convex. Hence, Δṽ _T+1(x)⩽Δṽ _T+1(x+1) holds. Assume that Δṽ _t+1(x)⩽Δṽ _t+1(x+1) and we need to show that Δṽ _t (x)⩽Δṽ _t (x+1). The key is to show that ΔT _i ṽ _t+1(x)⩽ΔT _i ṽ _t+1(x+1), where T _i ṽ _t+1(x)=max{ṽ _t+1(x+1)+r _i , ṽ _t+1(x)}. That is,

  

  which follows by

  

  Therefore Δṽ _t (x)⩽Δṽ _t (x+1) holds by Lemma 2 (Zhuang and Li, 2010).

  (b) Note that

  

  where the last inequality follows by Δṽ _t+1(x)⩽Δṽ _t+1(x+1). □

Proof of Theorem 3

• (a) Given that r _i ⩾r _j . By Δṽ _t+1(S _it ^*)>r _i ⩾r _j , it follows that S _it ^*⩾S _jt ^*.

  (b) By Lemma 3(b), we have Δṽ _t (S _it ^*)⩾Δṽ _t+1(S _it ^*)>r _i and it follows that S _it ^*⩾S _i,t−1 ^*. □

Proof of Lemma 4

• The proof follows similar arguments as that of Lemma 3 and thus is omitted. □