Route Planning in Transportation Networks

Scope

• The survey broadens prior road-network coverage to include schedule-based public transportation and multimodal scenarios combining scheduled and unrestricted modes.It covers research published through January 2015.Source: §1 · pp. 2–3

Road networks

• For continent-sized road networks, new methods answer queries in a few hundred nanoseconds, incorporate current traffic in under a second, and support many applications efficiently.These advances motivate evaluating methods across real transportation applications rather than query speed alone.Source: §1 · p. 2
• Road-routing algorithms offer different trade-offs in query time, preprocessing effort, space usage, and robustness, with current state-of-the-art methods finding provably exact solutions.There is no single best method because evaluation depends on the relevant measures.Source: §1 · p. 2

Public transportation

• Public-transit journey planning is harder because it is time-dependent and multicriteria, while weaker preprocessing makes approximations sometimes necessary despite millisecond-scale journeys at very large scale.The relevant systems include buses, trains, and trams.Source: §1 · p. 2

Multimodal and practical impact

• Multimodal planning is significantly harder than its component problems, although reasonable solutions remain possible for combinations of scheduled transport with walking and cycling.The survey emphasizes real-life impact: several discussed algorithms entered production systems serving millions of users daily.Source: §1 · p. 2

Problem formulations

• Shortest-path formulations include point-to-point, one-to-all, all-to-one, many-to-many, and all-pairs distance queries.Distances are defined as minimum sums of nonnegative arc lengths between specified sources and targets.Source: §2 · p. 3

Path representations

• Shortest-path trees compactly represent one-to-all or all-to-one shortest paths, including the path from a root to every vertex.Out-shortest path trees represent paths from the root, while in-shortest path trees represent paths to the root.Source: §2 · p. 3

Scope and model

• The section focuses on point-to-point shortest paths under a RAM-based server model, allowing lengthy preprocessing but requiring queries fast enough for interactive applications.Locality, cache misses, multicore execution, and machine-tailored implementations can affect performance.Source: §2 · p. 3

Organization

• The section first presents basic techniques and then preprocessing-based methods, described generally while using road networks as the motivating application.Precise road-network performance results are deferred to Section 3.Source: §2 · p. 3

Dijkstra’s algorithm

• Dijkstra’s algorithm maintains tentative distances in a priority queue, relaxes incident arcs, and permanently settles each scanned vertex with its correct distance [108].For point-to-point queries, it can stop when it scans the target; the scanned vertices form its search space.Source: §2.1 · pp. 3–4
• Dijkstra’s running time depends on the priority queue, ranging from O((|V| + |A|) log |V|) with binary heaps to faster bounds with specialized heaps, buckets, or average-case methods.Fibonacci heaps give O(|A| + |V| log |V|), while integer costs in [0, C] permit multi-level buckets with O(|A| + |V| √log C).Source: §2.1 · p. 4

Bidirectional search

• Bidirectional search runs simultaneous forward and backward searches and stops when their intersection provably contains a shortest-path vertex, visiting roughly half as many road-network vertices.Its practical benefit is a reduced search space compared with unidirectional Dijkstra search.Source: §2.1 · p. 4

Alternative algorithms

• Bellman-Ford is a label-correcting alternative that repeatedly scans improved vertices, has O(|V| |A|) worst-case time, and supports graphs with negative edge weights [46, 127,198].Despite its worst-case bound, it can be much faster in practice and competitive with Dijkstra’s algorithm in some scenarios.Source: §2.1 · p. 4
• Floyd-Warshall computes all-pairs distances in Θ(|V|^3) time and can outperform |V| Dijkstra runs on sufficiently dense graphs [126].Its scope is all vertex pairs rather than a single-source or point-to-point query.Source: §2.1 · p. 4

Goal-Directed Techniques

• A* search prioritizes vertices by dist(s, u) + π(u), using feasible lower-bound potentials to guide correct target-directed exploration.With exact potentials, only vertices on shortest s–t paths are scanned; feasible potentials permit termination when t is about to be scanned.Source: §2.2 · p. 5
• Bidirectional A* requires consistent forward and backward potentials or a modified stopping criterion to preserve correctness.One construction combines arbitrary feasible functions using (πf −πr)/2 and (πr −πf)/2.Source: §2.2 · p. 5
• ALT [148] improves A* lower bounds by storing landmark-to-vertex distances and taking the strongest valid triangle-inequality bound.Well-spaced landmarks near graph boundaries perform best on road networks, but some queries achieve only minor speedups over bidirectional Dijkstra; Figure 2 illustrates the inequalities.Source: §2.2 · pp. 5–6, Figure 2 · p. 5
• Geometric Containers prune arcs when the target is outside a precomputed geometric approximation of their shortest-path destinations, but preprocessing is costly.Approximations include angular sectors, ellipses, convex hulls, and bounding boxes, with bounding boxes performing consistently well.Source: §2.2 · p. 6
• Arc Flags currently achieve the fastest query times among purely goal-directed road-network methods, although preprocessing can take several hours.Multilevel partitions improve query performance, and PHAST can make Arc Flags more competitive with other techniques.Source: §2.2 · p. 6
• Precomputed Cluster Distances uses cell-to-cell shortest-path distances to prune Dijkstra search, achieving ALT-like query times with less space in road networks.Compressed Path Databases retrieve shortest paths through compressed first-move labels, yielding fast queries but large space consumption that leaves them dominated by other approaches.Source: §2.2 · pp. 6–7

Overview

• These techniques rely on the observation that road networks, despite tunnels and overpasses, have small separators similar to planar graphs.Planar graphs have efficiently computable small separators, and small separators have also been observed in road networks.Source: §2.3 · pp. 7–8

Vertex Separators

• Vertex-separator methods remove a small, balanced vertex set and add overlay shortcuts preserving distances between separator vertices, accelerating queries.The overlay is substantially smaller than the original graph and can accelerate parts of the query algorithm.Source: §2.3 · p. 8
• Multilevel vertex overlays connect separator vertices across levels, while denser shortcut variants trade increased preprocessing time and space for faster queries.HPML substantially reduces query times but significantly increases total space usage and preprocessing time.Source: §2.3 · p. 8

Arc Separators

• Arc-separator methods partition vertices into balanced cells, minimize cut arcs, and add shortcuts preserving distances between boundary vertices within each cell.HiTi runs Dijkstra’s algorithm on the relevant cell subgraph plus the overlay, but its grid-graph tests produced only modest speedups.Source: §2.3 · p. 8
• CRP adapts arc-separator overlays to real road systems by supporting turn costs, fast metric updates, road-tailored partitioning, and bidirectional overlay queries.Its preprocessing separates metric-independent topology construction from parallel metric customization, with Bellman-Ford contraction and GPUs offering further acceleration at potential space cost.Source: §2.3 · pp. 8–9

Contraction Hierarchies

• Contraction Hierarchies (CH) contracts vertices from least to most important, adding shortcuts that preserve shortest paths through removed vertices.Vertex importance is heuristically ordered during preprocessing, and shortcuts connect neighboring vertices when the unique shortest path between them contains the contracted vertex.Source: §2.4 · p. 9
• CH answers queries with bidirectional upward searches, whose common visited vertex minimizing ds(u) + dt(u) yields the exact shortest-path distance.The highest-ranked vertex on the original shortest path is visited by both searches with exact labels, although the searches cannot stop at their first meeting.Source: §2.4 · pp. 9–10
• CH query performance depends on vertex ordering, with shortcut-minimizing heuristics, offline shortest-path centrality, and nested dissection providing alternative ordering strategies.Approximate CH can accommodate networks with less inherent hierarchy, while CH is also used as a building block for other algorithms, extended queries, and applications.Source: §2.4 · p. 10

Reach

• Reach assigns each vertex a centrality value based on its maximum shortest-path reach and prunes Dijkstra searches when both endpoint distances exceed that value.Bidirectional searches use the opposite search radius as a lower bound to test the pruning conditions.Source: §2.4 · p. 10
• Exact reach computation is too expensive for large networks, but upper bounds from partial shortest-path trees preserve correctness, and shortcuts can make Reach practical at continental scale.Shortcuts reduce the reaches of most vertices, accelerating both queries and preprocessing.Source: §2.4 · p. 10

Labeling Algorithms

• Labeling algorithms answer distances from two vertex labels; Hub Labeling uses a cover property so intersecting hubs identify a shortest-path distance.For directed graphs, forward and backward labels replace a single label, and queries minimize the combined distances through common hubs.Source: §2.5 · p. 11
• Roughly five main-memory accesses make Hub Labeling the fastest known road-network query method, although its space usage exceeds competing methods.Hub Label Compression reduces space by an order of magnitude at the expense of higher query times.Source: §2.5 · pp. 11–12

Transit Node Routing

• Transit Node Routing combines access-node distances with transit-node distance tables, using locality filters and fallback searches to remain correct when shortest paths are local.Hierarchical transit layers can accelerate local queries, while global table-based queries tend to be faster than local graph searches.Source: §2.5 · p. 12

Pruned Highway Labeling

• Pruned Highway Labeling hybridizes labeling and transit nodes by decomposing the graph into shortest paths whose labeled intersections represent every shortest route.It does not require planarity but has only been evaluated on undirected graphs.Source: §2.5 · pp. 12–13

• Combining Geometric Containers, multilevel overlay graphs, and Euclidean-based A* achieved one- to two-order-of-magnitude speedups over Dijkstra’s algorithm [161,235].Source: §2.6 · p. 13
• REAL combines Reach and ALT, using either reach pruning with ALT bounds or reach-aware landmarks that save space but require two-stage queries.The reach-aware variant stores landmark distances only for high-reach vertices and activates goal direction after the search is sufficiently far from both endpoints.Source: §2.6 · p. 13
• Core-ALT and HH* [95] restrict landmark-based goal direction to a core reached after an initial bidirectional search.Core-ALT builds an overlay graph on a small core, such as 1% of vertices, while HH* uses Highway Hierarchies to determine that core.Source: §2.6 · p. 13
• ReachFlags computes approximate reach values, restricts arc flags to vertices above a threshold, and applies them during a second query phase.Source: §2.6 · p. 13
• SHARC [39] combines partition-restricted shortcuts with multilevel arc flags, providing compressed, unidirectional hierarchical guidance that also supports time-dependent routing.Shortcuts do not cross partition cells, and a shortcut is used for cell C exactly when the target is outside C; compression can reduce space.Source: §2.6 · pp. 13–14
• CHASE combines contraction hierarchies with arc flags, while TNR+AF prunes transit-node table lookups using cell-based access-node bit vectors.CHASE initially restricted arc flags to about 5% of vertices, but PHAST enabled full-graph flags and simpler, faster single-pass queries. TNR+AF keeps access nodes only when their vectors permit shortest paths toward the target’s cells.Source: §2.6 · p. 14

2.7.1 Path Retrieval

• Shortest-path algorithms can retrieve full paths using parent pointers, while shortcut-based methods require unpacking via stored middle vertices, stored sequences, or local searches.For CH, recursive unpacking is linear-time; the same techniques extend to bounded-hop algorithms.Source: §2.7.1 · pp. 14–15

2.7.2 Batched Shortest Paths

• Hierarchical bucket searches accelerate many-to-many distances to practical time comparable to O(|S| + |T|) point-to-point queries, while PHAST makes one-to-all computation over an order of magnitude faster than Dijkstra.PHAST uses a forward upward search followed by a source-independent linear scan that improves locality and enables parallelism, including on multiple cores and GPUs.Source: §2.7.2 · p. 15

2.7.3 Dynamic Networks

• Dynamic networks can be handled by repairing preprocessing, adapting queries around changed regions, making preprocessing metric-independent, or rerunning only metric-dependent stages.For example, ALT tolerates increased arc costs with slower queries, CH can bypass affected shortcuts, and CRP can retain its partitioning and overlay topology.Source: §2.7.3 · p. 16

2.7.4 Time-Dependence

• Under FIFO, time-dependent shortest paths remain solvable with Dijkstra-based and adapted speedup methods, but bidirectional search and shortcut storage become more difficult.Even a slight deviation from a linear combination of travel time and constant cost offset makes the problem NP-hard, although time-dependent CH has negligible practical errors.Source: §2.7.4 · p. 17

2.7.5 Multiple Objective Functions

• Vehicle-specific restrictions can be incorporated during queries or through metric updates, extending route planning beyond a single cost function.These restrictions include vehicle-dependent edge availability and user preferences such as accepting a longer but more scenic route.Source: §2.7.5 · p. 17
• Multicriteria search computes Pareto sets with label-setting or label-correcting methods, but exponentially large sets can limit speedups even with two criteria.(1 + ε)-Pareto sets have provable polynomial size, while linear combinations such as αc1+(1−α)c2 offer an alternative with query-time parameterization.Source: §2.7.5 · pp. 17–18

Preprocessing complexity

• Optimal preprocessing choices are NP-hard for ALT, Arc Flags, SHARC, Multilevel Overlay Graphs, Contraction Hierarchies, and Hub Labels, while minimizing CH shortcuts is APX-hard.SHARC nevertheless has a greedy factor-k approximation, although selecting k shortcuts optimally remains NP-hard.Source: §2.8 · pp. 18–19

Graph-class guarantees

• For restricted graph classes, CH admits provable bounds: nested dissection yields O(|V | log |V |) shortcuts on planar graphs, while treewidth-k graphs have search space O(k log |V |).More generally, balanced separators in minor-closed graph classes yield bounded CH search spaces.Source: §2.8 · p. 19

Road-network structure

• Highway dimension h links road-network structure to theoretical speedup bounds: after polynomial preprocessing, Reach and CH take O((h log h log D)2), HL takes O(h log h log D), and long-range TNR takes O(h2).Highway dimension also implies doubling dimension log(h + 1), supporting good ALT performance through landmark-based triangulation.Source: §2.8 · p. 19
• Highway dimension was introduced to explain observed CH, Reach, and TNR performance and subsequently predicted that HL would perform well before its implementation [3,7].Road networks are not strictly planar but have small separators, helping explain why planar-graph theory is relevant despite stronger performance on actual roads.Source: §2.8 · pp. 19–20

Additional theoretical work

• Generative road-network models produce graphs with provably small highway dimension, while further theory covers A*, overlays, transit nodes, labeling, and approximation methods.Approximate label-construction algorithms can improve labels over faster heuristics but may have prohibitive running time. The survey refers detailed theoretical coverage to specialized overviews.Source: §2.8 · p. 20

3.1 Experimental Results

• Experiments use carefully engineered C++ implementations and evaluate simplified and realistic turn models separately because turn modeling changes algorithm sensitivity.The realistic model includes turn information, represented either by graph expansion or compact intersection turn tables.Source: §3.1 · pp. 20–21

3.1.1 Simplified Model

• In the simplified model, no technique is best: the large Pareto set spans diverse preprocessing-time, query-time, and space trade-offs.All considered approaches answer queries in milliseconds or less; CHASE improves query time by another order of magnitude, while high-space methods can exceed the baseline by more than a million times.Source: Figure 7 · p. 22, §3.1.1 · pp. 23–24

3.1.2 Realistic Setting

• Realistic systems must handle turn costs, multiple metrics, robust query times, and rapid metric updates, making CH’s degradation under constraints a key limitation.CRP separates slow metric-independent preprocessing from fast metric-dependent customization, whereas CH is fastest to preprocess but degrades under realistic constraints.Source: §3.1.2 · pp. 24–26
• CRP remains robust to turn costs and cost functions, applying a new metric in roughly 370 ms and enabling personalized continental-scale directions.GPU customization reduces this to 36 ms, while CPU-only customization takes about one second on 12 cores.Source: §3.1.2 · pp. 25–26, Table 2 · p. 26

3.2 Applications

• Road-routing speedups support alternative paths, robust corridors, complex vehicle constraints, batched shortest paths, GPS matching, traffic simulation, route prediction, charging-station planning, ride sharing, and network-based POI queries.These applications extend beyond ordinary point-to-point shortest paths and include multiple criteria such as travel time, energy consumption, and cycling elevation.Source: §3.2 · pp. 26–27

3.3 Alternative Settings

• Routing methods can adapt to constrained environments: compressed CH supports interactive mobile queries, while HL enables interactive shortest-path applications entirely within relational databases.Database implementations of geometric distance oracles are approximate and expensive, limiting them to small instances.Source: §3.3 · pp. 27–28

4 Journey Planning in Public Transit Networks

• Public-transit networks require time-dependent, multicriteria journey planning because connections occur at discrete times and criteria such as transfers matter alongside arrival time.The section considers timetable-based networks of stops, routes, trips, elementary connections, and footpaths.Source: §4 · p. 28, §4.1 · p. 31

4.1 Modeling

• Timetable models include time-expanded event graphs, time-dependent stop graphs with travel-time functions, and frequency-based models that compress regular departures.These models support transfers, minimum change times, footpaths, and timetable compression, with time-dependent models avoiding the large graphs produced by time expansion.Source: §4.1 · pp. 29–31

4.2 Algorithms without Preprocessing

• Without preprocessing, Dijkstra variants, Connection Scan, Layered Dijkstra, and RAPTOR solve earliest-arrival, range, and multicriteria queries using timetable-specific scans or layered and round-based dynamic programming.RAPTOR scans each route at most once per round, supports parallelization, and extends to range and additional criteria; CSA and RAPTOR require transitively closed footpaths.Source: §4.2 · pp. 31–33

4.3 Speedup Techniques

• Preprocessing-based speedups remain difficult because public-transit networks have broad neighborhoods and inherent time dependency; SHARC-based multicriteria speedup remains below 15.Transfer Patterns, overlays, ACSA, and adapted road-network techniques accelerate selected queries, while ACSA achieves excellent query and preprocessing times on country-sized instances.Source: §4.3 · pp. 34–35, Separator-based techniques · p. 35

4.4 Extended Scenarios

• Real-time data improves journey quality under delays, while delay-aware models update timetable representations and Transfer Patterns computed without delays remain optimal for 99 % of queries under injected delays.Published timetables often fail to provide optimal or high-quality solutions, whereas GPS data can reduce experienced delay.Source: §4.4 · p. 37
• Reliable and robust journey methods model transfer success, expected arrival time, delay scenarios, recoverability, or historical performance, with light robustness more promising than strict robustness.Dibbelt et al. output decision graphs covering missed connections, while Goerigk et al. distinguish strict and light robustness; recoverable journeys are considered in, and Böhmová et al. use past traffic observations.Source: §4.4 · p. 37
• Overnight-train planning prioritizes sufficiently long sleeping periods and avoids excessively early arrivals, using explicit train enumeration or multicriteria search with sleeping time maximized.Gunkel et al. present both approaches for computing overnight journeys.Source: §4.4 · p. 38
• Exact fare optimization is difficult because real-world pricing schemes are hard to capture mathematically, motivating fare-zone Pareto sets with postprocessed cost evaluation.Müller-Hannemann and Schnee integrate cost into MOTIS, while Delling et al. optimize combinations of fare zones using McRAPTOR.Source: §4.4 · p. 38
• Guidebook Routing returns route instructions without a specified departure time, and practical routes can reduce Transfer Patterns preprocessing space and query times by a factor of 4 to 5.Routes are extracted from frequently used arcs across Pareto-optimal time-dependent paths; guidebook routes covering about 80 % of optimal full-period results can be computed in a fraction of a millisecond.Source: §4.4 · p. 38, §4.5 · p. 41

4.5 Experiments and Comparison

• The evaluation mainly uses London’s full metropolitan network because country-scale benchmark data is scarce and transit datasets are difficult to compare consistently.The London instance contains approximately 21 thousand stops, 2.2 thousand routes, 133 thousand trips, 46 thousand footpaths, and 5.1 million elementary connections for one day.Source: §4.5 · p. 39
• Preprocessing-based methods scale best for long-range, range, and full multicriteria queries, while RAPTOR and CSA outperform graph-based methods without preprocessing; Transfer Patterns is fastest overall in several query settings.Transfer Patterns trades substantially longer preprocessing for lower query times and is by far the fastest method for full multicriteria range queries.Source: §4.5 · pp. 39–41, Table 3 · p. 40

5 Multimodal Journey Planning

• Multimodal planning integrates unrestricted and schedule-based modes in one algorithm, explicitly modeling transfers because feasible journeys must exclude impossible mode sequences.Typical networks combine separate mode graphs with transfer links, using static walking and car graphs, time-dependent public transit, and dedicated flight models.Source: §5 · pp. 41–42

5.1 Combining Costs

• Combining travel time with transfer penalties, ticket cost, inconvenience, or user preferences provides a linear-cost approach to multimodal journey optimization.Examples include linear programming, TRANSIT’s utility function, and combined walking, car, and public-transit networks.Source: §5.1 · p. 42

5.2 Label-Constrained Shortest Paths

• Label-constrained shortest paths encode transport-mode rules as regular languages, enabling feasible multimodal journeys and polynomial-time solution via product-graph Dijkstra.Access-Node Routing answers intercontinental queries in milliseconds but fixes language constraints during preprocessing; UCCH supports arbitrary query-time mode sequences with less preprocessing than ANR.Source: §5.2 · pp. 42–44

5.3 Multicriteria Optimization

• Multicriteria optimization computes diverse Pareto-set journeys across arrival time and mode-specific criteria, addressing users’ limited network knowledge and need for alternatives.MCR combines RAPTOR, MLS, and taxi processing by transfer rounds, while TNT filters reasonable journey types and produces sets robust to the threshold choice.Source: §5.3 · pp. 44–45

• Road-network shortest-path algorithms are up to seven orders of magnitude faster than standard solutions, using goal direction, hierarchy, and small separators rather than vertex coordinates.Geometry-based methods are consistently dominated by established techniques; Arterial Hierarchies was compared with CH but not stronger techniques such as CHASE, HL, and TNR.Source: §6 · p. 45
• Real-data experiments are essential because simplified models can misrepresent production behavior, as turn penalties caused significant performance loss for CH.Source: §6 · p. 45
• Careful engineering lets CRP, CSA, HL, PHAST, and RAPTOR exploit locality and parallelism across instructions, cores, and GPUs.Source: §6 · pp. 45–46
• Several surveyed approaches serve millions of users through systems including TomTom’s Arc Flags variant, Bing Maps’ CRP, OSRM’s CH, Google Maps’ Transfer Patterns, and OpenTripPlanner’s RAPTOR.Source: §6 · p. 46
• A worldwide multimodal planner combining real-time and historic information, schedules, monetary costs, and personalization remains beyond current algorithms, despite rapid progress.Systems such as Rome2Rio7 provide only a simplified first step.Source: §6 · p. 46