A Linear Programming approach for robust network revenue management in the airline industry

The classical revenue management problem consists of allocating a fixed network capacity to different customer classes, so as to maximize revenue. This area has been widely applied in service industries that are characterized by a fixed perishable capacity, such as airlines, cruises, hotels, etc. It is traditionally assumed that demand is uncertain, but can be characterized as a stochastic process (See Talluri and van Ryzin (2005) for a review of the revenue management models). In practice, however, airlines have limited demand information and are unable to fully characterize demand stochastic processes. Robust optimization methods have been proposed to overcome this modeling challenge. Under robust optimization framework, demand is only assumed to lie within a polyhedral uncertainty set (Lan et al. (2008); Perakis and Roels (2010)). In this paper, we consider the multi-fare, network revenue management problem for the case demand information is limited (i.e. the only information available is lower/upper bounds on demand). Under this interval uncertainty, we characterize the robust optimal booking limit policy by use of minimax regret criterion. We present an LP (Linear Programming) solvable mathematical program for the maximum regret so our model is able to solve large-scale problems for practical use. A genetic algorithm is proposed to find the booking limit control to minimize the maximum regret. We provide computational experiments and compare our methods to existing ones. The results demonstrate the effectiveness of our robust approach.