DFG-Forschungszentrum Matheon

Application Area B: Traffic and communication networks
Project B6

Origin destination control in airline revenue management by dynamic stochastic programming

Lufthansa Systems Berlin DFG Forschungszentrum Berlin Humboldt-Universität zu Berlin
Duration: July 2002 - May 2006
Project director: Prof. Dr. W. Römisch

Department of Mathematics, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany

Tel: +49 (0)30 - 2093 2561 (office) / - 2093 2353 (secretary)

email: romisch@mathematik.hu-berlin.de
Responsible: Dipl.-Math. Andris Möller

Tel: +49 (0)30 - 2093 2262 (office) / - 2093 2353 (secretary)

email: andris@mathematik.hu-berlin.de
Cooperation: Lufthansa Systems Berlin
Support: DFG Research Center "Mathematics for Key Technologies"

Description :

Revenue (or yield) management aims to control sale of inventory under uncertainty such that the (expected) profit is maximized. Since its foundation, airline revenue management has concentrated on optimizing booking control parameters on a single flight (leg) level. However, many characteristics are not leg-specific (e.g. the uncertain passenger demand), but depend on origin destination itineraries. Hence, the performance of leg-based approaches is limited and optimization methods are needed that work on the origin destination (OD) level. But, the presently available OD optimization methods have some lacks in common (e.g. unrealistic assumptions, ignoring the integer nature of the model, separation of related tasks).

A new dynamic stochastic programming model for origin destination control in airline revenue management is developed in [5], [6]. The new model will be compared with earlier approaches both by simulation studies and by investigating its structural and stability properties. Implications of these properties concern both essential ingredients of the algorithmic approach, namely, the construction of approximations of the multivariate booking demand processes and the design of solution algorithms (e.g. LP-based branch-and-cut, Lagrangian decomposition [3], [7]). Based on ideas in [1] and [2] we developed methods for constructing scenario trees from data scenarios in [4]. The whole solution procedure has been implemented and tested on real-life data of the stochastic booking demand of the company Lufthansa Systems Berlin.

[1] J. Dupacova, N. Gröwe-Kuska and W. Römisch:

Scenario reduction in stochastic programming: An approach using probability metrics.

Mathematical Programming Ser. A 95 (2003), 493-511.
[2] N. Gröwe-Kuska, H. Heitsch and W. Römisch:

Scenario reduction and scenario tree construction for power management problems.

IEEE Bologna Power Tech Proceedings (A. Borghetti, C.A. Nucci, M. Paolone eds.), 2003 IEEE.
[3] D. Dentcheva and W. Römisch:

Duality gaps in nonconvex stochastic optimization.

Mathematical Programming Ser. A  101 (2004), 515-535.
[4] H. Heitsch and W. Römisch:

Scenario tree modelling for multistage stochastic programs.

Preprint 296, DFG Research Center Matheon "Mathematics for key technologies", 2005 and submitted.
[5] A. Möller, W. Römisch and K. Weber:

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

Journal of Revenue and Pricing Management 3 (2004), 265-276.
[6] A. Möller, W. Römisch and K. Weber:

Airline network revenue management by multistage stochastic programming,

Preprint 358, DFG Research Center Matheon "Mathematics for key technologies", 2006 and submitted.
[7] W. Römisch and R. Schultz:

Multistage stochastic integer programs: An introduction.

In: Online Optimization of Large Scale Systems (M. Grötschel, S.O. Krumke, J. Rambau eds.), Springer-Verlag, Berlin 2001, 579-598.

last modified November 20, 2006