Scholarlink

<p>We develop novel heuristics for the single-leg seat inventory control problem using robust optimization. Our starting point is the bounded, continuous knapsack formulation of the single-leg problem. We show how a modification of the classical knapsack problem brings the uncertain parameter (demand) to both the objective function and the constraints. We derive robust counterparts of this model based on different measures of robustness and uncertainty sets. The robust optimal capacity allocation is then modified heuristically to prevent under-utilization of capacity. The modified capacity allocation yields new nested booking limit policies for the single-leg revenue management problem with independent demand. For the choice-based demand model in revenue management, the same robust models—with minimal change—provide the optimal time each choice set should be offered. The performance of the new heuristic is shown to be effective in simulations, with good worst-case guarantees and low computational complexity.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Heuristics for revenue management: an application of the robust knapsack problem

  • 期刊论文

  • 发表日期：

    2026年4月10日

查看全文
  • İrem Bahtiyar,
  • Ali Eren Demir,
  • Mustafa Ç. Pınar,
  • Itir Karaesmen

摘要

We develop novel heuristics for the single-leg seat inventory control problem using robust optimization. Our starting point is the bounded, continuous knapsack formulation of the single-leg problem. We show how a modification of the classical knapsack problem brings the uncertain parameter (demand) to both the objective function and the constraints. We derive robust counterparts of this model based on different measures of robustness and uncertainty sets. The robust optimal capacity allocation is then modified heuristically to prevent under-utilization of capacity. The modified capacity allocation yields new nested booking limit policies for the single-leg revenue management problem with independent demand. For the choice-based demand model in revenue management, the same robust models—with minimal change—provide the optimal time each choice set should be offered. The performance of the new heuristic is shown to be effective in simulations, with good worst-case guarantees and low computational complexity.