IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v98y2017icp179-197.html
   My bibliography  Save this article

A dynamic programming approach for quickly estimating large network-based MEV models

Author

Listed:
  • Mai, Tien
  • Frejinger, Emma
  • Fosgerau, Mogens
  • Bastin, Fabian

Abstract

We propose a way to estimate a family of static Multivariate Extreme Value (MEV) models with large choice sets in short computational time. The resulting model is also straightforward and fast to use for prediction. Following Daly and Bierlaire (2006), the correlation structure is defined by a rooted, directed graph where each node without successor is an alternative. We formulate a family of MEV models as dynamic discrete choice models on graphs of correlation structures and show that the dynamic models are consistent with MEV theory and generalize the network MEV model (Daly and Bierlaire, 2006). Moreover, we show that these models can be estimated quickly using the concept of network flows and the nested fixed point algorithm (Rust, 1987). The main reason for the short computational time is that the new formulation allows to benefit from existing efficient solution algorithms for sparse linear systems of equations.

Suggested Citation

  • Mai, Tien & Frejinger, Emma & Fosgerau, Mogens & Bastin, Fabian, 2017. "A dynamic programming approach for quickly estimating large network-based MEV models," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 179-197.
    • Handle: RePEc:eee:transb:v:98:y:2017:i:c:p:179-197
    DOI: 10.1016/j.trb.2016.12.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515302216
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2016.12.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Rust, John, 1987. "Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher," Econometrica, Econometric Society, vol. 55(5), pages 999-1033, September.
    2. Mai, Tien & Fosgerau, Mogens & Frejinger, Emma, 2015. "A nested recursive logit model for route choice analysis," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 100-112.
    3. Eberwein, Curtis & Ham, John C., 2008. "Obtaining analytic derivatives for a popular discrete-choice dynamic programming model," Economics Letters, Elsevier, vol. 101(3), pages 168-171, December.
    4. Abbe, E. & Bierlaire, M. & Toledo, T., 2007. "Normalization and correlation of cross-nested logit models," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 795-808, August.
    5. Daly, Andrew & Bierlaire, Michel, 2006. "A general and operational representation of Generalised Extreme Value models," Transportation Research Part B: Methodological, Elsevier, vol. 40(4), pages 285-305, May.
    6. Ernst R. Berndt & Bronwyn H. Hall & Robert E. Hall & Jerry A. Hausman, 1974. "Estimation and Inference in Nonlinear Structural Models," NBER Chapters, in: Annals of Economic and Social Measurement, Volume 3, number 4, pages 653-665, National Bureau of Economic Research, Inc.
    7. Mai, Tien, 2016. "A method of integrating correlation structures for a generalized recursive route choice model," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 146-161.
    8. Fosgerau, Mogens & Frejinger, Emma & Karlstrom, Anders, 2013. "A link based network route choice model with unrestricted choice set," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 70-80.
    9. Papola, Andrea, 2004. "Some developments on the cross-nested logit model," Transportation Research Part B: Methodological, Elsevier, vol. 38(9), pages 833-851, November.
    10. Guevara, C. Angelo & Ben-Akiva, Moshe E., 2013. "Sampling of alternatives in Multivariate Extreme Value (MEV) models," Transportation Research Part B: Methodological, Elsevier, vol. 48(C), pages 31-52.
    11. Lai, Xinjun & Bierlaire, Michel, 2015. "Specification of the cross-nested logit model with sampling of alternatives for route choice models," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 220-234.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tien Mai & Patrick Jaillet, 2019. "Robust Product-line Pricing under Generalized Extreme Value Models," Papers 1912.09552, arXiv.org, revised Oct 2021.
    2. Shiva Habibi & Emma Frejinger & Marcus Sundberg, 2019. "An empirical study on aggregation of alternatives and its influence on prediction in car type choice models," Transportation, Springer, vol. 46(3), pages 563-582, June.
    3. Anna Fernández-Antolín & Matthieu Lapparent & Michel Bierlaire, 2018. "Modeling purchases of new cars: an analysis of the 2014 French market," Theory and Decision, Springer, vol. 84(2), pages 277-303, March.
    4. Dam, Tien Thanh & Ta, Thuy Anh & Mai, Tien, 2022. "Submodularity and local search approaches for maximum capture problems under generalized extreme value models," European Journal of Operational Research, Elsevier, vol. 300(3), pages 953-965.
    5. Song, Yuchen & Li, Dawei & Liu, Dongjie & Cao, Qi & Chen, Junlan & Ren, Gang & Tang, Xiaoyong, 2022. "Modeling activity-travel behavior under a dynamic discrete choice framework with unobserved heterogeneity," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    6. Tran, Hung & Mai, Tien, 2024. "Network-based representations and dynamic discrete choice models for multiple discrete choice analysis," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    7. Dam, Tien Thanh & Ta, Thuy Anh & Mai, Tien, 2023. "Robust maximum capture facility location under random utility maximization models," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1128-1150.
    8. Hung Tran & Tien Mai, 2023. "Network-based Representations and Dynamic Discrete Choice Models for Multiple Discrete Choice Analysis," Papers 2306.04606, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mai, Tien, 2016. "A method of integrating correlation structures for a generalized recursive route choice model," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 146-161.
    2. Mai, Tien & Yu, Xinlian & Gao, Song & Frejinger, Emma, 2021. "Routing policy choice prediction in a stochastic network: Recursive model and solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 151(C), pages 42-58.
    3. Mai, Tien & Bastin, Fabian & Frejinger, Emma, 2017. "On the similarities between random regret minimization and mother logit: The case of recursive route choice models," Journal of choice modelling, Elsevier, vol. 23(C), pages 21-33.
    4. Tran, Hung & Mai, Tien, 2024. "Network-based representations and dynamic discrete choice models for multiple discrete choice analysis," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    5. Oyama, Yuki & Hato, Eiji, 2019. "Prism-based path set restriction for solving Markovian traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 528-546.
    6. Oyama, Yuki & Hara, Yusuke & Akamatsu, Takashi, 2022. "Markovian traffic equilibrium assignment based on network generalized extreme value model," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 135-159.
    7. Yao, Rui & Bekhor, Shlomo, 2022. "A variational autoencoder approach for choice set generation and implicit perception of alternatives in choice modeling," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 273-294.
    8. Evanthia Kazagli & Michel Bierlaire & Matthieu de Lapparent, 2020. "Operational route choice methodologies for practical applications," Transportation, Springer, vol. 47(1), pages 43-74, February.
    9. Fiore Tinessa & Vittorio Marzano & Andrea Papola, 2021. "Choice probabilities and correlations in closed-form route choice models: specifications and drawbacks," Papers 2110.07224, arXiv.org.
    10. Marzano, Vittorio & Papola, Andrea & Simonelli, Fulvio & Vitillo, Roberta, 2013. "A practically tractable expression of the covariances of the Cross-Nested Logit model," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 1-11.
    11. Oskar Blom Västberg & Anders Karlström & Daniel Jonsson & Marcus Sundberg, 2020. "A Dynamic Discrete Choice Activity-Based Travel Demand Model," Transportation Science, INFORMS, vol. 54(1), pages 21-41, January.
    12. Yuki Oyama, 2022. "Capturing positive network attributes during the estimation of recursive logit models: A prism-based approach," Papers 2204.01215, arXiv.org, revised Jan 2023.
    13. Mai, Tien & Bui, The Viet & Nguyen, Quoc Phong & Le, Tho V., 2023. "Estimation of recursive route choice models with incomplete trip observations," Transportation Research Part B: Methodological, Elsevier, vol. 173(C), pages 313-331.
    14. Mai, Tien & Fosgerau, Mogens & Frejinger, Emma, 2015. "A nested recursive logit model for route choice analysis," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 100-112.
    15. Kazagli, Evanthia & Bierlaire, Michel & Flötteröd, Gunnar, 2016. "Revisiting the route choice problem: A modeling framework based on mental representations," Journal of choice modelling, Elsevier, vol. 19(C), pages 1-23.
    16. Hung Tran & Tien Mai, 2023. "Network-based Representations and Dynamic Discrete Choice Models for Multiple Discrete Choice Analysis," Papers 2306.04606, arXiv.org.
    17. Tien Mai & Fabian Bastin & Emma Frejinger, 2018. "A decomposition method for estimating recursive logit based route choice models," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 253-275, September.
    18. Marzano, Vittorio & Papola, Andrea, 2008. "On the covariance structure of the Cross-Nested Logit model," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 83-98, February.
    19. Peter Davis & Pasquale Schiraldi, 2014. "The flexible coefficient multinomial logit (FC-MNL) model of demand for differentiated products," RAND Journal of Economics, RAND Corporation, vol. 45(1), pages 32-63, March.
    20. Tien Mai & The Viet Bui & Quoc Phong Nguyen & Tho V. Le, 2022. "Estimation of Recursive Route Choice Models with Incomplete Trip Observations," Papers 2204.12992, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:98:y:2017:i:c:p:179-197. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.