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:
A coherent data model which permits the treatment of the
large quantities of data required for intelligent pricing.
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.
Various user interfaces facilitating the analysis of the optimization engine's results.
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.
Peter P. Belobaba.
The evolution of airline yield management: Fare class to origin-destination
inventory control.
In Butler and Keller [BK98], pages 285-302.
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.
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.
Donald Garvett and Laurence
Michaels.
Price parraying: A direction for quick, decisive and profit-maximizing pricing.
In Butler and Keller [BK98], pages 333-348.
Guillermo Gallego and
Garett Van Ryzin.
Optimal dynamic pricing of inventories with stochastic demand over finite
horizons. Management Science, 40(8):999-1020, 1994.
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.
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.
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.
Kevin Pak and Nanda Piersma.
Airline revenue management: An overview of or techniques 1982-2002.
Econometric Institute, Erasmus University, Rotterdam, Pays-Bas, 2002.
L. W. Robinson.
Optimal and approximate control policies for airline booking with sequential
nonmonotonic classes. Operations Research, 43(2):252-263, 1993.
J. Subramanian,
S. Shaler, and C.J. Lautenbacher.
Airline yield management with overbooking, cancellations, and no-shows. Transportation Science, 33(2):147-167, 1999.
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.
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.