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

Metropolis–Hastings sampling of paths

Author

Listed:
  • Flötteröd, Gunnar
  • Bierlaire, Michel

Abstract

We consider the previously unsolved problem of sampling paths according to a given distribution from a general network. The problem is difficult because of the combinatorial number of alternatives, which prohibits a complete enumeration of all paths and hence also forbids to compute the normalizing constant of the sampling distribution. The problem is important because the ability to sample from a known distribution introduces mathematical rigor into many applications, including the estimation of choice models with sampling of alternatives that can be formalized as paths in a decision network (most obviously route choice), probabilistic map matching, dynamic traffic assignment, and route guidance.

Suggested Citation

  • Flötteröd, Gunnar & Bierlaire, Michel, 2013. "Metropolis–Hastings sampling of paths," Transportation Research Part B: Methodological, Elsevier, vol. 48(C), pages 53-66.
  • Handle: RePEc:eee:transb:v:48:y:2013:i:c:p:53-66
    DOI: 10.1016/j.trb.2012.11.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S019126151200152X
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.trb.2012.11.002?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. Frejinger, E. & Bierlaire, M. & Ben-Akiva, M., 2009. "Sampling of alternatives for route choice modeling," Transportation Research Part B: Methodological, Elsevier, vol. 43(10), pages 984-994, December.
    2. Shlomo Bekhor & Moshe Ben-Akiva & M. Ramming, 2006. "Evaluation of choice set generation algorithms for route choice models," Annals of Operations Research, Springer, vol. 144(1), pages 235-247, April.
    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. 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.
    2. Zhang, Chao & Osorio, Carolina & Flötteröd, Gunnar, 2017. "Efficient calibration techniques for large-scale traffic simulators," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 214-239.
    3. 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.
    4. Batista, S.F.A. & Leclercq, Ludovic & Geroliminis, Nikolas, 2019. "Estimation of regional trip length distributions for the calibration of the aggregated network traffic models," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 192-217.
    5. Evanthia Kazagli & Michel Bierlaire & Matthieu de Lapparent, 2020. "Operational route choice methodologies for practical applications," Transportation, Springer, vol. 47(1), pages 43-74, February.
    6. Blom Västberg, Oskar & Karlström, Anders & Jonsson, Daniel & Sundberg, Marcus, 2016. "Including time in a travel demand model using dynamic discrete choice," MPRA Paper 75336, University Library of Munich, Germany, revised 11 Nov 2016.
    7. 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.
    8. 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.
    9. Hamzeh Alizadeh & Bilal Farooq & Catherine Morency & Nicolas Saunier, 2018. "On the role of bridges as anchor points in route choice modeling," Transportation, Springer, vol. 45(5), pages 1181-1206, September.

    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. 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.
    2. Evanthia Kazagli & Michel Bierlaire & Matthieu de Lapparent, 2020. "Operational route choice methodologies for practical applications," Transportation, Springer, vol. 47(1), pages 43-74, February.
    3. 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.
    4. Li, Dawei & Feng, Siqi & Song, Yuchen & Lai, Xinjun & Bekhor, Shlomo, 2023. "Asymmetric closed-form route choice models: Formulations and comparative applications," Transportation Research Part A: Policy and Practice, Elsevier, vol. 171(C).
    5. Lili Zheng & Tian Gao & Lin Meng & Tongqiang Ding & Wenhao Chen, 2024. "Research on the Route Choice Behavior of Urban Freight Vehicles Based on GPS Data," Mathematics, MDPI, vol. 12(2), pages 1-17, January.
    6. Dieter, Peter & Caron, Matthew & Schryen, Guido, 2023. "Integrating driver behavior into last-mile delivery routing: Combining machine learning and optimization in a hybrid decision support framework," European Journal of Operational Research, Elsevier, vol. 311(1), pages 283-300.
    7. Watling, David Paul & Rasmussen, Thomas Kjær & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2018. "Stochastic user equilibrium with a bounded choice model," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 254-280.
    8. Tomhave, Benjamin J. & Khani, Alireza, 2022. "Refined choice set generation and the investigation of multi-criteria transit route choice behavior," Transportation Research Part A: Policy and Practice, Elsevier, vol. 155(C), pages 484-500.
    9. Hess, Stephane & Quddus, Mohammed & Rieser-Schüssler, Nadine & Daly, Andrew, 2015. "Developing advanced route choice models for heavy goods vehicles using GPS data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 77(C), pages 29-44.
    10. Carlo Prato & Shlomo Bekhor & Cristina Pronello, 2012. "Latent variables and route choice behavior," Transportation, Springer, vol. 39(2), pages 299-319, March.
    11. Ding-Mastera, Jing & Gao, Song & Jenelius, Erik & Rahmani, Mahmood & Ben-Akiva, Moshe, 2019. "A latent-class adaptive routing choice model in stochastic time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 124(C), pages 1-17.
    12. Knapen, Luk & Hartman, Irith Ben-Arroyo & Schulz, Daniel & Bellemans, Tom & Janssens, Davy & Wets, Geert, 2016. "Determining structural route components from GPS traces," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 156-171.
    13. Selin Damla Ahipaşaoğlu & Uğur Arıkan & Karthik Natarajan, 2019. "Distributionally Robust Markovian Traffic Equilibrium," Transportation Science, INFORMS, vol. 53(6), pages 1546-1562, November.
    14. Rinaldi, Marco & Viti, Francesco, 2017. "Exact and approximate route set generation for resilient partial observability in sensor location problems," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 86-119.
    15. Mengying Cui & David Levinson, 2021. "Shortest paths, travel costs, and traffic," Environment and Planning B, , vol. 48(4), pages 828-844, May.
    16. Crawford, Gregory S. & Griffith, Rachel & Iaria, Alessandro, 2021. "A survey of preference estimation with unobserved choice set heterogeneity," Journal of Econometrics, Elsevier, vol. 222(1), pages 4-43.
    17. Mai, Tien & Frejinger, Emma & Bastin, Fabian, 2015. "A misspecification test for logit based route choice models," Economics of Transportation, Elsevier, vol. 4(4), pages 215-226.
    18. Brian Lee & Paul Waddell, 2010. "Residential mobility and location choice: a nested logit model with sampling of alternatives," Transportation, Springer, vol. 37(4), pages 587-601, July.
    19. Meyer de Freitas, Lucas & Becker, Henrik & Zimmermann, Maëlle & Axhausen, Kay W., 2019. "Modelling intermodal travel in Switzerland: A recursive logit approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 119(C), pages 200-213.
    20. 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.

    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:48:y:2013:i:c:p:53-66. 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.