IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v15y2015i3p635-653.html
   My bibliography  Save this article

Trip-Based Path Algorithms Using the Transit Network Hierarchy

Author

Listed:
  • Alireza Khani
  • Mark Hickman
  • Hyunsoo Noh

Abstract

In this paper, we propose a new network representation for modeling schedule-based transit systems. The proposed network representation, called trip-based, uses transit vehicle trips as network edges and takes into account the transfer stop hierarchy in transit networks. Based on the trip-based network, we propose a set of path algorithms for schedule-based transit networks, including algorithms for the shortest path, a logit-based hyperpath, and a transit A*. The algorithms are applied to a large-scale transit network and shown to have better computational performance compared to the existing labeling algorithms. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Alireza Khani & Mark Hickman & Hyunsoo Noh, 2015. "Trip-Based Path Algorithms Using the Transit Network Hierarchy," Networks and Spatial Economics, Springer, vol. 15(3), pages 635-653, September.
    • Handle: RePEc:kap:netspa:v:15:y:2015:i:3:p:635-653
    DOI: 10.1007/s11067-014-9249-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11067-014-9249-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-014-9249-3?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. Fisk, Caroline, 1980. "Some developments in equilibrium traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 14(3), pages 243-255, September.
    2. Nguyen, S. & Pallottino, S., 1988. "Equilibrium traffic assignment for large scale transit networks," European Journal of Operational Research, Elsevier, vol. 37(2), pages 176-186, November.
    3. Schmöcker, Jan-Dirk & Bell, Michael G.H. & Kurauchi, Fumitaka, 2008. "A quasi-dynamic capacity constrained frequency-based transit assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 925-945, December.
    4. Spiess, Heinz & Florian, Michael, 1989. "Optimal strategies: A new assignment model for transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 23(2), pages 83-102, April.
    5. Hamdouch, Younes & Lawphongpanich, Siriphong, 2008. "Schedule-based transit assignment model with travel strategies and capacity constraints," Transportation Research Part B: Methodological, Elsevier, vol. 42(7-8), pages 663-684, August.
    6. Homero Larrain & Juan Muñoz, 2008. "Public Transit Corridor Assignment Assuming Congestion Due to Passenger Boarding and Alighting," Networks and Spatial Economics, Springer, vol. 8(2), pages 241-256, September.
    7. Patrice Marcotte & Sang Nguyen & Alexandre Schoeb, 2004. "A Strategic Flow Model of Traffic Assignment in Static Capacitated Networks," Operations Research, INFORMS, vol. 52(2), pages 191-212, April.
    8. Sang Nguyen & Stefano Pallottino & Michel Gendreau, 1998. "Implicit Enumeration of Hyperpaths in a Logit Model for Transit Networks," Transportation Science, INFORMS, vol. 32(1), pages 54-64, February.
    9. Joaquín de Cea & Enrique Fernández, 1993. "Transit Assignment for Congested Public Transport Systems: An Equilibrium Model," Transportation Science, INFORMS, vol. 27(2), pages 133-147, May.
    10. Agostino Nuzzolo & Francesco Russo & Umberto Crisalli, 2001. "A Doubly Dynamic Schedule-based Assignment Model for Transit Networks," Transportation Science, INFORMS, vol. 35(3), pages 268-285, August.
    11. Sang Nguyen & Stefano Pallottino & Federico Malucelli, 2001. "A Modeling Framework for Passenger Assignment on a Transport Network with Timetables," Transportation Science, INFORMS, vol. 35(3), pages 238-249, August.
    12. Fitsum Teklu, 2008. "A Stochastic Process Approach for Frequency-based Transit Assignment with Strict Capacity Constraints," Networks and Spatial Economics, Springer, vol. 8(2), pages 225-240, September.
    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. Kai Lu & Tao Tang & Chunhai Gao, 2020. "The Depth-First Optimal Strategy Path Generation Algorithm for Passengers in a Metro Network," Sustainability, MDPI, vol. 12(13), pages 1-16, July.
    2. Chen, Bi Yu & Chen, Xiao-Wei & Chen, Hui-Ping & Lam, William H.K., 2020. "Efficient algorithm for finding k shortest paths based on re-optimization technique," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    3. Khani, Alireza, 2019. "An online shortest path algorithm for reliable routing in schedule-based transit networks considering transfer failure probability," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 549-564.
    4. Pramesh Kumar & Alireza Khani, 2021. "Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network," Networks and Spatial Economics, Springer, vol. 21(4), pages 771-800, December.
    5. Yongqiu Zhu & Rob M. P. Goverde, 2019. "Dynamic Passenger Assignment for Major Railway Disruptions Considering Information Interventions," Networks and Spatial Economics, Springer, vol. 19(4), pages 1249-1279, December.
    6. András Bóta & Lauren M. Gardner & Alireza Khani, 2017. "Identifying Critical Components of a Public Transit System for Outbreak Control," Networks and Spatial Economics, Springer, vol. 17(4), pages 1137-1159, December.
    7. S. Mahmassani, Hani & F. Hyland, Michael, 2016. "Gap-based transit assignment algorithm with vehicle capacity constraints: Simulation-based implementation and large-scale applicationAuthor-Name: Verbas, Ömer," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 1-16.
    8. Xin Zhang & Lei Nie & Xin Wu & Yu Ke, 2020. "How to Optimize Train Stops under Diverse Passenger Demand: a New Line Planning Method for Large-Scale High-Speed Rail Networks," Networks and Spatial Economics, Springer, vol. 20(4), pages 963-988, December.
    9. Peftitsi, Soumela & Jenelius, Erik & Cats, Oded, 2022. "Modeling the effect of real-time crowding information (RTCI) on passenger distribution in trains," Transportation Research Part A: Policy and Practice, Elsevier, vol. 166(C), pages 354-368.
    10. 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.
    11. László Hajdu & András Bóta & Miklós Krész & Alireza Khani & Lauren M. Gardner, 2020. "Discovering the Hidden Community Structure of Public Transportation Networks," Networks and Spatial Economics, Springer, vol. 20(1), pages 209-231, March.
    12. Mohammad Nurul Hassan & Taha Hossein Rashidi & Neema Nassir, 2021. "Consideration of different travel strategies and choice set sizes in transit path choice modelling," Transportation, Springer, vol. 48(2), pages 723-746, April.
    13. Zhang, Yu & Tang, Jiafu, 2018. "Itinerary planning with time budget for risk-averse travelers," European Journal of Operational Research, Elsevier, vol. 267(1), pages 288-303.

    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. Valentina Trozzi & Guido Gentile & Ioannis Kaparias & Michael Bell, 2015. "Effects of Countdown Displays in Public Transport Route Choice Under Severe Overcrowding," Networks and Spatial Economics, Springer, vol. 15(3), pages 823-842, September.
    2. Jiang, Y. & Szeto, W.Y., 2016. "Reliability-based stochastic transit assignment: Formulations and capacity paradox," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 181-206.
    3. Liu, Jiangtao & Zhou, Xuesong, 2016. "Capacitated transit service network design with boundedly rational agents," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 225-250.
    4. Codina, Esteve & Rosell, Francisca, 2017. "A heuristic method for a congested capacitated transit assignment model with strategies," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 293-320.
    5. Cortés, Cristián E. & Jara-Moroni, Pedro & Moreno, Eduardo & Pineda, Cristobal, 2013. "Stochastic transit equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 51(C), pages 29-44.
    6. Khani, Alireza, 2019. "An online shortest path algorithm for reliable routing in schedule-based transit networks considering transfer failure probability," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 549-564.
    7. Li, Qianfei & (Will) Chen, Peng & (Marco) Nie, Yu, 2015. "Finding optimal hyperpaths in large transit networks with realistic headway distributions," European Journal of Operational Research, Elsevier, vol. 240(1), pages 98-108.
    8. Younes Hamdouch & Siriphong Lawphongpanich, 2010. "Congestion Pricing for Schedule-Based Transit Networks," Transportation Science, INFORMS, vol. 44(3), pages 350-366, August.
    9. Nair, Rahul & Miller-Hooks, Elise, 2014. "Equilibrium network design of shared-vehicle systems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 47-61.
    10. Binder, Stefan & Maknoon, Yousef & Bierlaire, Michel, 2017. "Exogenous priority rules for the capacitated passenger assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 19-42.
    11. Elnaz Miandoabchi & Reza Farahani & Wout Dullaert & W. Szeto, 2012. "Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks," Networks and Spatial Economics, Springer, vol. 12(3), pages 441-480, September.
    12. Szeto, W.Y. & Jiang, Y., 2014. "Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 235-263.
    13. Du, Muqing & Chen, Anthony, 2022. "Sensitivity analysis for transit equilibrium assignment and applications to uncertainty analysis," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 175-202.
    14. Hamdouch, Younes & Ho, H.W. & Sumalee, Agachai & Wang, Guodong, 2011. "Schedule-based transit assignment model with vehicle capacity and seat availability," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1805-1830.
    15. Sun, S. & Szeto, W.Y., 2018. "Logit-based transit assignment: Approach-based formulation and paradox revisit," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 191-215.
    16. Trozzi, Valentina & Gentile, Guido & Bell, Michael G.H. & Kaparias, Ioannis, 2013. "Dynamic user equilibrium in public transport networks with passenger congestion and hyperpaths," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 266-285.
    17. S. Mahmassani, Hani & F. Hyland, Michael, 2016. "Gap-based transit assignment algorithm with vehicle capacity constraints: Simulation-based implementation and large-scale applicationAuthor-Name: Verbas, Ömer," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 1-16.
    18. Chen, Kang & Yang, Zhongzhen & Notteboom, Theo, 2014. "The design of coastal shipping services subject to carbon emission reduction targets and state subsidy levels," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 192-211.
    19. Xu, Zhandong & Xie, Jun & Liu, Xiaobo & Nie, Yu (Marco), 2020. "Hyperpath-based algorithms for the transit equilibrium assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    20. Hamdouch, Younes & Lawphongpanich, Siriphong, 2008. "Schedule-based transit assignment model with travel strategies and capacity constraints," Transportation Research Part B: Methodological, Elsevier, vol. 42(7-8), pages 663-684, August.

    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:kap:netspa:v:15:y:2015:i:3:p:635-653. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.