An LP based approximate dynamic programming model to address airline overbooking under cancellation, refund and no-show
DOI:
https://doi.org/10.2298/YJOR170918026SKeywords:
revenue management, approximate dynamic programming, overbooking, cancellation, no-Show, refundAbstract
In this paper we simultaneously address four constraints relevant to airline revenue management problem: flight cancellation, customer no-shows, overbooking, and refunding. We develop a linear program closely related to the dynamic program formulation of the problem, which we later use to approximate the optimal decision rule for rejecting or accepting customers. First, we give a novel proof that the optimal objective function of this linear program is always an upper bound for the dynamic program. Secondly, we construct a decision rule based on this linear program and prove that it is asymptotically optimal under certain circumstances. Finally, using Monte Carlo simulation, we demonstrate that, numerically, the result of the linear programming policy presented in this paper has a short distance to the upper bound of the optimal answer, which makes it a fairly good approximate answer to the intractable dynamic program.References
Arslan, A., Frenk, H., Sezer, S., On the Single leg Airline Revenue Management Problem in Continuous Time, Springer Verlag Berlin Heidelberg, 2015.
Beckmann, M.J., Decision and Team Problems in Airline Reservations, Econometrica, 26 (1958) 134-145.
Bertsimas, D., Popescu, I., Revenue Management in a Dynamic Network Environment, Transportation Science, 37 (2003) 257-257.
Birbil, S., Frenk, J., Gromicho, J., Zhang, Sh., A Network Airline Revenue Management Framework based on Decomposition by Origins and Destinations, Transportation Science, 48 (2013) 313-333.
Chapuis, J.M., Basics of Dynamic Programming for Revenue Management, HAL, 2008, 21.
Chatwin, E., Multiperiod Airline Overbooking with a Single Fare Class, Operations Research, 46 (1998) 805-819.
Chiang, Chen, Xu, An Overview of Research on Revenue Management Current Issues, and Future Research, International Journal of Revenue Management, 1 (2007) 33-49.
Coughlan, J., Airline Overbooking in the Multi Class Case, The Journal of the Operations Research Society, 50 (1999) 1098-1103.
Erdelyi, A., Topaloglu, H., A Dynamic Programming Decomposition Method for Making Overbooking Decisions Over an Airline Network, INFORMS Journal on Computing, 22 (2010) 443-456.
Erdelyi, A., Topaloglu, H., Approximate Dynamic Programming for Dynamic Capacity Allocation with Multiple Priority Levels, IIE Transactions, 43 (2011) 129-142.
Farias, V.F., An Approximate Dynamic Programming Approach to Network Revenue Management, 2007.
Farias, V.F., Van Roy, B., The Linear Programming Approach to Approximate Dynamic Programming, Operations Research, 51 (2003) 850-865.
Gallego, G., van Ryzin, G., A Multiproduct Dynamic Pricing Problem and its Applications to Network Yield Management, Operations Research, 45 (1997) 24-41.
Goench, J., Using Dynamic Programming Decomposition for Revenue Management with Opaque Products, German Academic Association for Business Research (VHB) 6 (2013) 94-115.
Goench, J., Steinhardt, C., On the Incorporation of Upgrades into Airline Network Revenue Management, Revenue Management Science, 2014.
Gosavi, Okay, Kahraman, Simulation Optimization for Revenue Management of Airlines with Cancellations and Overbooking, OR Spectrum, 29 (2006) 21-38.
Gosavi, Bandla, K., Das, A Reinforcement Learning Approach to a Single Leg Airline Revenue Management Problem with Multiple Fare Classes and Overbooking, IIE Transactions, 34 (2002) 729-742.
Karaesman, van Ryzin, B., Overbooking with Substitutable Inventory Classes, Operations Research, 52 (2004) 83-104.
Kleywegt, J., Anton, An Optimal Control Problem of Dynamic Pricing, Conference Proceedings, 2001.
Kunnumkal, Topaloglu, A Tractable Revenue Management Model for Capacity Allocation and Overbooking Over an Airline Network, Flexible Services and Manufacturing Journal, 20 (2008) 125-147.
Pak, Piersma, Overview of OR Techniques for Airline Revenue Management, Statistica Neerlandica, 56 (2002) 479-495.
Smet, T., Yield Management Literature Review, DocPlayer net, (2003) 15.
Talluri, T., van Ryzin, J., Karaesman, Z., Vulcano, J., Revenue Management Models and Methods, 2008 Winter Simulation Conference, Austin, TX 145-156.
Talluri, T., van Ryzin, J., An Analysis of Bid Price Controls for Network Revenue Management, Management Science, 44 (1998) 1577-1593.
Talluri, T., van Ryzin, J., The Theory and Practice of Revenue Management, New York, Kluwer Academic Publishers, 2004.
Thompson, H.R., Statistical Problems in Airline Revenue Management, Operations Research Society, 12 (1961) 167-185.
Weatherford, L., Khokhlov, A., The Theory and Practice of Dynamic Programming-based Bid Prices, Journal of Revenue and Pricing Management, 11 (2012) 518-535.
Zhang, D., An Improved Dynamic Programming Decomposition Approach for Network Revenue Management, Manufacturing and Service Operations Management, 13 (2011) 35-52.
Downloads
Published
Issue
Section
License
Copyright (c) 2019 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
