We study network revenue management problems motivated by applications such as railway ticket sales and hotel room bookings. Requests arrive sequentially, each requiring a resource for a consecutive stay, with known arrival probabilities. We investigate two scenarios: the accept-or-reject scenario, where any available resource can fulfill a request; and the BAM-based scenario, which generalizes the former by incorporating customer preferences through the Basic Attraction Model (BAM), allowing the platform to offer an assortment of available resources for customer choice.
We develop polynomial-time policies and evaluate their performance using approximation ratios, defined as the ratio between the expected revenue of our policy and that of the optimal online algorithm. For fixed request types (e.g., fixed stay intervals), we establish constant-factor guarantees: a ratio of $1 - 1/e$ for the accept-or-reject scenario and $0.25$ for the BAM-based scenario.
We extend these results to the case with random request types (e.g., random stay intervals). Here, the approximation ratios incur an additional multiplicative factor of $1 - 1/e$, yielding guarantees of at least $0.399$ for the accept-or-reject scenario and $0.156$ for the BAM-based scenario. These constant-factor guarantees contrast sharply with previous non-constant competitive ratios benchmarked against the offline optimum.
Blogger's Review: This paper presents effective algorithmic strategies for revenue management problems, particularly highlighting their application in random request scenarios. The constant-factor guarantees enhance the accuracy of revenue predictions and provide robust support for practical applications, making this work noteworthy and worthy of further exploration.