TY - JOUR

T1 - Some decomposition methods for revenue management

AU - Cooper, William L.

AU - Homem-De-mello, Tito

PY - 2007/8

Y1 - 2007/8

N2 - Working within a Markov decision process (MDP) framework, we study revenue management policies that combine aspects of mathematical programming approaches and pure MDP methods by decomposing the problem by time, state, or both. The "time decomposition" 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 policies perform well. By viewing the MDP as a large stochastic program, we derive some structural properties of two-leg problems. We show that these properties cannot, in general, be extended to larger networks. For such larger networks we also present a "state-space decomposition" approach that partitions the network problem into two-leg subproblems, each of which is solved. The solutions of these subproblems are then recombined to obtain a booking policy for the network problem.

AB - Working within a Markov decision process (MDP) framework, we study revenue management policies that combine aspects of mathematical programming approaches and pure MDP methods by decomposing the problem by time, state, or both. The "time decomposition" 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 policies perform well. By viewing the MDP as a large stochastic program, we derive some structural properties of two-leg problems. We show that these properties cannot, in general, be extended to larger networks. For such larger networks we also present a "state-space decomposition" approach that partitions the network problem into two-leg subproblems, each of which is solved. The solutions of these subproblems are then recombined to obtain a booking policy for the network problem.

KW - Markov decision processes

KW - Network revenue management

KW - Stochastic optimization

KW - Yield management

UR - http://www.scopus.com/inward/record.url?scp=70449623524&partnerID=8YFLogxK

U2 - 10.1287/trsc.1060.0184

DO - 10.1287/trsc.1060.0184

M3 - Article

AN - SCOPUS:70449623524

VL - 41

SP - 332

EP - 353

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 3

ER -