Finite horizon stochastic knapsacks with applications to yield management
成果类型：
Article
署名作者：
van Slyke, R; Young, Y
署名单位：
New York University; New York University Tandon School of Engineering
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.1.155.12457
发表日期：
2000
页码：
155-172
关键词：
摘要：
The finite horizon stochastic knapsack combines a secretary problem with an integer knapsack problem. It is useful for optimizing sales of perishable commodities with low marginal costs to impatient customers. Applications include yield management for airlines, hotels/motels, broadcasting advertisements, and car rentals. In these problems, K types of customers arrive stochastically. Customer type, k, has an integer weight w(k), a value b(k), and an arrival rate lambda(k)(t) (which depends on time). We consider arrivals over a continuous rime horizon [0, T] to a knapsack with capacity W. For each arrival that fits in the remaining knapsack capacity, we may (1) accept it, receiving b(k) while giving up capacity wk; or (2) reject it, forgoing the value and not losing capacity. The choice must be immediate; a customer not accepted on arrival is lost. We model the problem using continuous time, discrete state, finite horizon, dynamic programming. We characterize the optimal return function and the optimal acceptance strategy for this problem, and we give solution methods. We generalize to multidimensional knapsack problems. We also consider the special case where w(k) = 1 for all k. This is the classic airline yield problem. Finally, we formulate and solve a new version of the secretary problem.