IDEAS home Printed from https://ideas.repec.org/p/hal/wpaper/halshs-01155698.html
   My bibliography  Save this paper

The Monte Carlo first-come-first-served heuristic for network revenue management

Author

Listed:
  • Nicolas Houy

    (GATE Lyon Saint-Étienne - Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne - ENS de Lyon - École normale supérieure de Lyon - UL2 - Université Lumière - Lyon 2 - UCBL - Université Claude Bernard Lyon 1 - Université de Lyon - UJM - Université Jean Monnet - Saint-Étienne - CNRS - Centre National de la Recherche Scientifique)

  • François Le Grand

    (EM - EMLyon Business School)

Abstract

We introduce the Monte-Carlo based heuristic with first-come-first-served approximation for future optimal strategy (MC-FCFS) in order to maximize profit in a network revenue management problem. Like the randomized linear programming (RLP) model, one purpose of the MC-FCFS heuristic is to have information about displacement costs, considering the full probability distribution of future demands instead of a simplified degenerate distribution as in the deterministic linear programming (DLP) model. However, this information is conveyed by applying the FCFS heuristic as a future strategy rather than using the optimal ex-post profits as in the RLP heuristic. We show that MC-FCFS performs approximately as well as the RLP heuristic at a much lower computational cost and much better than the DLP heuristic at maximizing profit in a multi-night hotel booking setting with or without planned upgrades.

Suggested Citation

  • Nicolas Houy & François Le Grand, 2015. "The Monte Carlo first-come-first-served heuristic for network revenue management," Working Papers halshs-01155698, HAL.
    • Handle: RePEc:hal:wpaper:halshs-01155698
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-01155698
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-01155698/document
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Meissner, Joern & Strauss, Arne, 2012. "Network revenue management with inventory-sensitive bid prices and customer choice," European Journal of Operational Research, Elsevier, vol. 216(2), pages 459-468.
    2. Kalyan Talluri & Garrett van Ryzin, 1998. "An Analysis of Bid-Price Controls for Network Revenue Management," Management Science, INFORMS, vol. 44(11-Part-1), pages 1577-1593, November.
    3. Jeffrey I. McGill & Garrett J. van Ryzin, 1999. "Revenue Management: Research Overview and Prospects," Transportation Science, INFORMS, vol. 33(2), pages 233-256, May.
    4. Dan Zhang & Daniel Adelman, 2009. "An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice," Transportation Science, INFORMS, vol. 43(3), pages 381-394, August.
    5. Demet Çetiner, 2013. "Fair Revenue Sharing Mechanisms for Strategic Passenger Airline Alliances," Lecture Notes in Economics and Mathematical Systems, Springer, edition 127, number 978-3-642-35822-7, December.
    6. de Boer, Sanne V. & Freling, Richard & Piersma, Nanda, 2002. "Mathematical programming for network revenue management revisited," European Journal of Operational Research, Elsevier, vol. 137(1), pages 72-92, February.
    7. Huseyin Topaloglu, 2009. "Using Lagrangian Relaxation to Compute Capacity-Dependent Bid Prices in Network Revenue Management," Operations Research, INFORMS, vol. 57(3), pages 637-649, June.
    8. Kalyan Talluri & Garrett van Ryzin, 1999. "A Randomized Linear Programming Method for Computing Network Bid Prices," Transportation Science, INFORMS, vol. 33(2), pages 207-216, May.
    9. Demet Çetiner, 2013. "Selected Topics in Revenue Management," Lecture Notes in Economics and Mathematical Systems, in: Fair Revenue Sharing Mechanisms for Strategic Passenger Airline Alliances, edition 127, chapter 0, pages 3-30, Springer.
    10. Qian Liu & Garrett van Ryzin, 2008. "On the Choice-Based Linear Programming Model for Network Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 10(2), pages 288-310, October.
    11. Steinhardt, Claudius & Gönsch, Jochen, 2012. "Integrated revenue management approaches for capacity control with planned upgrades," European Journal of Operational Research, Elsevier, vol. 223(2), pages 380-391.
    12. Daniel Adelman, 2007. "Dynamic Bid Prices in Revenue Management," Operations Research, INFORMS, vol. 55(4), pages 647-661, August.
    13. Fred Glover & Randy Glover & Joe Lorenzo & Claude McMillan, 1982. "The Passenger-Mix Problem in the Scheduled Airlines," Interfaces, INFORMS, vol. 12(3), pages 73-80, June.
    14. Juan José Miranda Bront & Isabel Méndez-Díaz & Gustavo Vulcano, 2009. "A Column Generation Algorithm for Choice-Based Network Revenue Management," Operations Research, INFORMS, vol. 57(3), pages 769-784, June.
    15. Wen-Chyuan Chiang & Jason C.H. Chen & Xiaojing Xu, 2007. "An overview of research on revenue management: current issues and future research," International Journal of Revenue Management, Inderscience Enterprises Ltd, vol. 1(1), pages 97-128.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nicolas Houy & François Le Grand, 2015. "Financing and advising with (over)confident entrepreneurs : an experimental investigation," Working Papers 1514, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
    2. Meissner, Joern & Strauss, Arne, 2012. "Improved bid prices for choice-based network revenue management," European Journal of Operational Research, Elsevier, vol. 217(2), pages 417-427.
    3. Syed Asif Raza & Rafi Ashrafi & Ali Akgunduz, 2020. "A bibliometric analysis of revenue management in airline industry," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 19(6), pages 436-465, December.
    4. Strauss, Arne K. & Klein, Robert & Steinhardt, Claudius, 2018. "A review of choice-based revenue management: Theory and methods," European Journal of Operational Research, Elsevier, vol. 271(2), pages 375-387.
    5. Meissner, Joern & Strauss, Arne, 2012. "Network revenue management with inventory-sensitive bid prices and customer choice," European Journal of Operational Research, Elsevier, vol. 216(2), pages 459-468.
    6. Dan Zhang & Larry Weatherford, 2017. "Dynamic Pricing for Network Revenue Management: A New Approach and Application in the Hotel Industry," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 18-35, February.
    7. Wuyang Yuan & Lei Nie & Xin Wu & Huiling Fu, 2018. "A dynamic bid price approach for the seat inventory control problem in railway networks with consideration of passenger transfer," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-23, August.
    8. Thomas W. M. Vossen & Dan Zhang, 2015. "Reductions of Approximate Linear Programs for Network Revenue Management," Operations Research, INFORMS, vol. 63(6), pages 1352-1371, December.
    9. Yuhang Ma & Paat Rusmevichientong & Mika Sumida & Huseyin Topaloglu, 2020. "An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals," Operations Research, INFORMS, vol. 68(3), pages 834-855, May.
    10. Dan Zhang, 2011. "An Improved Dynamic Programming Decomposition Approach for Network Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 13(1), pages 35-52, April.
    11. Alexander Erdelyi & Huseyin Topaloglu, 2010. "A Dynamic Programming Decomposition Method for Making Overbooking Decisions Over an Airline Network," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 443-456, August.
    12. Juan M. Chaneton & Gustavo Vulcano, 2011. "Computing Bid Prices for Revenue Management Under Customer Choice Behavior," Manufacturing & Service Operations Management, INFORMS, vol. 13(4), pages 452-470, October.
    13. Steinhardt, Claudius & Gönsch, Jochen, 2012. "Integrated revenue management approaches for capacity control with planned upgrades," European Journal of Operational Research, Elsevier, vol. 223(2), pages 380-391.
    14. Mika Sumida & Huseyin Topaloglu, 2019. "An Approximation Algorithm for Capacity Allocation Over a Single Flight Leg with Fare-Locking," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 83-99, February.
    15. Chaoxu Tong & Huseyin Topaloglu, 2014. "On the Approximate Linear Programming Approach for Network Revenue Management Problems," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 121-134, February.
    16. Kalyan Talluri, 2014. "New Formulations for Choice Network Revenue Management," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 401-413, May.
    17. Sumit Kunnumkal & Kalyan Talluri, 2019. "A strong Lagrangian relaxation for general discrete-choice network revenue management," Computational Optimization and Applications, Springer, vol. 73(1), pages 275-310, May.
    18. Chan Seng Pun & Diego Klabjan & Fikri Karaesmen & Sergey Shebalov, 2016. "Itinerary-based nesting control with upsell," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 15(2), pages 107-137, April.
    19. Sebastian Koch & Jochen Gönsch & Claudius Steinhardt, 2017. "Dynamic Programming Decomposition for Choice-Based Revenue Management with Flexible Products," Transportation Science, INFORMS, vol. 51(4), pages 1046-1062, November.
    20. Hans Buhl & Robert Klein & Johannes Kolb & Andrea Landherr, 2011. "CR 2 M—an approach for capacity control considering long-term effects on the value of a customer for the company," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 22(2), pages 187-204, December.

    More about this item

    Keywords

    Network revenue management; Monte-Carlo simulations; randomized linear programming;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:wpaper:halshs-01155698. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.