Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Workshop on Engineering Applications

• Publication date

  2008-05-30

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1007/978-3-540-68552-4_24
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• TO PLANAR GRAPHS

  2010cited by this paper
• Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm

  2008influential reference
• Route Planning in Road Networks

  2008influential reference
• Better Approximation of Betweenness Centrality

  2008cited by this paper
• SHARC: Fast and robust unidirectional routing

  2008cited by this paper
• Mobile Route Planning

  2008cited by this paper
• Better Landmarks Within Reach

  2007cited by this paper
• Dynamic Highway-Node Routing

  2007influential reference
• Computing Many-to-Many Shortest Paths Using Highway Hierarchies

  2007influential reference
• Engineering Fast Route Planning Algorithms

  2007cited by this paper
• Fast Routing in Road Networks with Transit Nodes

  2007cited by this paper
• Fast Point-to-Point Shortest Path Computations with Arc-Flags

  2006cited by this paper
• Reach for A*: Efficient Point-to-Point Shortest Path Algorithms

  2006influential reference
• Goal-directed shortest-path queries using precomputed cluster distances

  2006cited by this paper
• Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings

  2006cited by this paper
• An Experimental Evaluation of Point-To-Point Shortest Path Calculation on Road Networks with Precalculated Edge-Flags

  2006cited by this paper
• Highway hierarchies star

  2006cited by this paper
• Highway Hierarchies Hasten Exact Shortest Path Queries

  2005cited by this paper
• Computing the shortest path: A search meets graph theory

  2005cited by this paper
• Computing Point-to-Point Shortest Paths from External Memory

  2005cited by this paper
• Acceleration of Shortest Path and Constrained Shortest Path Computation

  2005cited by this paper
• Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings

  2005cited by this paper
• Partitioning Graphs to Speed Up Dijkstra's Algorithm

  2005cited by this paper
• Multiple-source shortest paths in planar graphs

  2005cited by this paper
• Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks

  2004cited by this paper
• Planar graphs, negative weight edges, shortest paths, and near linear time

  2001cited by this paper
• A set of measures of centrality based upon betweenness

  1977cited by this paper
• The rush in a directed graph

  1971cited by this paper
• Shortest Paths

  1968cited by this paper
• A Formal Basis for the Heuristic Determination of Minimum Cost Paths

  1968cited by this paper
• Linear programming and extensions

  1965cited by this paper
• A note on two problems in connexion with graphs

  1959influential reference

• COL-Trees: Efficient Hierarchical Object Search in Road Networks

  2026cites this paper
• Resilience analysis of multi-level highway networks under disruptions

  2026cites this paper
• An Empirical Survey and Benchmark of Learned Distance Indexes for Road Networks

  2026cites this paper
• EAR-MM: An Efficient Adaptive and Robust Algorithm for Streaming Map Matching

  2026cites this paper
• CONCERTO: Constrained Linear Multi-Objective Routing Path Optimization

  2025cites this paper
• Optimization Framework for Contraction Hierarchies Preprocessing for Efficient Path Indexing in Urban Road Networks

  2025cites this paper
• Enhancing Last-Mile Logistics: AI-Driven Fleet Optimization, Mixed Reality, and Large Language Model Assistants for Warehouse Operations

  2025cites this paper
• An Overview of Path Queries on Graphs

  2025cites this paper
• Techniques for Practical Parallel BFS and SSSP

  2025cites this paper
• PAV-A-kNN: A Novel Approachable kNN Query Method in Road Network Environments

  2025cites this paper
• Efficient Route and Area Matching Query in Dynamic Road Networks

  2025cites this paper
• Efficient Algorithms for Approximate k-Radius Coverage Query on Large-Scale Road Networks

  2025cites this paper
• Accelerating Shortest Path Counting on Road Networks

  2025cites this paper
• Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs

  2025cites this paper
• Physical Complexity of a Cognitive Artifact

  2025cites this paper
• Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs

  2025cites this paper
• Optimal route search using the hamiltonian circuit algorithm for assessing vehicular pollution and public health impacts in urban corridors

  2025cites this paper
• GeoLayer: Towards Low-Latency and Cost-Efficient Geo-Distributed Graph Stores with Layered Graph

  2025cites this paper
• FAHL: An Efficient Labeling Index for Flow-Aware Shortest Path Querying in Road Networks

  2025cites this paper
• Integrated Balanced and Staggered Routing in Autonomous Mobility-on-Demand Systems

  2025cites this paper
• Exploring the interplay between population profile and optimal routes in U.S. cities

  2025cites this paper
• Optimizing Dijkstra’s Algorithm: Enhancing Pathfinding Efficiency Through Heuristics and Structural Techniques

  2025influential citation
• Assessing the complexity of a path search optimization method based on clustering for a transport graph

  2025cites this paper
• QoT-aware multi-constraint routing in large-scale optical networks based on contraction hierarchies and propagation chains

  2025cites this paper
• Leveraging Call Detail Records to Uncover Azimuth Configuration Errors in Cellular Networks

  2025cites this paper
• Graph coarsening for fugitive interception

  2025cites this paper
• Traffic Anomaly Detection via Trajectory-Augmented Dynamics and Joint Spatiotemporal Transformer

  2025cites this paper
• SCG-tree: shortcut enhanced graph hierarchy tree for efficient spatial queries on massive road networks

  2025cites this paper
• Predictive Spike Timing Enables Distributed Shortest Path Computation in Spiking Neural Networks

  2025cites this paper
• FedRoad: Secure and Efficient Road Network Queries over Traffic Data Federation

  2025influential citation
• UAV Group Distribution Route Optimization Under Time‐Varying Weather Network

  2025cites this paper
• Sustainable Planning of Pick-up and Delivery for Waste Collection

  2025cites this paper
• SPHERE: Spherical partitioning for large-scale routing optimization

  2025cites this paper
• Large-Scale Optical Networks Fast Routing: a Modified Contraction Hierarchy Approach for Path Recovery

  2025influential citation
• Discovering environmental health effects of transport scenarios through agent-based simulations.

  2025cites this paper
• Cluster-based route planning for electric vehicles travel time optimization

  2025cites this paper
• Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks

  2025cites this paper
• Efficient Alternative Route Planning in Road Networks

  2024cites this paper
• A hierarchical model with hexagon grids for multi-objective route planning in large-scale off-road environments

  2024cites this paper
• Multi-Agent Reinforcement Learning with Hierarchical Coordination for Emergency Responder Stationing

  2024cites this paper
• Guards: Benchmarks for weighted grid-based pathfinding

  2024cites this paper
• Staggered routing in autonomous mobility-on-demand systems

  2024influential citation
• A Survey of Route Recommendations: Methods, Applications, and Opportunities

  2024cites this paper
• FulBM: Fast Fully Batch Maintenance for Landmark-based 3-hop Cover Labeling

  2024cites this paper
• Metaverse for smart cities: A surveys

  2024cites this paper
• Efficient Stochastic Routing in Path-Centric Uncertain Road Networks

  2024cites this paper
• First Passage Percolation with Queried Hints

  2024cites this paper
• Heterogeneous Modular Traffic Prediction Based on Multilayer Graph Convolutional Network

  2024cites this paper
• Avoiding Node Re-Expansions Can Break Symmetry Breaking

  2024cites this paper
• Machine learning for predictions of road traffic accidents and spatial network analysis for safe routing on accident and congestion-prone road networks

  2024cites this paper
• Timetable Nodes for Public Transport Network

  2024cites this paper
• Electric Vehicle Charging Guidance Strategy Considering “Traffic Network-Charging Station-Driver” Modeling: A Multiagent Deep Reinforcement Learning-Based Approach

  2024cites this paper
• Distribution Hub Optimization: Application of Conditional P-Median Using Road Network Distances

  2024cites this paper
• High Throughput Shortest Distance Query Processing on Large Dynamic Road Networks

  2024influential citation
• TrajRoute: Rethinking Routing with a Simple Trajectory-Based Approach – Forget the Maps and Traffic!

  2024cites this paper
• Graph-theoretical approach to the eigenvalue spectrum of perturbed higher-order exceptional points

  2024cites this paper
• Optimal Planning of Electric Vehicle Charging Stations: Integrating Public Charging Networks and Transportation Congestion

  2024cites this paper
• Efficient processing of coverage centrality queries on road networks

  2024cites this paper
• We Keep an Eye on You! How High-Tech Security Assets Help Police Forces Make Cities Safer

  2024cites this paper
• Space-time tree: a spatiotemporal construct for efficient similarity matrix calculations among network-constrained trajectories

  2024cites this paper
• Optimal Honeypot Allocation Using Core Attack Graph in Partially Observable Stochastic Games

  2024cites this paper
• Eco-Friendly Route Planning Algorithms: Taxonomies, Literature Review and Future Directions

  2024cites this paper
• DDR: A Deadline-Driven Routing Protocol for Delay Guaranteed Service

  2024cites this paper
• Routing with Massive Trajectory Data

  2024cites this paper
• Parallel Contraction Hierarchies Construction on Road Networks

  2024influential citation
• Managing the Future: Route Planning Influence Evaluation in Transportation Systems

  2024cites this paper
• A well-separated pair decomposition for low density graphs

  2024cites this paper
• Parallel Contraction Hierarchies Can Be Efficient and Scalable

  2024cites this paper
• Dynamic learning-based search for multi-criteria itinerary planning

  2024cites this paper
• The role of transport systems in housing insecurity: a mobility-based analysis

  2024cites this paper
• A Note on Computing Betweenness Centrality from the 2-core

  2024cites this paper
• A comparative measurement study of cross-layer 5G performance under different mobility scenarios

  2024cites this paper
• SUMMIT: A multi-modal agent-based co-simulation of urban public transport with applications in contingency planning

  2023cites this paper
• Granularity of origins and clustering destinations in indoor wayfinding

  2023cites this paper
• Analysis of Shortest Routing and Waiting Time of Electric Vehicle Charging Stations

  2023cites this paper
• Least cost path analysis as an objective and automatic method to define the main fault trace for probabilistic fault displacement hazard analyses

  2023cites this paper
• Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks

  2023cites this paper
• Individual Path Recommendation Under Public Transit Service Disruptions Considering Behavior Uncertainty

  2023cites this paper
• Routing in Multimodal Transportation Networks with Non-scheduled Lines

  2023cites this paper
• Designing SafeMap Based on City Infrastructure and Empirical Approach: Modified A-Star Algorithm for Earthquake Navigation Application

  2023cites this paper
• Network Fundamental Diagram based Dynamic Routing in a Clustered Network

  2023cites this paper
• A rapid globe-wide shortest route planning algorithm based on two-layer oceanic shortcut network considering great circle distance

  2023cites this paper
• Timing co-evolutionary path optimisation method for emergency vehicles considering the safe passage

  2023cites this paper
• Stochastic Routing with Arrival Windows

  2023influential citation
• Siting and Sizing Charging Infrastructure for Electric Vehicles With Coordinated Recharging

  2023cites this paper
• Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks

  2023cites this paper
• Label-constrained shortest path query processing on road networks

  2023cites this paper
• Time-variant road network-based bridgelets

  2023cites this paper
• Highway Systems: How Good are They, Really?

  2023cites this paper
• A Universal Scheme for Dynamic Partitioned Shortest Path Index: Survey, Improvement, and Experiments

  2023cites this paper
• A Universal Scheme for Partitioned Dynamic Shortest Path Index

  2023cites this paper
• Reinforcement Learning based Tree Decomposition for Distance Querying in Road Networks

  2023cites this paper
• Towards Efficient Shortest Path Counting on Billion-Scale Graphs

  2023cites this paper
• Experimental Evaluation of Indexing Techniques for Shortest Distance Queries on Road Networks

  2023cites this paper
• Efficiently computing alternative paths in game maps

  2023cites this paper
• Global Routing Optimization In Road Networks

  2023cites this paper
• Finding Top-k Optimal Routes with Collective Spatial Keywords on Road Networks

  2023cites this paper
• Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies

  2023influential citation
• Optimal Pathfinding on Weighted Grid Maps

  2023cites this paper
• Polestar++: An Intelligent Routing Engine for National-Wide Public Transportation

  2023cites this paper