PaperlayerView exact revision on arXiv

Source-linked AI summary

Route Planning in Transportation Networks

Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck

arXiv:1504.05140v1cs.DS

TL;DR

Route-planning research must support fast queries across road, public-transit, and multimodal networks with different structural and temporal constraints. This survey synthesizes practical algorithms and their trade-offs, showing strong production impact while identifying public-transit, pricing, and fully general multimodal planning as harder boundaries.

  • Problem

    Efficient routing must handle road networks as well as time-dependent, multicriteria public transit and even harder multimodal journeys.

  • Method

    The survey synthesizes practical routing algorithms for static roads, schedule-based transit, and multimodal transportation, including preprocessing and dynamic-programming approaches.

  • Results

    Several surveyed algorithms have reached mainstream production systems serving millions of users daily.

  • Takeaways & Limitations

    Practical routing methods offer application-dependent trade-offs, while exact continent-scale transit and general multimodal planning still require simplification, heavy preprocessing, or approximation.

  • Takeaways & Limitations

    A worldwide multimodal planner combining real-time traffic and transit, historic patterns, schedule constraints, monetary costs, and personalization remains beyond current algorithms.

Abstract

from arXiv · show

We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.

1 Introduction

The survey updates the state of practical route-planning algorithms, covering road, public-transit, and multimodal networks. It emphasizes major performance gains alongside application-dependent trade-offs and unresolved challenges.

  • Recent algorithms answer continent-scale road-network queries in a few hundred nanoseconds or incorporate current traffic information in under a second.The survey broadens earlier road-focused coverage to public-transit and multimodal scenarios.
  • Road-routing methods have different trade-offs in query time and preprocessing effort, so no single solution is best for every problem.
  • Public-transit journey planning is harder because it is time-dependent and multicriteria, making preprocessing less effective and approximations sometimes necessary.
  • Multimodal journey planning combines schedule-based transportation with less restricted modes such as walking and cycling, but remains significantly harder than its individual components.
  • Several surveyed algorithms have entered mainstream production systems serving millions of users daily.
  • The survey covers research published through January 2015 and generally cites final journal versions.

2 Shortest Paths Algorithms

This section frames shortest-path routing around several query variants and an interactive server model. It presents general graph methods while keeping road networks as the motivating application.

  • Point-to-point routing computes the shortest distance between a source and target, while one-to-all and all-to-one variants compute distances from or to a single vertex.
  • Shortest-path applications may also require an out-shortest path tree or in-shortest path tree representing all paths from or to a root.
  • The basic server model assumes graph data fits in RAM, allows stronger machines for preprocessing, and requires queries fast enough for interactive applications.
  • The section presents basic and preprocessing-based methods for arbitrary graphs, then evaluates road-network performance with precise numbers later.

2.1 Basic Techniques

Basic shortest-path techniques range from Dijkstra’s priority-queue search to alternative algorithms with different complexity, graph assumptions, and search-space reductions.

  • Dijkstra’s algorithm maintains tentative distances in a priority queue, scans the minimum-distance vertex, and relaxes its outgoing arcs.Once a vertex is scanned, its distance is correct, enabling early termination when the target is scanned.
  • Dijkstra’s running time depends on the priority queue, with bounds ranging from O((|V| + |A|) log |V|) for binary heaps to linear time on average.
  • Bidirectional search runs forward and backward searches simultaneously and visits roughly half as many vertices as unidirectional search on road networks.
  • Bellman-Ford uses rounds and a FIFO queue rather than a priority queue, supports negative edge weights, and has O(|V| |A|) worst-case time.
  • Floyd-Warshall computes all-pairs distances in Θ(|V|^3) time and can outperform |V| Dijkstra runs on sufficiently dense graphs.

2.2 Goal-Directed Techniques

Goal-directed methods reduce shortest-path search by steering queries toward the target through potentials, landmarks, geometry, partitions, overlays, or compressed path information.

  • A* and ALT: A* prioritizes vertices by dist(s,u) + π(u), where π is a lower bound on the remaining distance to the target.With exact lower bounds, only vertices on shortest s–t paths would be scanned; bidirectional variants require additional correctness care.
  • A* and ALT: Geographical-distance potentials provide poor or negligible gains on road networks, while more aggressive bounds can sacrifice correctness.
  • A* and ALT: ALT preserves correctness by using landmark distances and triangle inequalities to compute stronger lower bounds on dist(u,t).
  • A* and ALT: ALT query performance depends on landmark placement, with well-spaced landmarks near graph boundaries performing best on average but offering minor speedups for some queries.
  • Partition- and overlay-based methods: Arc Flags partition the graph into balanced cells and prune arcs whose flags do not indicate shortest paths to the target cell.The method’s flags can be computed from backward shortest-path trees or simultaneous label-correcting searches.
  • Partition- and overlay-based methods: Precomputed Cluster Distances uses intercell shortest-path distances to derive lower bounds and achieves query times similar to ALT with less space on road networks.
  • Partition- and overlay-based methods: Overlay methods add shortcuts among important or separator vertices, including multilevel connections and cell-restricted boundary shortcuts.
  • Compressed path information: Compressed Path Databases store the first move toward every destination in vertex labels, allowing queries to recursively retrieve shortest paths.

2.3 Separator-Based Techniques

Separator-based methods partition transportation graphs and add shortcut overlays that preserve boundary or separator distances. Variants trade query speed against preprocessing time, space, and support for changing cost functions.

  • Vertex Separators: Small separators decompose road-like graphs into cells, enabling smaller overlay graphs that accelerate shortest-path queries.The overlay preserves distances between separator vertices through shortcut arcs.
  • Vertex Separators: Hierarchical overlays add arcs among separator vertices across levels, extending the basic separator approach to multilevel routing.Some variants add substantially more shortcuts to reduce query time.
  • Arc Separators: Arc-separator methods partition vertices into balanced cells while minimizing cut arcs, then preserve within-cell boundary distances with shortcuts.The overlay includes boundary vertices and shortcut distances between boundary pairs in each cell.
  • Arc Separators: CRP separates metric-independent preprocessing from customization, allowing fast updates of costs while supporting turn costs and road-network partitions.Customization computes clique-arc costs bottom-up and in parallel.

2.4 Hierarchical Techniques

Hierarchical techniques exploit the tendency of long shortest paths to converge onto important road subnetworks. They use pruning, shortcuts, or rank restrictions to reduce search while preserving exactness under their stated conditions.

  • Overview: Hierarchical methods focus searches on important arterial roads because sufficiently long shortest paths tend to converge onto a small subnetwork.Road-category heuristics exploit this structure but do not guarantee exact shortest paths.
  • Contraction Hierarchies: Contraction Hierarchies contracts vertices from least to most important and adds shortcuts when a removed vertex lies on a unique shortest connection between neighbors.Queries then use only arcs leading to higher-ranked vertices.
  • Contraction Hierarchies: CH remains exact because the highest-ranked vertex on an original shortest path is visited by both upward searches with exact distance labels.The shortest path is selected by minimizing ds(u) + dt(u) among vertices visited by both searches.
  • Contraction Hierarchies: CH query performance depends on the heuristic vertex order, which seeks to limit the number of added shortcuts during preprocessing.The order considers shortcut growth and nearby vertices already contracted.
  • Contraction Hierarchies: CH is conceptually simple and versatile, serving as a building block for other point-to-point algorithms, extended queries, and applications.It succeeds Highway Hierarchies and Highway Node Routing while being faster according to the survey passage.
  • Reach: Reach prunes a Dijkstra-based search when both source-side and target-side distances exceed a vertex's reach value.Exact reach computation is too expensive on large road networks, so preprocessing may use upper bounds.

2.5 Bounded-Hop Techniques

Bounded-hop methods replace broad graph searches with precomputed distances or labels that summarize short virtual routes. Hub labeling offers exceptionally fast queries on road networks, while transit-node and hybrid methods depend on coverage and locality assumptions.

  • Overview: Bounded-hop techniques precompute pairwise distances as virtual shortcuts, allowing queries to return paths with very few hops.Queries can use only the precomputed distances rather than the input graph.
  • Labeling Algorithms: Labeling algorithms assign each vertex a label from which distances between any vertex pair can be determined using only the two endpoint labels.Hub Labeling stores hubs and distances, with a cover property requiring a common hub for every pair.
  • Labeling Algorithms: Hub Labeling queries use a linear sweep over two hub-ID-sorted arrays, yielding the fastest known road-network queries.With careful engineering, a query takes roughly the time of five main-memory accesses.
  • Labeling Algorithms: Hub Labeling's main drawback is significantly higher space usage than competing methods.Hub Label Compression reduces space by an order of magnitude at the expense of higher query times.
  • Transit Node Routing: Transit Node Routing stores distances among selected transit nodes and access-node distances, then minimizes the combined source-to-access-to-target distance.A locality filter invokes a fallback shortest-path algorithm for potentially local queries.
  • Transit Node Routing: TNR correctness requires handling shortest paths that contain no transit node, making the choice of transit-node set and locality filter crucial.Grid-based separators provide natural locality filters that work well enough in practice for road networks.
  • Pruned Highway Labeling: Pruned Highway Labeling combines labeling with transit-node-like path subsets so shortest paths can be represented through a labeled subpath.Queries find the lowest-cost intersecting path using the labels of the source and target.

2.6 Combinations

Combination methods stack complementary speedup techniques to improve routing performance. They commonly use staged queries, restricting expensive goal-directed or labeling work to a smaller core or candidate set.

  • Hybrid Algorithms: Combining Geometric Containers, multilevel overlays, and Euclidean A* produced speedups of one or two orders of magnitude over Dijkstra's algorithm.These early combinations exploit different graph properties simultaneously.
  • Hybrid Algorithms: REAL combines Reach and ALT by using ALT lower bounds together with reach-based pruning.A more sophisticated variant uses reach-aware landmarks.
  • Core-Based Methods: Core-ALT computes an overlay for a small core and stores landmarks only for core vertices, reducing the scope of landmark preprocessing.Queries first run bidirectional search and apply ALT after entering the core.
  • Core-Based Methods: ReachFlags computes approximate reaches, extracts a high-reach subgraph, and computes arc flags only on that subgraph for the second query phase.The method explicitly separates preprocessing and query work into two stages.
  • SHARC: SHARC combines shortcuts with multilevel arc flags, restricting shortcuts within partition cells and using flags to guide target-directed queries.Compression techniques can reduce its space usage.
  • CHASE: CHASE combines Contraction Hierarchies with arc flags by computing flags only on a subgraph induced by the highest-ranked vertices.Queries first use the hierarchy and then run a second phase on the restricted subgraph.
  • TNR+AF: TNR+AF reduces transit-node table lookups by partitioning transit nodes into cells and storing bit vectors for access-node reachability.Each bit indicates whether a shortest path through an access node reaches the corresponding transit-node cell.

2.7 Extensions

The survey extends shortest-path routing beyond basic point-to-point queries to paths, batched computations, dynamic networks, time dependence, and multiple criteria. These extensions introduce distinct preprocessing, query-time, complexity, and approximation trade-offs.

  • Path retrieval: Shortest-path methods can retrieve complete paths, not just distances, by maintaining parent pointers or unpacking shortcut-based representations.Shortcut unpacking can be linear-time when each shortcut stores its middle vertex.
  • Batched shortest paths: Hierarchical speedup techniques support batched source-target computations in practice with time comparable to O(|S| + |T|) point-to-point queries.This improves substantially over performing |S| · |T| independent queries.
  • Batched shortest paths: PHAST accelerates one-to-all computations through an upward search followed by a parallelizable linear scan, exceeding Dijkstra’s speed by more than an order of magnitude on road networks.The method also benefits from multiple cores and GPUs and extends to one-to-many queries.
  • Dynamic networks: Dynamic networks can be handled by repairing preprocessing, adapting queries, using metric-independent preprocessing, or separating metric-independent and metric-dependent stages.These approaches trade rebuilding cost, query speed, and preprocessing complexity differently.
  • Time dependence: Time-dependent routing models departure-time effects with travel-time functions, while FIFO preserves Dijkstra’s correctness and non-FIFO-like extensions can make optimization NP-hard.Even a slight deviation from the specified linear travel-time-plus-offset model yields NP-hardness; a heuristic time-dependent CH adaptation has negligible practical errors.
  • Multiple criteria: Multicriteria routing computes a Pareto set of mutually incomparable paths, commonly by extending Dijkstra’s algorithm with nondominated labels.This supports preferences such as accepting a slightly longer route for a more scenic journey.

2.8 Theoretical Results

Theoretical results explain when routing speedups work, expose computational limits in preprocessing, and relate search-space bounds to graph structure. Highway dimension and related models connect empirical road-network performance with formal graph properties, while the survey deliberately keeps its theoretical treatment brief.

  • Scope and motivation: Most surveyed algorithms are exact, but their practical performance varies with the input graph and can approach Dijkstra’s performance outside real road networks.Theoretical work therefore seeks graph properties that explain observed speedups.
  • Preprocessing complexity: Optimizing preprocessing choices is computationally difficult: optimal ALT landmarks and Arc Flags choices are NP-hard, while minimizing CH shortcuts is APX-hard.SHARC admits a greedy factor-k approximation, although selecting k shortcuts to minimize search space remains NP-hard.
  • Graph-structural bounds: Specific graph structures yield nontrivial query bounds, including O(k log |V |) CH search space on graphs of treewidth k and bounds based on separator size.Such results are unavailable in comparable form for arbitrary graphs, where many algorithms can be ineffective.
  • Graph-structural bounds: Planar-graph separator theory is relevant to road networks because real road networks have small separators, although speedups are typically much stronger on actual roads than on arbitrary planar graphs.Explaining this gap requires formalizing properties specific to real road networks.
  • Highway dimension: Highway dimension was proposed to explain the observed performance of CH, Reach, and TNR and subsequently predicted good practical performance for HL before implementation.The concept models locally sparse hitting sets for long shortest paths across scales.
  • Scope and motivation: The survey emphasizes algorithm engineering and refers readers elsewhere for fuller coverage of theoretical work.It also discusses generative road-network models and theoretical analyses of A*, overlays, transit nodes, and labeling algorithms.

3 Route Planning in Road Networks

Road-network routing methods achieve very fast queries, but no single technique is best: preprocessing time, query time, space, realism, and customization needs create different trade-offs. Experiments show strong performance on continental-scale networks while exposing limitations under turn costs, restrictions, and changing cost functions.

  • Experimental setting: Carefully engineered experiments compare road-routing methods using preprocessing time, average query time, scanned vertices, and space requirements.Implementations use C++, custom data structures, adjacency arrays, and specialized priority queues; results include simplified and realistic turn models separately.
  • Simplified model: Figure 7 relates preprocessing time to average query time for shortest-path queries on Western Europe, revealing a wide range of space-time trade-offs.The plot uses uniformly random source-target pairs and does not explicitly show space consumption.
  • Simplified model: There is no best technique because the Pareto set spans competing preprocessing-time, query-time, and space requirements.The table-lookup baseline is impractical because it requires more than one petabyte of RAM, despite extremely fast queries.
  • Simplified model: Algorithms based on separator, hierarchy, or goal-directed methods answer queries in milliseconds or less, while CHASE and non-graph methods provide further speedups at different space costs.CH and CRP use little more space than Dijkstra while running three to four orders of magnitude faster; non-graph methods can exceed a million-fold speedup over the baseline.
  • Realistic setting: Realistic turn costs and restrictions alter performance, and results from simplified models are difficult to extrapolate to production-like networks.CH preprocesses fastest and queries interactively, but its performance degrades under realistic constraints; CRP was designed for those constraints.
  • Realistic setting: CRP supports robust query performance across cost functions and turns, enabling rapid customization for user-specific or traffic-aware driving directions.Customization takes roughly 370 ms for a new cost function, can fall to 36 ms with GPUs, or take about one second on a 12-core CPU without contraction-based customization.
  • Realistic setting: The appropriate method depends on application requirements: simplified models may suffice for travel-time estimates, while realistic directions require handling turns, restrictions, and multiple cost functions.CH, HL, and HLC remain viable for static realistic problems when expanded-graph space is acceptable.

4 Journey Planning in Public Transit Networks

Public-transit journey planning is time-dependent and multicriteria, making modeling and preprocessing harder than road routing. The survey reviews practical algorithms and extended scenarios, finding strong metropolitan performance but substantial trade-offs and limits at larger scales.

  • Modeling: Public-transit journeys combine scheduled trips, stops, routes, and elementary connections whose feasibility depends on discrete departure times.The survey presents timetable modeling as a fundamental challenge because transit segments are traversable only at specific times.
  • Problem variants: Multicriteria planning seeks Pareto-optimal journeys balancing arrival time, transfers, fares, reliability, and other objectives.The number of criteria enlarges Pareto sets and makes exact real-time queries harder, although correlated criteria can keep sets manageable.
  • Algorithms: RAPTOR uses rounds over routes and transfers, while preprocessing-based methods provide much larger speedups than graph-based adaptations alone.RAPTOR scans each route at most once per round; transit preprocessing speedups nevertheless remain several orders of magnitude lower than in road networks.
  • Extended scenarios: Real-time vehicle locations can improve journey quality because timetable-only planning may fail to produce optimal or high-quality journeys.A Rome case study reports improved experienced-delay outcomes when GPS data is incorporated.
  • Experiments and comparison: Preprocessing creates a query-speed versus preprocessing-cost trade-off across metropolitan and larger transit networks.Transfer Patterns can achieve optimal solutions with quadratic preprocessing, while Germany-wide preprocessing may take over 60 times longer than alternatives but yield considerably lower query times.
  • Experiments and comparison: For range queries, CH, ACSA, and Transfer Patterns scale better than CSA or SPCS, with Transfer Patterns fastest for full multicriteria ranges.rRAPTOR instead depends linearly on the number of journeys departing during the queried time range.

5 Multimodal Journey Planning

Multimodal journey planning integrates unrestricted and schedule-based transportation while enforcing feasible mode sequences. The survey presents penalty-based, label-constrained, and Pareto-oriented approaches, including preprocessing and automaton-based speedups, but practical methods retain important trade-offs.

  • Problem formulation: Multimodal planning must integrate multiple transportation modes and explicitly account for feasible transfers and user preferences.The survey distinguishes true multimodal journeys from journeys using only buses, trains, or trams represented as one public-transit schedule.
  • Problem formulation: A multimodal network can merge separate mode-specific graphs, using static models for walking and car travel and time-dependent models for transit and sometimes driving.Link arcs or vertices enable modal transfers between the component networks.
  • Label-constrained methods: Label-constrained shortest paths encode transportation modes as arc labels and require journeys to satisfy a query-specified language of allowed mode sequences.This approach explicitly controls which modal sequences may occur in a journey.
  • Label-constrained methods: LCSPP-D is solvable in deterministic polynomial time by constructing a product network with a finite automaton and running Dijkstra between compatible origin and destination states.The product vertices combine original graph vertices with automaton states.
  • Speedup techniques: Access-Node Routing precomputes road-network access points to transit and flight networks, then searches the smaller network between relevant access nodes.Core-Based ANR further restricts access-node preprocessing to a smaller core graph.
  • Speedup techniques: ANR supports millisecond queries on intercontinental multimodal networks, but preprocessing depends strongly on transit and flight-network density and fixes the regular language during preprocessing.The language therefore cannot be freely specified at query time without losing optimality.
  • Speedup techniques: SDALT precomputes lower bounds for each vertex and automaton state, with more aggressive bounds available when a label-correcting search preserves correctness.The aggressive bounds can be incorrect, but repeated vertex scans maintain correctness.
  • Journey quality: Filtering journeys by concrete limits on walking or car travel can prune the search space and reduce query time, with resulting journey sets fairly robust to the threshold.One example threshold for “little” walking and car travel is 10 minutes.

6 Final Remarks

Recent routing algorithms achieve dramatic performance gains, but practical success depends on real-data validation and careful engineering. Despite production adoption, a worldwide multimodal planner combining current information, constraints, costs, and personalization remains beyond current algorithms.

  • Progress: Modern road-network routing algorithms can be up to seven orders of magnitude faster than standard solutions.The survey attributes this progress to goal direction, hierarchy, and small separators rather than explicit vertex coordinates.
  • Lessons: Experiments on real data are essential because production-data properties may differ from simplified models and folklore assumptions.The survey gives turn penalties in Contraction Hierarchies as an example where a common performance belief proved wrong.
  • Lessons: Careful engineering helps routing algorithms exploit locality and parallelism across instructions, cores, and GPUs.The survey identifies CRP, CSA, HL, PHAST, and RAPTOR as examples.
  • Impact: Several surveyed approaches have entered mainstream production systems serving millions of users daily.The survey connects this adoption to routing-related projects at major technology and mapping companies.
  • Open challenges: A worldwide multimodal journey planner combining real-time and historic information, schedule constraints, monetary costs, and personalization remains beyond current algorithms.Existing systems such as Rome2Rio provide only a simplified first step toward that goal.
Loading 1504.05140v1…