Scalable Algorithms for Bicriterion Trip-Based Transit Routing

The paper proposes multiple extensions to the popular bicriteria 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 accelerated 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 like Scalable Transfer Patterns and HypRAPTOR. Additionally, we integrate the 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.