IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v49y2015i3p591-604.html
   My bibliography  Save this article

Round-Based Public Transit Routing

Author

Listed:
  • Daniel Delling

    (Microsoft Research Silicon Valley, Mountain View, California 94043)

  • Thomas Pajor

    (Microsoft Research Silicon Valley, Mountain View, California 94043)

  • Renato F. Werneck

    (Microsoft Research Silicon Valley, Mountain View, California 94043)

Abstract

We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for multiple criteria, such as arrival time and number of transfers. Existing algorithms consider this as a graph problem and solve it using various graph search algorithms. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Starting from arrival time and number of transfers as criteria, it can be easily extended to handle flexible departure times or arbitrary additional criteria. As practical examples we consider fare zones and reliability of transfers. When run on complex public transportation networks (such as London), RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications.

Suggested Citation

  • Daniel Delling & Thomas Pajor & Renato F. Werneck, 2015. "Round-Based Public Transit Routing," Transportation Science, INFORMS, vol. 49(3), pages 591-604, August.
  • Handle: RePEc:inm:ortrsc:v:49:y:2015:i:3:p:591-604
    DOI: 10.1287/trsc.2014.0534
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2014.0534
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.2014.0534?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
    ---><---

    Citations

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


    Cited by:

    1. Goliszek Sławomir & Połom Marcin & Duma Patryk, 2020. "Potential and cumulative accessibility of workplaces by public transport in Szczecin," Bulletin of Geography. Socio-economic Series, Sciendo, vol. 50(50), pages 133-146, December.
    2. Lucas Albuquerque-Oliveira, João & Moraes Oliveira-Neto, Francisco & Pereira, Rafael H.M., 2024. "A novel route-based accessibility measure and its association with transit ridership," Transportation Research Part A: Policy and Practice, Elsevier, vol. 179(C).
    3. Milos Balac & Sebastian Hörl & Basil Schmid, 2024. "Discrete choice modeling with anonymized data," Transportation, Springer, vol. 51(2), pages 351-370, April.
    4. Paulsen, Mads & Rasmussen, Thomas Kjær & Nielsen, Otto Anker, 2021. "Impacts of real-time information levels in public transport: A large-scale case study using an adaptive passenger path choice model," Transportation Research Part A: Policy and Practice, Elsevier, vol. 148(C), pages 155-182.
    5. Panagiotis Georgakis & Adel Almohammad & Efthimios Bothos & Babis Magoutas & Kostantina Arnaoutaki & Gregoris Mentzas, 2020. "Heuristic-Based Journey Planner for Mobility as a Service (MaaS)," Sustainability, MDPI, vol. 12(23), pages 1-25, December.
    6. , Marcin Wozniak & Radzimski, Adam & Wajchman-Świtalska, Sandra, 2024. "Is More Always Better? Evaluating Accessibility to Parks and Forests in 33 European Cities Using Sustainable Modes of Transportation," OSF Preprints hcwgp, Center for Open Science.
    7. Pereira, Rafael H. M. & Herszenhut, Daniel & Saraiva, Marcus & Farber, Steven, 2023. "Ride-hailing and transit accessibility considering the trade-off between time and money," OSF Preprints pesjk, Center for Open Science.

    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:inm:ortrsc:v:49:y:2015:i:3:p:591-604. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.