From Point A to Point B: Pathfinding for Cars and Public Transport
Jan 24, 2025
Kateryna Bilyk, Andrii Rohovyi
What is Pathfinding?
Pathfinding is a fundamental concept in computer science that involves determining the most efficient route from one point to another. It is widely used across various applications - from digital maps and navigation systems to the intricate worlds of video games. But if we look globally, it can affect everything: How quickly can medicine or blood be delivered to a hospital? How are evacuation exits in buildings planned? How can we optimize package transfers across cities? How can a vessel deliver goods without encountering a storm?
Pathfinding affects aspects of daily life we don’t always notice. Algorithms adapt to different types of networks—whether static networks like walking graph or complex, dynamic networks like public transit systems with schedules and connections. At its core, pathfinding focuses on optimizing the wayfinding process, whether that means finding the shortest route, the fastest one, or the one that avoids certain obstacles.
Various algorithms, from basic approaches like Dijkstra’s or A*, to advanced ones like the Contraction Hierarchy, address unique challenges depending on network size, time constraints, and real-time adjustments.
In this article, we’ll explore some of the most advanced pathfinding techniques and how they’re transforming modern logistics, transportation, and beyond.
Route-Network and Transit-Network - What is the difference?
What Is It: In pathfinding, various types of problems arise depending on the context and the network being navigated. Two common examples are Route Networks and Transit Networks, which can both be represented as directed graphs but differ significantly in how their nodes and arcs are defined, as well as the type of information they require.
What Is the Difference: To understand the global difference better, we can use the analogy from Hanna Bast's article [1]: Route-Network is akin to driving a car, where the route is generally fixed and independent of time factors. Transit-Network is more like using public transportation, where you must plan your trip according to schedules, transfers, and waiting times. This distinction dramatically affects how routing algorithms are designed and applied in these two contexts.
Route-Network is more straightforward and static, much like driving a car. You can plan a direct route from one point to another, and the pathfinding algorithms simply need to calculate the shortest or fastest way between two locations on the road. There are no complex schedules or transfers involved. It's about finding the best possible route in a relatively simple, fixed network. These networks are also hierarchical: highways handle long trips, while local streets manage shorter connections, helping algorithms focus on the most important roads.
Transit-Network, on the other hand, is more like navigating a bus or train system. In these networks, the challenge is not only to find the shortest distance but to factor in time schedules, waiting periods, and transfers between different transport modes. A node in the graph doesn’t just represent a physical location but a specific event (such as the arrival or departure of a train). This makes transit networks far more complex, as the pathfinding algorithm must consider dynamic elements like transfer times and timing constraints in addition to just the spatial distance.
The visual below highlights this difference: on the left, a road network of Manhattan where the shortest path is calculated based on distance, and on the right, a transit network of Zurich, where schedules and transfers are key to finding the optimal route [1]:
This difference stems from the underlying structure: road networks rely on uniform edges with straightforward metrics like distance or time, whereas transit networks incorporate hierarchies, transfer dependencies, and time-sensitive schedules, adding complexity to route optimization [1].
Basic Algorithms
Djikstra
What Is It: Dijkstra’s Algorithm is a classic method for finding the shortest path between nodes in a graph. It prioritizes nodes with the smallest cumulative distance, ensuring efficient and accurate route calculations. Widely used in map services and network optimization, it also serves as the foundation for many advanced algorithms.
Why It’s Effective:
Efficient Exploration: It prioritizes the nearest unvisited node, minimizing redundant checks.
Versatility: Works for both directed (one-way streets) and undirected graphs (two-way streets).
Adaptable: Can be modified for time-dependent or weighted graphs.
Reliability: Provides guaranteed shortest paths for graphs with non-negative weights.
Simplicity: Easy to implement and forms the basis for more complex pathfinding methods
How It Works: Imagine you have five locations - A,B,C,D,E (nodes) connected by paths (edges) with different travel times (weights). We want to find the shortest path from A to E.
Initialization: Assign a distance of 0 to the starting node (A) and ∞ to all others.
Start at A
A → B: Distance = 4 → B = 4
A → C: Distance = 2 → C = 2
New distances: A = 0, B = 4, C = 2, D = ∞, E = ∞
Next vertex: The next vertex to visit is always the one with the smallest tentative distance from the starting point. This is because we are seeking the shortest path and want to expand the search from the closest node. In this case it is C (distance = 2)
Move to C
C → D: Distance = 8 → D = 10
C → E: Distance = 10 → E = 12
New distances: A = 0, B = 4, C = 2, D = 10, E = 12
Next vertex: B (distance = 4)
Move to B
B → D: Distance = 5 → D = 9
New distances: A = 0, B = 4, C = 2, D = 9, E = 12
Next vertex: D (distance = 9)
Move to D
D → E: Distance = 2 → E = 11
New distances: A = 0, B = 4, C = 2, D = 9, E = 11
Next vertex: E (distance = 11)
Output: The shortest path from A to E is 11 via the sequence A → C → B → D → E.
Limitations: Dijkstra’s Algorithm recalculates paths for all nodes, making it inefficient for "one-to-one" queries in large graphs.
Bidirectional Search
What Is It: Bidirectional Search improves upon Dijkstra’s Algorithm by performing two simultaneous searches: one from the source node and another from the target node. These searches expand toward the middle and meet at a common point, drastically reducing the search space.
Why It’s Effective:
Faster Execution: By halving the search space, it reduces computational time, making it ideal for large graphs.
Optimized for Fixed Targets: Works efficiently when the start and end points are predetermined.
How It Works:
Start Two Searches: Begin one search from the source node and another from the target node.
Expand Toward the Middle: Each search explores neighbors and updates tentative distances.
Meet in the Middle: When the two searches overlap, the shortest path is determined by combining the forward and backward paths.
Limitations: Ineffective for dynamic targets or scenarios where the destination is unknown and requires additional memory to track two search fronts simultaneously.
A* Algorithm
What Is It: The A* Algorithm is a pathfinding algorithm that improves upon Dijkstra’s Algorithm by using heuristics to estimate how close a node is to the target. This allows A* to prioritize the most promising paths, reducing unnecessary exploration and making the search more efficient.
Why It’s Effective:
Guided by Heuristics: A* uses an estimate of the remaining distance to guide its search, narrowing the focus to paths more likely to lead to the destination.
Balances Accuracy and Speed: Combines the thoroughness of Dijkstra’s Algorithm with the efficiency of heuristic-based guidance.
Flexible and Versatile: Adaptable to various scenarios depending on the heuristic used, such as straight-line distance for maps or simple grid-based navigation.
How It Works:
Start the Search:
Begin at the source node.
Use a list to decide which nodes to check next, prioritizing those estimated to be closer to the target.
Explore Paths:
Check the nearest node and calculate potential paths to its neighbors.
Add these neighbors to the queue if they seem promising.
Use a Heuristic: A* estimates how close each node is to the target, focusing on paths that move toward the destination.
Find the Solution: Stop when the target node is reached, returning the shortest path.
Limitations: The algorithm’s performance heavily depends on choosing an appropriate heuristic. A poorly chosen heuristic can make the search slower or less effective. A* keeps track of all explored nodes, which can lead to high memory consumption for large graphs.
Comparison of Algorithms
This illustration from the article [2] demonstrates how the search space decreases when finding the shortest path using different algorithms. The left figure shows Dijkstra's algorithm, which explores the entire search space radiating outward from the source node sss. The middle figure illustrates bidirectional search, which reduces the search space by simultaneously exploring from s and t and meeting at an intermediate node x. The right figure represents the A* algorithm, which focuses the search towards the target node t by utilizing a heuristic, significantly narrowing the area that needs to be analyzed.
Route-Network
Algorithms
Using Hierarchy in Road Networks
In most road networks, roads are naturally divided into hierarchical categories based on speed and importance:
“White” roads – Slower roads, usually within cities or villages.
“Yellow” roads – Intermediate roads connecting local areas.
“Orange” roads – Major arterial roads or highways designed for fast travel.
Illustration from [3]
Key Observations:
Optimal routes often start and end with “white” roads.
As the distance from the source increases, “yellow” roads and then “orange” roads dominate the journey to ensure faster travel.
A simple heuristic prioritizes “yellow” and “orange” roads as the journey progresses.[4]
However, this heuristic approach isn’t always precise. Complex networks may include shorter paths that deviate from the strict hierarchy. To overcome these limitations, advanced algorithms like Contraction Hierarchies (CH) dynamically prioritize connections based on road importance..
Contraction Hierarchy
What It Is: Contraction Hierarchies is a pathfinding algorithm that speeds up shortest-path queries by simplifying the graph. It removes less important nodes and replaces them with shortcuts that preserve the shortest paths. During preprocessing, CH orders the nodes by "importance" (heuristically determined) and contracts them from least to most important [3]. This preprocessing reduces the graph's complexity, enabling faster queries, especially in large networks like road maps.
Why It`s Effective:
Exploits Hierarchy: Prioritizes key connections in the graph, minimizing unnecessary exploration.
Speeds Up Queries: Shortcuts drastically reduce the search space.
Handles Large Graphs: Scales well to networks with millions of nodes.
Versatile: Suitable for alternative routes, time-dependent navigation, and multi-route queries.[4].
How It Works:
Contraction Phase:
Nodes are ranked by importance (e.g., connectivity, centrality).
Less important nodes are contracted by removing them and adding shortcuts between their neighbors to preserve shortest paths.
Example: If Node B connects Node A and Node C, and the shortest path A → B → C is known, contracting Node B adds a direct shortcut A → C.
Preprocessing Phase:
Nodes are contracted in order of increasing importance.
Shortcuts and original edges are directed from less important to more important nodes, aligning with the graph’s hierarchy.
Query Phase:
A bidirectional search starts from the source and target nodes, exploring only higher-ranked nodes.
The searches meet at a shared node, and the shortest path is reconstructed using precomputed shortcuts.
For a practical and visual understanding of Contraction Hierarchy, visit this guide. This guide provides an intuitive step-by-step explanation of node contraction, shortcut creation, and query execution with clear illustrations.
Hub Labeling
What It Is: Labeling algorithms preprocess a graph to allow efficient shortest-path queries. Each vertex is assigned a label containing critical information about distances to other vertices, enabling fast lookups without traversing the entire graph. Hub Labeling assigns each vertex a set of hubs - other vertices frequently encountered in shortest paths. The labels store distances to these hubs, enabling rapid query processing. An essential property of HL is that the labels of any two vertices must intersect in at least one hub. This ensures that the hub lies on the shortest path between the two vertices.
Why It`s Effective:
Fast Queries: Queries involve comparing vertex labels to find common hubs, avoiding graph traversal.
Efficient Memory Usage: Labels are compact, storing only essential information.
Optimized Storage: Techniques like Hub Label Compression (HLC) reduce space usage while maintaining performance.
How It Works:
Preprocessing Phase:
Each vertex is assigned a label containing its hubs and their distances.
Hubs are selected based on their importance in the graph, often determined using Contraction Hierarchy or Top-Down Label Generation [5].
Query Phase:
Queries operate entirely on the vertex labels. After the preprocessing phase, the actual graph is no longer needed for queries.
For any two vertices, their labels are compared to identify shared hubs.
The shortest path is calculated using the distances stored in the labels.
For directed graphs, labels are typically split into two parts:
Forward Label: Contains distances from the vertex to the hubs.
Backward Label: Contains distances from the hubs to the vertex. [3]
Transit Node Routing
What It Is: Transit Node Routing (TNR) speeds up shortest-path queries by focusing on a small set of important vertices called transit nodes. These nodes represent key global connections, enabling rapid pathfinding for long-distance journeys while relying on fallback algorithms for local queries.
Why It`s Effective:
Fast Global Queries: Precomputed distances between transit nodes allow quick routing.
Scalable: Can handle large-scale networks efficiently by adding hierarchical layers of transit nodes.
Fallback for Local Queries: Uses algorithms like CH for paths not involving transit nodes.
How It Works:
Preprocessing Phase:
Transit Node Selection: Important nodes (e.g., highways intersections) are selected as transit nodes (contract until k nodes are left) [3].
Distance Computation: Pairwise distances between all transit nodes are precomputed.
Access Nodes: For each non-transit node, the nearest transit nodes are identified, and their distances are stored.
Query Phase:
Global Queries: For long-distance routes, the shortest path is found by combining:
The path from the source to its nearest transit node.
The precomputed path between the transit nodes.
The path from the transit node to the destination.
Local Queries: If no transit nodes are involved, fallback algorithms (e.g., CH) compute the shortest path..
Optimization:
Hierarchical Layers: Adding layers of transit nodes improves global query performance.
Locality Filters: Determine whether a query involves transit nodes to ensure efficiency.
Comparison of Algorithms
This is a table from “Route Planning in Transportation Networks” [4]. Look at Dijkstra, Bidir. Dijkstra, CH(Contraction Hierarchy), HL(Hub Labeling), we can compare these algorithms in terms of space usage, preprocessing time, the number of scanned nodes, and execution time:
Performance of various speedup techniques on Western Europe [4]:
Transit-Network
Types of Networks
Planning journeys in public transit systems requires creating models that simplify how timetables are handled. Here are the three main approaches [3]:
Time-Expanded Network
Imagine unrolling the timetable like a timeline. Each moment in the schedule becomes a point on this timeline, with connections showing how trips and transfers happen over time.
How It Works:
Every departure or arrival is a dot on the timeline (a vertex).
Arrows (arcs) connect these dots, showing trips or waiting periods.
For example, a bus leaving at 8:00 and arriving at 8:30 would have an arrow linking these times.
Good For:
Clearly showing every step of a trip, including transfers or waiting times.
Drawback:
The timeline can get really long and detailed, especially for large networks.
Time-Dependent Network
Think of this as a simplified map, where each stop is a point, and lines connect stops if a route exists. Instead of tracking every schedule, it remembers when and how often trips happen between stops.
How It Works:
Stops are dots, and routes are lines between them.
Each line knows how long a trip takes and when it starts.
For example, a bus route might say, “Trips every 10 minutes, travel time 20 minutes.”
Good For:
Keeping things compact, especially in systems with many stops.
Drawback:
Needs careful tracking of time so trips align with schedules.
A node A in a transport network, with outgoing edges to B, C, and D. From [9].
Frequency-Based Network
Imagine summarizing a bus route like this: “Buses every 5 minutes during rush hour and every 10 minutes the rest of the day.” Instead of listing every trip, it groups similar ones to save space. Like a time-dependent model, but with frequency labels.
How It Works:
Stops are points, and connections summarize schedules using patterns (like “every 10 minutes from 9:00 to 18:00”).
It focuses on capturing the regularity of trips, skipping unnecessary details.
Good For:
Simplifying schedules that repeat often, like in city buses or metro systems.
Drawback:
Not ideal for systems with irregular or unpredictable schedules.
Historically, transit network modeling evolved from graph-based approaches to more simplified models designed to handle complex timetables. Initially, models like the Time-Expanded Network represented every event as a distinct point on a timeline, with connections between these points reflecting trips and waiting times. This model, while accurate, often became too large and detailed for complex networks. Over time, this evolved into the Time-Dependent Network, where stops were simplified as points, and routes were represented as lines with time information attached to each route. This helped reduce the complexity but still required careful time management. The latest evolution is the Frequency-Based Network, which abstracts away specific times and instead uses patterns to describe regular services, making it ideal for frequent routes like those in city buses or metro systems. These developments illustrate a shift towards simplifying the representation of transit networks, moving away from intricate graph-based structures to more compact models better suited for large-scale scheduling.
As transit networks moved from graph-based models to more compact, simplified representations, algorithms like CSA, RAPTOR, Transfer Patterns, and Trip-Based Routing emerged to better manage the complexities of timetable-based systems and large-scale, real-time routing.
Algorithms
Сonnection Scan Algorithm
What It Is: The Connection Scan Algorithm (CSA) It is a non-graph approach that is specialized for timetable systems. It operates on a pre-sorted list of connections, such as bus or train schedules, to determine the earliest arrival time or the optimal journey between two points. It requires minimal preprocessing efforts, only needing to sort all connections.
Why It`s Effective:
Simplicity: It processes the transit data sequentially, avoiding complex operations or data structures. It is easy to implement from scratch in any programming language.
Speed: By scanning connections in chronological order, it achieves excellent performance, especially on large transit networks.
Scalability: It is highly adaptable to additional constraints, such as limiting transfers or time windows.
How It Works:
Input:
Sorted Connections: A list of all transit connections (departure stop, departure time, arrival station, arrival time, and trip) [6], sorted by departure time.
Source and Target: The starting stop (source) and destination stop (target).
Departure Time: The time you wish to begin your journey.
Initialization:
Set the earliest arrival time for all stops to infinity.
Set the earliest arrival time for the source stop to the desired departure time [7].
Scan Connections:
Process each connection in the list (from earliest to latest departure time).
For each connection, check if you can catch it (i.e., if you’ve reached the departure station by the connection’s departure time).
If you can catch it, update the earliest arrival time at the connection’s arrival station.
RAPTOR
What Are Pareto Sets and Multi-Criteria Optimization?
Multi-criteria optimization is a method used to find solutions that balance multiple conflicting objectives, such as cost, time, and efficiency. Instead of finding a single optimal solution, it identifies a set of Pareto-optimal solutions, where improving one criterion (e.g., reducing time) leads to worsening another (e.g., increasing transfers). This approach is valuable in fields like transportation, logistics, and decision-making, where different criteria must be considered simultaneously:
What Are Pareto Sets? Pareto sets are collections of optimal routes that balance trade-offs between two or more criteria, such as travel time and number of transfers.
Pareto-optimality means that no route can be improved in one criterion (e.g., reducing travel time) without worsening another criterion (e.g., increasing the number of transfers).
Example:
Route A: 30 minutes with 2 transfers.
Route B: 40 minutes with 1 transfer.
Both routes can be Pareto-optimal because improving one aspect (e.g., reducing time) would degrade another aspect (e.g., increasing transfers).
The paths highlighted in green are Pareto-optimal, while all others are not:
Why Pareto Sets Matter? Pareto sets provide users with flexibility to choose routes based on what they value most, such as speed or convenience. This is particularly useful in transportation systems where different people have different priorities. For example:
A business traveler may prefer the fastest route, even if it involves more transfers.
A parent with children may prefer fewer transfers, even if the journey takes longer.
Thus, Pareto sets offer multiple optimal journey options, each catering to different user preferences.
What It Is: RAPTOR (RoundbAsed Public Transit Optimized Router) is a fast and effective algorithm that considers multiple factors, such as travel time, number of transfers, and user preferences, to provide a range of optimal journey options. Unlike traditional graph-based algorithms, RAPTOR uses a round-based approach to progressively refine results, making it ideal for public transit networks.
Why It’s Effective:
Efficient Handling of Multi-Criteria Optimization: If the number of transports is among the criteria for selection, RAPTOR dynamically updates Pareto-optimal paths during execution.
Transfer-based Design: The round-based approach aligns naturally with the structure of transit systems, where transfers are a critical factor.
Scalability for Large Networks: RAPTOR processes only the necessary routes in each round, making it efficient even for large or complex transit systems.
Possible to parallel: RAPTOR can easily be parallel between different cores.
Adaptability to User Needs:
Handles additional constraints like deadlines, specific stops, or exclusions.
Provides a range of options: fastest routes, fewer transfers, or balanced trade-offs.
How It Works:
Input:
Transit Timetable: A schedule of stops, routes, and timings.
Source and Target: The starting and destination stops for the journey.
Departure Time: When the user plans to begin their trip.
Round-based Exploration:
RAPTOR operates in rounds, with each round representing journeys that include one more transfer than the previous round [7].
It starts from the source stop and identifies all reachable stops via direct routes (0 transfers).
Updating Earliest Arrival Times:
During each round, RAPTOR processes the routes accessible from stops reached in the previous round.
For each connection, it updates the earliest possible arrival time at the destination stop based on the route's schedule.
Stops reached in the current round are added to the next round for further exploration.
Dynamic Multi-Criteria Optimization Using Pareto Sets:
RAPTOR dynamically updates Pareto-optimal sets of paths for each stop during execution.
These sets ensure that only the best routes for the given criteria (e.g., travel time and transfers) are kept.
For example:
Route A might be faster but involve more transfers.
Route B might take longer but require fewer transfers.
Both are stored as part of the Pareto set because they satisfy different user priorities.
Termination: The algorithm stops when no further improvements can be made or when a maximum number of transfers is reached.
Start stop ps and end stop pt are marked in red. Routes:
r1 (blue): First route scanned in round 1.
r2 (green): Second route, added in round 2.
r3 (orange): Another route from round 2.
r4 (red): Final route completing the path to pt.
Trip-Based-routing
What It Is: What happens if we add the Dijkstra strategy to RAPTOR? Trip-Based Routing is an algorithm for public transit systems that evaluates entire trips (e.g., bus routes or train journeys) rather than individual stops. By focusing on trips as units, it simplifies route planning and enhances efficiency for complex transit networks.
Why It’s Effective:
Works with entire trips, reducing the complexity of analyzing schedules.
Stores relationships between trips in advance, enabling fast queries.
Naturally aligns with fixed-schedule public transit systems.
Efficiently handles dense urban networks by focusing on relevant trips.
How It Works:
Input: Transit schedules, including trips, stops, and departure/arrival times.
Preprocessing: Analyzes the schedules and precomputes the connections between trips and transfer points. This involves identifying which trips can be connected through specific stops and how much time is required for each transfer. This step helps avoid redundant calculations when searching for a route.
Query Phase: The algorithm first filters trips that align with the user's specified departure time and identifies potential transfer points. It then examines all possible routes by linking trips through these transfer points, evaluating each route based on factors such as total travel time or other user preferences.
Transfer patterns
What It Is: Transfer Patterns is an algorithm for public transit routing that precomputes sequences of transfers between station pairs. It simplifies route queries by leveraging precomputed data, reducing the need for live calculations. Transfer Patterns have been used in systems like Google Maps since 2010 [3].
Why It’s Effective:
Precomputed Time Coverage: Transfer patterns are calculated in advance for all departure times and across all permissible dates in the timetable (e.g., weekdays, weekends, or holidays). This ensures the algorithm is ready for any query, no matter the time or date.
Efficient Querying: Queries focus on precomputed transfer patterns, reducing unnecessary exploration and speeding up calculations.
Compact Representation: Instead of storing schedules for every possible trip, transfer patterns summarize the key decisions for routing, greatly reducing storage requirements.
Scalable for Large Networks: Techniques like clustering (e.g., dividing cities or regions into smaller groups) make this method work even for continent-sized networks.
How It Works:
Precomputing Transfer Patterns: To prepare the network for fast routing, Transfer Patterns are precomputed for all pairs of stations. This involves calculating optimal paths for all departure times and across all timetable variations, such as morning peaks, evenings, and weekends for whole year.
For example, between Lviv and Dnipro, the algorithm might compute two primary paths:
Path 1: A direct train (Lviv → Dnipro) available at specific times.
Path 2: A transfer via Kyiv (Lviv → Kyiv → Dnipro) for other times.
Each pattern is stored along with its conditions of optimality, such as departure times.
Building the Query Graph: When a user requests a route between two stations (e.g., A to B), the system constructs a query graph using only the relevant transfer patterns. The graph contains:
Transit arcs: Represent precomputed transfer sequences.
Walking arcs: Account for precomputed walking distances (e.g., between platforms).
The algorithm then runs a time-dependent Dijkstra search on this graph, factoring in the user’s specific departure time..
Managing Complexity with Clustering:
To handle large-scale networks, the system divides the network into smaller clusters, such as cities or regions.
Within Clusters: Transfer Patterns are computed for local trips inside each cluster.
Between Clusters: Transfer Patterns are calculated for trips connecting clusters via boundary stops (e.g., major train stations).
This clustering significantly reduces computational complexity by limiting the analysis to essential connections.
Example: In Germany’s transit network, only 4.32% of stops (10,886 of 251,763) are boundary stops. These serve as key points for inter-cluster travel, dramatically reducing the number of connections to consider [8].
The public transit network of Germany (dots and lines), split into clusters (shown in various colors). Of all 251,763 stops, only 10,886 (4.32%) are boundary stops, highlighted as red boxes.
Comparison of Algorithms
CSA best use case: urban or metropolitan transit networks, where the network size is small to medium, and travel time is the primary optimization criterion. Perfect choice for stop-to-stop queries. Less suited for large networks due to its exhaustive scan approach.
RAPTOR best use case: national transit networks or moderately large regional systems, particularly when minimizing transfers is important. It works perfectly for multi-criteria queries. Its simplicity makes it adaptable to real-time changes, such as delays.
TB-routing best use case: national or large regional transit networks where preprocessing can reduce unnecessary computations, making it more efficient for queries within moderately sized networks.
Transfer patterns best use case: large-scale and cross-continental networks where extremely fast query times are required, and preprocessing for transfer patterns is feasible. Ideal for static scenarios.
Other approaches for Transit network
Labeling algorithms for transit networks, such as PTL (hub labeling on time-expanded graphs) and TTL (station-based labeling), enable extremely fast query times—often in the microsecond range. However, PTL requires massive storage (e.g., 26 GB for London), while TTL is more space-efficient (~1 GB) but limited to travel-time optimization and lacks adaptability for delays or Pareto-optimal solutions [10]. The Transfer Connection Database (TCD) precomputes a compact database of first transfer connections for all origin-destination pairs, enabling earliest arrival time optimization. By employing compression and clustering techniques, TCD achieves up to 1000x speedup over CSA while preserving exact transfer costs.
ULTRA: A Mix of Two Worlds
ULTRA bridges the gap between route and transit networks, combining the efficiency of road-based navigation with the complexity of transit systems. By integrating multi-modal transport options like walking, cycling, and public transit, it offers seamless route planning that balances speed, convenience, and transfers. This makes ULTRA versatile for both urban transit systems and regional or intercity networks.
ULTRA (UnLimited TRAnsfers for Multi-Modal Route Planning)
What It Is: ULTRA extends transit routing to include secondary modes like walking, cycling, or scooters. It computes Pareto-optimal journeys by balancing earliest arrival time and number of transfers.
Why It`s Effective:
Integration of Multi-Modal Transport: Combines public transit with secondary modes for comprehensive journey planning.
Efficient Preprocessing: Uses smart techniques to simplify the network and focus on the best routes. This helps reduce the amount of data the system needs to process, making it faster and more efficient when finding routes for users.
Flexible Integration: Works seamlessly with algorithms like CSA, RAPTOR, or Trip-Based for real-time routing.
Scalable for Urban Networks: Preprocessing reduces transfer graph size, ensuring fast query responses.
How It Works:
Input Data: Includes information about public transit stops, schedules, and routes. Incorporates connections for secondary modes like walking or cycling.
Preprocessing Phase: The system simplifies the network by focusing only on Pareto-optimal routes - journeys that balance travel time and the number of transfers. These routes are precomputed to ensure efficient use of public transit and secondary modes.
Query Phase: When a user searches for a route, ULTRA leverages precomputed data to quickly evaluate and present the best route options. The system ranks these based on user-defined criteria, such as minimizing travel time or transfers. This ensures a user-centric approach that adapts to different travel preferences and needs.
Сitation
Hannah Bast: “Car or Public Transport - Two Worlds”. Access: https://ad-publications.cs.uni-freiburg.de/EfficientAlgorithms_Car_Bast_2009.pdf
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner and Renato F. Werneck: “Route Planning in Transportation Networks”. Access: https://arxiv.org/pdf/1504.05140
“A Research Agenda for Geographic Information Science at the United States Geological Survey”. Access: https://www.researchgate.net/figure/Example-map-display-with-detailed-hierarchy-of-roads-shown-in-different-widths-and-a_fig4_270591287
ICAPS 2018: Hannah Bast on "Route Planning in Large Transportation Networks: Surprisingly Hard ...". Access: https://www.youtube.com/watch?v=B3wKfJAVRkg
Hub Labels in Databases Shortest Paths for the Masses, Andrew Goldberg, Microsoft Research: https://www.youtube.com/watch?v=OK40Gfgdyz8
Julian Dibbelt, Thomas Pajor, Ben Strasser, Dorothea Wagner: “Connection Scan Algorithm”. Access: https://arxiv.org/pdf/1703.05997
“14 Jonas Sauer - Journey planning in public transit networks”. Access: https://www.youtube.com/watch?v=AdArDN4E6Hg
Arno Eigenwillig: “An Update on fast Transit Routing with Transfer Patterns”. Access: https://research.google/blog/an-update-on-fast-transit-routing-with-transfer-patterns/
Andrii Rohovyi, Peter J. Stuckey, Toby Walsh: “Timetable Nodes for Public Transport Network”. Access: https://arxiv.org/abs/2410.15715
Hannah Bast, Matthias Hertel, Sabine Storandt: “Scalable Transfer Patterns”. Access: https://ad-publications.cs.uni-freiburg.de/ALENEX_scalable_tp_BHS_2016.pdf
Additional Information
“Hub Labels: Theory and Practice”. Access: https://renatowerneck.wordpress.com/wp-content/uploads/2016/06/dgsw14-hl-approx.pdf
“Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns”. Access: ‘https://www.researchgate.net/publication/220770569_Fast_Routing_in_Very_Large_Public_Transportation_Networks_Using_Transfer_Patterns
Sascha Witt: “Trip-Based Public Transit Routing”. Access: https://arxiv.org/pdf/1504.07149
Daniel Delling, Thomas Pajor, Renato F. Werneck: “Round-Based Public Transit Routing”. Access: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/01/raptor_alenex.pdf
