|
Article Excerpt
During the past few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose 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, deterministic, linear programming model (CDLP) of Gallego et al. (2004) [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York], and the follow-up dynamic programming decomposition heuristic of van Ryzin and Liu (2008) [van Ryzin, G. J., Q. Liu. 2008. On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2) 288-310]. We focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-hard and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective and that the overall approach leads to high-quality, practical solutions.
Subject classifications: analysis of algorithms: computational complexity; marketing: choice models; programming: fractional, linear applications.
Area of review: Transportation.
History: Received March 2007; revisions received September 2007. December 2007; accepted December 2007. Published online in Articles in Advance March 30, 2009.
1. Introduction
Capacity control-based revenue management (RM) involves controlling a fixed and perishable capacity of resources over a finite horizon, with the objective of maximizing revenues. Applications of RM include service industries such as airlines, hotels, railways, cruises, etc. In this paper, we will use the terminology for the airline application as representative of the problem.
Traditionally, RM systems have been built upon the independent demand model assumption. This assumption views demand as a sequence of requests for products, which are insensitive to the capacity controls applied by an airline, and to market conditions such as prices offered by competitors, frequency of departures, brand preference of the customers, etc. (see, e.g., Talluri and van Ryzin 2004a for further details). Under the independent demand model assumption, it is also generally assumed that low fare demand comes first. Thus, an airline's problem is posed as: How much capacity should be reserved for the high fare demand that will come later? There is wide agreement nowadays about the limitations of this assumption, based on the observation that the sale of a product is indeed the outcome of a customer's purchase decision subject to market conditions. Furthermore, the expansion of low-cost airlines offering simplified, undifferentiated fare structures, and their usual strategy of saturating a market with several flights during the day, has raised the interest in formally capturing customer choice behavior in RM systems.
Accounting for customer choice behavior involves two main challenges. The first is to model the choice decision of a customer at a particular moment in time, and to estimate the parameters that describe that decision. The second is to incorporate this sophisticated demand model in the optimization module of an RM system, so that the availability controls explicitly account for customer choice behavior.
A very interesting piece of work on this second aspect is the paper by Gallego et al. (2004). They propose a choice-based deterministic linear programming (CDLP) model for network RM, which is the choice-based analog of the deterministic linear programming (DLP) model of traditional RM. Although their formulation is for the case of flexible product offerings, where the firm has the flexibility of offering a collection of products to serve market demand, its application for choice-based RM is straightforward: It includes offer sets, i.e., sets of products offered by the seller at different points in time during the booking horizon, thus restating the problem as: Which alternatives should the firm make available to the customers to profitably influence their choices? The decision variables are the lengths of time during which the different offer sets must be available. One limitation of their approach is that the market demand model does not allow any kind of segmentation.
In a follow-up paper, van Ryzin and Liu (2004) present two approaches to implement the outcome of the CDLP. In the first approach, the primal solution of the CDLP is applied right away, and the offer sets remain available for the length of time indicated by the values of the decision variables. The other approach uses the optimal dual variables in a decomposition scheme that splits the global network problem into a collection of computationally tractable leg-level problems. They present a market segmentation model in which each customer belongs to one specific segment. In their case, the segments are defined by disjoint consideration sets of products. Their results show that the decomposition heuristic produces significant improvements in revenue compared to a direct application of the CDLP primal solution. They also compare the revenue gap of both approaches with respect to results obtained under the traditional independent demand assumption, and verify that the decomposition heuristic consistently outperforms the latter, while the performance of CDLP is mixed.
Motivated by the appealing ideas of Gallego et al. (2004) and the promising results of van Ryzin and Liu (2004), in this paper, we consider the extension of the CDLP--and its derivations--to the general case of overlapping segments (i.e., segments whose corresponding consideration sets have a nonempty intersection). In Gallego et al. (2004), the absence of market segments eliminates the different preference weights that different customers could have for the same product. In van Ryzin and Liu (2004), the restriction imposed in the numerical experiments is a strong one because it partitions the space of products among different customer segments. For example, consider a simple airline market with two parallel flights (say, one morning flight and one afternoon flight), and two fare classes (high and low) per flight. One segment could be defined by time-sensitive customers, with a strong morning preference, i.e., customers who prefer to pay the low fare, but are eventually willing to pay the high fare for the morning flight. Another segment could be defined by price-sensitive customers, that will go for the lowest available fare, no matter the time. Clearly, the preference order is different for these two types of customers (which is precluded in the model of Gallego et al. 2004), and the product "morning flight, low fare class" belongs simultaneously to both consideration sets (which is not allowed in the model of van Ryzin and Liu 2004). Certainly, allowing for overlapping segments would be a more natural fit for modeling real situations of market segmentation, and constitutes a strong limitation of the previous two papers. The cases known so far where the CDLP model and its derivations can be solved efficiently are very restrictive. In this paper, we present a method that closes the gap between the CDLP framework and its real practical potential.
As in van Ryzin and Liu (2004), we also focus on the multinomial logit (MNL) choice model of demand, a model widely used in the marketing and economics literature. The main difficulty suffered by their approach from a computational standpoint is solving the CDLP efficiently by column generation. Indeed, it turns out that the column generation subproblem is difficult on its own. A structurally similar problem to the column generation one arises in the operational policy derived from the decomposition algorithm, when the firm needs to dynamically compute the next offer set to exhibit. As van Ryzin and Liu (2004) show in [section]6.3, for the case of nonoverlapping segments, this can be done in polynomial time. For the more general case of overlapping segments, the problem is of the fractional-programming type. Our theoretical contribution is a negative result in this regard: even the column generation subproblem is NP-hard. The proof that we present here relies on a polynomial transformation from the minimum vertex cover problem, which is well known to be NP-hard.
Being able to solve, or at least approximately solve, the column generation subproblem in an efficient way has broader implications than the clear benefit that it would bring to our methodology. For example, in a marketing science framework, our column generation subproblem is equivalent to the problem faced by a seller that receives streams of customers from overlapping segments, and needs to decide the optimal assortment of products to offer in order to maximize the instantaneous revenue rate, when the product prices are fixed.
To provide a polynomial algorithm for the column generation subproblem, we use a greedy heuristic that performs quite well in practice, from the perspective of computational speed as well as quality of solutions, finding optimal outcomes in most of the cases that we considered.
The main practical contribution of our paper is illustrated by computational experiments. We ran an exhaustive series of computational tests extending the decomposition heuristic of van Ryzin and Liu (2004) to the overlapping segment case, and compared its performance with CDLP a randomized variation of CDLP, and a reoptimization scheme that uses elements of both the decomposition heuristic (DCOMP) and the primitive CDLP. Our results are somewhat aligned with the findings of van Ryzin and Liu (2004): DCOMP outperforms the other methods, especially in scarce capacity settings. However, the other methods show a good revenue performance, outperforming the behavior of the independent demand model assumption generally by more than 10%, indeed showing that choice behavior is a first-order effect from a revenue management perspective.
Our experiments also show the practical feasibility of this approach by providing the computational times of the different methods. The speed for solving the column generation subproblem gives a strong support for the potential of the choice-based methods. The decomposition heuristic is clearly the most time-consuming method, taking around 8 to 10 minutes in a small to medium network setting (four nodes, seven legs, 11 products, 10 customer segments). However, its core involves building off-line a big two-dimensional table to be used later on when computing in real time the offer sets. This is indeed a batch process that is typically run overnight by the airlines, and hence it is still practically feasible. Nevertheless, if time becomes an issue for larger networks, the computational times for solving the CDLP approximately or the times given by the other methods are at least an order of magnitude shorter, hence constituting an interesting alternative considering the high quality of the solutions obtained.
The remainder of this paper is organized as follows. In [section]2. we review the related literature. In [section]3, we introduce the stochastic model and the related choice-based linear programming formulation CDLP. Section 4 presents our approach for solving the column generation subproblem derived from CDLP. Our main theoretical result, the NP-hardness of this subproblem, is included here. Section 5 describes the decomposition heuristic and explains the difficulty of solving each of the leg-level problems exactly in polynomial time. Our numerical results are reported in [section]6, and we conclude in [section]7.
2. Literature Review
A complete description of traditional network RM models can be found in Talluri and van Ryzin (2004a, Chapter 3). As was pointed out before, these methods typically work under the independent demand model paradigm, which is understood nowadays as a serious limitation for modeling customer behavior.
The interest in enriching these models with...
|
