A new approach to O&D revenue

A new approach to O&D revenue management based on scenario trees1

Andris Mo ller*,Werner Ro misch*and Klaus Weber**

Received(in revised form):12th July,2004

*Humboldt-University Berlin,Institute of Mathematics,Unter den Linden6,Berlin,10099,Germany Tel:+493020932353;Fax:+493020932232;E-mail:romisch@mathematik.hu-berlin.de

**Lufthansa Systems Berlin GmbH,Fritschstrasse27–28,Berlin,10585,Germany

Tel:+493034007178;Fax:+493034007100;E-mail:klaus.weber@https://www.sodocs.net/doc/3a18966722.html,

Andris Mo¨ller is a research fellow at the Institute of Mathematics of the Humboldt-University Berlin.Before that,he was a research fellow at the Weierstrass Institute for Applied Analysis and Stochastics in Berlin and the Humboldt-University Berlin. His research interests include unit com-mitment in power production planning, optimal control of destillation processes with probabilistic constraints and airline revenue management.His web address is http://www.mathematik.hu-berlin.de/

~andris/.

Werner Ro¨misch is a Professor at the Institute of Mathematics of the Humboldt-University Berlin.His current research interests include the theory and solution methods for large-scale mixed-integer stochastic programming problems,and he is actively working on several indus-trial applications.He is Co-editor of the Stochastic Programming E-Print Series.His web address is http:// www.mathematik.hu-berlin.de/~romisch/.

Klaus Weber is the Product Manager Pro?t-Line/Yield and Senior Scienti?c Analyst at Lufthansa Systems.Before that, he was a scienti?c assistant at the Compu-ter Science Research Centre in Karlsruhe and at Brandenburg Technical University at Cottbus,Germany.Currently,his research interests include revenue

management,decision support systems,

fuzzy and stochastic optimisation,and

agent technology.His web address is

http://vieta.math.tu-cottbus.de/~klweber/.

A BSTRACT

KEYWORDS:O&D revenue management,

seat inventory control,multistage stochas-

tic programming,scenario tree generation

Origin and destination(O&D)revenue man-

agement(RM),either leg-based or PNR based,

has become a standard in the airline industry.

This paper presents a new approach to O&D

RM which does not make any assumptions on

demand distributions or on the correlations of the

booking process.Protection levels are determined

for all origin–destination itineraries,fare classes,

points of sale and data collection points

(DCPs),and for a variety of demand patterns

over the complete booking period.This

approach to the seat inventory problem is mod-

elled as a multistage stochastic program,where

its stages correspond to the DCPs of the booking

horizon.The stochastic passenger demand pro-

cess is approximated by a scenario tree generated

from historical data by a recursive scenario

reduction procedure.The stochastic program

represents a specially structured large scale

linear program(LP)that may be solved by

standard LP software(eg CPLEX).Prelimin-

ary numerical experience is reported.

Page265

Journal of Revenue and Pricing

Management,Vol.3,No.3,2004,

pp.265–276

#Henry Stewart Publications,

1476–6930

Journal of Revenue and Pricing Management Volume3Number3

INTRODUCTION

Revenue management(RM)refers to stra-tegies for controlling the sale of(perish-able)products or services in order to maximise revenue.It started in the early 1970s with the work of Littlewood(1972) and was enforced after the deregulation of US airline industry in1979.For overviews, refer to Weatherford(1998),McGill and van Ryzin(1999),Pak and Piersma(2002), Klein and Petrick(2003),Talluri and van Ryzin(2004).

The EMSRa and EMSRb methods (Belobaba,1987,1989)became most popu-lar for single-leg problems.They are com-monly used under the assumption that demand for each fare class is independent and normally distributed.Extension for di?erent types of distributions or depen-dencies may be found in Curry(1990), Wollmer(1992),Brumelle and McGill (1991),Brumelle et al.,(1990).In Glover et al.,(1982),the?rst network formulation of the RM was given.Optimal booking limits were applied to the network pro-blem by Curry(1990).Smith and Penn (1988)and Simpson(1989)proposed the bid price concept for network revenue management.An extensive study of bid prices in comparison with other methodol-ogies was done by Williamson(1992).The-oretical properties of bid-price controls were provided by Talluri and van Ryzin (1999).In van Ryzin and McGill(2000),an adaptive scheme was used for updating protection levels based on frequencies of certain?ll events and for solving some optimality conditions.The rate of occur-ence of the?ll events was determined directly from historical booking records. Neither assumptions about the distributions nor uncensoring was requested.General stochastic network models based on Markov decision processes and several types of approximations were developed and discussed in van Ryzin and Talluri (2003).Markov decision processes and mathematical programming approaches were combined in Cooper and Homem-de-Mello(2003).

The present paper is based on a feasibil-ity study which investigates a scenario tree-based stochastic programming approach to the O&D revenue manage-ment problem.For this purpose,a sce-nario tree consisting of a?nite number of scenarios approximates the stochastic demand process.The approach has four characteristics:whereas many other meth-ods build parameterised models and esti-mate the values of the parameters from historical booking data,this study tries to exploit historical booking progressions themselves.It does not mean to use such data exclusively.Other data,eg expert forecasts or demand forecasts from alter-native models,can be taken into account in a straightforward way.Secondly,the problem of optimising booking control parameters is modelled as a linear pro-gram.Unlike other revenue management linear program models,it is neither the result of a relaxed non-linear program, nor does it employ expectation values or other simple substitutes of the stochastic demand process.Instead,this process is modelled by a set of scenarios,which are considered in the linear program simulta-neously.Thirdly,the scenario tree model does not make any assumptions on the probability distribution of the stochastic demand process,except that it was dis-crete.Finally,the relation between the number of scenarios(and thus the result-ing computational complexity of the linear program)and the accuracy with which they model the stochastic process is known and exploited for practical computation.This work is a preliminary study.Its?rst aim is to demonstrate the viability of this approach;quantitative evaluations and comparisons with other methods will be the subject of future work and publications.

age266

new approach to O&D revenue management

In the next section,the stochastic pro-gramming model for O&D revenue man-agement is established in scenario and node formulation.Furthermore,the generation of a booking and cancellation scenario tree from individual scenarios is described.In the?nal sections,preliminary numerical experience is reported,and concluding comments are given.

STOCHASTIC PROGRAMMING MODEL Modelling

An O&D network is considered,consisting of I origin–destination itineraries,J fare classes,K points of sale,L legs with M(l) compartments in each leg l=1,...,L. Let the booking horizon be subdivided into T booking subintervals with data col-lection points(dcps)t=0,...,T.The booking process is controlled over time by decisions on protection levels P i,j,k,t for each fare class j[{1,...,J},itinerary i[{1,...,I},point of sale k[{1,...,K} and at each dcp t=0,...,T–1.The decisions at t are made for the next book-ing interval(t,t+1]based on the pre-vious process of bookings and cancellations up to t and recursively over time.Protec-tion levels are upper bounds for the inven-tory of booked,uncancelled seats.

It is assumed that the fares and the com-partment capacities are given,ie,they are deterministic input variables.The booking demand and the cancellation processes are regarded as a multivariate stochastic process {x t}T t=0over time,where x0represents a known deterministic starting value.The components of the random input vector x t at t are the stochastic booking demands d i,j,k,t and stochastic cancellation rates c i,j,k,t. Hence,x t is a2IJK-dimensional random vector whose components are statistically dependent and,furthermore,the random input vector x t depends on its history(x0, x1,...,x t–1).

To state the stochastic programming

(SP)model,it is assumed that S scenarios

with probabilities p s>0,s=1,...,S,of

the booking demand and cancellations pro-

cess are given.These scenarios may be

obtained from stochastic demand models

and by relying on expert knowledge,

respectively.

Scenario-based SP model

To set up the SP model,some further

notation is needed.We denote the index

set of itineraries containing leg l(ie,the

incidence set)by I l({1,...,I},the

number of compartments on leg l by M(l)

and the index set of fare classes of compart-

ment m on leg l by J m(l)({1,...,J}.

Further input data are the fares f i,j,k,t and

the capacities C l,m of compartments m[{1,

...,M(l)}and legs l.

The stochastic input variables are the

booking demand d s i,j,k,t and and the cancel-

lation rates g s i,j,k,t.The bookings b s i,j,k,t and

the cumulative bookings B s i,j,k,t represent

the stochastic state variables of the model

while the protection levels P s i,j,k,t are the

stochastic decisions.Here,the superscript s

always refers to scenario s.The expected

total revenue is considered the objective

function,where total refers to the whole

O&D network and booking horizon,all

fare classes and points of sale.

Summarising,our scenario-based sto-

chastic programming model consists in

maximising

X S

s?1

s

X T

t?1

X I

i?1

X J

j?1

X K

k?1

f i;j;k;teb s i;j;k;tàc s i;j;k;tT

e1T

subject to all protection levels P s i;j;k;t satisfy-

ing

e1à s i;j;k;tTB s i;j;k;t P s i;j;k;tà1e2T

Page267

Mo ller,Ro misch and Weber

where B s i;j;k;t are the cumulative bookings, ie,

B s i;j;k;0:? B0i;j;k;

B s i;j;k;t:?B S i;j;k;tà1tb s i;j;k;te3Twith b s i;j;k;t satisfying the demand constraints

b s i;j;k;t d s i;j;k;te4Tand the leg capacity limits

X i2I l

X

j2J melT

X K

k?1

P s i;j;k;Tà1C l;me5T

For some#2e0:0;0:5 the cancellations are approximated by

s

i;j;k;t

B s i;j;k;tà s i;j;k;tà1B s i;j;k;tà1à#

c s i;j;k;t

s

i;j;k;t

B s i;j;k;tà s i;j;k;tà1B s i;j;k;tà1t# Finally,the integrality and non-negativity constraints

b s i;j;k;t;

c s i;j;k;t;P s i;j;k;t2Ze7T

b s i;j;k;t;

c s i;j;k;t;P s i;j;k;t!0e8Tan

d th

e non-anticipativity constraints have to be satis?ed,the latter meaning that decisions at t only depend on the data until t.(9) Here,(1)corresponds to the total expected revenue.Like the revenue values processed in real revenue management systems,the fares in the model are divided according to booking period,itinerary(and thus origin, destination,and?ight period),booking class,and point o

f sale.However,the objec-tive function is simpli?ed,as full refund of cancelled tickets is assumed.This is justi?-able,because it is not a mathematical pro-blem to take cancellation fees and refunds into account,but a practical one.In fact,it is quite di?cult to determine from an airline’s database for what reason a bookin

g was cancelled:A ticket may have been given back or the passenger may have been rebooked to another?ight.In order to uncover cancellation fees or refunds cor-rectly,the original tari?information should be available.Even in passenger name records,however,often only book-ing class information is stored.Approxima-tions could be received by analysis of coupon information from check-in and PNR data,but most airlines have not established suc

h process.

Equation(3)describes the update of the cumulative bookings starting with the initial value B0i;j;k2Z.The constraint(5) expresses that,for each leg,the correspond-ing protection levels may not exceed the physical capacities of the compartments on the day of departure.The latter implies no-show based overbooking is not part of the model.This is another simpli?cation, owing to the study character of the work. Since constraint(5)applies at time of depar-ture only,overbooking is possible during the entire booking period.Actually,it is more demanding to model overbooking to compensate cancellations than to model overbooking to counteract no-shows. While the protection levels,the number of bookings and the number of cancella-tions have to be non-negative integers by nature,the constraint(9)expresses how the information?ow evolves over time.(9) may be modelled by linear equations in various ways,see Ruszczynski and Shapiro (2003,Chapter 3.6)and Ro misch and Schultz(2001).Altogether,the model(1)–(9)represents a large scale multistage sto-chastic integer program.

Input scenario trees

The non-anticipativity constraint(9) implies that the?nitely many scenarios f s t g T t?0;s?1;...;S,can be represented in the form of a scenario tree.The scenario tree is based on a?nite set N?f0;1;...;N g of nodes that are

age268

new approach to O&D revenue management

arranged at the stages t =0,...,T .The

root node n =0is the only node at stage

t =0.The number of nodes at stage t =1

corresponds to the number of di?erent rea-

lisations of 1.Each of these nodes is con-

nected with the root node by an arc.In

general,each node n 2N ;n ?0has a

unique predecessor node denoted by n –and

a set N ten Tof successor nodes.Each node

in N ten Tis connected with n by an arc.

The set {0,...,n –,n}of recursive prede-

cessors of n is denoted by path(n ),which

refers to the path from the root to n.t(n)

denotes the number of elements in path(n )

minus 1and,thus,refers to the stage to

which n is arranged,ie,the nodes in

N t :?f n 2N :t ?t en Tg correspond to

the di?erent realisations of t .Nodes n

belonging to set N T have the property

N ten T?1and are called leaves.Hence,a

scenario corresponds to a path from the

root to some leaf,ie to path(n )for some

n 2N T ,and its probability is renamed by

p n .We also say that p n is the probability of

the leaf n.Clearly,we have f n g n 2N T ?f s g S s ?1.The probabilities of

nodes n 2=N T compute by the recursion

n :?P n t2N ten T n t.Clearly,we have

that P n 2N t n ?1and t en T?f n g n 2N t ,for each t =0,1,...,T.The generation of scenario trees that approximate the stochastic input process f t g T t ?0is a challenging task when solving multistage stochastic programs.In Dupa-c ova et al.(2000),an overview of scenario tree generation techniques is provided.More recent contributions are based on the moment-matching principle (H?yland and Wallace,2001),the use of distances of probability distributions (P?ug,2001)and (Gro we-Kuska et al.,2003),and Quasi-Monte Carlo methods (Pennanen,2004),respectively.Next,the scenario tree construction approach presented in Gro we-Kuska et al.(2003)is brie?y described.It assumes that a ?nite number of individual scenarios f s t g T t ?0with probabilities p s >0,s =1,...,S,and common root node,ie, 10?...? S 0is given.These scenarios may be obtained from simulations of a parametric statistical model (eg based on time series analysis)or from a non-parametric model (eg by resampling methods).This fan of individual scenarios is modi?ed by a procedure of recursive bundling and deletion of similar scenarios,respectively,leading to a tree structure.Its methodology is based on the scenario reduction techniques developed by Dupa-c ova et al.(2003)and Heitsch and Ro misch (2003)and employs these techni-

ques backwards in time starting at t =T.

The bundling and deletion process relies

on computing and bounding the Kantoro-

vich distance of the original probability

distribution D e Tgiven by the individual

scenarios and their weights and of the dis-

tributions of the approximate trees.If f ~ t g T t ?0and q !0; ?1;...;S ;denote the scenarios and weights of another dis-crete probability distribution D (x ~),the Kantorovich distance of D (x )and D (x

~)is given

by

Figure 1:Scenario tree with T =4,N =21and

11leaves t ?0t ?1t en TT

Page 269

Mo

ller,Ro misch and Weber

eD e T;D e~

TT:?inf X S

s ; ?1

s X T à0k s à~ k :X

S ?1 s ?p s ;X S s ?1 s ?q

where k ák is a norm in a Euclidean space,

whose dimensions correspond to the

number of components of t for each t.Hence,the distance eD e T;D e~

TTis de-?ned as the optimal value of a (linear)

transportation problem.Refer to Rachev

and Ru schendorf (1998,Chapter 2)for a

general introduction to mass transportation

problems and to the Kantorovich distance,

respectively.

Given tolerances ">0and "t >0;t ?1;...;T ;such that P T t ?1"t ",

the algorithm for constructing scenario

trees consists of the following T steps:

Step 1:Delete scenarios from the origi-

nal probability distribution D e Tby deter-

mining index sets I T and J T of remaining

and deleted scenarios such that I T |J T =

{1,...,S}and

X

2J T p min s 2I T X T ?0k s à k "T e10TThe left-hand side of (10)corresponds to

the best possible Kantorovich distance of

D e Tto the set of all distributions with sce-

narios s ;s 2I T .The optimal weights of these scenarios are T s ?p s tP 2J s T p ,s 2I T ,where J s T :?f 2J T :s ?s e Tg and s e Tminimises min s 2I T P T ?0k s à k (see Dupac ova

et al.,2003,Theorem 2)).Thus,the new probability T s of scenario s ;s 2I T ,is equal to the sum of its former

probability p s and of all probabilities of

deleted scenarios that are closest to it.

Step t:Consider the time intervals

between 0and T –t +1and determine

index sets I T–t +1and J T–t +1such that

I T–t +1|J T–t +1=I T–t +2and X 2J T àt t1p min s 2I T àt t1X T àt t1 ?0k s à k "T àt t1Analogously to Step 1,the new weights of the remaining scenarios s ;s 2I T àt t1,are determined by T àt t1s :? T àt t2s tX 2J s T àt t1 T àt t2 ;where J s T àt t1:?f 2J T àt t1:s ?e Tg and s e Tminimizes min s 2I T àt t1P T àt t1 ?0k s à k .Result:After T steps of the algorithm a chain of index sets is obtained I 0 I 1 I 2 ááá I T f 1;...;S g where I 0is a singleton that corresponds to the root t =0and I t is the index set of sce-narios between t =0and t =t.Branching of scenario s 2I t at t appears if the branch-ing set J s t is non-empty.Scenario s has a branching degree r at t =t,ie r successors,if j J s t j ?r à1.The ?nal scenario tree con-sists of scenarios ~ s ;s 2I T ;which coincide at t with some of the original scenarios at t,ie ~ s t ? t for some 2I t .As a result of the tree construction we obtain for the Kantorovich distance of the probability distributions D e Tand D e~

Tthe estimate eD e T;D e~ TT X T t ?1"t "e11TFor a proof of the latter result,refer to the forthcoming paper (Heitsch and Ro misch,2004).The Kantorovich distance was selected by stability arguments for multi-stage stochastic programs in the sense that the optimal values of stochastic programs obtained with the input distributions D e Tand D e~ Tare close if eD e T;D e~ TTis small.It is worth noting that no assump-tions on the original discrete probability distribution D e Thave to be imposed.The estimate (11)is valid without any further

age 270

new approach to O&D revenue management

conditions(eg on dependences).Solving transportation problems for evaluating the Kantorovich distance is not needed,too. Of course,the?nal scenario tree depends on the choice of"and on the strategy of selecting"t for every t=T,...,1.The recursive strategy"T:?"e1àqT,"t:?q"tt1;t?Tà1;...;1;reduces the number of free parameters to"and q2e0;1T.For q close to1,only a few scenarios will be reduced in Step1,while a higher branch-ing degree appears already at t=1.If q is small,the original scenario set will be reduced considerably.The tree in Figure3 is obtained with q=0.95.

Figure2illustrates the construction pro-cedure starting from a fan of individual scenarios on a time horizon with T=4. After three reduction and bundling steps at t=3,2and1,the?nal result is shown in(d).The?nal scenario tree exhi-bits a possibly di?erent branching struc-ture at all stages,which is detected by the algorithm.SP model in node form

Using the description of scenario trees,the SP model(1)–(9)may alternatively be represented in node formulation.To this end we introduce input,state and decision variables at all nodes using superscript n= 0,...,N.Making use of a mapping that assigns to each time-scenario pair(t,s)the corresponding node n with t=t(n)and with path(n)being a part of scenario s,the booking demands d n i;j;k,cancellation rates n

i;j;k

,bookings b n i;j;k,booking inventories B n i;j;k and protection levels P n i;j;k at all nodes n2N and all triples(i,j,k)are obtained. Then the node formulation of the SP model consists in maximising

X N

n?1

n

X I

i?1

X J

j?1

X K

k?1

f i;j;k;tenTeb n i;j;kàc n i;j;kTe12T

subject to all protection levels P n i;j;k satisfy-ing

e1à n i;j;kTB n i;j;k P nài;j;ke13T

Figure2:Construction of a scenario tree

(a)Initial fan(b)1st step

(c)2nd step(d)3rd step and?nal tree

Page271

Mo ller,Ro misch and Weber

where B n i ;j ;k are the cumulative bookings,ie

B 0i ;j ;k :? B 0i ;j ;k

B n i ;j ;k :?B n ài ;j ;k tb n i ;j ;k e14T

with b n i ;j ;k satisfying the demand constraints

b n i ;j ;k d n i ;j ;k e15T

and for all n 2N T à1the leg capacity limits

X i 2I t X j 2J m el TX

K k ?1P n i ;j ;k C l ;m e16T

For some #2(0.0,0.5]the cancellations

are approximated by

n i ;j ;k B n i ;j ;k à n ài ;j ;k B n ài ;j ;k à#

c n i ;j ;k <

e17T

n i ;j ;k B n i ;j ;k à n ài ;j ;k B n ài ;j ;k t#Finally,we have the non-negative integer

constraints

b n i ;j ;k ;

c n i ;j ;k ;P n i ;j ;k 2Z

e18Tb n i ;j ;k ;c n i ;j ;k ;P n i ;j ;k !0e19Twhile the nonanticipativity constraints are satis?ed by construction.Altogether,the model (12)–(19)represents a large-scale structured integer program which is of smaller dimension compared to its scenario formulation.More precisely,it contains IJK +4IJK(N–1–S )+3IJKS variables and 3IJK(N–1)+(P L l ?1M (l ))S constraints.Since all variables are non-negative and the bookings are bounded from above,the objective function is also bounded from above.Hence,the LP relaxation of the integer program,ie when the constraint (18)is ignored,is solvable.For its solution,any standard LP solver may be used.Owing to the distinction of itinerary,booking class,and point of sale the protec-tion levels eP n i ;j ;k Tn 2N allow considerably accurate control of booking requests.Today’s inventory systems usually hold

and process protection levels (or booking protects)on leg,booking class level or bid prices on leg,compartment level.Thus,processing of the protection levels in the present approach requires seamless booking control which is actually practised for par-tial or complete ?ight networks at some airlines.In the case of seamless control booking requests are not responded to by the computer reservation system (CRS)but processed by the airline’s inventory system or a separate ‘availability processor’(AP).In the following,use of an AP is assumed.The protection levels as solutions of the multistage stochastic programs form a (multivariate)stochastic process over time with the same structure as the input data.This di?ers from methods which calculate protection levels for the entire remaining booking period,but is similar to dynamic program approaches,which compute bid price vectors for all dcps to come.For practical operation,protection levels may be operated as follows.—The (deterministic)protection levels of

dcp t =0may be taken directly to the

AP.At dcps t ?t 0;t 02f 1;...;T à1g ,

the further process depends on the

actual booking inventory B i ;j ;k ;t 0:—If there exists a node n such that t(n)=

t 0and B i ;j ;k ;t 0?B n i ;j ;k ,the protection

levels P n i ;j ;k can be uploaded to the AP

for controlling the booking process

until the next dcp.

—If B i ;j ;k ;t 0?B n i ;j ;k for all nodes n with t(n)

=t 0,the stochastic optimisation model

is restarted with a new input scenario

tree having its root node at t 0.

—If,for any reason,such a re-optimisa-

tion is not possible,then information

on the probability distribution (means,

quantiles etc)of the relevant protection

levels (determined by the di?erence

between B i ;j ;k ;t 0and f B n i ;j ;k g t en T?t 0)could be taken to compute a fallback solution.age 272

new approach to O&D revenue management

NUMERICAL RESULTS

In the preliminary numerical tests,the SP model was set up and solved for a single leg?ight(namely,LH400,A340-300, Tuesday as day of departure).Table1 shows the dimensions of the corresponding O&D RM problem.The passenger demand was modelled starting from histor-ical data of the corresponding?ight as fol-lows.First,the data were adjusted subject to a suitable demand model(unconstrain-ing).Next,a set of scenarios was drawn by resampling techniques from the records containing Tuesday as day of departure. The average of three randomly drawn samples out of this set was then taken as an invidual scenario of the passenger demand process.In this way,300scenarios were generated and used as a starting point for the tree https://www.sodocs.net/doc/3a18966722.html,ing the tree con-struction algorithm(see section‘input sce-nario trees’)a scenario tree consisting of 150scenarios was generated,where150 scenarios were deleted in Step 1.The dimensions of the scenario tree and,thus, of the SP model(12)–(19)are shown in Table2.The tree is illustrated in Figure3. It contains branches at all dcps and exhibits branches of varying degree,starting with many branches at the root node.Ignoring the integrality constraints(18)the SP model was solved by CPLEX8.1.An opti-mal solution was found by CPLEX8.1in 4.62seconds on a Linux-PC equipped with a2GHz Intel Celeron processor.Figure4 shows the optimal protection levels at the ?rst stage,ie for the interval[0,1),and the corresponding fares.Figure5provides the trees of optimal protection levels over the whole booking horizon and the corre-sponding demand scenario trees for selected fare classes.Each picture also contains the mean value and the5per cent and95per cent quantile curves.All in all,the results seem to be reasonable and raise the expec-tation that moderately sized O&D network problems may be solved in acceptable run-ning times.

CONCLUSIONS

A stochastic programming approach to O&D revenue management is proposed.It is based on modelling scenario trees for passenger demand and does not require any assumption on the underlying demand distributions or on the correlations of the booking process.The RM problem is modelled by a multistage stochastic pro-gram in node form and solved by standard LP software.Numerical experience for a single-leg model indicates that the approach bears potential for solving O&D network models in reasonable time.Future work will be directed to the following issues:

Table1:Dimensions

L I J K T M(1) 11141183

Table2:SP model dimensions

S N No.of No.of

variables constraints 150115962,76248,786

Figure3:Scenario tree

Page273

Mo ller,Ro misch and Weber

Figure 4:Fares and optimal ?rst stage protection

levels

Figure 5:Cumulative passenger demand and protection level for selected fare classes

age 274

new approach to O&D revenue management

—analysis of O&D data,the generation of O&D demand scenarios and of demand scenario trees

—study of structural properties of the stochastic RM model and of the adapt-ability of decomposition approaches —numerical tests on entire networks —comparison with other approaches —completion of the model(no-shows, denied boarding cost)

—study of modelling speci?c demand patterns(seasonal demand,special events).

ACKNOWLEDGMENTS

The authors wish to thank Nicole Gro we-Kuska(formerly with the Humboldt-Uni-versity Berlin)for her invaluable input at earlier stages of this project and Holger Heitsch(Humboldt-University Berlin)for his assistance on generating the passenger demand scenario tree.Moreover,the com-ments and suggestions of the referees are gratefully acknowledged.

NOTES

1This research is supported by the DFG Research Center‘Mathematics for key technologies’(FZT 86)in Berlin.

R EFERENCES

Belobaba,P.P.(1987)‘Airline yield manage-ment:an overview of seat inventory control’,Transportation Science,21,63–73. Belobaba,P.P.(1989)‘Application of a prob-abilistic decision model to airline seat inven-tory control’,Operations Research,37,183–197.

Birge,J.R.and Louveaux,F.(1997)Introduc-tion to Stochastic Programming,Springer,New York.

Brumelle,S.L.and McGill,J.I.(1991)‘Airline seat allocation with multiple nested fare classes’,Operations Research,41,127–137 Brumelle,S.L.,McGill,J.I.,Oum,T.H., Sawaki,K.and Tretheway M.W.(1990)‘Allocation of airline seats between stochasti-cally dependent demands’,Transportation Sciences,24,182–192.Cooper,W.L.and Homem-de-Mello,T.

(2003)‘A class of hybrid methods for

revenue management’,Working Paper,Uni-

versity of Minnesota,Department of

Mechanical Engineering,URL:http://

https://www.sodocs.net/doc/3a18966722.html,/*billcoop/chm.pdf.

Curry,R.E.(1990)‘Optimal airline seat with

fare classes nested by origin and destinations’,

Transportation Science,24,193–204.

Dupac ova,J.,Consigli,G.and Wallace,S.W.

(2000)‘Scenarios for multistage stochastic

programs’,Annals of Operations Research,100,

25–53.

Dupac ova,J.,Gro we-Kuska,N.and Ro misch,

W.(2003)‘Scenario reduction in stochastic

programming:An approach using probabil-

ity metrics’,Mathematical Programming,Ser.

A,95,493–511.

Glover, F.,Glover,R.,Lorenzo,J.and

McMillan, C.(1982)‘The passenger-mix

problem in the scheduled airlines’,Interfaces,

12,73–79.

Gro we-Kuska,N.,Heitsch,H.and Ro misch,

W.(2003)‘Scenario reduction and scenario

tree construction for power management

problems’,in Borghetti, A.,Nucci, C. A.

and Paolone,M.(eds),IEEE Bologna Power

Tech Proceedings,IEEE.

Heitsch,H.and Ro misch,W.(2003)‘Scenario

reduction algorithms in stochastic program-

ming’,Computational Optimization and Appli-

cations,24,187–206.

Heitsch,H.and Ro misch,W.(2004)‘Scenario

tree modelling for multistage stochastic

programs’,in preparation.

H?yland,K.and Wallace,S.W.(2001)Gener-

ating scenario trees for multi-stage decision

problems’,Management Science,47,295–307.

Klein,R.and Petrick, A.(2003)‘Revenue

Management–Eine weitere Erfolgsstory des

Operations Research’,OR News,17,5–9.

Littlewood,K.(1972)‘Forecasting and control

of passengers’,in12th AGIFORS Symposium

Proceedings,American Airlines,New York,

95–128.

McGill,J.I.and van Ryzin,G.J.(1999)

‘Revenue management:research overview

and prospects’,Transportation Science,33,

233–256.

Pak,K.and Piersma,N.(2002)Airline Revenue

Management:An Overview of OR Techniques

Page275

Mo ller,Ro misch and Weber

1982–2001,Econometric Institute Report EI 2002-03,Erasmus University Rotterdam, URL:http://www.eur.nl/WebDOC/doc/ econometrie/feweco20020213101151.pdf. Pennanen,T.(2004)‘Epi-convergent discretiza-tions of multistage stochastic programs via integration quadratures’,Stochastic Program-ming E-Print Series2004(https://www.sodocs.net/doc/3a18966722.html,). P?ug,G.(2001)‘Scenario tree generation for multiperiod?nancial optimization by optimal discretization’,Mathematical Program-ming,Ser.B,89,251–271.

Rachev,S.T.and Ru schendorf,L.(1998)Mass Transportation Problems,Vol.I:Theory, Springer,New York.

Ro misch,W.and Schultz,R.(2001)Multi-stage stochastic integer programs:An intro-duction,in Gro tschel,M.,Krumke,S.O.and Rambau,J.(eds)Online Optimization of Large Scale Systems,Springer,Berlin,579–598. Ruszczy nski,A.and Shapiro,A.(eds)(2003) Stochastic Programming,Handbooks in Opera-tions Research and Management Science,Vol. 10,Elsevier,Amsterdam.

Simpson,R.W.(1989)Using Network Flow Techniques to Find Shadow Prices for Market Demands and Seat Inventory Control,(FTL Memorandum,M89-1),Massachusetts Insti-tute of Technology,Flight Transportation Laboratory,MA.

Smith,B.C.and Penn,C.W.(1988)Analysis of alternative origin-destination control stra-tegies,in Proceedings of the Twenty Eighth

Annual AGIFORS Symposium,New Seabury,MA.

Talluri,K.T.and van Ryzin,G.J.(1999)‘An analysis of bid-price controls for network revenue management’,Management Science, 44,1577–1593.

Talluri,K.T.and van Ryzin,G.J.(2004)The Theory and Practice of Revenue Management, Kluwer,Boston.

Van Ryzin,G.and McGill,J.(2000)Revenue management without forecasting or optimi-zation:an adaptive algorithm for determin-ing seat protection levels’,Management Science,46,760–775.

Van Ryzin,G.J.and Talluri,K.T.(2003) Revenue management,in Hall,R.W.(eds), Transportation Science,2nd edn,Kluwer, Boston,599–659.

Weatherford,L.R.(1998)‘A tutorial on opti-mization in the context of perishable-asset revenue management problems for the airline industry’,in Yu,G.(eds),Operations Research in the Airline Industry,fourth printing2002,Kluwer,Boston,68–100. Williamson,E.L.(1992)‘Airline network seat inventory control:methodologies and revenue impacts,PhD thesis,Massachusetts Institute of Technology,Department of Aeronautics and Astronautics.

Wollmer,R.D.(1992)‘An airline seat man-agement model for a single leg route when lower fare classes book?rst’,Operations Research,40,26–37.

age276

new approach to O&D revenue management