Finite Horizon Stochastic Knapsacks with Applications to Yield Management

Richard Van Slyke () and Yi Young
Additional contact information
Richard Van Slyke: Polytechnic University, 6 Metro Tech Center, Brooklyn, New York 11201
Yi Young: Polytechnic University, 6 Metro Tech Center, Brooklyn, New York 11201

Operations Research, 2000, vol. 48, issue 1, 155-172

Abstract: 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 time 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 w k ; 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.

Keywords: Dynamic programming/Optimal control models: stochastic; finite horizon; continuous time; finite states; Probability; stochastic model applications; Transportation: airline yield management (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.1.155.12457 (application/pdf)

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:inm:oropre:v:48:y:2000:i:1:p:155-172

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().