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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Scalable Algorithms for Bicriterion Trip-Based Transit Routing


    Beteiligte:
    Agarwal, Prateek (Autor:in) / Rambha, Tarun (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    01.10.2024


    Format / Umfang :

    9639355 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    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

    Freier Zugriff