Pricing substitutable flights in airline revenue management

We develop a Markov decision process formulation of a dynamic pricing problem for multiple substitutable flights between the same origin and destination, taking into account customer choice among the flights. The model is rendered computationally intractable for exact solution by its multi-dimensional state and action spaces, so we develop and analyze various bounds and heuristics. We first describe three related models, each based on some form of pooling, and introduce heuristics suggested by these models. We also develop separable bounds for the value function which are used to construct value- and policy-approximation heuristics. Extensive numerical experiments show the value- and policy-approximation approaches to work well across a wide range of problem parameters, and to outperform the pooling-based heuristics in most cases. The methods are applicable even for large problems, and are potentially useful for practical applications.     

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.     

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.     

Integrated revenue management approaches for capacity control with planned upgrades

In many service industries, firms offer a portfolio of similar products based on different types of resources. Mismatches between demand and capacity can therefore often be managed by using product upgrades. Clearly, it is desirable to consider this possibility in the revenue management systems that are used to decide on the acceptance of requests. To incorporate upgrades, we build upon different dynamic programming formulations from the literature and gain several new structural insights that facilitate the control process under certain conditions. We then propose two dynamic programming decomposition approaches that extend the traditional decomposition for capacity control by simultaneously considering upgrades as well as capacity control decisions. While the first approach is specifically suited for the multi-day capacity control problem faced, for example, by hotels and car rental companies, the second one is more general and can be applied in arbitrary network revenue management settings that allow upgrading. Both approaches are formally derived and analytically related to each other. It is shown that they give tighter upper bounds on the optimal solution of the original dynamic program than the well-known deterministic linear program. Using data from a major car rental company, we perform computational experiments that show that the proposed approaches are tractable for real-world problem sizes and outperform those disaggregated, successive planning approaches that are used in revenue management practice today.     

Risk-sensitive stopping problems for continuous-time Markov chains

In this paper we consider stopping problems for continuous-time Markov chains under a general risk-sensitive optimization criterion for problems with finite and infinite time horizon. More precisely our aim is to maximize the certainty equivalent of the stopping reward minus cost over the time horizon. We derive optimality equations for the value functions and prove the existence of optimal stopping times. The exponential utility is treated as a special case. In contrast to risk-neutral stopping problems it may be optimal to stop between jumps of the Markov chain. We briefly discuss the influence of the risk sensitivity on the optimal stopping time and consider a special house selling problem as an example.     

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.     

Approximate nucleolus-based revenue sharing in airline alliances

Alliances allow the airlines to extend their networks and increase the number of destinations they can access. Different from the traditional single airline approach, in an alliance, partner airlines may sell tickets for the same itinerary. In addition, one itinerary may consist of several flight legs, each of which may be operated by a different airline. A major issue that needs to be addressed is how to share the revenue generated from selling a ticket for a product among the individual airlines in a fair way. The fair allocation of the revenue has a critical importance for the long-term stability of the alliance. We model the problem as a cooperative game and show that the core of the game is non-empty. We propose to use a revenue proration scheme based on the concept of the nucleolus. The numerical studies reveal that the revenue shares can effectively be computed even for large alliance networks.     

Cash management in a randomly varying environment

We study a cash management system, in which the distribution of the cash flow X_n in period n=1,2,… depends on the state I_n of a randomly varying environment. Sufficient conditions are found for the optimality of a simple transfer rule, generalizing and partially improving the well-known results for the classical case with i.i.d. cash flows. These and further structural results obtained for the cash balance are shown to reduce the computational effort drastically in determining an optimal transfer rule. In addition, structural and computational results w.r.t. the environment are derived. Finally, some examples are given for economic and statistical environments and their interactions with the cash flow process.     

Monotonicity in multidimensional Markov decision processes for the batch dispatch problem

Structural properties of stochastic dynamic programs are essential to understanding the nature of the solutions and in deriving appropriate approximation techniques. We concentrate on a class of multidimensional Markov decision processes and derive sufficient conditions for the monotonicity of the value functions. We illustrate our result in the case of the multiproduct batch dispatch (MBD) problem.     

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.     

Risk-sensitive finite-horizon piecewise deterministic Markov decision processes

This paper deals with risk-sensitive piecewise deterministic Markov decision processes, where the expected exponential utility of a finite-horizon reward is to be maximized. Both the transition rates and reward functions are allowed to be unbounded. Feynman–Kac’s formula is developed in our setup, using which along with an approximation technique, we establish the associated Hamilton–Jacobi–Bellman equation and the existence of risk-sensitive optimal policies under suitable conditions.     

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.     

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.     

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.     

Risk-sensitive average continuous-time Markov decision processes with unbounded rates

Abstract

In this paper we study the risk-sensitive average cost criterion for continuous-time Markov decision processes in the class of all randomized Markov policies. The state space is a denumerable set, and the cost and transition rates are allowed to be unbounded. Under the suitable conditions, we establish the optimality equation of the auxiliary risk-sensitive first passage optimization problem and obtain the properties of the corresponding optimal value function. Then by a technique of constructing the appropriate approximating sequences of the cost and transition rates and employing the results on the auxiliary optimization problem, we show the existence of a solution to the risk-sensitive average optimality inequality and develop a new approach called the risk-sensitive average optimality inequality approach to prove the existence of an optimal deterministic stationary policy. Furthermore, we give some sufficient conditions for the verification of the simultaneous Doeblin condition, use a controlled birth and death system to illustrate our conditions and provide an example for which the risk-sensitive average optimality strict inequality occurs.     

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.     

Risk sensitive control of finite state Markov chains in discrete time, with applications to portfolio management

In this paper we extend standard dynamic programming results for the risk sensitive optimal control of discrete time Markov chains to a new class of models. The state space is only finite, but now the assumptions about the Markov transition matrix are much less restrictive. Our results are then applied to the financial problem of managing a portfolio of assets which are affected by Markovian microeconomic and macroeconomic factors and where the investor seeks to maximize the portfolio's risk adjusted growth rate.     

Optimal admission control in queues with abandonments

We consider a multi-sever Markovian queueing system with abandonments where admitted customers pay a reward either at the time of arrival or service completion. There is a cost associated with abandonments and a holding cost associated with customers in the system. We prove that the policy that maximizes the long-run average reward is of threshold type and completely characterize the optimal thresholds. We conclude with a comparison of various characteristics of the two variants of the model.     

On the value function in constrained control of Markov chains

It is known that the value function in an unconstrained Markov decision process with finitely many states and actions is a piecewise rational function in the discount factor a, and that the value function can be expressed as a Laurent series expansion about = 1 for close enough to 1. We show in this paper that this property also holds for the value function of Markov decision processes with additional constraints. More precisely, we show by a constructive proof that there are numbers O = _o <₁ <... < _m–1 < _m = 1 such that for everyj = 1, 2, ...,m – 1 either the problem is not feasible for all discount factors in the open interval (_j–1, _j) or the value function is a rational function in a in the closed interval [_j–1, _j]. As a consequence, if the constrained problem is feasible in the neighborhood of = 1, then the value function has a Laurent series expansion about = 1. Our proof technique for the constrained case provides also a new proof for the unconstrained case.