Scalable Algorithms for Bicriterion Trip-Based Transit Routing
A. Prateek Agarwala,∗ , B. Tarun Rambhab
a Ph.D. Student, Indian Institute of Science (IISc) Bangalore, Karnataka, India

prateeka@iisc.ac.in∗ Corresponding authorb Assistant Professor, Department of Civil Engineering

Center for Infrastructure, Sustainable Transportation, and Urban Planning (CiSTUP)
Indian Institute of Science (IISc) Bangalore, India
tarunrambha@iisc.ac.in
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 31, 2022
Keywords: transit routing; shortest paths; multi-criteria optimization, hypergraph partitioning

1INTRODUCTION

Public transit systems are an indispensable part of any metropolitan city. Its success depends on
many factors, chief among which is the ease users can query for optimal journeys using mobileapps. Public Transit Routing (PTR) is typically aided by mobile apps and backend algorithms.
Ideally, these algorithms must be fast and should provide details on efficient routes between
origins and destinations of passengers. Conventional approaches model the transit network as atime-expanded or time-dependent graph and run a variant of the Dijkstra’s algorithm. However,this method turns out to be too slow for large networks. Furthermore, while planning a journeyusing public transit, the number of transfers is equally important besides travel time. Populartechniques developed for PTR in the past decade include—Transfer Patterns algorithm (Bastet al., 2010), Connection Scan Algorithm (CSA) (Dibbelt et al., 2013), Round based Public
Transit Routing algorithm (RAPTOR) (Delling et al., 2015), and Trip-Based public Transit
Routing (TBTR) algorithm (Witt, 2015). The main goal of our work is to propose routing
algorithms that are efficient and practical. Specifically, we address the following types of routing
problems. The improvements summarized above are based on country- and city-level transit
datasets.
• HypTBTR: Shortest path algorithms are usually made more efficient by partitioning theunderlying graph. We propose “HypTBTR” by combining TBTR with a partitioning-based
speed-up. For one-to-one shortest path queries, HypTBTR was found to be 30–40% fasterthan the TBTR algorithm. Additional analysis studying the effect of different weighting
schemes and hypergraph partitioning tools (KaHyPar, hMETIS, Integer Program) is alsopresented.
• One-To-Many rTBTR: Solving profile queries is one of the major bottlenecks in modern PTR approaches such as Scalable Transfer Patterns (Bast et al., 2016), HypRAPTOR (Delling et al., 2017), and HypTBTR. To address this problem, we extend thepopular rTBTR algorithm to its One-To-Many variant. This algorithm not only reduces
the preprocessing times significantly but is also helpful from a practical standpoint as users
TRISTAN XI Symposium

Original abstract submittal

P. Agarwal, T. Rambha

2often query the shortest path between two locations instead of two transit stops (a location
can have multiple stops near it). Compared to the existing approaches, our implementations were 40–50% faster.
• Multilevel extensions for HypTBTR and HypRAPTOR: The reduced query times in HypTBTRand HypRAPTOR come at the cost of increased preprocessing. We solve this issue using
multilevel partitioning. Compared to standard partitioning implementations, preprocessing times were reduced by approximately 20–50%. Apart from CSA, none of the PTR
algorithms have been extended to incorporate multilevel partitioning.

2METHODOLOGYHypTBTR: We introduce an additional preprocessing step to TBTR which partitions routes
into p disjoint sets R1 , R2 , . . . , Rp , also known as route cells. The central idea in HypTBTR isto construct a hypergraph G in which every node represents a route, and a hyperedge between
a subset of nodes that represents intersecting routes (two routes are called intersecting if they
have at least one stop in common). Footpaths or walking connections are also treated as routes
with two stops. A partitioning algorithm (based on a min-cut approach) is then used to generateroute cells. By definition, route cells are mutually exclusive and exhaustive (i.e., Ri ∩ Rj = ∅Sfor all i and j, and pi=1 Ri = R). Consider the example in Figure 1. Subfigure (b) shows
the corresponding hypergraph with each route as a node (a hyperedge is added between the red,orange, and grey nodes). The black node represents the footpath. Assuming p = 3, a partitioning
algorithm creates three route cells namely R1 (dark blue), R2 (cyan), and R3 (purple), as shownin Subfigure (c). Subfigure (d) shows the cutstops derived from the route cells in (c).
s8

s6

s5

sor1(a)

s2

r3
s7

r3r2

hyperedge

s9

r4

r5
s3

R2

R1

R3

r5

r4
r2r1(b)Partitioning algorithmsdEvery route is a node(c)Cutstops

Cutstop(d)Figure 1 – HypRAPTOR: Route partitioning using a hypergraph representation
Similar to route cells, stops cells S0 , S1 , . . . , Sp is a partition of stops. To construct a stopcell Si , we start by including all stops belonging to the routes in the corresponding route cell Ri .
However, the resulting stop cells are not mutually exclusive due to cutstops. Thus, define S0 tocontain all the cutstops and update stop cell Si as Si ← Si \ S0 . For example, in Figure 1, thestop cells are S0 = {s0 , s2 , s8 , s9 }, S1 = ∅, S2 = {s5 , s6 }, and S3 = {s3 , sd , s7 }. The next
step is to find and store optimal routes between these cutstops, referred to as fill-in. To thisend, a profile query (using our version of One-To-Many rTBTR) is made for all possible pairs ofcutstops in S0 . If a route belongs to an optimal journey between a pair of cutstops, it is added
to the fill-in set.
In the query phase, given the source so and destination sd , the first step is to identify So andSd , i.e., the stop cell to which so and sd belong to. Let the corresponding route cells be Ro andRd . If the source stop is a cutstop, then So and Ro are set to S0 and ∅ respectively (the sameconvention is used for the destination stop). A trip is scanned only if it is a part of fill-in or if
all its stops belong to the source or destination cells.
Multilevel Extensions Consider the example in Figure 2. The base network is an abstractionof a transit network before partitioning. Nodes in white indicate stops, and those in blue show theTRISTAN XI Symposium

Original abstract submittal

P. Agarwal, T. Rambha

3source and destination. In Standard Partitioning, the network is partitioned into six parts. Rednodes represent cutstops. Labels show the stop cell ID for each partition (S1 , S2 , . . . , S6 ) and S0
is assumed to contain all the red cutstops. Thus, using standard
partitioning, HypTBTR’s fill-in7
trip set will require finding optimal journeys between 2 2! = 42 source-destination permutationsof the cutstops.
In Multilevel Partitioning, we use two levels. In Level 1, the network is partitioned into threeparts (S1 , S2 , S3 ). These are referred to as parent partitions. Green nodes show the cutstops ofLevel 1. Next, in Level 2, each parent partition is divided into two subparts (i.e., child partitions).
E.g., S1 is divided into S11 and S12 . Cutstops are shown using pink nodes here. Finding thefill-in set F can then be divided into parts. First, Compute the trips required to travel between
cutstops at the topmost level, i.e., 42 2! = 12 source-destination permutations of the four green
cutstops of Level 1. Second, For each parent partition, determine the trips required to travel
between its cutstops and the cutstops of its children. E.g., in Figure 2, arrows between Levels 1and 2 indicate 4 source-destination permutations for S1 and its children S11 and S12 . Similarly
for S2 and its children S21 and S22 , we have 8 permutations. Thus, we get a total of 4+8+4 = 16
permutations between the two levels.
The overall number of source-destination pairs in the multilevel scheme is 12 + 16 = 28
compared to 42 in the standard scheme (a 33% benefit).
Base Network

Standard Partitioning: 6 way

S1S1S4Multilevel partitioning : 3-2 way

S2S5S2S3S6S11S12S3S21
S22

Level 1

S31

S32

Level 2

Figure 2 – Example to illustrate the advantages of multilevel partitioning
One-To-Many rTBTR: As stated above, given a set of cutstops, partitioning-based speed-up
methods find and store the optimal paths between them. To do this, the existing approach is to
apply a One-To-One algorithm (e.g., rRAPTOR, rTBTR) for all possible cutstop combinations.
This step is the major bottleneck during preprocessing. We propose to solve this by extending
existing rTBTR and rRAPTOR algorithms to their One-To-Many variants. For a given destination stop list, these algorithms find all optimal journeys departing within a specified timerange. Our framework aggressively prunes the destination list to achieve faster runtimes. Practical applications of the proposed techniques include point-of-interest queries (find the closes fiverestaurants), dynamic traffic assignments, and building distance tables in isochrones.

3RESULTS

Figure 3 shows Switzerland and Sweden when partitioned into four parts. Table 1 compares
the performance One-To-Many rTBTR against rTBTR. The benefits are in the range of 90–95%. Table 2 compares the performance of HypTBTR and MHypTBTR against its base variant.
For One-To-One queries, we observe benefits in the range of 23–37%. Furthermore, we noticea reduction of 5–58% in preprocessing times (not shown here) using multilevel partitioning.
Results from different hypergraph weighting schemes and partitioning algorithms (like hMETIS,KaHyPar, Integer Program) will also be presented. Additional analysis illustrating the effects ofthe proposed techniques on city- and country-level datasets will also be shown.1
1A working paper with more details and results can be found at https://arxiv.org/abs/2111.06654

TRISTAN XI Symposium

Original abstract submittal

P. Agarwal, T. Rambha

4

Figure 3 – Illustration of standard 4-way partitioning for Switzerland and Sweden (Partitions instandard partitioning are indicated by blue, green, yellow, and purple. Red dots indicate cutstops)
Table 1 – Query times (in milliseconds) of various PTR algorithms
NetworkSwitzerland
SwedenRAPTOR
334.7
103.5

TBTR
96.9
6.3

rTBTR
81 710.6
1 250.9

One-To-Many rTBTR3 654.1
131.8

Table 2 – Query performance (in milliseconds) of algorithms combined with partitioning-based
speed-up (values in teal indicate % gain over their base variant)Partitions
6 (3-2)8 (4-2)

Network

MetricSwitzerland

HypRAPTORHypTBTR
MHypRAPTORMHypTBTR

230.6 (31.1%)
62.4 (35.6%)
230.2 (31.2%)
65.0 (32.9%)240.1 (28.3%)
67.3 (30.5%)
231.9 (30.7%)
65.1 (32.8%)

231.4 (30.9%)
63.4 (34.6%)
232.4 (30.6%)
66.2 (31.7%)

226.7 (32.3%)
61.4 (36.6%)
235.8 (29.5%)
65.4 (32.5%)

SwedenHypRAPTORHypTBTR
MHypRAPTORMHypTBTR

90.9 (12.1%)
4.8 (23.8%)
93.5 (9.7%)
4.7 (25.4%)

88.7 (14%)
4.5 (28.6%)
93.4 (9.7%)
4.3 (31.7%)

89.6 (13.4%)
4.4 (30.2%)
85.2 (17.7%)
4.4 (30.2%)

91.1 (12%)
4.3 (31.7%)
85.1 (17.8%)
4.3 (31.7%)

4 (2-2)10 (5-2)References
Bast, Hannah, Carlsson, Erik, Eigenwillig, Arno, Geisberger, Robert, Harrelson, Chris, Raychev, Veselin,& Viger, Fabien. 2010. Fast Routing in Very Large Public Transportation Networks Using Transfer
Patterns. Pages 290–301 of: European Symposium on Algorithms. Springer.
Bast, Hannah, Hertel, Matthias, & Storandt, Sabine. 2016. Scalable Transfer Patterns. Pages 15–29 of:2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX).
SIAM.
Delling, Daniel, Pajor, Thomas, & Werneck, Renato F. 2015. Round-Based Public Transit Routing.
Transportation Science, 49(3), 591–604.
Delling, Daniel, Dibbelt, Julian, Pajor, Thomas, & Zündorf, Tobias. 2017. Faster Transit Routing byHyper Partitioning. In: 17th Workshop on Algorithmic Approaches for Transportation Modelling,Optimization, and Systems (ATMOS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
Dibbelt, Julian, Pajor, Thomas, Strasser, Ben, & Wagner, Dorothea. 2013. Intriguingly Simple and Fast
Transit Routing. Pages 43–54 of: International Symposium on Experimental Algorithms. Springer.
Witt, Sascha. 2015. Trip-based Public Transit Routing. Pages 1025–1036 of: Algorithms-ESA 2015.
Springer.

TRISTAN XI Symposium

Original abstract submittal