Welcome to Transit-routing’s documentation!

Conventional approaches model the transit network as a time-expanded or time-dependent graph and run a variant of the Dijkstra’s algorithm. However, this method turns out to be too slow for large networks. Furthermore, while planning a journey using public transit, the number of transfers is equally important besides travel time. Popular techniques developed for PTR in the past decade include—Transfer Patterns algorithm, Connection Scan Algorithm (CSA), Round based Public Transit Routing algorithm (RAPTOR), and Trip-Based public Transit Routing (TBTR) algorithm. This repository provides various efficient algorithms to solve bicriteria shortest path problems in public transit routing.

We mainly focus on two popular approaches: Round-Based Public Transit Routing (RAPTOR) and Trip-Based public Transit Routing (TBTR) working on arrival time and number of transfers as the two optimization criteria. Apart from the already published HypRAPTOR, we also include our variant of HypTBTR. Furthermore, both HypRAPTOR and HypTBTR have been extended using multilevel partitioning (MhypTBTR and MhypRAPTOR).

Additionally, to make the RAPTOR and TBTR approach more practical, we also include One-To-Many rTBTR and One-To-Many rRAPTOR. These not only reduce the preprocessing times of the partitioning variants but also significantly outperform the existing approach for location-based queries (as a location can have multiple stops near it)

Switzerland’s public transit network has been provided as a test case. The figure below shows the transit stop location (left) and 4-way partitioning using KaHyPar (right).

List of Algorithms

Algorithms	Varient	Source	Status	Comments
Time-Expanded Graph	Dijkstra Algorithm	link	Complete
RAPTOR	Standard RAPTOR	link	Complete
RAPTOR	rRAPTOR	link	Complete
RAPTOR	HypRAPTOR	link	Complete
RAPTOR	One-To-Many rRAPTOR	link	To be added soon
TBTR	Standard TBTR	link	Complete
TBTR	rTBTR	link	Complete
TBTR	One-To-Many rTBTR	link	Complete
TBTR	HypTBTR	link	Complete
TBTR	MHypTBTR	link	Complete
TBTR	MHypTBTR	link	Complete
Transfer Patterns	Standard TP	link	Complete
Transfer Patterns	Scalable TP	link	To be addeed soon
Connection Scan Algorithm	Standard CSA	link	Complete

Navigation

• Quickstart
• GTFS preprocessing
• List of Algoirthms
• Miscellaneous Functions

Contributing

We welcome all suggestions from the community. If you wish to contribute or report any bug please contact the creaters or create an issue on issue tracking system.

Creators

1. Prateek Agarwal

   • Ph.D. at Indian Institute of Science Bengaluru India

   • Website: https://sites.google.com/view/prateek-agarwal/

   • Mail Id: prateeka@iisc.ac.in

2. Tarun Rambha

   • Assistant Professor in the Civil Engineering and the Center for Infrastructure, Sustainable Transportation and Urban Planning (CiSTUP) at Indian Institute of Science Bengaluru India.

   • Website: http://civil.iisc.ernet.in/~tarunr/

   • Mail Id: tarunrambha@iisc.ac.in

Copyright and license

The content of this repository is bounded by MIT License. For more information see COPYING file