This is a test repository where development for routing algorithms, prior to integration with catenary-backend live. Essentially, its a playground for little ideas to be written and tested.
Previously, we attemped to rewrite Transfer Patterns and Scalable Transfer Patterns, however, upon further reading and testing, the memory overhead for precomputation was much too high for our purposes. As such, we are attempting to implement RAPTOR (Round-bAsed Public Transit Optimized Router) instead.
Supplemented by exercises from Lectures 9-11 from Uni Freiburg's Efficient Route Planning course (2012 Summer) with Professor Hannah Bast
[1]: Bast, H. et al. (2010). Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns. In: de Berg, M., Meyer, U. (eds) Algorithms – ESA 2010. ESA 2010. Lecture Notes in Computer Science, vol 6346. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15775-2_25
[2]: H. Bast, M. Hertel, and S. Storandt, “Scalable Transfer Patterns,” 2016 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pp. 15–29, Jan. 2016, doi: https://doi.org/10.1137/1.9781611974317.2.
[3]: D. Delling, T. Pajor, and R. Werneck, “Round-Based Public Transit Routing - Microsoft Research,” Microsoft Research, 2012. https://www.microsoft.com/en-us/research/publication/round-based-public-transit-routing/
Extracting from a compressed bincode is faster.
Run this to produce a bincode from the catenary-backend.
cargo run --release --bin osm_extractor -- --routing_export_path ./testing_routing_export --temp_dir ./testing_temp_dirDownload le file GTFS de STM
wget https://www.stm.info/sites/default/files/gtfs/gtfs_stm.zipTo produce a query graph, for example, on the first run, execute
./target/release/transit-router --makequerygraph true
or cargo run --release -- --makequerygraph true
to reuse, put false