The paper introduces innovative techniques to enhance Trip-Based Transit Routing (TBTR), a popular bicriterion transit routing approach. Inspired by Hypergraph-based Round-based Public Transit Routing (HypRAPTOR), we present Hypergraph-based TBTR (HypTBTR), a partitioning variant aimed at improving TBTR’s query times. However, this improvement in HypTBTR (and HypRAPTOR) comes with increased preprocessing requirements. To address this issue, we propose two novel techniques: a One-To-Many variant of TBTR and multilevel partitioning. Our One-To-Many algorithm efficiently handles profile queries, and integrating multilevel graph partitioning in both HypTBTR and HypRAPTOR significantly reduces preprocessing computations. Extensive experiments on large-scale GTFS datasets of Switzerland, Netherlands, and Sweden, showcase the efficacy of the proposed algorithms. Empirically, HypTBTR outperforms TBTR by 23–37%, the One-To-Many variant shows a speed-up of 90–95%, and multilevel partitioning reduces preprocessing calculations by up to 53%. These improvements have the potential to enhance user experiences in web and mobile navigation applications and expedite problems such as transit assignments that involve repeated calls to routing algorithms.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Scalable Algorithms for Bicriterion Trip-Based Transit Routing


    Contributors:

    Published in:

    Publication date :

    2024-10-01


    Size :

    9639355 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Bicriterion Traffic Assignment: Basic Theory and Elementary Algorithms

    Dial, R. B. | British Library Online Contents | 1996




    Trip-Based Public Transit Routing Using Condensed Search Trees

    Witt, Sascha | DataCite | 2016

    Free access