key: cord-0604902-20dnrkil
authors: Agarwal, Prateek; Rambha, Tarun
title: Scalable Algorithms for Bicriterion Trip-Based Transit Routing
date: 2021-11-12
journal: nan
DOI: nan
sha: 147df31bd27cad45b95532ebe7daa553bf735cdc
doc_id: 604902
cord_uid: 20dnrkil

This paper proposes multiple extensions to the popular bicriterion 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 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 such as HypRAPTOR. Next, we integrate a 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. Additional analysis studying the effect of hypergraph partitioning tools (hMETIS, KaHyPar, and an integer program) along with different weighting schemes is also presented.

Finding the "shortest/best" path efficiently is a widely researched problem in network science. Particularly, in transportation networks, the problem of route planning can be divided into two categories-Personal Mobility Routing and Public Transit Routing (PTR). Considerable advances have been made in the past few decades in both categories, see Delling et al. [2009] and Bast et al. [2016a] for details. While the goal in both cases is similar, i.e., to find the "best" path between a given source and destination, solution methods for PTR differ primarily due to its inherent time-dependent nature as buses/trains arrive and leave periodically on fixed routes. Further, transit users have greater sensitivity to objectives other than travel time such as transfers, wait and walk time, cost, crowding, and comfort. This makes the problem challenging since users look for journeys that weigh the trade-offs between several attributes. At a broad level, the problem of journey planning in PTR can be divided into the following categories:

1. Earliest Arrival Problem: Given a source, destination, and departure time, this problem aims to find a journey that reaches the destination as early as possible.

2. Multi-criterion Problem: For a source-destination pair and a departure time, the goal is to find a journey (or a set of journeys) based on multiple optimization criteria. The output of this problem is generally a Paretooptimal set of journeys. Among the possible objective function combinations, the bicriterion problem with travel time and transfers is the most explored setting.

3. Range Problem: In this problem, instead of a single departure time, we seek all optimal journeys departing within a specific time range (e.g., journeys departing between 0700-0730). If the time range is 24 hours, it is also referred to as a Profile Query.

A routing algorithm generally solves one or more of the above-mentioned problems. Early approaches in this direction involved modeling a transit network as either a Time-Expanded (TE) graph Schnee, 2007, Pyrga et al., 2008] or a Time-Dependent (TD) graph [Cooke and Halsey, 1966, Ziliaskopoulos and Wardell, 2000] and running a variant of the Dijkstra's method [Dijkstra et al., 1959] . Müller-Hannemann et al. [2007] and Pyrga et al. [2008] compared both approaches and showed that while the TD model results in a compact graph and better performance, the TE approach allows modeling more realistic situations such as transfers. Although several heuristics that accelerate shortest path computations have been proposed over the years [Dreyfus, 1969, Brodal and Jacob, 2004] , their biggest drawback has been that they cannot fully account for the dynamic nature of transit networks. For instance, speed-up techniques such as graph contraction, destination pruning, bi-directional search, and precomputing labels work well for routing in road networks, but fail to give satisfactory results for PTR [Bast, 2009] . With improvements in communication technologies and increased use of smartphones, travelers expect transit routing apps running these algorithms to have minimal response times. Thus, the main goal of our work is to extend PTR algorithms and make them more efficient and practical.

Popular algorithms for PTR developed in the past decade include-Transfer Patterns [Bast et al., 2010] , Connection Scan Algorithm (CSA) [Dibbelt et al., 2013] , Round-based Public Transit Routing (RAPTOR) [Delling et al., 2015] , and Trip-Based public Transit Routing (TBTR) [Witt, 2015] . RAPTOR computes Pareto-optimal journeys by increasing the number of allowable transfers in each round. It works directly on a timetable and does not require any preprocessing. It has been extended to include multiple criteria (e.g., arrival time, transfer, fare zones, and reliability). CSA also works directly on a timetable but employs a lightweight preprocessing scheme to store all the connections in a sorted array. Its performance is comparable to RAPTOR for small to medium-sized networks. However, as the network size increases, CSA's performance is poorer because a large number of connections must be evaluated before the algorithm terminates. Transfer Patterns is another efficient bicriterion transit routing algorithm built on the idea that the optimal journeys for a source-destination pair can be derived from a small fixed subset of nodes. Given this set, a significant portion of the network can be ignored during the query stage. However, the preprocessing associated with the Transfer Patterns algorithm is much higher than its counterparts. TBTR, on the other hand, involves a lightweight preprocessing procedure and shows slightly better performance than RAPTOR and CSA. Another line of research in PTR involves modeling online routing strategies [Hall, 1986 , Hickman and Bernstein, 1997 , Nguyen et al., 1998 , Khani et al., 2015 , Li et al., 2015 , Rambha et al., 2016 , Khani, 2019 . These are particularly useful in situations involving transfers and uncertain trip times. In this paper, we focus on deterministic settings.

A more recent field of study in PTR is to use partitioning-based approaches to improve query times. Transit networks are partitioned (either based on routes or stops) into subnetworks and the optimal paths between the boundary nodes are precomputed. For example, consider the transit network in the left panel of Figure 1 where each route is indicated by a different color. The panel on the right shows the network split into three subnetworks. For source-destination pairs that lie completely within each subnetwork, we can use regular PTR algorithms on a smaller graph. However, to travel between these subnetworks, a passenger has to pass through the red boundary stops (also known as cutstops). Thus, we can accelerate routing queries by precomputing and storing the shortest paths between the red stops for all departure times. Building on this idea, CSA was extended to ACSA in Strasser and Wagner [2014] , Transfer Patterns was extended to Scalable Transfer Patterns in Bast et al. [2016b] , and RAPTOR was extended to HypRAPTOR in Delling et al. [2017] . To the best of our knowledge, ACSA is the only algorithm (relevant to the current study) to exploit a multilevel paradigm. However, its application is limited since it only solves the Earliest Arrival Problem. For a more detailed discussion on CSA and related algorithms, refer Strasser [2017] and Grötschla [2017] . Although the preprocessing times of Scalable Transfer Patterns is less than that of Transfer Patterns, it is still higher when compared with other PTR approaches. A partitioning variant for TBTR has not been explored till now.

As stated above, partitioning-based speed-up methods find and store the optimal paths between a given set of cutstops. To do this, existing approaches repeatedly apply a One-To-One algorithm (e.g., rRAPTOR, rTBTR) for all possible cutstop combinations. This step is the major bottleneck during preprocessing. Sauer et al. [2020a] solved this issue by proposing a One-To-Many framework by combining UnLimited TRAnsfer technique (ULTRA) with Parallel Hardware-Accelerated Shortest path Trees (PHAST). However, adapting the ULTRA-PHAST framework to profile search remains unexplored. Apart from aiding preprocessing, One-To-Many algorithms have several other practical benefits. These include queries involving Points-of-Interest [Delling and Werneck, 2014] , e.g., "find the closest restaurants near me", transit assignment problems, and building isochrones [Bauer et al., 2008 , Baum et al., 2016 , i.e., a set of vertices reachable from a given point within a time or distance limit. While several extensions to road routing algorithms have been proposed to handle such problems [Knopp et al., 2007 , Delling et al., 2013 , literature on One-To-Many PTR algorithms is sparse to date. Table 1 summarizes the gaps in existing frameworks for transit routing and highlights the features of the algorithms proposed in this paper. Lehoux and Loiodice [2020] More specifically, the following contributions address these gaps. The improvements summarized here are based on empirical results from six country-and city-level transit datasets. Results from Switzerland, Netherlands, and Sweden were found to be very encouraging are summarized below.

• HypTBTR: Section 3 proposes HypTBTR by combining TBTR with a partitioning-based speed-up method.

For One-To-One shortest path queries, HypTBTR was found to be 23-37% faster than the TBTR algorithm. Additional analysis studying the effect of different weighting schemes and hypergraph partitioning tools is also presented.

• One-To-Many rTBTR: Solving profile queries is one of the major bottlenecks in modern PTR approaches such as Scalable Transfer Patterns, HypRAPTOR, and HypTBTR. To address this problem, we extend the popular rTBTR algorithm to its One-To-Many variant in Section 4.1. This algorithm not only reduces the preprocessing times significantly, but can also help query the shortest path between two locations (which may have multiple bus stops near them) instead of two transit stops. Compared to existing approaches, our implementation was found to be 90-95% faster.

Bangalore-that do not benefit from partitioning in Section 5 and point to a few network topology-specific metrics that can distinguish these instances from the success stories.

The remainder of the paper is structured as follows. In Section 2, we introduce terminology related to PTR, and review TBTR and RAPTOR. In Section 3, we reduce the TBTR algorithm's query time by extending it to HypTBTR. Section 4 is devoted to reducing preprocessing times. Specifically, Subsection 4.1 introduces the One-To-Many rTBTR algorithm. Subsection 4.2 showcases how multilevel partitioning can be used to further reduce the preprocessing in HypTBTR and HypRAPTOR. In Section 5, we compare the performance of the proposed techniques on a few transit datasets. Finally, Section 6 summarizes our findings and suggests potential extensions to the current research.

To keep the paper concise, other algorithmic details and results from additional experiments are provided in the appendices. Appendix A contains the steps involved in TBTR preprocessing. In Appendix B, we present the One-To-Many variant of rRAPTOR. Appendix C illustrates the effect of different hypergraph weighting schemes. Lastly, Appendix D compares the performance of different partitioning methods-hMETIS, KaHyPar, and an Integer Program (IP).

We describe the terminology used in the public transit networks in Subsection 2.1 and summarize the notation in Table 2 . Subsection 2.2 reviews a few journey planning algorithms that are closest to our work.

A timetable in a public transit network is defined as a tuple (S, R, T, F ), where S is a set of stops, R denotes the set of routes, T represents the set of trips, and F indicates a set of footpaths. The timetable corresponds to bus/train schedules and contains information related to a transit network and the movement of vehicles on routes. The most common format for representing timetable information is General Transit Feed Specification (GTFS). Maintained by Google, it defines headers for multiple files and rules on how they are related to each other.

A stop s ∈ S is a distinct location in the network where the passengers can board/alight vehicles. For example, bus or train platforms. The source and destination stops are labeled s o and s d , respectively. A route r ∈ R is a sequence of stops followed in a particular order. The i th stop on route r is denoted by r(i). The length of route r, denoted by l r , is the total number of stops in the route.

A trip t ∈ T is defined as the movement of a vehicle along a route. A stop event (or simply an event) refers to a trip arrival or departure at a stop. Similar to r(i) and l r , we use t(i) and l t to denote i th stop and the length/number of stops of trip t, respectively. A trip segment t(i → j) is used to refer to a section of a trip t from stop index i to j, that is from the i th stop of the trip to the j th stop. Route ID of trip t is indicated by route(t). The arrival and departure times at the i th stop of trip t are denoted by arr(t, i) and dep(t, i), respectively. Unless stated otherwise, trips along a route are assumed to be non-overtaking, i.e., trips follow the First-In-First-Out (FIFO) property. Additionally, for two trips t 1 and t 2 operating on the same route, i.e., route(t 1 ) = route(t 2 ), the following notation is used to indicate precedence. If arr(t 1 , i) < arr(t 2 , i) ∀ i = 1, . . . , l t1 , t 1 ≺ t 2 . Likewise, if arr(t 1 , i) ≤ arr(t 2 , i) ∀ i = 1, . . . , l t1 , we express this scenario as t 1 t 2 .

A footpath (s 1 , s 2 ) ∈ F (also sometimes referred to as a transfer ) is a pedestrian connection between stops s 1 , s 2 ∈ S. For a footpath (s 1 , s 2 ) ∈ F , the time required to travel between stops s 1 and s 2 is denoted by f (s 1 , s 1 ). We assume that footpaths are transitively closed, i.e., if (s 1 , s 2 ), (s 2 , s 3 ) ∈ F , then (s 1 , s 3 ) ∈ F . Also, footpath times are assumed to follow the triangle inequality, i.e., f (s 1 , s 3 ) ≤ f (s 1 , s 2 ) + f (s 2 , s 3 ). Since in GTFS, the transfers.txt file that contains footpath details between stops is optional, most online sources do not provide it. Thus, to construct the set F , we first define an upper limit on the walking time between a pair of stops. Additional footpaths are then added so that F is transitively closed. We also define the neighborhood of a stop s, denoted by N (s), as N (s) = {s | (s, s ) ∈ F } ∪ {s}. Intuitively, for a stop s, N (s) is a set of stops directly connected to s via footpaths in F and includes itself.

For processing shortest path queries efficiently, we need to precompute trip-transfers. A trip-transfer, denoted by t 1 , i, t 2 , j , represents a possible transfer from i th stop of trip t 1 to j th stop of trip t 2 . Note that transfer and trip-transfer are different terms and are not interchangeable. While a transfer just refers to a footpath connection between two stops, a trip-transfer indicates switching between two trips. The switch is possible by either alighting the current trip and waiting at the same stop to board another trip or by walking to a different stop via a footpath and then boarding a trip. The set of trip-transfers is denoted by T . See Section 2.2 and Appendix A for more details on computing T .

A journey y is a sequence of trips and footpaths (in the order of traversal). To evaluate a journey y, we define a vector g(y) = (g 1 (y), g 2 (y), . . . , g m (y)), where each element of the right-hand side represents the attributes of various optimization criteria associated with y. A journey y 1 dominates journey y 2 if all the elements g(y 1 ) are no worse than that in g(y 2 ). For example, if the arrival time and the number of transfers are the optimization criteria, a journey y 1 with g(y 1 ) = (1030, 1 transfer) dominates a journey y 2 with g(y 2 ) = (1100, 2 transfers). The set of g(y) for different Pareto-optimal journeys is denoted by J . A set J is Pareto-optimal if none of the journeys in J are dominated by the others. For example, J = (1030, 1 transfer), (1100, 0 transfers) is Pareto-optimal.

Some studies also consider the minimum change time and dwell time at each stop. Minimum change time refers to the time spent by a passenger while transferring between trips. Dwell time represents the time interval for which bus/train waits at a stop before departing. To keep the pseudocodes simple, both these parameters are assumed to be zero for all stops, but extending them to a realistic setting is straightforward. 

index of the first stop of trip t that has been scanned in TBTR's query phase route(t) route of trip t arr(t, i) arrival time of trip t at stop index i dep(t, i) departure time of trip t at stop index i t(i → j) trip-segment of trip t from stop index i to j t 1 , i, t 2 , j possible transfer between i th stop of trip t 1 and j th stop of trip t 2 l t total number of stops in trip t r route R set of all routes R i set of routes belonging to i th partition r(i) i th stop on route r l r total number of stops in route r 

For illustrating the algorithms discussed in this paper, we use the toy network shown in Figure 2 . The colored solid edges indicate different routes. The timetable is periodic, i.e., there is a trip on each route starting from 0800 at a 10-minute frequency. Each row represents a route (color-coded) and every cell is a tuple (trip ID, starting time). Let the travel time between any two stops directly connected by an edge be 10 minutes. [Delling et al., 2015] is a fully dynamic routing algorithm mainly designed for PTR. While the basic version of the algorithm minimizes the bicriterion problem involving travel time and the number of transfers, its extensions can incorporate other optimizing criteria such as the number of fare zones and cost. RAPTOR uses array and bag data structures to store the transit timetable in the form of trips, and works in rounds. The n th round computes arrival times at stops reachable using exactly n − 1 transfers. For a stop s, two types of labels are used: τ opt (n, s) which denotes the earliest arrival time label in round n i.e., using exactly n − 1 transfers and τ * (s) which represents the best arrival time at s so far. (Note that unlike RAPTOR, the TBTR algorithm and the rest of the paper assumes that τ opt (n, s) represents the optimal journey times using at most n transfers.) Each round is divided into two phases: a route phase and a transfer phase.

In the route phase, all routes serving a set of marked stops (source stop or stops whose label was improved in the previous round) are collected. For each of these routes, the earliest possible trip that can be boarded from its marked stop is determined, and its subsequent stop labels are improved (if possible). Any stop whose label is updated is added to the marked stop list. In the transfer phase, footpath connections of stops in the marked stop list are evaluated. Stops whose arrival time improves with these footpath connections are added to the marked stop list. RAPTOR has also been extended to handle range queries (rRAPTOR) and multi-criteria queries (McRAPTOR).

The following example illustrates the RAPTOR algorithm. The pseudocode for RAPTOR is reviewed in Appendix B.

In Figure 2 , in Round 0, the label τ opt (0, s o ) is updated to the departure time τ and is added to the marked stop list. Thus, the first round involves boarding the earliest possible trips on the pink (r 1 ) and green (r 2 ) routes at 0800 and updating its subsequent stop labels. Stops whose labels are updated (i.e., s 2 , s 3 , s 5 , and s 8 ), are added to the marked stop list. In the transfer phase of Round 1, footpath connections are evaluated, and the label of stop s d is updated to 0900, and s d is added to the marked stop list. Next, Round 2 begins its route phase using the marked stop list from the transfer phase of Round 1. The algorithm proceeds similarly and terminates when the maximum transfer limit is reached or no stop labels are updated. For the current example, Round 1 explores the pink route (r 1 ), green route (r 2 ), and the footpath; Round 2 scans the grey (r 3 ) and orange route (r 4 ); and finally, Round 3 explores the red route (r 5 ) and terminates. The final Pareto-optimal journeys are (0900, 0 transfers) and (0850, 2 transfers).

TBTR [Witt, 2015] solves the bicriterion (travel time and transfer) optimization problem using trips and trip-transfers as building blocks. The core idea in TBTR is similar to a breadth-first search on a graph in which trips are modeled as nodes and trip-transfers as edges. The first level can be imagined to represent the earliest trips that can be boarded from the source stop, and each subsequent level corresponds to a transfer. TBTR's search pattern is similar to RAPTOR, but unlike RAPTOR, it does not maintain multi-labels for all stops. The Preprocessing phase and Query phase of TBTR are as described below.

Preprocessing phase: TBTR has a two-stage preprocessing phase. Using the GTFS set, the first stage collects all possible trip-transfers in a set T (referred to as the Trip-transfers set). This may result in a large collection of trip-transfers, most of which are never part of optimal journeys for any source-destination pair. Hence, the second stage aims to reduce T to only contain useful trip-transfers. Appendix A provides the pseudocodes for both the stages along with relevant illustrations.

Query phase: Given an input (T , s o , s d , τ ), the query stage maintains a set J of Pareto-optimal tuples of the form (arrival time, number of transfers) and a queue Q n of trips-segments to be scanned for each allowed number of transfers n, where n ∈ {0, 1, . . . , λ} and λ is the maximum transfer limit. Q 0 is initialized with the earliest trip-segments that can be boarded on all routes passing through stops in N (s o ). Additionally, for every trip t, we maintain a variable, ind(t), which denotes the index of the first stop of trip t that can be reached. To efficiently check if a trip passes through s d , the algorithm initializes a set L which keeps track of all routes that pass through at least one of the stops in N (s d ). The best known arrival time at the destination stop s d using at most n transfers is denoted by τ opt (n). TBTR, like RAPTOR, also works in rounds. In the n th round, trip-segments in the queue Q n are scanned. While scanning a trip-segment t(h → k) in round n, the following operations are performed:

• Using L, check if the trip t passes through stop s d (or stops in its neighborhood) and results in a non-dominated label. If so, update τ opt (m) ∀ m = n, . . . , λ. Note that reducing the labels for all subsequent rounds ensures that the optimality check in later rounds is done against the destination's best arrival time.

• Using the trip-transfers t, i, t , j available from the i th stop of t within a trip-segment t(h → k), we add trip-segments t (j → ind(t )) to the queue Q n+1 if the arrival time at the (h + 1) th stop on t is less than the destination's best known arrival time (i.e., arr(t, h + 1) < τ opt (n)) and the trip t from j onwards has not already been explored (i.e., j < ind(t )).

The algorithm stops when the maximum transfer limit λ is reached, i.e., n = λ or when Q n is empty for n < λ. The pseudocode for the TBTR's bicriterion query is shown in Algorithm 1. Lines 1-5 represent the initialization phase where τ opt (n) is initialized to ∞ for all n ≤ λ. Lines 6-8 generate the set L, which is used during the query phase to check if a journey reached the destination stop. Lines 9-14 add the trip-segments that can be boarded from stops in N (s o ) to Q 0 . Lines 15-26 scan every trip-segment t(h → k) as described above. Connections from the trip-segment (assuming the condition in Line 21 is satisfied) are collected in a list clist. Next, Line 24 calls the function Enqueue which iterates over the elements of clist and adds unexplored trip-segments to Q n+1 . Figure 3 illustrates the main while-loop of the TBTR algorithm. Consider the example from Figure 2 to illustrate the TBTR algorithm and assume T = t 1 , 2, t 8 , 1 , t 2 , 3, t 14 , 1 , t 14 , 2, t 20 , 1 , t 8 , 3, t 20 , 1 . Note that this is smallest T required to solve the example query. Round 0 starts by scanning the trips in queue Q 0 = {t 1 (1 → 3), t 2 (1 → 3)}. Since trip t 1 is connected to s d via a footpath, τ opt (0) is updated to 0900. Next, we scan T to get trip-transfers from trips t 1 and t 2 and add the corresponding trip-segments to queue Q 2 . Round 1 starts with Q 1 = {t 8 (1 → 3), t 14 (1 → 2)} and proceeds in a similar fashion. For Round 2,

The final output of the algorithm is τ opt (0) = 0900, τ opt (1) = 0900, and τ opt (2) = 0850.

TBTR has been extended to incorporate range queries, similar to rRAPTOR. The idea behind this algorithm is to run the main query for different departure times while preserving labels between runs. Later departure times are processed first. Another version of TBTR is Trip-based Routing using Condensed Search Trees or TBTR-CT [Witt, 2016] . This algorithm exploits the observation that the optimal journey for a source-destination pair at any time can be constructed using only a fixed set of routes instead of the complete network. It preprocesses routes for each source-destination pair, and thus, the query phase explores a much smaller graph, resulting in faster queries. Just like Transfer Patterns [Bast et al., 2010] , faster query times in TBTR-CT come at the cost of high preprocessing time and increased memory usage. 

This section extends TBTR to HypTBTR by combining it with partitioning-based approaches. We start with the relevant background in Subsection 3.1, followed by the development of HypTBTR in Subsection 3.2.

Delling et al. [2017] proposed HypRAPTOR for faster queries by introducing a preprocessing step which partitions routes into p disjoint sets R 1 , R 2 , . . . , R p , also known as route cells. The central idea in HypRAPTOR is to construct a hypergraph G in which nodes represent routes, and hyperedges between subsets of nodes represent intersecting routes. Two routes are called intersecting if they have at least one stop in common. Footpaths are also treated as routes with two stops. A partitioning algorithm (based on a min-cut approach) is then used to generate route cells. By definition, route cells are mutually exclusive and exhaustive (i.e., R i ∩ R j = ∅ for all i and j, and

. Suitable edge and node weights can be used to influence the partitions. Multi-edges that result from routes intersecting at more than one stop are reduced to a single edge by summing their weights. Note that every boundary edge of the partition (an edge with nodes in different cells) represents a stop in the original transit network and is referred to as a cutstop. Consider the example in Figure 4 . Subfigure (b) shows the corresponding hypergraph with each route as a node (a hyperedge with three nodes is added between the red, orange, and grey routes). The black node represents the footpath. Assuming p = 3, a partitioning algorithm creates three route cells namely R 1 (dark blue), R 2 (cyan), and R 3 (purple), as shown in Subfigure (c). Subfigure (d) shows the cutstops derived from the route cells in (c).

Similar to route cells, stops cells S 0 , S 1 , . . . , S p is a partition of stops. To construct a stop cell S i , we start by including all the stops belonging to the routes in the corresponding route cell R i . However, the resulting stop cells are not mutually exclusive due to cutstops. Thus, define S 0 to contain all the cutstops and update stop cell S i as S i ← S i \ S 0 . For example, in Figure 2 , the stop cells are S 0 = {s 0 , s 2 , s 8 , s 9 }, S 1 = ∅, S 2 = {s 5 , s 6 }, and S 3 = {s 3 , s d , s 7 }. Note that for p partitions, there are p route cells and p + 1 stop cells.

The next step is to find and store optimal routes between these cutstops, referred to as fill-in. To this end, a profile query (using rRAPTOR) is made for all possible pairs of cutstops in S 0 . 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 and destination, the first step is to identify S o and S d , the stop cells to which s o and s d belong to, respectively. Let the corresponding route cells be R o and R d . If the source stop is a cutstop, then S o and R o are set to S 0 and ∅, respectively. The same convention is used for the destination stop. The algorithm scans a route only if it belongs to the fill-in set or if all its stops are in the source or destination cells. Building Algorithm 1 TBTR: Bicriterion query

add (t , j, n + 1) to clist if not already present 24:

on this idea we construct the HypTBTR algorithm. A new hypergraph weighting scheme is proposed, and changes to the query phase are suggested for the trip-based setting. In a subsequent section, we discuss methods to make HypTBTR preprocessing more efficient.

Preprocessing in HypTBTR can be grouped into two phases: trip-transfer phase and fill-in computation phase. The trip-transfer phase generates a trip-transfer set T and is similar to TBTR's preprocessing (see Appendix A for details).

The fill-in computation phase can be further divided into two steps. The first step is similar to that of HypRAPTOR and generates a hypergraph by modeling each route as a node. We then add hyperedges between routes that have common stops. Next, to generate the partitions and cutstops, we use the state-of-the-art KaHyPar algorithm [Schlag, Figure 4 : Route partitioning using a hypergraph representation 2020]. KaHyPar works on a min-cut principle and finds nearly equal-sized cells such that the sum of weights of the hyperedges in the cut is minimized. The size of a cell is defined as the sum of the weights of nodes belonging to it. Thus, different weighting schemes, as described below, can be used to influence the partitioning process.

1. Sc 1 : This represents a simple unweighted scheme where no weights are imposed on nodes and edges. Thus, the algorithm minimizes the number of hyperedges cut.

2. Sc 2 : This scheme was first proposed by Delling et al. [2017] . Here, the nodes (i.e., routes in the original transit network) are weighted by the total numbers of events in the route. The weights of nodes corresponding to footpath connections are set to zero. Each hyperedge is assigned a weight equal to the logarithm of the total number of events associated with the corresponding transit stop.

3. Sc 3 : In this case, nodes are weighted similar to Sc 2 . But for a hyperedge corresponding to a stop s, the weight is set to the logarithm of the sum of events associated with all the stops in N (s).

In HypRAPTOR's (or HypTBTR's) preprocessing, walking from the source stop must be allowed. That is, when finding the trips required to cover optimal journeys between a cutstop pair s i and s j in the preprocessing phase, Round 0 would have to start with all the earliest trips from N (s i ) (instead of trips from s i ). This is because, although the cutstop s i is a source stop during preprocessing, it can become an intermediate stop between some s o and s d during the query phase. For example, an optimal journey could be of the form-board the first trip from s o and alight at s i , walk from s i to some stop s ∈ N (s i ), take a bus from s to s j , and board the next available trip from s j and reach s d . Thus, walking from the source cutstop s i must be allowed during preprocessing to maintain the algorithm's correctness. Therefore, the fill-in calculations associated with a stop s, depend not only on s but on all the stops in N (s). For this reason, we expect Sc 3 , which sets the hyperedge weights to the logarithm of the sum of events in N (s), to perform better than Sc 2 . Experiments in Section 5 are carried out using Sc 3 . Comparison of other weighting schemes is documented in Appendix C.

For a pre-determined partition size p, the output of the first step includes p route cells R 1 , R 2 , . . . , R p and p + 1 stop cells S 0 , S 1 , . . . , S p , where S 0 is the set of cutstops. The second step in the fill-in computation phase is to find the fill-in trip set F, i.e., the set of trips required for all optimal journeys between the cutstops. For this purpose, Delling et al. [2017] use a profile query for all possible cutstop permutations by repeatedly applying rRAPTOR. To speed-up this process, we propose a new accelerated version of rTBTR, a One-To-Many rTBTR in Section 4.1. Our implementation significantly outperforms the existing approach by rapidly solving profile queries between all possible cutstops pairs. Next, we discuss a few alternate hypergraph partitioning tools that have also been tested in this paper.

Hypergraph partitioning is a widely studied problem in graph theory because of its numerous applications. As mentioned earlier, the problem involves dividing the vertices of the hypergraph into a given number of partitions such that the number of hyperedges cut is minimized and the size of each partition is bounded. We review an IP formulation of the problem [Kucar et al., 2004] , followed by a discussion on other algorithmic approaches.

Let G = (V, E) represent an undirected hypergraph where V is the set of nodes and E is the set of hyperedges. Denote using w v and w e , the weight of a node v and a hyperedge e, respectively. The decision variables of the problem include x vi , which equals 1 if node v belongs to partition i, i.e., v ∈ R i and is 0 otherwise and y ei , which is 1 if hyperedge e lies inside partition i, i.e., if v ∈ R i ∀ v ∈ e. Note that y ei = 1 implies that hyperedge e is uncut. Let α i and β i represent the lower and upper bound on the size of the partition i. Recall that the size of a partition is defined as the sum of the weights of hypernodes in it. The IP model for hypergraph partitioning can thus be formulated as follows.

The objective function (1) maximizes the sum of the weights of uncut hyperedges. Equation (2) ensures that every node belongs to exactly one partition. Constraint (3) imposes bounds on the partition sizes. Constraint (4) stipulates that for a hyperedge e, y ei is 1 if and only if all the nodes in e are in partition i. Boolean constraints on the decision variables are enforced in (5) and (6).

IP models like the one discussed above have both pros and cons. Their biggest advantage is the ability to easily incorporate different weighted objective functions. However, while solving for the optimal partitions, enumerative techniques such as branch-and-cut are used, which tend to be slow in practice and do not scale well.

To overcome these drawbacks, several alternate heuristics (e.g., iterative methods, genetic algorithms, multilevel methods) have been studied in the literature. See Kucar et al. [2004] for more details. Among these approaches, multilevel partitioning algorithms such as hMETIS [Karypi, 2007] and KaHyPar [Schlag, 2020 , Schlag et al., 2021 These multilevel methods typically work in three steps: Coarsening, Initial Partitioning, and Refinement. Coarsening reduces the size of the hypergraph by contracting subsets of nodes, i.e., a set of nodes is replaced by a single vertex. It successively generates smaller hypergraphs such that partitions on the smaller hypergraph are not significantly worse than partitions generated directly on the original hypergraph. The next step involves partitioning the coarsened graph. Finally, in the Refinement phase, the graph is uncoarsened by successively projecting it to back to a finerlevel. Several refinement techniques such as the FM algorithm [Fiduccia and Mattheyses, 1982] are used to improve the quality of partitions without violating user-specified constraints. KaHyPar and hMETIS differ in the algorithms used in these three phases. E.g., for coarsening, hMETIS uses the firstchoice algorithm and KahyPar uses community aware coarsening. The readers can refer to Schlag [2020] for more details. All experiments in Section 5 were done using KaHyPar. We used publicly available implementations of KaHyPar (github.com/kahypar) and hMETIS (hMETIS Code). Only the KaHyPar code offered flexibility in configuring various parameters such as the objective function and seed value. For performance metrics of HypTBTR using hMETIS, refer Appendix D.

Depending on the fill-in representation, the query phase can be implemented in many ways. The simplest approach is to scan a route only if it belongs to the source or destination cell, or is a part of the fill-in. Other methods include marking every event that is a part of fill-in computations as opposed to marking the whole route or generating a new overlay graph by copying the events of the source and destination cells and fill-in.

These methods present a trade-off between speed and memory usage. Experiments by Delling et al. [2017] show that overlay graphs are slightly better, but other methods have comparable performance and the exact benefits vary depending on the network and partition structure. In this paper, we use the simplest form of fill-in representation, i.e., for every trip t, we initialize a one-bit variable known as a trip flag denoted by f lag(t). A trip's flag is true if it belongs to the source or destination cell or is a part of the fill-in. The pseudocode for the query phase is described in Algorithm 2.

Lines 1-5 are used to initialize the variables and are similar to Algorithm 1. In Line 6, we introduce a function Labeling which, given s o and s d , identifies S o and S d , the stop cells to which source and destination stop belong, respectively. The corresponding route cells are also identified as R o and R d . Although we do not necessarily need S o and S d , we include it in the pseudocode since it helps establish a proof of correctness. if arr(t, h + 1) < τ opt (n) then for (t, i, n) ∈ clist do 3:

if f lag(t) and i < ind(t) then 4:

for trip t s.t. t t and route(t) = route(t ) if s o ∈ S i then 5: In Case (i), as both s o and s d are cutstops, HypTBTR will only scan trips in the fill-in set F (since Lines 7-9 set f lag(t) = True ∀ t ∈ F). Thus, if y is optimal, the fact that F contains all the optimal trips between the cutstops is contradicted. In Case (ii), optimal journeys are either fully contained in the route cell or exit the route cell at some cutstop s i and enter again at another cutstop s j . The former scenario reduces to a simple TBTR without partitioning and in the latter instance, all the trips from the route cell and F are scanned in Lines 7-9 and hence it again contradicts the definition of F. The arguments for Case (iii) are similar. Further, note that Line 29 restricts J to only contain Pareto-optimal labels and hence it does not contain any extra labels corresponding to sub-optimal journeys.

In this section, we speed-up preprocessing using a One-To-Many rTBTR which reduces the time required for profile queries (Section 4.1) and multilevel partitioning which reduces the calculations required for the fill-in set computation (Section 4.2).

As discussed in Section 3.2.1, preprocessing involves solving profile queries between all possible cutstop pairs. Existing approaches use a range algorithm (rRAPTOR or rTBTR) for all possible cutstop pair combinations. In this section, we propose a One-To-Many version to make this step more efficient.

For a give source stop s o , let tlist represent a list of all departure times of trips (sorted in descending order) from s o (or N (s o ) if walking from the source is allowed). Let dlist be list of destination stops. Similar to L, J , and τ opt (n) in TBTR, we define L(s), J (s), and τ opt (n, s) for each s ∈ dlist where L(s) keeps track of routes through N (s), J (s) stores the optimal journey attributes to s, and τ opt (n, s) is the optimal label of stop s using at most n transfers, respectively. Lastly, to preserve labels between runs, we also store the index of the first stop on trip t that can be reached within n transfers, ind(n, t).

In addition to dlist, we also maintain a dummy list dlist and a variable scope whose purpose is to prune the list of destination stops as the algorithm proceeds. To understand the idea behind pruning the destination list, consider the toy network shown in Figure 2 . For simplicity, imagine that only one trip on the pink and green routes departs from s o at 0800 and suppose dlist = [s 6 , s d ]. Thus, tlist = arr(t 1 , 1), arr(t 2 , 1)]. As discussed in Section 2.2.2, for Round 0, Q 0 = t 1 (1 → 3), t 2 (1 → 3) . Next, Round 1 starts with Q 1 = t 8 (1 → 3), t 14 (1 → 2) and updates τ opt (1, s 6 ) to 0820. Since all trip-transfers t, i, t , j from trips t 8 and t 14 are such that arr(t 1 , i) is greater than τ opt (1, s 6 ), there are no other optimal journeys to s 6 . Hence, we can safely remove s 6 from dlist. Thus, as the algorithm proceeds, the destination list is progressively pruned, resulting in faster queries.

Compared to the rTBTR algorithm, the One-To-Many version scans trip-segments fewer times. In the above example, repeated application of rTBTR scans the trip-segments t 1 (1 → 3), t 2 (1 → 3), t 8 (1 → 3), and t 14 (1 → 2) twice (once for each destination node) whereas the One-To-Many rTBTR does it only once.

The pseudocode for the One-To-Many rTBTR is presented in Algorithm 3. Lines 1-7 initialize the variables L(s), J (s), ind(n, t), and τ opt (n, s). Line 8 iterates over all all possible departure times τ in a decreasing order. Lines 9-16 initialize n and Q n as before. We start by copying all the elements of dlist into a dummy list dlist in Line 17. In the main while-loop, for each allowed number of transfers n (≤ λ), Line 19 first defines an empty set scope.

While scanning a trip-segment t(h → k), a for -loop (Line 21) is introduced which iterates over all the stops in dlist . Lines 22-32 scan the trip-segments as described in the TBTR algorithm. An additional step is introduced in Line 29 that adds stops whose labels could improve to scope. Lastly, Lines 35-36 increment n and update dlist using scope. for (t, i, n) ∈ clist do 3:

if i < ind(n, t) then 4:

Q ← Q ∪ t(i → ind(n, t)) 5:

for trip t s.t. t t and route(t) = route(t ) do 6:

for j = n, n + 1, . . . , λ do 7:

ind(j, t ) ← min ind(j, t ), i

Proof of correctness: Observe that if dlist was the same as dlist, i.e., if the destination list was not pruned, then Algorithm 3 is equivalent to repeated application of rTBTR. Also, s d is deleted in some round n < λ only when the if -condition in Line 28 is violated, i.e., "for all trip-segments t(h → k) ∈ Q n , their first stops t(h + 1) are reached later than the best known arrival time at s d ". Thus, to establish the algorithm's correctness, it is enough to show that the updates to τ opt labels is identical in the following two cases: (i) dlist is pruned (ii) dlist is not pruned in round n even when Line 28 is violated for all trip-segments.

In Case (i), given that s d is removed in round n, τ opt (m, s d ) will not be updated for n + 1 ≤ m ≤ λ because the for -loop in Lines 22-32 will not iterate over s d . In Case (ii), for round n + 1, we can show that there does not exist any t(h → k) ∈ Q n+1 that satisfies the arrival time condition in Line 23 and hence the algorithm will consequently not update τ opt (n + 1, s d ). To see why, note that for all trip segments t (i → j) ∈ Q n , since Line 28 was violated, arr(t , i + 1) > τ opt (n, s d ). Because every trip segment t(h → k) ∈ Q n+1 was added using some trip segment t (i → j) ∈ Q n in the previous round, we can conclude that arr(t, h) ≥ arr(t , i + 1) > τ opt (n, s d ). At the start of round n + 1, the value of τ opt (n + 1, s d ) is same as τ opt (n, s d ) since it was set in Lines 24-26 in the previous round. Thus, arr(t, h) > τ opt (n, s d ) = τ opt (n + 1, s d ) and the if -condition in Line 23 is violated. Hence, the τ opt label for round n + 1 is not updated. A similar argument holds for later rounds.

This section introduces MHypTBTR, i.e., HypTBTR combined with multilevel partitioning. While we propose this concept using HypTBTR, a similar approach can be used for HypRAPTOR. Consider the example in Figure 5 . The base network is an abstraction of a transit network before partitioning. Nodes in white indicate stops, and those in blue show the source and destination.

• Standard Partitioning: The figure on the left shows the network partitioned into six parts (as discussed in Section 3). Red nodes represent cutstops. The labels show the stop cell ID for each partition (S 1 , S 2 , . . . , S 6 ) and S 0 is assumed to contain all the red cutstops. Thus, using standard partitioning, HypTBTR's fill-in trip set will require finding optimal journeys between 7 2 2! = 42 source-destination permutations of the cutsops. • Multilevel Partitioning: The figure on the right depicts multilevel partitioning with two levels. In Level 1, the network is partitioned into three parent partitions (S 1 , S 2 , S 3 ). Green nodes show the cutstops of Level 1. Next, in Level 2, each parent partition is divided into two subparts (i.e., child partitions). E.g., S 1 is divided into S 11 and S 12 . Cutstops are shown using pink nodes here. Finding the fill-in set F can then be divided into two steps:

1. Compute the trips required to travel between cutstops at the topmost level, i.e., 4 2 2! = 12 sourcedestination permutations of the four green cutstops.

2. For each parent partition, determine the trips required to travel between its cutstops and the cutstops of its children. E.g., in Figure 5 , arrows between Levels 1 and 2 indicate 4 source-destination permutations for S 1 and its children S 11 and S 12 . Similarly for S 2 and its children S 21 and S 22 , 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). Note that if the parent partition is split into two parts, the optimal trips between the cutstops of sibling partitions are not required. However, if the split is performed differently, F would also include the optimal trips required to travel between siblings.

The fill-in computation can be implemented in multiple ways. The most straightforward scheme is to store the fill-in trips in a single set F, i.e., there is no distinction between trips required to travel between successive levels and within a level. In this case, MHypTBTR starts from S 12 (source stop cell) in Level 2 and travels up to Level 1 through a trip in F. It then explores a much sparser graph and again transfers down to Level 2 using another trip in F. A full Pareto-set is obtained since all the optimal trips between the cutstops are contained in F. Alternately, a pointer for each trip indicating the level and cutstops for which it is optimal can be maintained (similar to how multilevel arc-flags are used in road networks). This allows additional pruning because, for every trip in F, we have some extra information on the source-destination pairs for which the trip was optimal. However, the differences between these methods are likely to be pronounced in the query phase. Since the main goal here is to decrease preprocessing, we adopt the former fill-in scheme due to its simplicity. 

All algorithms used in our experiments were implemented in Python 3, and the source codes are available at github.com/transnetlab/transit-routing. The query phase codes were run on an Intel Core i7-8700 CPU clocked at 3.2 GHz with 32 GB RAM. The more intensive algorithms related to preprocessing were evaluated in parallel using a 128-core Intel Xeon Gold CPU clocked at 3.0 GHz with 512 GB RAM. The metrics obtained using the parallel method have been marked with an asterisk (T -time * and F-time * ). Query times were averaged over a set of 10 000 randomly selected source and destination stops. For comparison, we also include results from Dijkstra's algorithm on a Time-Expanded graph (labeled as TED). A maximum transfer limit of four was used for all the algorithms (except TED).

We tested our algorithms on six transit networks: Switzerland, Netherlands, Sweden, Israel, Taichung, and Bangalore. Most of these are open data sets (Source: transitfeeds.com) except for Bangalore. Bangalore's network is derived from the Bangalore Metropolitan Transport Corporation (BMTC) timetable, which is the sole public transit agency that operates buses in the city. Note that while the first four networks are country-level networks that combine multiple modes such as buses, rails, trams, and metro, the last two datasets correspond to city-level networks. Table 3 summarizes various statistics for these networks for a single day . Columns hypedges and hypnodes represent the number of hyperedges and hypernodes in the corresponding hypergraph, respectively. A significant amount of preprocessing was required to generate these datasets. For example, country-level datasets often contain overtaking trips since they integrate timetables from multiple agencies and modes. As the algorithms discussed in the present study require trips to follow the FIFO property, overtaking trips were discarded. Also, none of the above-mentioned datasets provide footpath details. This information was separately extracted from OpenStreetMaps (OSM) (geofabrik.de). To do so, all stops were snapped to the nearest OSM coordinate and the corresponding distance matrix was calculated. Next, assuming a constant walking speed of 1 m/s, we obtained footpath times. Using a threshold on walking time, these footpath edges are then filtered and subsequently adjusted to satisfy transitivity and triangle inequality. The values in parenthesis in the footpaths column of Table 3 indicates the threshold on walking time in seconds. Note that these values represent the initial threshold used in the OSM network but since more footpaths are added to ensure transitivity, the final footpath graph can contain edges which take longer to walk. Table 4 presents the query performance (in milliseconds) of the non-partitioning algorithms. The following list summarizes our findings.

• TED vs. others: The query times reported are from NetworkX's implementation of the Dijkstra's algorithm on a time-expanded graph (TED). The results reconfirm that modern PTR algorithms such as RAPTOR and TBTR perform better than conventional Dijkstra-based approaches.

• RAPTOR vs. TBTR: TBTR outperforms RAPTOR in all three instances mainly because it uses the triptransfers set T to directly switch between trips as opposed to RAPTOR's method of finding the earliest trip to board a route. Results from the preprocessing phase of TBTR are in Appendix A.

• rTBTR vs. One-To-Many rTBTR: To compare rTBTR against its One-To-Many variant, we first randomly selected 70 source stops. For each of these source stops, 70 random destinations were chosen, and a profile query was run. That is, rTBTR queries were run 4 900 times, whereas the OTM rTBTR was run 70 times with different source stops as input. In all the test cases, our implementation significantly beats repeated application of rTBTR by 90-95%, demonstrating the potential of the One-To-Many version in reducing the preprocessing time of HypTBTR.

• rRAPTOR vs. One-To-Many rRAPTOR: rRAPTOR was also upgraded to handle One-To-Many queries (see Appendix B for pseudocodes), similar to One-To-Many rTBTR, by pruning the destination list for faster queries. The experimental setup used to compare rRAPTOR and One-To-Many rRAPTOR is the same as described above. One-To-Many rRAPTOR was also found to improve runtimes by 98% when compared with repeated application of rRAPTOR. Next, we analyzed the preprocessing phase of HypTBTR (see Table 5 ). The trip-transfer computation phase of HypTBTR is the same as that of TBTR. For the fill-in computation phase, we first generate a hypergraph using the GTFS data. Table 3 contains the details of these hypergraphs. The parameters used for the KaHyPar algorithm are seed -1, epsilon 0.2, and cut kKaHyPar sea20.ini configuration. The top panel in Figure 6 shows the stops when the test networks are partitioned into four cells (blue, green, yellow, and purple) using the standard method. The multilevel partitions are shown in the bottom panel, where shades of the same color depict siblings of a parent partition. Cutstops are indicated in red. The Sc 3 weighting scheme was used in these experiments, i.e., the weight of a hyperedge corresponding to a stop s is set to the logarithm of total stopevents associated with the stops in N (s). The weight of a hypernode is determined by the total number of events along the corresponding route. A comparison of the weighting schemes discussed in Section 3.2 is presented in Appendix C. The parameters reported in Table 5 include: scut: number of cutstops and % w.r.t total stops in the network, pqueries: number of profile queries required to compute the fill-in set, F size: % of trips that are part of fill-in, and F time: time for computing fill-in trips. For each of the three networks, results from both standard and multilevel partitioning are reported. A column label with label 10 (5-2) implies that the standard partitioning approach splits the network into ten parts, and the multilevel partitioning method creates five parent partitions at the upper level and each parent is divided into two child partitions. The following observations are noteworthy.

• With an increase in the number of partitions, both scut and pqueries increase as expected.

• The values in the parenthesis indicate the % benefit of the multilevel partition over its standard version. For example, in Sweden's ten partitioning case, the number of pqueries needed are 46 440 (standard) and 19 362 (multilevel), which translates to a benefit of 58.3%. A significant reduction can be seen in terms of the pqueries and F time across standard and multilevel versions in all test cases. An advantage of comparing pqueries is that it is a language-agnostic metric. The benefits are mostly in the range of 5-58%.

• While multilevel partitioning was consistently better in all test cases, the percentage benefit varies. This is mainly because the partitions (and hence the cutstops) generated depend on the initial KaHyPar configuration such as seed and epsilon. However, since the aim here is to compare the benefits of multilevel partitioning over standard partitioning, the configuration parameters used were kept same in all the experiments. Table 6 contains the query time (in milliseconds) for HypRAPTOR, HypTBTR, and their multilevel versions. Based on these results, the following conclusions can be drawn.

• HypRAPTOR vs. RAPTOR: As expected, HypRAPTOR performs better than RAPTOR in all the test cases. The benefits were found to be in the range of 12-32%.

• HypTBTR vs. TBTR: HypTBTR consistently performs better than TBTR on all networks. The gain observed was in the range of 23-37%.

• HypRAPTOR vs. HypTBTR: In all the three networks, we observe that the average gains from using HypTBTR over TBTR are more than that between HypRAPTOR and RAPTOR. In other words, the partitioning-based scheme performed better in the TBTR setting than RAPTOR. A possible reason could again be that TBTR uses trips as building blocks instead of routes. For example, imagine a route with m trips of which only one is part of the fill-in set. While HypRAPTOR adds the route (and all m trips) to its fill-in set, HypTBTR adds only one trip.

• MHypTBTR vs. HypTBTR and MHypRAPTOR vs. HypRAPTOR: Query times of the multilevel versions are in the same range as their standard counterparts. This is expected since the size of the fill-in trips in multilevel partitioning is approximately the same as that of standard partitioning. Multilevel partitioning mainly helped reduce preprocessing times.

Multilevel (2-2) way partitions Standard 4-way partitions While the benefits in query times of the partitioning-based methods depend on many factors such as the partitioning algorithm and weighting scheme used, the network topology also plays a key role. While experimenting with different networks, it was observed that the proposed methods do not always perform well. To understand why, recall that the benefits in query times are inversely related to the size of the fill-in set (since the network explored during the query phase comprises of fill-in and source/destination regions). For some transit networks such as Israel, Taichung, and Bangalore, the fill-in set size was found to be relatively high. Table 7 highlights a few metrics that distinguish these networks. Columns spr and eps denote the average number of routes and events (arrival/departure) per stop. KaHyPar was used for partitioning and the results reported are for four partitions. Figure 7 shows the locations of cutstops for these networks.

As can be seen from the table and the figure, the % of cutstops in Israel, Taichung, and Bangalore is significantly higher compared to the ones studied earlier. As a result, the size of fill-in trips is also drastically higher. While we can influence the partitions to some extent using different weighting schemes and partitioning algorithms, our empirical tests indicated that the % of cutstops mainly depended on the network topology, particularly the density of footpath graph and the extent of overlapping routes (represented by spr and eps). For this reason, we even lowered the initial walking threshold (Table 3 Column footpaths) from 180 to 120 s for the latter three networks. Since footpaths are joined to make the graph complete under transitivity, a larger threshold in a dense network like Bangalore might form a full clique resulting in unrestricted walking. As the number of partitions increase, the number of cutstops (and hence the size of the fill-in set) increases. Also, recall that in multilevel partitioning, the size of the fill-in set was found to be close to that of the corresponding standard partitioning case. Multilevel partitioning mainly speeds-up the fill-in computation phase. Thus, we did not notice significant benefits from creating more partitions or from multilevel partitioning for Israel, Taichung, and Bangalore. 

Seamless journey planning plays an essential role in improving the attractiveness of public transit. Given the widespread use of mobile applications for this purpose, the algorithms used in the backend must be fast and efficient. To achieve this goal, we modified an existing well-known Trip-based Transit Routing (TBTR) algorithm for efficiently solving One-To-One queries by extending it to a graph partition-based method called HypTBTR. A new weighting scheme for partitioning the hypergraph was introduced. The benefits observed in the query times were in the range of 23-37% on three country-level open datasets. Since query time reduction comes at the expense of increased preprocessing, we introduced a One-To-Many version for range queries.

The proposed extension not only improves preprocessing times by solving One-To-Many profile queries 90-95% faster, but also makes the TBTR approach more practical. This is because users often query for the shortest path between two locations, and a location can have multiple stops near it. Furthermore, we also explored a multilevel partitioning paradigm compatible with HypTBTR and HypRAPTOR, which further reduces the fill-in computation time by 5-53%. The proposed extensions enable TBTR to handle queries in large-scale networks by eliminating preprocessing-related bottlenecks, making it more scalable. Our experiments also revealed instances where the number of cutstops generated by partitioning algorithms during preprocessing were prohibitively large. One could explore other objectives and weighting schemes in the partitioning algorithms to tackle these instances. Partitions generated from past source-destination query data can also make the proposed algorithms more practical for mobile and real-time applications.

Other algorithms such as CSA and ACSA were not used for comparison as they only evaluate the earliest arrival time query. Also, Transfer Patterns-based algorithms (Transfer Patterns, and Scalable Transfer Patterns) are expected to perform better, but the preprocessing associated with them is likely to be much higher than algorithms in the current study. We defer these comparisons and multilevel partitioning extensions of Transfer Patterns for future research. Apart from partitioning, the goal-directed method is another successful technique that is generally studied in road routing for faster One-To-One queries. E.g., Finkelstein and Régin [2020] extended the CSA to Goal-Directed CSA. Similar extensions can be explored for RAPTOR and TBTR.

Most results in recent transit routing literature, including ours, are empirical in nature. In PTR, for the Earliest Arrival Problem, we can model the transit timetable as a TE-graph and run Dijkstra's algorithm to get the fastest route. One can thus argue that the Earliest Arrival Problem can be solved in polynomial time (as a function of the number of nodes and edges in the TE-graph) [Kaufman and Smith, 1993, Chabini, 1998 ]. Multiobjective problems, on the other hand, are in general NP-Hard since the efficiency frontier can have an exponential number of solutions (see Tarapata [2007] for more details). In special cases where one of the criteria is the number of transfers with a maximum allowable transfer limit, one can create a finite number of layers of the TE-graph and use the Dijkstra's method to compute the Pareto set [Brodal and Jacob, 2004] . Hence, this PTR variant can also be solved in polynomial time. Note that the above discussion is valid only for networks with FIFO property. Delling et al. [2015] provided a loose bound of O(λ(Σ r∈R (l r ) + |T | + |F |)) on the worst-case complexity of RAPTOR using their naive variant (i.e., assuming the local and destination-based pruning are not used). In such a setting, every route is scanned exactly once per round. However, the above expression does not reflect the true complexity of the RAPTOR algorithm because its success comes mainly from the marking and pruning methods. TBTR's pruning methods are more involved, because of which a worst-case complexity result is difficult to derive. Computing optimal partitions for preprocessing on the other hand is known to be NP-Hard [Lengauer, 2012] . In general, research on complexity analysis is sparse and is another open topic for future research. 

Case 1 Case 2 t' Figure 9 : Removing U-turn like movements using Algorithm 5

Algorithm 5 TBTR: Remove trip-transfers resulting in U-turns Input: GTFS, T Output: T 1: for t, i, t , j ∈ T do 2:

if t(i − 1) = t (j + 1) and arr(t, i − 1) ≤ dep(t , j + 1) then 3:

T ← T \ t, i, t , j at any stop. To this end, each trip t is scanned in the decreasing order of its stop sequence. For every trip t, we maintain an arrival time label τ arr (s) for each stop s ∈ S (Lines 1-2). The τ arr (s) variable need not be stored for each trip and can be overwritten. Hence, we skip the trip index in its notation.

Algorithm 6 TBTR: Remove non-optimal trip-transfers Input: GTFS, T Output: T 1: for t ∈ T do 2:

τ arr (s) ← ∞ ∀ s ∈ S 3:

for i = l t , . . . , 2 do 4:

for s ∈ N (t(i)) do

τ arr (s) ← min τ arr (s), arr(t, i) + f (t(i), s)

for t, i, t , j ∈ T do 7:

keep ← false 8:

for stop t (k) with k > j do 9:

for s ∈ N (t (k)) do if not keep then 14:

T ← T \ t, i, t , j

While iterating over the i th stop of trip t, we first improve the arrival time labels of all the stops in the neighborhood of stop t(i) if possible (Lines 3-5). Next, for each trip-transfer t, i, t , j from the stop t(i), we check if taking the transfer improves the arrival time at any stop (Lines 6-12). (The symbols t and i in Line 6 are assumed to be the same as the trip t and stop index i from Lines 1 and 3.) This is done by iterating over all the stops of t from j onwards and by performing a similar update on the τ arr (.) labels. The trip-transfer is discarded if it does not result in an improved label (Lines 13-14). Lehoux and Loiodice [2020] proposed an additional route-based pruning scheme that accelerated trip-transfer computations. However, unlike several other PTR algorithms, their methods were tested on instances with footpath graphs that were not necessarily transitively closed. Table 8 summarizes statistics associated with the above mentioned algorithms on the six test cases. For each algorithm, two metrics are reported-T -time * and T -size. T -time * is the time (in seconds) required to compute and refine T and T -size is the number of trip-transfers in T (in millions) at the end of preprocessing. [Delling et al., 2015] . The list of stops whose labels improved in the previous round is indicated by mlist and is initialized with the source s o . if (r, r(j)) ∈ Q for some index j ∈ {0, . . . , l r } then 9:

replace (r, r(j)) in Q by (r, r(i)) if i < j 10:

else Q ← Q ∪ (r, r(i)) 11:

mlist ← mlist\{s} 12:

for (r, r(i)) ∈ Q do 13:

t ← null 14:

for j = i, . . . , l r do 15:

if t = null and arr(t, j) < min τ * (r(j)), τ * (s d ) then 16:

τ opt (n, r(j)) ← arr(t, j) 17:

τ * (r(j)) ← arr(t, j)

mlist ← mlist ∪ r(j)

if τ opt (n − 1, r(j)) < dep(t, j) then if mlist is empty then 28:

break Delling et al. [2015] also modified RAPTOR to rRAPTOR which handles range queries. Building on rRAPTOR, Algorithm 8 outlines the pseudocode for our version of One-To-Many rRAPTOR. Given a list of destinations to which optimal journeys are sought, we update a stop label only if the new arrival time at the stop is less than the maximum of the labels of stops in the destination list. To do so, in each round, Line 10 initializes τ * max to the maximum of destination labels. Pruning conditions in Lines 22 and 32 are verified as described above. The algorithm also prunes the destination list using Lines 7-9 motivated by the ideas discussed in Section 4.1. Specifically, for every departure time, we initialize dlist to a copy of dlist in Line 5. Next, we find τ * min , the minimum of labels updated in the previous round. If the best arrival time at s d ∈ dlist is less than τ * min , we can safely remove it from dlist since we cannot improve the labels of s d as all updates in the current(later) round(s) will be greater than τ * min (since Pareto-optimality requires that the arrival time should decrease with the number of rounds). C Appendix: Effect of weighting schemes on hypergraph partitioning

In this section, we study the effect of different weighing schemes discussed in Section 3.2. The partitioning algorithm used is KaHyPar and the experimental setup and metrics presented are same as that in Section 5. Tables 9 summarizes the performance metrics of the Sc 1 (unweighted) and Sc 2 scheme. These results are compared with the Sc 3 from Table 5 . Table 9 : HypTBTR preprocessing using KaHyPar with Sc 1 and Sc 2 scheme (scut: cutstop count and % of cutstops, pqueries: profile queries required, F size: % of fill-in trips, F time * : time in seconds to compute F. Values in teal indicate % gain in the multilevel version over its standard counterpart.)

Partitions 4 (2-2) 6 (3-2) 8 (4-2) 10 (5-2) Since the nodes and edges are unweighted in Sc 1 , KaHyPar's objective reduces to minimizing the number of cut hyperedges. Hence, the size of the route cells varies greatly. The size of a route cell is defined as the sum of events associated with stops belonging to the route cell. For example, in Sweden, using standard partitioning, the ratio of the largest route cell size to the smallest varies in the range of 31-823. For Sc 3 and Sc 2 , this ratio varies between 1-5. Recall that HypTBTR (and HypRAPTOR) only scans trips belonging to the source/destination route cells and the fill-in during the query phase. Thus, the greater the differences in the sizes of partitions generated, the larger is the variation in query times. Furthermore, we anticipate the fill-in computation time to increase with the number of partitions (due to increase in cutstops). While Sc 2 and Sc 3 show the expected trend, the time required to compute the fill-in for Sc 1 was found to be erratic. In terms of scut, F size, and F time * , Sc 3 was found to marginally outperform Sc 2 .

D Appendix: Performance of alternate hypergraph partitioning methods

In Section 3.2, three methods for hypergraph partitioning were discussed: KaHyPar, hMETIS, and an IP. Table  10 shows the performance of the HypTBTR algorithm on the Sweden network using hMETIS with the following parameters: UBfactor 15, Nruns 50, Ctype 1, Rtype 1, Vcycle 1, Reconst 0, and dbglvl 0. The metrics presented are same as those discussed in Section 5.

Comparing the number of cutstops and the fill-in size with the corresponding values in Table 5 , we see that KaHyPar performs marginally better than hMETIS. A drawback of the hMETIS implementation (hMETIS Code) used is that the seed could not be fixed and hence it was not possible to replicate results in repeated runs. We did not face this issue with KaHyPar since it allows configuring the seed. Results from partitions generated by the IP formulation are presented in Table 11 . The optimization model was solved using CPLEX. While implementations of KaHyPar (github.com/kahypar) and hMETIS (hMETIS Code) can generate partitions in a few seconds, the IP model could take several hours to converge to the optimal solution, especially for large networks. E.g., for partitioning the Sweden network into two partitions, CPLEX took about 15 minutes to achieve a gap of 0.01%. However, for four partitions, even after four days, the gap reduced to only 1.01%. Because of the longer run times, we only report results for four partitions and the corresponding 2-2 multilevel case. Note that there is a significant drop in the values of scut and F size from the standard to the multilevel version. This could possibly be due to the higher optimality gap for the 4-way standard partitioning. 

Engineering Route Planning Algorithms

Route Planning in Transportation Networks

Finding all Attractive Train Connections by Multicriteria Pareto Search

Efficient Models for Timetable Information in Public Transportation Systems

The Shortest Route through a Network with Time-dependent Internodal Transit Times

An Intermodal Optimum Path Algorithm for Multimodal Networks with Dynamic Arc Travel Times and Switching Delays

A Note on Two Problems in Connexion With Graphs

Timetable Information: Models and Algorithms

An Appraisal of Some Shortest-path Algorithms

Time-dependent Networks as Models to Achieve Fast Exact Timetable Queries

Car or Public Transport-Two Worlds

Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns

Intriguingly Simple and Fast Transit Routing

Round-Based Public Transit Routing

Trip-based Public Transit Routing

The Fastest Path Through a Network with Random Time-Dependent Travel Times

Transit Service and Path Choice Models in Stochastic and Time-Dependent Networks

Implicit Enumeration of Hyperpaths in a Logit Model for Transit Networks

Trip-based Path Algorithms using the Transit Network Hierarchy

Optimal Transit Routing with Partial Online Information

Finding Optimal Hyperpaths in Large Transit Networks with Realistic Headway Distributions

Adaptive Transit Routing in Stochastic Time-dependent Networks

An Online Shortest-path Algorithm for Reliable Routing in Schedule-based Transit Networks Considering Transfer Failure Probability

Connection Scan Accelerated

Scalable Transfer Patterns

Faster Transit Routing by Hyper Partitioning

Algorithm Engineering for Adaptive Route Planning

On the Complexity of Public Transit Profile Queries

An Efficient Solution for One-To-Many Multi-modal Journey Planning

Customizable Point-Of-Interest Queries in Road Networks

Computing Isochrones in Multi-modal, Schedule-based Transport Networks

Fast Exact Computation of Isochrones in Road Networks

Computing Many-To-Many Shortest-paths Using Highway Hierarchies

PHAST: Hardware-Accelerated Shortest Path Trees

Frequency-Based Search for Public Transit

Fast and Exact Public Transit Routing with Restricted Pareto Sets

Trip-based Public Transit Routing Using Condensed Search Trees

Multicriteria Trip-based Public Transit Routing

Integrating ULTRA and Trip-based Routing

:12, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik

Unlimited Transfers for Multi-Modal Route Planning: An Efficient Solution

High-Quality Hypergraph Partitioning

Hypergraph partitioning techniques. Dynamics of Continuous Discrete and Impulsive Systems Series A

METIS -Family of Multilevel Partitioning Algorithms

PaToH (Partitioning Tool for Hypergraphs)

Parallel Hypergraph Partitioning for Scientific Computing

A Linear-time Heuristic for Improving Network Partitions

Using Goal Directed Techniques for Journey Planning With Multi-criteria Range Queries in Public Transit

Fastest Paths in Time-dependent Networks for Intelligent Vehicle-highway Systems Application

Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Runtime

Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms

Acknowledgments. The authors would like to thank the Managing Director of BMTC for facilitating data sharing. Special thanks to Mr. Dibya Ranjan Jena, Consultant (BMTC) for helping us understand BMTC's operations, GPS, and ticketing data. The authors also appreciate Hemant Gehlot's comments on an earlier draft of this article. The first author would also like to thank John Varghese George, Saumya Bhatnagar, and Nipun Choubey for useful discussions on programming and version control.

A Appendix: Preprocessing phase of the TBTR algorithmThe TBTR algorithm by Witt [2015] has a two-stage preprocessing phase. The first stage (Algorithm 4) involves creation of a trip-transfers set T . This set may contain a large collection of trip-transfers, most of which may never be part of optimal journeys for any source-destination pair. Hence, the second stage (Algorithms 5 and 6) aims to reduce T by removing trip-transfers that are guaranteed to never be a part of an optimal journey. These algorithms are reviewed here to keep this paper self-contained. More details including an explanation of the correctness of the algorithms can be found in the original paper.Algorithm 4: This algorithm generates an initial set of trip-transfers T from the GTFS data by iterating over all stops starting from the second stop of each trip. For each such stop, a stop s in its neighborhood is picked (Line 4). Next, for each route r passing through s (with s not being the last stop on r), we find the earliest trip t on r that the passenger can board, i.e., arr(t, i) + f (t(i), s) ≤ arr(t , j), where i and j are the i th and j th stops on trips t and t , respectively. If such a trip exists, the corresponding trip-transfer will be feasible if both the trips are on different routes, i.e., r = route(t). Furthermore, transfers between trips on the same route are needed only if t ≺ t or if j comes before i (j < i). To understand this condition, consider the example in Figure 8 . Note that the stop IDs of the nodes are different in the subfigures. For Case 1, let t and t be two trips on the green route such that t ≺ t. The arrival times associated with the two trips are shown in the table. Also let (s 2 , s 5 ) ∈ F with f (s 2 , s 5 ) = 10 minutes. Thus, for a bicriterion query with τ = 0805 and s o and s d as shown, the trip-transfer t, 2, t , 5 is a part of the optimal journey. Case 2 illustrates the j < i scenario, i.e., when the passenger transfers to an earlier stop on the same route. Transfers to later trips on the same route or later stops on the same trip are not needed. if r = route(t) then 8:else if t ≺ t or j < i then 10:T ← T ∪ { t, i, t , j } Algorithm 5: This algorithm uses the GTFS data and the output from Algorithm 4 to reduce the size of the trip-transfer set T . The objective here is to remove trip-transfers from T that result in a U-turn like movement. For illustration see Case 1 of Figure 9 . The example shown considers two trips t and t for which t(i) = s 1 , t (j) = s 2 , and t(i − 1) = t (j + 1) = s 3 . Further, let (s 1 , s 2 ) ∈ F be such that t, i, t , j ∈ T . According to Line 2 of the algorithm, if arr(t, i − 1) ≤ dep(t , j + 1), trip-transfer t, i, t , j is never part of an optimal journey because a passenger traveling on t can switch to t at stop s 3 . To understand the need for condition t(i − 1) = t(j + 1) while checking for U-turns, consider Case 2. Here, the trip-transfer t, i, t , j may be part of an optimal journey between s o and s d and hence, cannot be removed.Algorithm 6: The set T can be further reduced to only contain trip-transfers that result in improved arrival times if (r, r(j)) ∈ Q for some index j ∈ {0, . . . , l r } then 15:if i < j then 16:replace (r, r(j)) in Q by (r, r(i)) 17:else Q ← Q ∪ (r, r(i)) if t = null and arr(t, j) < min τ * (r(j)), τ * max then 23:τ opt (n, r(j)) ← arr(t, j)

τ * (r(j)) ← arr(t, j)

mlist ← mlist ∪ r(j)

if r(j) ∈ dlist then 27:τ * max ← max s∈dlist τ * (s)

if τ opt (n − 1, r(j)) < dep(t, j) then 29:t ← earliest trip on r from stop r(j)

for s ∈ mlist do 31:for s ∈ N (s) do 32:if τ opt (n, s) + f (s, s ) < min τ * (s ), τ * max then 33:τ opt (n, s ) ← τ opt (n, s) + f (s, s ) if mlist is empty then 39:break