Optimization Online


What Multistage Stochastic Programming Can Do for Network Revenue Management

Victor DeMiguel (avmiguel***at***london.edu)
Nishant Mishra (nmishra.phd2003***at***london.edu)

Abstract: Airlines must dynamically choose how to allocate their flight capacity to incoming travel demand. Because some passengers take connecting flights, the decisions for all network flights must be made simultaneously. To simplify the decision making process, most practitioners assume demand is deterministic and equal to average demand. We propose a multistage stochastic programming approach that models demand via a scenario tree and can accommodate any discrete demand distribution. This approach reflects the dynamic nature of the problem and does not assume the decision maker has perfect information on future demand. We consider four different methodologies for multistage scenario tree generation (Monte-Carlo sampling, principal-component sampling, moment matching, and bootstrapping) and conclude that the sampling methods are best. Finally, our numerical results show that the multistage approach performs significantly better than the deterministic approach and that revenue managers who ignore demand uncertainty may be losing between 1% and 2% in average revenue. Moreover, the multistage approach is also significantly better than the randomized linear programming approach of Talluri and Van Ryzin (1999) provided the multistage scenario tree has a sufficiently large number of branches.

Keywords: network revenue management, multistage stochastic programming, scenario generation,

Category 1: Applications -- OR and Management Sciences (Airline Optimization )

Category 2: Stochastic Programming

Citation: London Business School working paper 2006.

Download: [PDF]

Entry Submitted: 10/31/2006
Entry Accepted: 10/31/2006
Entry Last Modified: 10/31/2006

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