This page is based on the article:
In 2013, the paper was awarded the OR Society's Goodeve medal for the best paper published in JORS in 2012.
Besides the contribution to the theory of revenue management, the obtained results also represent a significant improvement of the practical approaches to large-scale revenue management...The improved computational performance results in reduced IT requirements and hence substantial potential cost savings of carriers.
J. Goerke-von Stockert, Director Revenue Management & Pricing, Lufthansa Systems AG
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.