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

Laureano F. Escudero, Juan Francisco Monge, Dolores Romero Morales, J. Wang

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

This paper studies a multistage 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 as 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, whereas the differences among all the approaches we have tested are insignificant for extreme values. Moreover, our approach requires significantly less computation time than does 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 one minute, with 800 pairs in less than five minutes, and with 4,000 pairs in less than one hour. The time taken by DEM was, in general, of one order of magnitude higher. Finally, for the three largest problem instances, and after two hours, the expected revenue returned by DEM was below that obtained by EFV by 13.47%, 17.14%, and 38.94%, respectively.
This paper studies a multistage 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 as 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, whereas the differences among all the approaches we have tested are insignificant for extreme values. Moreover, our approach requires significantly less computation time than does 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 one minute, with 800 pairs in less than five minutes, and with 4,000 pairs in less than one hour. The time taken by DEM was, in general, of one order of magnitude higher. Finally, for the three largest problem instances, and after two hours, the expected revenue returned by DEM was below that obtained by EFV by 13.47%, 17.14%, and 38.94%, respectively.
LanguageEnglish
JournalTransportation Science
Volume47
Issue number2
Pages181-197
ISSN0041-1655
DOIs
StatePublished - 2013
Externally publishedYes

Keywords

    Cite this

    @article{d03cc19aabaa45c195c121348caf3d58,
    title = "Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management",
    abstract = "This paper studies a multistage 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 as 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, whereas the differences among all the approaches we have tested are insignificant for extreme values. Moreover, our approach requires significantly less computation time than does 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 one minute, with 800 pairs in less than five minutes, and with 4,000 pairs in less than one hour. The time taken by DEM was, in general, of one order of magnitude higher. Finally, for the three largest problem instances, and after two hours, the expected revenue returned by DEM was below that obtained by EFV by 13.47{\%}, 17.14{\%}, and 38.94{\%}, respectively.",
    keywords = "Network revenue management, Scenario trees, Stochastic dynamic programming, Expected future value curves, Nonadditive bid prices, Load factor of demand",
    author = "Escudero, {Laureano F.} and Monge, {Juan Francisco} and Morales, {Dolores Romero} and J. Wang",
    year = "2013",
    doi = "10.1287/trsc.1120.0422",
    language = "English",
    volume = "47",
    pages = "181--197",
    journal = "Transportation Science",
    issn = "0041-1655",
    publisher = "Institute for Operations Research and the Management Sciences",
    number = "2",

    }

    Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management. / Escudero, Laureano F.; Monge, Juan Francisco; Morales, Dolores Romero; Wang, J.

    In: Transportation Science, Vol. 47, No. 2, 2013, p. 181-197.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

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

    AU - Escudero,Laureano F.

    AU - Monge,Juan Francisco

    AU - Morales,Dolores Romero

    AU - Wang,J.

    PY - 2013

    Y1 - 2013

    N2 - This paper studies a multistage 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 as 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, whereas the differences among all the approaches we have tested are insignificant for extreme values. Moreover, our approach requires significantly less computation time than does 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 one minute, with 800 pairs in less than five minutes, and with 4,000 pairs in less than one hour. The time taken by DEM was, in general, of one order of magnitude higher. Finally, for the three largest problem instances, and after two hours, the expected revenue returned by DEM was below that obtained by EFV by 13.47%, 17.14%, and 38.94%, respectively.

    AB - This paper studies a multistage 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 as 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, whereas the differences among all the approaches we have tested are insignificant for extreme values. Moreover, our approach requires significantly less computation time than does 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 one minute, with 800 pairs in less than five minutes, and with 4,000 pairs in less than one hour. The time taken by DEM was, in general, of one order of magnitude higher. Finally, for the three largest problem instances, and after two hours, the expected revenue returned by DEM was below that obtained by EFV by 13.47%, 17.14%, and 38.94%, respectively.

    KW - Network revenue management

    KW - Scenario trees

    KW - Stochastic dynamic programming

    KW - Expected future value curves

    KW - Nonadditive bid prices

    KW - Load factor of demand

    U2 - 10.1287/trsc.1120.0422

    DO - 10.1287/trsc.1120.0422

    M3 - Journal article

    VL - 47

    SP - 181

    EP - 197

    JO - Transportation Science

    T2 - Transportation Science

    JF - Transportation Science

    SN - 0041-1655

    IS - 2

    ER -