Accelerating Revenue Optimisation for Customers Choosing between Product Alternatives
This page is based on the following article:
Meissner, J., Strauss, A. and Talluri, K. 2013. "An Enhanced Concave Program Relaxation for Choice Network Revenue Management". Production & Operations Management 22(1) 71-87.
Service providers such as airlines, trains or hotels sell products that require capacity of one or several resources out of a network of flight legs, train itinerary segments or room nights. Until recently, it was common to assume that one can partition the set of products into disjoint subsets corresponding to customer segments, particularly because this greatly simplifies the optimisation problem of when to offer which products. However, it is more realistic that some products might be considered for purchase by customers from different segments, e.g. business customers willing to buy down to a cheaper economy product if it becomes available. Hence, there are complex interactions of demand between such customer segments which make the revenue optimisation problem hard to solve.
Solution in 10 minutes instead of 10 hours
The network choice revenue management problem models customers as choosing from an offerset, and the firm decides the best subset to offer at any given moment to maximize expected revenue. The resulting dynamic program for the firm is intractable and approximated by a deterministic linear program called the CDLP which has an exponential number of columns. However, under the choice-set paradigm when the segment consideration sets overlap, the CDLP is difficult to solve. Column generation has been proposed but finding an entering column has been shown to be NP-hard.
In this work, starting with a concave program formulation based on segment-level consideration sets called SDCP, we add a class of constraints called product constraints, that project onto subsets of intersections. In addition we propose a natural direct tightening of the SDCP called κSDCP, and compare the performance of both methods on the benchmark data sets in the literature. Both the product constraints and the κSDCP method are very simple and easy to implement and are applicable to the case of overlapping segment consideration sets. In our computational testing on the benchmark data sets in the literature, SDCP with product constraints achieves the CDLP value at a fraction of the CPU time taken by column generation and we believe is a very promising approach for quickly approximating CDLP when segment consideration sets overlap and the consideration sets themselves are relatively small. For test networks with two hubs as depicted above (though with up to 16 spokes, 68 flight legs and close to 3,000 products), CDLP required more than 10 hours, whereas our approach based on product constraints required only about 10 minutes to obtain almost the same objective.