Overbooking with Bounded Loss

• 成果类型: Article
• 署名作者: Freund, Daniel; Zhao, Jiayu (Kamessi)
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1293
• 发表日期: 2023
• 页码: 1344-1363
• 关键词: Network Revenue Management; linear-programming method; yield-management; DECISION; POLICY

摘要

We study a classic 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, that is, its expected loss is inde omega(root T) pendent of T. This improves upon prior works achieving omega(T) guarantees.