A column generation algorithm for the choice-based linear programming model for network revenue management

JUAN JOSÉ MIRANDA BRONT; ISABEL MÉNDEZ-DÍAZ; GUSTAVO VULCANO

Rio de Janeiro

Congreso; International Symposium on Mathematical Programming; 2006

UFRJ(Brasil) and Mathematical Programming Society

Capacity-based revenue management (RM) involves controlling fixed and perishable capacity of resources over a finite horizon, with the objective of maximizing revenues. Applications of RM spans service industries like airlines, hotels, railways, cruises, etc. In the last few years, there has been a trend to enrich traditional RM models to account for customer choice behavior. This extension involves both modeling and computational challenges. One possible way of describing choice behavior is to assume that each customer belongs to a segment (which is characterized by a candidate set of products), and that she chooses a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based linear programming (LP) model of van Ryzin and Liu and propose an efficient column generation algorithm that allows to implement the general version of their model, where customers belong to overlapping segments. In this case, the column generation algorithm consists of solving a fractional programming problem. Our results show that the approach has good potential to be applied on real size networks, and that it leads to high quality solutions.