Network revenue management with inventory-sensitive bid prices and customer choice

We develop an approximate dynamic programming approach to network revenue management models with customer choice that approximates the value function of the Markov decision process with a non-linear function which is separable across resource inventory levels. This approximation can exhibit significantly improved accuracy compared to currently available methods. It further allows for arbitrary aggregation of inventory units and thereby reduction of computational workload, yields upper bounds on the optimal expected revenue that are provably at least as tight as those obtained from previous approaches. Computational experiments for the multinomial logit choice model with distinct consideration sets show that policies derived from our approach can outperform some recently proposed alternatives, and we demonstrate how aggregation can be used to balance solution quality and runtime.     

Structural properties of Markov modulated revenue management problems

The admission decision is one of the fundamental categories of demand-management decisions. In the dynamic model of the single-resource capacity control problem, the distribution of demand does not explicitly depend on external conditions. However, in reality, demand may depend on the current external environment which represents the prevailing economic, financial, social or other factors that affect customer behavior. We formulate a Markov Decision Process (MDP) to maximize expected revenues over a finite horizon that explicitly models the current environment. We derive some structural results of the optimal admission policy, including the existence of an environment-dependent thresholds and a comparison of threshold levels in different environments. We also present some computational results which illustrate these structural properties. Finally, we extend some of the results to a related dynamic pricing formulation.     

Dynamic cruise ship revenue management

Recently, it has been recognized that revenue management of cruise ships is different from that of airlines or hotels. Among the main differences is the presence of multiple capacity constraints in cruise ships, i.e., the number of cabins in different categories and the number of lifeboat seats, versus a single constraint in airlines and hotels (i.e., number of seats or rooms). We develop a discrete-time dynamic capacity control model for a cruise ship characterized by multiple constraints on cabin and lifeboat capacities. Customers (families) arrive sequentially according to a stochastic process and request one cabin of a certain category and one or more lifeboat seats. The cruise ship revenue manager decides which requests to accept based on the remaining cabin and lifeboat capacities at the time of an arrival as well as the type of the arrival. We show that the opportunity cost of accepting a customer is not always monotone in the reservation levels or time. This non-monotone behavior implies that “conventional” booking limits or critical time periods capacity control policies are not optimal. We provide analysis and insights justifying the non-monotone behavior in our cruise ship context. In the absence of monotonicity, and with the optimal solution requiring heavy storage for “large” (industry-size) problems, we develop several heuristics and thoroughly test their performance, via simulation, against the optimal solution, well-crafted upper bounds, and a first-come first-served lower bound. Our heuristics are based on rolling-up the multi-dimensional state space into one or two dimensions and solving the resulting dynamic program (DP). This is a strength of our approach since our DP-based heuristics are easy to understand, solve and analyze. We find that single-dimensional heuristics based on decoupling the cabins and lifeboat problems perform quite well in most cases.     

Risk-sensitive capacity control in revenue management

Both the static and the dynamic single-leg revenue management problem are studied from the perspective of a risk-averse decision maker. Structural results well-known from the risk-neutral case are extended to the risk-averse case on the basis of an exponential utility function. In particular, using the closure properties of log-convex functions, it is shown that an optimal booking policy can be characterized by protection levels, depending on the actual booking class and the remaining time. Moreover, monotonicity of the protection levels with respect to the booking class and the remaining time are proven.     

An option-based revenue management procedure for strategic airline alliances

An airline has to decide whether to accept an incoming customer request for a seat in the airplane or to reject it in hope that another customer will request the seat later at a higher price. Capacity control, as one of the instruments of revenue management, gives a solution to this decision problem. In the presence of strategic alliances capacity control changes. For the case of two airlines in the alliance and a single flight leg we propose an option-based capacity control process. The determination of booking limits for capacity control is done with real options. A simulation model is introduced to evaluate the booking process of the partner airlines within the strategic alliance, considering the option-based procedure. In an iterative process the booking limits are improved with simulation-based optimization. The results of the option-based procedure will be compared with the results of the simulation-based optimization, the results of a first-come-first-served (FCFS) approach and ex post optimal solutions.     

On the structural properties of a discrete-time single product revenue management problem

We consider a multi-period revenue management problem in which multiple classes of demand arrive over time for the common inventory. The demand classes are differentiated by their revenues and their arrival distributions. We investigate monotonicity properties of varying problem parameters on the optimal reward and the policy.     

Integrated capacity and inventory management with capacity acquisition lead times

We model a make-to-stock production system that utilizes permanent and contingent capacity to meet non-stationary stochastic demand, where a constant lead time is associated with the acquisition of contingent capacity. We determine the structure of the optimal solution concerning both the operational decisions of integrated inventory and flexible capacity management, and the tactical decision of determining the optimal permanent capacity level. Furthermore, we show that the inventory (either before or after production), the pipeline contingent capacity, the contingent capacity to be ordered, and the permanent capacity are economic substitutes. We also show that the stochastic demand variable and the optimal contingent capacity acquisition decisions are economic complements. Finally, we perform numerical experiments to evaluate the value of utilizing contingent capacity and to study the effects of capacity acquisition lead time, providing useful managerial insights.     

A revenue management model for products with two capacity dimensions

Many perishable products and services have multiple capacity attributes. Shipping capacity of container liners, for example, is measured by both volume and weight. Containers with different size consume various capacities in the two dimensions. Restaurant revenue management aims to maximize the revenue per available seat-hour that captures both the number of dining tables and service manpower. Similar issues arise in the air cargo, trucking and health care industries.     

Revenue management approach to stochastic capacity allocation problem

To formulate stochastic capacity allocation problems in a manufacturing system, the concept and techniques of revenue management is applied in this research. It is assumed the production capacity is stochastic and hence its exact size cannot be forecasted in advance, at the time of planning. There are two classes of “frequent” and “occasional” customers demanding this capacity. The price rate as well as the penalty for order cancellation caused by overbooking is different for each class. The model is developed mathematically and we propose an analytical solution method. The properties of the optimal solution as well as the behavior of objective function are also analyzed. The objective function is not concave, in general. However, we prove it is a unimodal function and by taking advantage of this property, the optimal solution is determined.     

Mathematical programming models for revenue management under customer choice

We study a network airline revenue management problem with discrete customer choice behavior. We discuss a choice model based on the concept of preference orders, in which customers can be grouped according to a list of options in decreasing order of preference. If a customer’s preferred option is not available, the customer moves to the next choice on the list with some probability. If that option is not available, the customer moves to the third choice on the list with some probability, and so forth until either the customer has no other choice but to leave or his/her request is accepted. Using this choice model as an input, we propose some mathematical programs to determine seat allocations. We also propose a post-optimization heuristic to refine the allocation suggested by the optimization model. Simulation results are presented to illustrate the effectiveness of our method, including comparisons with other models.     

Improved bid prices for choice-based network revenue management

One of the latest developments in network revenue management (RM) is the incorporation of customer purchase behavior via discrete choice models. Many authors presented control policies for the booking process that are expressed in terms of which combination of products to offer at a given point in time and given resource inventories. However, in many implemented RM systems—most notably in the hotel industry—bid price control is being used, and this entails the problem that the recommended combination of products as identified by these policies might not be representable through bid price control. If demand were independent from available product alternatives, an optimal choice of bid prices is to use the marginal value of capacity for each resource in the network. But under dependent demand, this is not necessarily the case. In fact, it seems that these bid prices are typically not restrictive enough and result in buy-down effects.We propose (1) a simple and fast heuristic that iteratively improves on an initial guess for the bid price vector; this first guess could be, for example, dynamic estimates of the marginal value of capacity. Moreover, (2) we demonstrate that using these dynamic marginal capacity values directly as bid prices can lead to significant revenue loss as compared to using our heuristic to improve them. Finally, (3) we investigate numerically how much revenue performance is lost due to the confinement to product combinations that can be represented by a bid price.The heuristic is not restricted to a particular choice model and can be combined with any method that provides us with estimates of the marginal values of capacity. In our numerical experiments, we test the heuristic on some popular networks examples taken from peer literature. We use a multinomial logit choice model which allows customers from different segments to have products in common that they consider to purchase. In most problem instances, our heuristic policy results in significant revenue gains over some currently available alternatives at low computational cost.     

Strategic and operational decisions in restaurant revenue management

The paper addresses restaurant revenue management from both a strategic and an operational point of view. Strategic decisions in restaurants are mainly related to defining the most profitable combination of tables that will constitute the restaurant. We propose new formulations of the so-called “Tables Mix Problem” by taking into account several features of the real setting. We compare the proposed models in a computational study showing that restaurants, with the capacity of managing tables as renewable resources and of combining different-sized tables, can improve expected revenue performances. Operational decisions are mainly concerned with the more profitable assignment of tables to customers. Indeed, the “Parties Mix Problem” consists of deciding on accepting or denying a booking request from different groups of customers, with the aim of maximizing the total expected revenue. A dynamic formulation of the “Parties Mix Problem” is presented together with a linear programming approximation, whose solutions can be used to define capacity control policies based on booking limits and bid prices. Computational results compare the proposed policies and show that they lead to higher revenues than the traditional strategies used to support decision makers.     

A Markov model for single-leg air cargo revenue management under a bid-price policy

In this paper, we consider the capacity allocation problem in single-leg air cargo revenue management. We assume that each cargo booking request is endowed with a random weight, volume and profit rate and propose a Markovian model for the booking request/acceptance/rejection process. The decision on whether to accept the booking request or to reserve the capacity for future bookings follows a bid-price control policy. In particular, a cargo will be accepted only when the revenue from accepting it exceeds the opportunity cost, which is calculated based on bid prices. Optimal solutions are derived by maximizing a reward function of a Markov chain. Numerical comparisons between the proposed approach and two existing static single-leg air cargo capacity allocation policies are presented.     

On the asymptotic optimality of the randomized linear program for network revenue management

For network revenue management problems, it is known that the bid prices computed through the so-called deterministic linear program are asymptotically optimal as the capacities on the flight legs and the expected numbers of product requests increase linearly with the same rate. In this paper, we show that the same asymptotic optimality result holds for the bid prices computed through the so-called randomized linear program. We computationally investigate how the performance of the randomized linear program changes with different problem parameters and with the number of samples. The hope is that our asymptotic optimality result and computational experiments will raise awareness for the randomized linear program, which has yet not been popular in the research community or industry.     

Revenue management for low-cost providers

Low-cost providers have emerged as important players in many service industries, the most predominant being low-cost, or the so-called discount airlines. This paper presents models and results leading toward understanding the revenue management outlook for a discount pricing firm. A framework and model is formulated specifically for the airline industry, but is generalizable to low-cost providers in similar revenue management settings. We formulate an optimal pricing control model for a firm that must underprice to capture a segment of exogenous demand. Two specific model formulations are considered: a continuous deterministic version, and a discrete stochastic version. Structural results are derived for the deterministic case, providing insight into the general form of optimal underpricing policies. The stochastic results support the structural insight from the deterministic solution, and illuminate the effect of randomness on the underpricing policies.     

Dynamic pricing of limited inventories for multi-generation products

In this research, we consider a retailer selling products from two different generations, both with limited inventory over a predetermined selling horizon. Due to the spatial constraints or the popularity of a given product, the retailer may only display goods from one specific generation. If the transaction of the displayed item cannot be completed, the retailer may provide an alternative from another generation. We analyze two models - posted-pricing-first model and negotiation-first model. The former considers negotiation as being allowed on the price of the second product only and in the latter, only the price of the first product is negotiable. Our results show that the retailer can adopt both models effectively depending on the relative inventory levels of the products. In addition, the retailer is better off compared to the take-it-or-leave-it pricing when the inventory level of the negotiable product is high.     

Forecasting cancellation rates for services booking revenue management using data mining

Revenue management (RM) enhances the revenues of a company by means of demand-management decisions. An RM system must take into account the possibility that a booking may be canceled, or that a booked customer may fail to show up at the time of service (no-show). We review the Passenger Name Record data mining based cancellation rate forecasting models proposed in the literature, which mainly address the no-show case. Using a real-world dataset, we illustrate how the set of relevant variables to describe cancellation behavior is very different in different stages of the booking horizon, which not only confirms the dynamic aspect of this problem, but will also help revenue managers better understand the drivers of cancellation. Finally, we examine the performance of the state-of-the-art data mining methods when applied to Passenger Name Record based cancellation rate forecasting.     

Revenue management for a supply chain with two streams of customers

In this paper, we consider revenue management for a service supply chain with one supplier and one retailer. The supplier has a limited capacity of a perishable product and both the supplier and the retailer face customers. Each customer may choose to buy a product from either the supplier or the retailer by considering prices and the cost associated with switching. For the centralized model, the supplier determines the selling prices for both herself and the retailer, and the retailer simply collects a commission fee for each product sold. We derive monotone properties for the revenue functions and pricing strategies. Further, we show that the commission fee increases the retailer’s price while decreasing the supplier’s and leads to efficiency loss of the chain. For the decentralized decision-making model, the supplier and the retailer compete in price over time. Two models are considered. In the first, the retailer buys products from the supplier before the selling season and in the second the retailer shares products with the supplier in retailing. For both models, we discuss the existence of the equilibrium and characterize the optimal decisions. Numerical results are presented to illustrate properties of the models and to compare the supply chain performance between the centralized and the decentralized models.     

Airline network revenue management by multistage stochastic programming

A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, points of sale of the airline network and all dcps of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a finite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported. This research is supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

Joint management of capacity and inventory in make-to-stock production systems with multi-class demand

We evaluate the benefits of coordinating capacity and inventory decisions in a make-to-stock production environment. We consider a firm that faces multi-class demand and has additional capacity options that are temporary and randomly available. We formulate the model as a Markov decision process (MDP) and prove that a solution to the optimal joint control problem exists. For several special cases we characterize the structure of the optimal policy. For the general case, however, we show that the optimal policy is state-dependent, and in many instances non-monotone and difficult to implement. Therefore, we consider three pragmatic heuristic policies and assess their performance. We show that the majority of the savings originate from the ability to dynamically adjust capacity, and that a simple heuristic that can adjust production capacity (based on workload fluctuation) but uses a static production/rationing policy can result in significant savings.