Mathematical programming for network revenue management revisited

Mathematical programming models for airline seat inventory control provide booking limits and bid-prices for all itineraries and fare classes. E.L. Williamson [Airline network seat inventory control: methodologies and revenue impacts, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 1992] finds that simple deterministic approximation methods based on average demand often outperform more advanced probabilistic heuristics. We argue that this phenomenon is due to a booking process that includes nesting of the fare classes, which is ignored in the modeling phase. The differences in the performance between these approximations are studied using a stochastic programming model that includes the deterministic model as a special case. Our study carefully examines the trade-off between computation time and the aggregation level of demand uncertainty with examples of a multi-leg flight and a single-hub network.     

Analysis of seat allocation and overbooking decisions with hybrid information

We investigate a single-leg airline revenue management problem where an airline has limited demand information and uncensored no-show information. To use such hybrid information for simultaneous overbooking and booking control decisions, we combine expected overbooking cost with revenue. Then we take a robust optimization approach with a regret-based criterion. While the criterion is defined on a myriad of possible demand scenarios, we show that only a small number of them are necessary to compute the objective. We also prove that nested booking control policies are optimal among all deterministic ones. We further develop an effective computational method to find the optimal policy and compare our policy to others proposed in the literature.     

Censored regression analysis of multiclass passenger demand data subject to joint capacity constraints

In most passenger transportation systems, demand for seats is not recorded after all spaces for a particular trip have been sold out or after a booking limit has been reached. Thus historical booking data is comprised of ticketsales notdemand — a condition known as censorship of the data. Data censorship is particularly complex when there are multiple classes of demand since the demand in one class can influence the degree of censorship in another. This paper examines the problem of simultaneously estimating passenger demand models for two or more correlated classes of demand that are subject to a common capacity constraint. It is shown that theEM method of Dempster et al. [5] can be adapted to provide maximum likelihood estimates of the parameters of the demand model under these circumstances. The problem of modelling demand for airline flights is discussed as a typical example of this estimation problem. Numerical examples show that, with reasonable sample sizes, it is possible to obtain good estimates even when 75% or more of the data have been censored.     

A stochastic approach to professional services firms’ revenue optimization

Regarding professional service time as perishable goods, it should be possible to directly migrate the successful airline revenue management techniques to professional services firms (PSFs) for their analogous business characters. However, there are salient differences between airlines and PSFs should be highlighted—the network structure of length-of-continuance and capacity allocation of multifunctional staff. Customers booking to be served from a first continuance time to a last continuance time in consecutive time continuance. Multifunctional professionals should be properly allocated to maximize the benefit. The arrival demands and lengths of service are stochastic in nature.     

A hybrid model for airline seat inventory control of the multi-leg problems

To address the discrepancy between dynamic models and industrial practice in airline revenue management, we propose a hybrid model for the multi-leg problem that integrates static and dynamic models. We formulate the problem using a stochastic dynamic program and characterize the optimal booking policy as a switching-curve (surface) type.     

基于旅客选择的高速铁路客运收益管理研究

本文旨在探讨收益管理在高速铁路客运中的应用,给出了存在多级票价时,考虑旅客选择行为的铁路客运收益管理模型,优化结果能够同时给出发车指令和座位出售限制.利用模拟数据对模型进行了数值试验,表明在不同路段长度下,考虑旅客选择行为的总收益较需求独立模型均有所提高,且随着票价等级增多而增长.     

Revenue impacts of fare input and demand forecast accuracy in airline yield management

Most airline yield management seat allocation models require inputs of the expected demand by fare class, the variance of this demand, and a revenue value associated with the bookings expected in each class. In this paper, we examine the impacts of errors in the demand forecasts and fare estimates on the revenue performance of some commonly used seat allocation heuristic decision rules. Through simulation analysis of scenarios in which the fare or demand inputs used by the models differ from the ‘actual’ values simulated in the flight booking process, we examine the effects of unexpected variability in the actual fare values, misestimation of the mean fare values of the different booking classes, and forecasting errors in the expected demand for each class. Our findings confirm previous studies that found the accuracy of the demand forecasts to be of greatest importance, but we also uncover some instances where misestimation of the mean demands and/or mean fare values used as inputs to the decision models can actually be beneficial. At the same time, we conclude that the variability of actual fare values around the mean fare values used as inputs does not have a significant impact, given the mathematical characteristics of existing EMSR seat allocation methods.     

Optimizing revenue in CDMA networks under demand uncertainty

Mathematical programming models for telecommunications network design are prevalent in the literature, but little research has been reported on stochastic models for cellular networks. We present a stochastic revenue optimization model for CDMA networks inspired by bid pricing models from the airline industry. We describe the optimality conditions for the model and develop a supergradient algorithm to solve it. We provide computational results that show the effects of the distribution and variance of demand. Finally, we discuss areas of future research, including a method to optimize the locations of the towers.     

Network capacity management under competition

We consider capacity management games between airlines who transport passengers over a joint airline network. Passengers are likely to purchase alternative tickets of the same class from competing airlines if they do not get tickets from their preferred airlines. We propose a Nash and a generalized Nash game model to address the competitive network revenue management problem. These two models are based on well-known deterministic linear programming and probabilistic nonlinear programming approximations for the non-competitive network capacity management problem. We prove the existence of a Nash equilibrium for both games and investigate the uniqueness of a Nash equilibrium for the Nash game. We provide some further uniqueness and comparative statics analysis when the network is reduced to a single-leg flight structure with two products. The comparative statics analysis reveals some useful insights on how Nash equilibrium booking limits change monotonically in the prices of products. Our numerical results indicate that airlines can generate higher and more stable revenues from a booking scheme that is based on the combination of the partitioned booking-limit policy and the generalized Nash game model. The results also show that this booking scheme is robust irrespective of which booking scheme the competitor takes.     

乘客策略行为下考虑需求学习的航空客运动态定价策略研究

研究航空公司在需求学习下的动态定价策略。通过假设乘客到达率不确定以及具有策略等待行为,运用贝叶斯理论和博弈论对航空公司需求学习下的多周期动态定价问题进行建模,探讨了机票最优定价策略的充分条件,并通过分析航空公司收益函数的性质,得到了最优定价随时间和已出售机票数量的变化趋势。最后应用算例分析了需求学习的效果,得出:需求学习能够缓解需求不确定带来的损失,但不能完全消除;乘客策略程度越大,需求学习效果越明显。     

Airline pricing and fare product differentiation: A new theoretical framework

A basic premise in the development of yield management has been that the differentiated fare products offered by airlines are targeted to distinct segments of the total demand for air travel in a market, each of which compete for space on a fixed capacity aircraft. Such representations of differential pricing assume that the airline can segment its demand perfectly and without cost to consumers, and further, ignore the dependence of the demand for a given fare product on the price levels and characteristics of the other available fare products. In this paper, we introduce a new ‘generalised cost’ model of fare product differentiation that incorporates the relationships between available airline fare products as well as the cost incurred by consumers of accepting more restrictions. We extend the model to incorporate the diversion of passengers to lower-priced fare products as a result of their ability to meet the additional restrictions imposed by airlines, and then demonstrate how seat inventory control can be used to induce diverting passengers to ‘sell up’ to higher-priced fare products by applying booking limits. An example of how the model can be used for joint fare product price level optimisation is presented, along with a numerical example that illustrates the extent to which the conventional model of price discrimination over-estimates passenger demand and, in turn, total airline revenues.     

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.     

Airline Base Schedule Optimisation by Flight Network Annealing

A system for rigorous airline base schedule optimisation is described. The architecture of the system reflects the underlying problem structure. The architecture is hierarchical consisting of a master problem for logical aircraft schedule optimisation and a sub-problem for schedule evaluation.The sub-problem is made up of a number of component sub-problems including connection generation, passenger choice modelling, passenger traffic allocation by simulation and revenue and cost determination.Schedule optimisation is carried out by means of simulated annealing of flight networks. The operators for the simulated annealing process are feasibility preserving and form a complete set of operators.     

A framework for solving network revenue management problems with customer choice behavior

Revenue management is the process of understanding, anticipating and influencing consumer behavior in order to maximize revenue. Network revenue management models attempt to maximize revenue when customers buy bundles of multiple resources. The dependence among the resources in such cases is created by customer demand. Network revenue management can be formulated as a stochastic dynamic programming problem whose exact solution is computationally intractable. Solutions are based on approximations of various types. Customer choice behavior modeling has been gaining increasing attention in the revenue management. A framework for solving network revenue management problems with customer choice behavior is proposed. The modeling and solving framework is composed from three inter-related network structures: basic network model, Petri net, and neural net.     

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.     

Stochastic air freight hub location and flight routes planning

This paper introduced a stochastic programming model to address the air freight hub location and flight routes planning under seasonal demand variations. Most existing approaches to airline network design problems are restricted to a deterministic environment. However, the demand in the air freight market usually varies seasonally. The model is separated into two decision stages. The first stage, which is the decision not affected by randomness, determines the number and the location of hubs. The second stage, which is the decision affected by randomness, determines the flight routes to transport flows from origins to destinations based upon the hub location and realized uncertain scenario. Finally, the real data based on the air freight market in Taiwan and China is used to test the proposed model.     

Scenario reduction in stochastic programming

 Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario tree the optimal reduced tree still has about 90% relative accuracy. Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem – electrical load scenario tree Mathematics Subject Classification (1991): 90C15, 90C31     

Adaptive discretization of convex multistage stochastic programs

We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm starts with a rough approximation of the original tree and locally refines this approximation as long as necessary. Promising numerical results for scenario tree reductions in the settings of portfolio management and power management with uncertain load are presented.     

Scenario tree modeling for multistage stochastic programs

An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optimal values of the original process and its tree approximation, respectively, by relying on a recent stability result in Heitsch, Römisch and Strugarek (SIAM J Optim 17:511–525, 2006) for multistage stochastic programs. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management.     

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.