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

Prism-based path set restriction for solving Markovian traffic assignment problem

Author

Listed:
  • Oyama, Yuki
  • Hato, Eiji

Abstract

This paper deals with a main limitation of Markovian traffic assignment (MTA) models: when the network includes cyclic structures and the link costs are small enough, the fact that the MTA models assign traffic flows to all feasible paths causes computational challenges. This study addresses this issue by proposing a method of restricting path set based on the concept of choice-based prism. To achieve a prism-based path set, a novel network description and the constraints are introduced. These are flexible and compatible with the MTA operation, meaning that our method does not extinguish the mathematical and computational advantages of the MTA models. Our network description allows the expected minimum cost to take a value specific for each state, or a pair of node and choice-stage. This enables us to perform traffic assignment with a simple solution procedure, regardless of parameter setting or network structure. The numerical experiments show that our method solves the computational challenges of the MTA models and that the incorporation of the prism constraints does not increase computational effort required, or rather, it is computationally efficient even when considering the correlation among path utilities.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:122:y:2019:i:c:p:528-546
    DOI: 10.1016/j.trb.2019.02.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517311955
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2019.02.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. 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. Takashi Akamatsu, 1997. "Decomposition of Path Choice Entropy in General Transport Networks," Transportation Science, INFORMS, vol. 31(4), pages 349-362, November.
    3. 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.
    4. Azevedo, JoseAugusto & Santos Costa, Maria Emilia O. & Silvestre Madeira, Joaquim Joao E. R. & Vieira Martins, Ernesto Q., 1993. "An algorithm for the ranking of shortest paths," European Journal of Operational Research, Elsevier, vol. 69(1), pages 97-106, 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. Akamatsu, Takashi, 1996. "Cyclic flows, Markov process and stochastic traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 30(5), pages 369-386, October.
    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. 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.
    9. Pierre Robillard, 1974. "Calibration of Dial's Assignment Method," Transportation Science, INFORMS, vol. 8(2), pages 117-125, May.
    10. Kivimäki, Ilkka & Shimbo, Masashi & Saerens, Marco, 2014. "Developments in the theory of randomized shortest paths with a comparison of graph node distances," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 393(C), pages 600-616.
    11. 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.
    12. Watling, David Paul & Rasmussen, Thomas Kjær & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2015. "Stochastic user equilibrium with equilibrated choice sets: Part I – Model formulations under alternative distributions and restrictions," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 166-181.
    13. Van Vliet, Dirck, 1981. "Selected node-pair analysis in dial's assignment algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 15(1), pages 65-68, February.
    14. Bell, Michael G.H., 2009. "Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation," Transportation Research Part B: Methodological, Elsevier, vol. 43(1), pages 97-107, January.
    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. Leleux, Pierre & Courtain, Sylvain & Françoisse, Kevin & Saerens, Marco, 2022. "Design of biased random walks on a graph with application to collaborative recommendation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 590(C).
    2. Yuki Oyama, 2023. "Global path preference and local response: A reward decomposition approach for network path choice analysis in the presence of locally perceived attributes," Papers 2307.08646, arXiv.org.
    3. 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.
    4. 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.

    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. 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.
    2. 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.
    3. Evanthia Kazagli & Michel Bierlaire & Matthieu de Lapparent, 2020. "Operational route choice methodologies for practical applications," Transportation, Springer, vol. 47(1), pages 43-74, February.
    4. 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.
    5. Hung Tran & Tien Mai, 2023. "Network-based Representations and Dynamic Discrete Choice Models for Multiple Discrete Choice Analysis," Papers 2306.04606, arXiv.org.
    6. 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.
    7. 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.
    8. 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.
    9. Mogens Fosgerau & Mads Paulsen & Thomas Kj{ae}r Rasmussen, 2021. "A perturbed utility route choice model," Papers 2103.13784, arXiv.org, revised Sep 2021.
    10. 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.
    11. Yuki Oyama, 2023. "Global path preference and local response: A reward decomposition approach for network path choice analysis in the presence of locally perceived attributes," Papers 2307.08646, arXiv.org.
    12. 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.
    13. 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.
    14. Papola, Andrea & Tinessa, Fiore & Marzano, Vittorio, 2018. "Application of the Combination of Random Utility Models (CoRUM) to route choice," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 304-326.
    15. 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).
    16. 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.
    17. Jorge Lorca & Emerson Melo, 2020. "Choice Aversion in Directed Networks," Working Papers Central Bank of Chile 879, Central Bank of Chile.
    18. 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.
    19. Cortés, Cristián E. & Donoso, Pedro & Gutiérrez, Leonel & Herl, Daniel & Muñoz, Diego, 2023. "A recursive stochastic transit equilibrium model estimated using passive data from Santiago, Chile," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    20. 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.

    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:122:y:2019:i:c:p:528-546. 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.