A tractable revenue management model for capacity allocation and overbooking over an airline network

In this paper, we develop a revenue management model to jointly make the capacity allocation and overbooking decisions over an airline network. The crucial observation behind our model is that if the penalty cost of denying boarding to the reservations were given by a separable function, then the optimality equation for the joint capacity allocation and overbooking problem would decompose by the itineraries. We exploit this observation by building an approximation to the penalty cost that is separable by the numbers of reservations for different itineraries. In this case, we can obtain an approximate solution to the optimality equation by plugging the separable approximation into the boundary condition of the optimality equation. Our computational experiments compare our approach with a standard deterministic linear programming formulation, as well as a recent joint capacity allocation and overbooking model. When compared with the standard deterministic linear programming formulation, our approach can provide significant profit improvements. On the other hand, when compared with the recent joint capacity allocation and overbooking model, our approach can provide similar profit performance with substantially shorter runtimes.