Round-Based Public Transit Routing

The authors 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. The authors take a different approach. They introduce RAPTOR, their 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 the authors 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.

• Record URL:
  https://doi.org/10.1287/trsc.2014.0534
• Record URL:
  http://pubsonline.informs.org/doi/abs/10.1287/trsc.2014.0534
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • Delling, Daniel
  • Pajor, Thomas
  • Werneck, Renato F
• Publication Date: 2015-8

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 591-604
• Serial:
  • Transportation Science
  • Volume: 49
  • Issue Number: 3
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Dynamic programming; Optimization; Public transit; Routing; Shortest path algorithms; Timetables; Transfers
• Uncontrolled Terms: Arrival times
• Subject Areas: Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01573929
• Record Type: Publication
• Files: TRIS
• Created Date: Aug 11 2015 3:15PM