Optimization Online


Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management

L.F. Escudero(laureano.escudero***at***urjc.es)
J.F. Monge(monge***at***umh.es)
D. Romero Morales(dolores.romero-morales***at***sbs.ox.ac.uk)
J. Wang(jingbo.wang***at***sbs.ox.ac.uk)

Abstract: This paper studies a multi-stage stochastic programming model for large-scale network revenue management. We solve the model by means of the so-called Expected Future Value (EFV) decomposition via scenario analysis, estimating the impact of the decisions made at a given stage on the objective function value related to the future stages. The EFV curves are used to define bid prices on bundles of resources directly, as opposed to the traditional additive bid prices. Numerical results show that the revenue outcome of our approach is generally comparable to that of state-of-the-art additive approaches, and tends to be better when the network structure is complex. Moreover, our approach requires significantly less computation time than the direct optimization, taking only up to 5 minutes for large-scale problem instances (up to 2.6 million variables and 2.3 million constraints).

Keywords: network revenue management, scenario trees, stochastic dynamic programming, expected future value curves, non-additive bid prices

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

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/21/2009
Entry Accepted: 12/21/2009
Entry Last Modified: 12/21/2009

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