Constant-Factor Algorithms for Revenue Management with Consecutive Stays

We study network revenue management problems motivated by applications, such as railway ticket sales and hotel room bookings. Requests, each requiring a resource for a consecutive stay, arrive sequentially with known arrival probabilities. We investigate two scenarios: the accept-or-reject scenario, where a request can be fulfilled by assigning any available resource, and the basic attraction model (BAM)-based scenario, which generalizes the former by incorporating customer preferences through the BAM, allowing the platform to offer an assortment of available resources from which the customer may choose. We develop polynomial-time policies and evaluate their performance using approximation ratios defined as the ratios between the expected revenue of our policy and that of the optimal online algorithm. When each arrival has a fixed request type (e.g., the stay interval is fixed), we establish constant-factor guarantees: a ratio of $1-1/e\approx 0.632$ for the accept-or-reject scenario and 0.271 for the BAM-based scenario. We further extend these results to the case where the request type is random (e.g., the stay interval is random). In this setting, the approximation ratios incur an additional multiplicative factor of $1-1/e$, resulting in guarantees of at least 0.399 for the accept-or-reject scenario and 0.171 for the BAM-based scenario. These constant-factor guarantees stand in sharp contrast to the prior nonconstant competitive ratios that are benchmarked against the offline optimum.

Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2021-04295].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2025.1994.