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.
Scalable Algorithms for Bicriterion Trip-Based Transit Routing
IEEE Transactions on Intelligent Transportation Systems ; 25 , 10 ; 14313-14327
2024-10-01
9639355 byte
Article (Journal)
Electronic Resource
English
Bicriterion traffic assignment: Efficient algorithms plus examples
Online Contents | 1997
|Bicriterion Traffic Assignment: Basic Theory and Elementary Algorithms
British Library Online Contents | 1996
|Bicriterion Traffic Assignment: Basic Theory and Elementary Algorithms
Online Contents | 1996
|Solving the bicriterion routing and scheduling problem for hazardous materials distribution
Online Contents | 2010
|