Expected Future Value Decomposition Based Bid Price Generation For Large-scale Network Revenue Management

This paper studies a multi-stage stochastic programming (SP) 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 approach. We compare our revenues to those obtained by additive bid prices, such that the bid prices derived from the Deterministic Equivalent Model (DEM) of the compact representation of the SP model. Our computational experience shows that the revenues obtained by our approach are better for middle-range values of the load factor of demand, while the differences among all the approaches we have tested are insignificant for extreme values. Moreover, our approach requires significantly less computation time than the optimization of DEM by plain use of optimization engines. Problem instances with 72 pairs of bundle-fare classes have been solved in less than 1 minute, with 800 pairs in less than 5 minutes, and with 4000 pairs in less than 1 hour. The time taken by DEM was, in general, of one order of magnitude higher. Finally, for the three largest problem instances, and after 2 hours, the expected revenue returned by DEM was below that obtained by EFV by 13.47%, 17.14%, 38.94%, respectively.