Revenue Management with Lufthansa Systems
This page is based on the following article:
Kemmer, P., Strauss, A. and Winter, T. 2011. "Dynamic Simultaneous Fare Proration for Large-Scale Network Revenue Management", submitted. [Download PDF]
Airlines, train companies and
other service providers share a common problem: how to optimise the prices for
their products over a large network of some sort. The optimal solution for such
problems can theoretically be obtained by a dynamic programme; however, it
cannot be solved exactly due to the size of the state space even for small
networks. In practice, flight networks of major airlines can include over 1,000
flights, over 15,000 itineraries and about 20 booking classes that have to be
optimised repeatedly every day. Additional complexity stems from incorporating
customer choice behaviour between available product alternatives. In order to
tackle problems of such size, a standard approach is to decompose the network
optimisation problem in some way into a collection of small problems
corresponding to the individual flight legs. Improved variants of such
decomposition techniques in combination with models of customer choice are
currently intensively researched. However, the techniques recently published
typically focus on very small problems (<10 flights) and are too slow to be
applied for large-scale problems.
Average run time reduction of 80% relative to current method
We propose a new dynamic fare proration method specifically having large-scale applications in mind. It decomposes the network problem by fare proration and solves the resource-level dynamic programs simultaneously using simple, endogenously obtained dynamic marginal capacity value estimates to update fare prorations over time. An extensive numerical simulation study demonstrates that the method results in tightened upper bounds on the optimal expected revenue, and that the obtained policies are very effective with regard to achieved revenues and required runtime.
The figure depicts the marginal value of capacity over time for three different methods. The benchmark method uses a static estimate over the entire time horizon, whereas our proposed techniques reflect the decrease in marginal capacity value as we approach the departure day without significantly increased computational cost.
