Optimization Online


A Class of Hybrid Methods for Revenue Management

William Cooper (billcoop***at***me.umn.edu)
Tito Homem-de-Mello (tito***at***northwestern.edu)

Abstract: We consider a Markov decision process model of a network revenue management problem. Working within this formal framework, we study policies that combine aspects of mathematical programming approaches and pure Markov decision process methods. The policies employ heuristics early in the booking horizon, and switch to a more-detailed decision rule closer to the time of departure. We present a family of formulations that yield such policies, and discuss versions of the formulation that have appeared in the literature. Subsequently, we describe sampling-based stochastic optimization methods for solving a particular case of the formulation. Numerical results for two-leg problems suggest that the resulting hybrid policies do perform strongly. By viewing the Markov decision process as a large stochastic program, we derive some structural properties of two-leg problems. We also show that these properties cannot, in general, be extended to larger networks.

Keywords: Revenue management, Markov decision processes, stochastic optimization, Monte Carlo methods

Category 1: Applications -- OR and Management Sciences (Yield Management )

Category 2: Stochastic Programming

Category 3: Other Topics (Dynamic Programming )

Citation: Working paper 03-015, Department of IE/MS, Northwestern University

Download: [PDF]

Entry Submitted: 07/24/2002
Entry Accepted: 07/25/2002
Entry Last Modified: 06/24/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society