Robust Optimization Approach in Revenue Management

Robust Optimization Approach in Revenue Management

By Zheyu Jiang
School of Business Administration, South China University of Technology, Guangzhou, China

Robust Optimization Approach in Revenue Management — A Subject Review

Revenue management is one of the classical topics in operations research. In last decade, robust optimization methodology motivated a rapidly growing amount of literature on robust revenue management. This stream of research does not rely on strict prior assumptions on the distribution of random demand as defined in classical revenue management theory but, it is all about the system being capable to maintain tractability and to derive interesting structural properties of the optimal solution.

The Concept of Classical Revenue Management

In the book, The Theory and Practice of Revenue Management (Talluri, K.T., and Van Ryzin, G.J. (2005) Springer, New York), classical revenue management is classified according to control methods. The first type is to manage revenue by capacity control (quantity-based revenue management). Researchers seek to design optimal method to allocate limited capacity to different classes or bundles of demand at given prices. Two successful examples are managing the sales of different fare classes on flights or controlling the sales of different rooms in hotels. The other type is to control sales by setting right prices (price-based revenue management). Research in this field is based on the classical assumption in the economy which demands of one product is affected by its price. By dynamically setting prices, the firms can control the demand and sales of their products. In this article, we aim to introduce basic research questions and control methods in revenue management, thus we just review some fundamental papers in revenue management.

Capacity Control

Managers apply robust control in revenue management by allocating the capacity of one or multiple resources to different classes of demand. In most cases, demands from different customers are classified by prices that they offer. For example, in single-leg flight capacity control problem, airline allocates all seats to different classes of customers who are classified by prices they offer. 

In classical revenue management theory, there are three basic capacity-based controls to allocate capacity: booking limits, protection levels, and bid prices. Booking limits are controls that limit the amount of capacity that can be sold to any particular class at a given point in time. To increase the utilization of capacity, firms prefer to set nested booking limit. Protection levels specify an amount of capacity to reserve for a particular class or set of classes.

Similarly, firms prefer to set nested protection levels. Booking limit and protection levels are alternative controls. Bid prices are one control method that firms set a threshold price such that a request is accepted if its revenue exceeds the threshold price and rejected otherwise. The textbook by Talluri and Ryzin (as mentioned above), offers detailed overview and references about capacity-based revenue management.

Pricing Control

Price control is a more natural mechanism in practice. Managers apply it by setting appropriate prices to control demand and optimize revenue. Pricing control includes different forms such as personalized pricing, markdowns, display and trade promotions, coupons and discounts, clearance sales, auctions and price negotiations.

To optimize policies with uncertain demand, researchers have developed stochastic models to study on price-based revenue management. Single-product dynamic pricing is one basic research problem in revenue management which establishes a theoretical basis for more complex problems. 

Gallego, G. and van Ryzin, G. (1994), were the first to study dynamic pricing problem of a single product over a finite sales horizon gave a fixed inventory at the start of the sales horizon. They formulate the problem using intensity control and obtain structural monotonicity results for the optimal intensity as a function of the stock level and the length of the horizon. They also find optimal pricing strategy in closed form for one particular exponential family of demand functions and prove that simply fixed price policies are asymptotically optimal as the expected sales tend to infinity. 

But, Feng, Y. and Gallego, G. (1995), has taken the two-price model as an example, where prices are fixed in each period and firms can only decide to switch from one to the other, obtain structural properties of the optimal stopping time problem. They prove that the optimal policy is of a threshold type.

To learn more about Classical Revenue Management and its evolution, kindly refer to the followings:

There are some other detailed textbooks or literature on classical dynamic pricing problem, see 

[2] Talluri, K.T. and Van Ryzin, G.J. (2005) The Theory and Practice of Revenue Management. Springer, New York.

For more recent research, 

[3] Ben-Tal, El Ghaoui, L.and Nemirovski, A. (2009) Robustness Optimization. Princeton University Press, Princeton. 

It provides an in-depth overview of the available literature on dynamic pricing and learning. 

Whereas, the below-mentioned book identifies most recent trends in dynamic pricing research involving pricing with multiple products, pricing with competition and pricing with limited information.

[4] Chen, M. and Chen, Z.-L. (2015) Recent Developments in Dynamic Pricing Research: Multiple Products, Competition, and Limited Demand Information. Production and Operations Management, 24, 704-731. 

Robust Revenue Management

In this section, we will first explain some advantages of robust revenue management comparing to classical revenue management. First, robust revenue management does not require much prior knowledge. Robust capacity control or price control can be employed with limited or without prior data about uncertainty. This allows robust control to be applied in situations which is more difficult to collect data. For example, in ocean freight industry, firms often set prices by unofficial and infrequent negotiation (for example, see "Fractional Price Matching Policies Arising from the Ocean Freight Service Industry. Production and Operations Management"). Secondly, robust revenue management shows computational tractability and efficiency. For example, the authors of the article "Dynamic Pricing to Minimize Maximum Regret. Production and Operations. Management", has discussed the development of polynomial time algorithm to solve robust dynamic pricing problem.

Robust Capacity Control

Perakis, G. and Roels, G. (2010) prove that when the seller knows only the upper and lower bounds of the demand, the network revenue management problem (multiple products use multiple resources) using maximin and the minimax regret criteria are both NP-hard. Then they discuss several special but tractable revenue network: single resource revenue management, bundle revenue management. Finally, a heuristic algorithm is given for general cases. Birbil, S.I., Frenk, J.B.G., Gromicho, J.A.S. and Zhang, S. (2009) respectively discusses a robust version of static and dynamic single resource capacity allocation and designs polynomial time algorithm. 

Ball, M. and Queyranne, M. (2009) introduced competitive ratio criteria to robust revenue management from the perspective of an online algorithm in computing science. For two fare classes, multiple fare classes and bid-price controls problem, they obtain the lower bounds of competitive ration and corresponding protection level or bidding price. Notice that, they assume that the seller knows no information about uncertain demand.

Lan, Y., Gao, H., Ball, M. and Karaesmen, I. (2008) employs competitive analysis to study single resource multi-fare revenue management problem. Authors have assumed that the seller knows only the upper and lower bounds of the demand for each product. The competition ratio and absolute regret value are taken as performance criteria. They prove that the optimal capacity control policies under both criteria are nested booking limit. 

Lan, Y., Ball, M. and Karaesmen, I. (2011) studies the robust version of another classical problem in revenue management―overbooking. They develop a model of overbooking and fare-class allocation in multi-fare, single? resource problem. They obtain optimal overbooking levels and booking limits in closed form which are nested. 

Maglaras, C. and Eren, S. (2015), in order to avoid the spiral drop effect produced by "truncated" demand, uses entropy to estimate the total demand and introduce the capacity control revenue management problem of the two products. Finally, the convergence of the algorithm is proved.

Robust Pricing Control

Thiele, A. (2006) establishes a robust optimization model for the single product dynamic pricing problem, where uncertain demand belongs to a given polyhedron uncertainty set. Then, it obtains the tractable convex optimization form which is equivalent to the original model. The new form has only one new variable called reference price variable. The article shows that when the uncertainty of demand increases, the optimal price is gradually converging to the reference price. They also show that if the price is low and the uncertainty is strong, the price below the nominal value is not the most important decision. Thiele uses the same modeling method to solve the multi-product pricing problem and shows that when the product uses the same resource, the equivalent pricing form is inverse convex programming. When a product uses multiple resources at the same time, the equivalent form is non-convex programming. Next, he proposed the lower bound for the second problem.

Bergemann, D. and Schlag, K. (2011) studies monopoly pricing problem under incomplete information. The seller only knows that the real demand belongs to one given uncertainty set. They compare two models with two different objectives, maximizing minimal utility and minimizing maximal regret value. They prove that the equilibrium price under two goals is lower than the price when demand is fixed. In order to ensure the robustness of decision-making, the seller needs to pay more information rents (information rent). Earlier in 2008, the same authors discussed how the seller set price when the seller knows the least information about the demand, that is when the support of the consumer value is only known. The objective of the model is to minimize the maximal regret value. The article shows that consumers with the lower value will be excluded from the market at high prices.

Lim, A.E.B. and Shanthikumar, J.G. (2007) studied the dynamic pricing problem of a single product. Unlike the previous ones, the paper studies Markovian pricing strategy and uses the notion of relative entropy to represent the uncertainty in demand rate model. In this paper, they use the probability measure knowledge of point process to transform the original model and get the solvable reformulation. Finally, Isaacs equation for stochastic differential games is applied to obtain optimal pricing policy. In particular, they give the closed-form solutions for the exponential nominal demand rate model. Later in 2010, along with T. Watewai, authors extended their own modeling method (2007) to multi-product case. The paper considers that the demand for different products have different levels of uncertainty and proves that this problem is equivalent to a risk-sensitive dynamic pricing problem. Under some additional assumptions, they show some features of the model and characterize the revenue sharing rule which leads to the equivalence between the risk-sensitive pricing problem.

Chen, Z.L., Hall, N.G. and Keller, H. (2017) proposes a polynomial time algorithm for the two-stage dynamic pricing model under minimizing the maximal regret value. Eren, S.S., and Maglaras, C. (2010) study the problem of robust pricing under a limited information or different learning ability and establishes a model with the objective of minimizing the competition ratio (competitive ratio). For each situation, the optimal solution in the form of closed-form is given. 

Chen, Y.W., and Farias, V.F. (2016) studied the dynamic pricing problem of strategic consumers and designed an approximate algorithm to solve it. Numerical results show that this kind of control has greatly improved the average revenue compared with previous studies.

Unlike above research, Perakis, G. and Sood, A. (2006) study the dynamic pricing problem of multiple products with oligopoly. Such a model is a parametric pricing strategy, that is, the parameter of the demand function is uncertain which belongs to a given polyhedron set. It is proved that the solution of the model is equal to the solution of the system of quasi-variational inequalities, and it is proved that there exists an equilibrium solution for the inequality group. Finally, the iterative learning algorithm is designed to find out the equilibrium solution.

The Future

First, there is still a gap between classical revenue management theory and robust revenue management. For example, there are few kinds of literature on robust auction mechanism design. Comparing to dynamic pricing problem, in the auction problem, one customer offers a price to bid one product and then firms decide which bids to accept. Auctioning problems are common in practice. This mechanism has been applied in many industries such as used cars, art, real state, and electricity etc. In classical auction theories, equilibrium strategies are based on some prior assumptions of uncertain factors, for example, the distribution of customer’s private evaluation. These assumptions may not be satisfied in reality, this study on robust auction mechanism is of great importance.

Second, data-driven research provides a new methodology for classical revenue management. With the rapid growth of IT, the researcher is facing a new era when an enormous amount of data are generated and stored. "Big data" era presents new opportunities as well as challenges for researchers in different fields including revenue management. For example, Cohen, M.C., Lobel, R., and Perakis, G. (2014) study a dynamic pricing problem to determine a robust and dynamic pricing strategy. Comparing to existing work, they develop a tractable optimization model which can directly use demand sample data. In addition to their work, it is interesting to see how capacity control and pricing control can be extended in the robust data-driven setting.

 This article is an excerpt taken from a research article, titled - "Robust Capacity Control in Revenue Management: A Literature Review", published at Open Journal of Business and Management, under creative commons license.