Heuristic policies for stochastic knapsack problem with time‐varying random demand

Yingdong Lu

Applied Stochastic Models in Business and Industry, 2018, vol. 34, issue 6, 1007-1016

Abstract: In this paper, we consider the classic stochastic (dynamic) knapsack problem, a fundamental mathematical model in revenue management, with general time‐varying random demand. Our main goal is to study the optimal policies, which can be obtained by solving the dynamic programming formulated for the problem, both qualitatively and quantitatively. It is well known that, when the demand size is fixed and the demand distribution is stationary over time, the value function of the dynamic programming exhibits extremely useful first‐ and second‐order monotonicity properties, which lead to monotonicity properties of the optimal policies. In this paper, we are able to verify that these results still hold even in the case that the price distributions are time dependent. When we further relax the demand size distribution assumptions and allow them to be arbitrary, for example, in random batches, we develop a scheme for using value function of alternative unit demand systems to provide bounds to the value function. These results confirm some of the basic understandings of the stochastic knapsack problem. As a natural consequence, we propose a new class of heuristic policies, two‐dimensional switch‐over policies, and discuss numerical procedures for optimizing the parameters of the policies. Extensive numerical experiments demonstrate that these switch‐over policies can provide performances that are in a close neighborhood of the optimum statistically.

Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/asmb.2389

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:apsmbi:v:34:y:2018:i:6:p:1007-1016

Access Statistics for this article

More articles in Applied Stochastic Models in Business and Industry from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().