Mathematics of Information Technology and Complex Systems


Homepage
 
Project Highlights
 
Milestones
 
Research
 
Team Members
 
Partner Organizations
 
Students
 
Publications
 
Presentations
 
Events
 
MITACS Home
 

research

Research

Introduction


Since the late 60's, major airlines have been using a methodology know as  “revenue management” or “revenue optimization”. The need for such a procedure arose when airlines started differentiating their products and offering lower fares. The problem they had to tackle was to maximize yield by discounting otherwise unsold seats while ensuring that high-paying customers would keep on purchasing premium tickets. This was achieved by imposing carefully designed fences between fares and protecting high-yield seats with stringent booking limits. Overbooking, the practice of selling more seats than the actual aircraft capacity allows, also became an issue. Using sophisticated statistical forecasting methods, carriers were able to devise rules for optimally computing overbooking levels, taking into account the costs involved when boarding is denied to booked passengers. Over the years, the practice of revenue management evolved, grew in breadth and sophistication and spread to other fields. It is used today in domains that at first glance appear to be quite different from the airline industry but share some of its basic characteristics: fixed capacity, high fixed costs and low marginal costs, product perishability, etc. Revenue management has been successfully applied in rail transport, cargo, telecoms, car rental, tourism and hospitality to name only a few.

Nowadays, it is generally agreed (see for instance Kimes [Kim90]) that airline revenue management can be decomposed into four sub-problems: demand forecasting, overbooking policy determination, capacity allocation (sometimes called seat inventory control) and pricing. These four interdependent issues are the links that form the revenue optimization chain of an airline. While demand forecasting remains a fundamentally statistical task, the determination of overbooking and capacity allocation policies are usually addressed via optimization techniques. Indeed, these issues have been the subject of several studies in the Operations Research or Management Science literature, over the last thirty years. As a result, major airlines now rely on computerized tools for addressing the overbooking and seat allocation problems. On the other hand, although experts agree that pricing/fare optimization is a vital ingredient of the revenue management process (see Kretsch [Kre95] and Garvett and Michaels [GM98]), few papers deal with this topic. The reason for this situation is twofold. First, while a comprehensive pricing model must involve stochastic, dynamic and game theoretic elements, there is no agreed modeling approach within the revenue management community. Next, the gathering of data required in a real-life application constitutes a daunting task. One must indeed track down information about competitors' fares, demand forecast, historical sales patterns, etc. Airlines generally rely on computerized database systems to store such information. As these systems seldom use compatible formats, one must extract, interpret and reformat the required data in order to establish links between the various sources of information and develop a coherent database. We refer to Kretsch [Kre95] for an overview of the difficulties surrounding the retrieval and treatment of fare data.


Project Objectives


This research endeavour is concerned with the development of a joint pricing and seat allocation model for the airline and related industries. Our approach is based on the bilevel programming paradigm, which is a special case of hierarchical mathematical optimization. The bilevel structure of our model allows us to take into account not only the topology of the airline network and the interactions between overlapping routes but also the behaviour of customers, who make their purchase decisions based on the attributes of the products offered by the carriers as well as their own willingness to pay. As we shall see in the following literature review, our work is one of the first research efforts to simultaneously tackle pricing and seat allocation. It is also, to our knowledge, the first time that bilevel programming is applied to problems of such scale.


Literature Review


A recent survey of revenue management can be found in the work of McGill and Van Ryzin [MVR99]. In the airline industry, it can be characterized in several ways. Weatherford and Bodily [WB92] adopt the mathematical programming point of view and classify the various objectives to be optimized (revenue, capacity utilization, customer utility), as well as the operational, financial and marketing constraints. They propose a taxonomy of revenue management models based on the objectives that are explicitly addressed and the constraints that must be satisfied. However, a unified approach seeking to simultaneously deal with all aspects of the problem has been judged intractable in practice by Smith, Leimkuhler and Darrow [SLD92]. Their paper, based on the experience acquired at a major American carrier, suggests that a decomposition of the general problem into structurally simpler sub-problems is unavoidable, given today's theoretical and technological capabilities. Kimes [Kim90] suggests the decomposition introduced earlier, i.e., demand forecasting, overbooking policy determination, seat allocation and pricing.

Our work is primarily concerned with the joint seat allocation and pricing processes. Seat inventory control can be traced back to the works of Littlewood [Lit72]. One can distinguish between so-called "static" models, where bookings are taken sequentially, starting with the lowest class and proceeding to the next class only when the current class is filled, and "dynamic" methods, which make no assumption on the order of arrival of booking requests. There is a further distinction between leg-based methods, which ignore the interactions between flight legs, and broader, network-based methods. Among articles dealing with static, leg-based approaches, we cite Brumelle et al. [BMO+90] and Belobaba.[Bel87a,Bel87b,Bel98] This last author has proposed heuristics usually referred to as EMRSa and EMRSb that are often used in practice. Optimality conditions for such static methods have been obtained by Curry [Cur90], Brumelle and McGill [BM93], Wollmer [Wol92] and Robinson [Rob93]. Dynamic versions of the leg-based methods have been proposed, most of them relying on dynamic programming for their solution. Examples of such approaches can be found in Lee and Hersh [LH93], Lautenbacher, Stidham and Subramanian [SSL99], Lautenbacher and Stidham [LS99] and Feng and Xiao [FX01]. They are differentiated, in particular, by the consideration (or not) of no-shows and cancellations.

Network-based seat inventory control methods can be divided into two broad categories. Improved versions of leg-based methods that seek to exploit some of the network structure through modeling devices such as virtual booking classes fall into the first category. The main advantage of these approaches it that they fully exploit the network structure and, since they rely on existing frameworks, require small investments. We refer to Belobaba [Bel98] and Smith, Leimkuhler and Darrow [SLD92] for further details. The second category, which regroups methods that are explicitly based on linear programming network formulations, includes the works of Glover et al. [GGLM92], Curry [Cur90] and Wong, Koppelman and Daskin [WKD93]. In De Boer, Freling et Piersma [dBFP99], deterministic and stochastic network formulations are compared, and numerical results are presented. Surprisingly, these authors have found that simple deterministic models based on expected demand generate better revenue than more sophisticated probabilistic models. According to Belobaba [Bel98], these methods can take into account the combinatorial structure inherent to any real-life transportation system. However, they are not without any drawbacks. First, the integration of dynamic and stochastic aspects within a network formulation can only be achieved at the expense of a significant increase in complexity. Second, the seat allocation schemes they produce are non-nested and highly "partitioned", i.e., the "optimal" number of seats allocated to a given booking class on a given itinerary may be too small to be of any practical use. Nevertheless, linear programming network formulation are sometimes used as an auxiliary procedure in "bid price" methods. Talluri and van Ryzin[TvR98] describe bid prices as threshold values set for each leg of a network such that a product (which can be seen as an itinerary in the network) is sold only if its fare exceeds the sum of the bid prices of the legs along its path. In other words, the bid price of a leg represents the marginal contribution of this leg to the global network revenue. Those familiar with linear programming will recognize that this is the classical interpretation of dual multipliers of capacity constraints in a capacitated maximum-flow network formulation, whence the use of such models in bid price methods. More details can be found in [Tal01,PP02,Bel98,Vin95,TvR98].

The literature on airline pricing and fare optimization is much more limited. Gallego and Van Ryzin [GR97,GR94] and You [You99] model the pricing of multi-leg flights as a stochastic decision process, and solve the resulting recurrence equations by dynamic programming techniques. They underline the strong duality relationship between pricing and seat allocation and argue that the latter can be derived from the former by allowing prices to become infinite on a given booking class, which is tantamount to closing it. Recently, Kuyumcu and Garcia-Diaz [KGD00] claimed that their model jointly solved the pricing and seat allocation problems. We believe this is an overstatement. The authors actually formulate and solve (exactly or heuristically) an integer program model which, given a restricted number of fare structures, determines the one that should be implemented, together with the number of seats to be allocated to each class. Fares are therefore exogenous data, and not determined by the optimization process.

The model


Bilevel programming is used to model those situations in which a main agent, whom we call the leader, strives to optimize a given quantity but controls only a subset of the decision variables. The remaining variables fall under the control of a second agent, the follower, who optimizes its own problem by taking into account the decisions taken by the leader. The solution optimal solution to such an interactive process constitutes what economists call a Stackelberg equilibrium.

In our approach, the first (i.e. leader) level is occupied by the client airline, which strives to maximize its revenues. Of course, revenues are only half of the equation when it comes to airline profitability, as expenses must also be taken into account. However, once the scheduled is committed and crews and aircraft have been assigned, costs are practically fixed, no matter whether the aircraft takes off empty of full. Therefore, in the short term, revenue maximization is tantamount to profit maximization.

We express revenue simply as the product of the fares and the number of passengers purchasing those fares. Prices, (i.e. fares), are directly under the control of the leader, which is not the case for the number of passengers choosing to buy at this price. This passenger "flow" is determined by the reaction of the customers to the fares offered not only by the leader airline but also by its competitors. We suppose passengers react rationally by minimizing their perceived cost of travel. This quantity includes the fare and the monetary valuation of certain attributes of the products offered, for instance travel duration, number of transits or quality of service.

Constraints in the model are of a physical nature. They insure that passengers ultimately get to their destination (flow conservation) and that aircraft capacities and previously set booking limits are respected. Capacity constraints have a coupling effect on the model, which would otherwise be separable by market (i.e. origin-destination pair). Therein lies the main algorithmic difficulty when solving the model.

Research issues


The main issues with which our research is concerned are the following:

  • Modelling
    The informal description of our model given above does not mention some technical but important issues. As it is presented, the model is static and deterministic. However, the revenue management problem possesses some stochastic and dynamic aspects that cannot be ignored, particularly if our approach is to be used in a longer-term strategic context. We are therefore investigating ways of integrating the uncertainty of certain data into the model and refining its use in dynamic settings.

  • Algorithmics
    Bilevel programs are amongst the hardest problems one can come across. Generic, brute force solution methods using commercial codes can tackle only toy instances. If one wishes to solve real-life instances of practical size, one must rely on specialized algorithms that have been tailored for this problem and can exploit its structure. The development of such procedures, either exact of heuristic, is one of the most challenging — and exciting! — aspects of our research. This work involves an in-depth analysis of the problem in order to better understand the interactions between its components and to identify its structural properties that may be taken advantage of in decomposition methods. Keeping practicality and usability in mind, we develop and validate our algorithms using real airline data.

  • Calibration
    The second-level model, which describes how passengers react to offered fares, is driven by a set of parameters representing the passengers’ monetary valuation of certain fare attributes. These values, which are not readily available, must be obtained for historical sales data. In order to do so, we have devised an automated procedure based on the principle of inverse optimization.


Breakthroughs and Achievements


After five years of research, including three under MITACS sponsorship, our achievements fall into two distinct but complementary categories.

On the theoretical side, our research has yielded important results that allow a better comprehension of bilevel models, for instance on the interactions between first and second levels and on the meaning of constraints for the agents. The complexity of the problem has been studied and some formulations have been shown NP-hard. We have devised various resolution methods, either discrete or continuous, and convergence proofs have been obtained. We have also explored the still untouched field of inverse combinatorial optimization and conceived a methodology which is used in the calibration of the model’s parameters.

On the technical side, our main achievement is the development of the NetPrO (Network PRricing Optimization) engine, a software module which consists of:

  1. A coherent data model which permits the treatment of the large quantities of data required for intelligent pricing.

  2. A software implementation of the bilevel model and its associated solution algorithms. As of now, we are able to solve large instances of practical size at near optimality (98-99%) within minutes of CPU times.

  3. Various user interfaces facilitating the analysis of the optimization engine's results.

  4. A calibration module that can treat historical data and obtain parameter values which are then used in the optimization module.


The NetPrO engine has been extensively tested on real airline data and its results, after having been carefully analyzed and validated by industry experts, tend to confirm the potency of the bilevel programming paradigm for solving pricing problems in network industries. Following in this direction, the engine is currently being adapted for solving analogous problems in the (passenger) rail and telecommunication industries. As with the airline case, this work is conducted in close collaboration with industrial partners.


References

Bel87a

Peter P. Belobaba.
Airline yield management: An overview of seat inventory control.
Transportation Science, 21(2):63-73, 1987.

Bel87b

Peter P. Belobaba.
Application of a probabilistic decision model to airline seat inventory control.
Operations Research, 37(2):183-197, 1987.

Bel98

Peter P. Belobaba.
The evolution of airline yield management: Fare class to origin-destination inventory control.
In Butler and Keller [BK98], pages 285-302.

BK98

Gail F. Butler and Martin R. Keller, editors.
Handbook of Airline Marketing.
Aviation Week Group, McGraw-Hill, 1998.

BM93

S. L. Brumelle and J. I. McGill.
Airline seat allocation with multiple fare classes.
Operations Research, 41(1):127-137, 1993.

BMO+90

S. L. Brumelle, J. I. McGill, T. H. Oum, K. Sawaki, and M. W. Tretheway.
Allocation of airline seats between stochastically dependant demands.
Transportation Science, 24(3):183-192, 1990.

Cur90

R.E. Curry.
Optimal airline seat allocation with fare classes nested by origins and destinations.
Transportation Science, 24(3):193-204, 1990.

dBFP99

Sanne V. de Boer, Richard Freling, and Nanda Piersma.
Stochastic programming for multiple-leg network revenue management.
Technical Report EI-9935/A, ORTEC Consultants, Gouda, Pays-Bas, 1999.

FX01

Youyi Feng and Baichun Xiao.
A dynamic seat inventory control model and its optimal policy.
Operations Research, 49(6):938-949, 2001.

GGLM92

F. Glover, R. Glover, J. Lorenzo, and C. McMillan.
The passenger mix problem in the scheduled airlines.
Interfaces, 12(3):73-79, 1992.

GM98

Donald Garvett and Laurence Michaels.
Price parraying: A direction for quick, decisive and profit-maximizing pricing.
In Butler and Keller [BK98], pages 333-348.

GR94

Guillermo Gallego and Garett Van Ryzin.
Optimal dynamic pricing of inventories with stochastic demand over finite horizons.
Management Science, 40(8):999-1020, 1994.

GR97

Guillermo Gallego and Garett Van Ryzin.
A multiproduct dynamic pricing problem and its applications to network yield management.
Operations Research, 45(1):24-41, 1997.

Jen95

Darryl Jenkins, editor.
Handbook of Airline Economics.
Aviation Week Group, McGraw-Hill, 1995.

KGD00

A. Kuyumcu and A. Garcia-Diaz.
A polyhedral graphs theory approach to revenue management in the airline industry.
Computers and Industrial Engineering, 38(3):375-395, 200.

Kim90

S. Kimes.
Yield management: A tool for capacity-constrained service firms.
Journal of Operations Management, 8:348-363, 1990.

Kre95

Steven S. Kretsch.
Airline fare management and policy.
In Jenkins [Jen95], pages 477-482.

LH93

T. C. Lee and M. Hersh.
A model for dynamic airlaine seat inventory control with multiple seat bookings.
Transportation Science, 27(3):252-265, 1993.

Lit72

K. Littlewood.
Forecasting and control of passenger bookings.
AGIFORS Symposium Proceedings, 12:95-117, 1972.

LS99

C.J. Lautenbacher and S. Shaler.
The underlying markov decision process in the single-leg airline yield-management problem.
Transportation Science, 33(2):136-146, 1999.

MVR99

J.L. McGill and G.J. Van Ryzin.
Revenue management: Research overview and prospects.
Transportation Science, 33(2):233-256, 1999.

PP02

Kevin Pak and Nanda Piersma.
Airline revenue management: An overview of or techniques 1982-2002.
Econometric Institute, Erasmus University, Rotterdam, Pays-Bas, 2002.

Rob93

L. W. Robinson.
Optimal and approximate control policies for airline booking with sequential nonmonotonic classes.
Operations Research, 43(2):252-263, 1993.

SLD92

B. Smith, J. Leimkuhler, and R. Darrow.
Yield management at american airlines.
Interfaces, 22(1):8-31, 1992.

SSL99

J. Subramanian, S. Shaler, and C.J. Lautenbacher.
Airline yield management with overbooking, cancellations, and no-shows.
Transportation Science, 33(2):147-167, 1999.

Tal01

Kalyan T. Talluri.
Airline revenue management with passenger routing control: A new model with solution approaches.
International Journal of Services Technology and Management, 2(1/2):102-115, 2001.

TvR98

Kalyan Talluri and Garrett van Ryzin.
An analysis of bid-price controls for nework revenue management.
Management Science, 44(11):1577-1593, 1998.

Vin95

Ben Vinod.
Origin-and-destination yield management.
In Jenkins [Jen95], pages 459-468.

WB92

L. Weatherford and S. Bodily.
A taxonomy and research overview of perishableasset revenue management: Yield management, overbooking, and pricing.
Operations Research, 40(5):831-844, 1992.

WKD93

J.T. Wong, F.S. Koppelman, and S.D. Daskin.
Flexible assignment approach to itinerary seat allocation.
Transportation Research B, 27B(1):33-48, 1993.

Wol92

Richard D. Wollmer.
An airline seat management model for a sinle leg route when lower fare classes book first.
Operations Research, 40(1):26-37, 1992.

You99

P.-S. You.
Dynamic pricing in airline seat management for flights with multiple flight legs.
Transportation Science, 33(2):192-206, 1999.