An LP based Approximate Dynamic Programming Model to Address Airline Overbooking under Cancellation, Refund, and No-Show

Abstract

In this paper we simultaneously address four constraints, namely, flight cancellation, customer no-shows, overbooking, and refunding, relevant to the airline revenue management problem. We develop a linear program with close relation to the dynamic program of the problem, which we later use to approximate the optimal decision rule for rejecting, or accepting customers. We first provide a novel proof for the fact that the optimal objective function of this linear program, is always an upper bound for the dynamic program. Secondly, we construct a decision rule based on this linear program, and prove that it is asymptotically optimal, under certain circumstances. Finally, using Monte Carlo simulation, we numerically demonstrate that, in fact the result of the linear programming policy, presented, in this paper has a short distance to the upper bound of the optimal answer, which makes it a fairly good approximate answer to the intractable dynamic program.