Scalable Algorithms for Bicriterion Trip-Based Transit Routing

Author name not available (Why is that?)

Publication date: 12 November 2021

Abstract: This paper proposes multiple extensions to the popular bicriterion transit routing approach -- Trip-Based Transit Routing (TBTR). Specifically, building on the premise of the HypRAPTOR algorithm, we first extend TBTR to its partitioning variant -- HypTBTR. However, the improvement in query times of HyTBTR over TBTR comes at the cost of increased preprocessing. To counter this issue, two new techniques are proposed -- a One-To-Many variant of TBTR and multilevel partitioning. Our One-To-Many algorithm can rapidly solve profile queries, which not only reduces the preprocessing time for HypTBTR, but can also aid other popular approaches such as HypRAPTOR. Next, we integrate a multilevel graph partitioning paradigm in HypTBTR and HypRAPTOR to reduce the fill-in computations. The efficacy of the proposed algorithms is extensively tested on real-world large-scale datasets. Additional analysis studying the effect of hypergraph partitioning tools (hMETIS, KaHyPar, and an integer program) along with different weighting schemes is also presented.

Has companion code repository: https://github.com/transnetlab/transit-routing

This page was built for publication: Scalable Algorithms for Bicriterion Trip-Based Transit Routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382872)