Overbooking with Bounded Loss

DOI10.1287/MOOR.2022.1293MaRDI QIDQ6121630zbMATH OpenOpenAlexFDO

Authors Daniel Freund, Jia-Yu Zhao

Publication date 27 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.11148

zbMATH Keywords

approximate dynamic programmingcapacity managementonline stochastic decision makingoverbookingrevenue management

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22)

Abstract: We study a classical problem in revenue management: quantity-based single-resource revenue management with no-shows. In this problem, a firm observes a sequence of $T$ customers requesting a service. Each arrival is drawn independently from a known distribution of $k$ different types, and the firm needs to decide irrevocably whether to accept or reject requests in an online fashion. The firm has a capacity of resources $B$, and wants to maximize its profit. Each accepted service request yields a type-dependent revenue and has a type-dependent probability of requiring a resource once all arrivals have occurred (or, be a no-show). If the number of accepted arrivals that require a resource at the end of the horizon is greater than $B$, the firm needs to pay a fixed compensation for each service request that it cannot fulfill. With a clairvoyant, that knows all arrivals ahead of time, as a benchmark, we provide an algorithm with a uniform additive loss bound, i.e., its expected loss is independent of $T$. This improves upon prior works achieving $Omega(sqrtT)$ guarantees.

Recommendations

• Toward Robust Revenue Management: Competitive Analysis of Online Booking
• Technical note -- An improved analysis of LP-based control for revenue management
• Online stochastic reservation systems
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Capacity allocation for demand of different customer-product-combinations with cancellations, no-shows, and overbooking when there is a sequential delivery of service

This page was built for publication: Overbooking with Bounded Loss

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6121630)