Engineering Route Planning Algorithms

DOI10.1007/978-3-642-02094-0_7zbMath1248.90017OpenAlexW2168148394WikidataQ55924035 ScholiaQ55924035MaRDI QIDQ3637315

Dominik Schultes, Peter Sanders, Dorothea Wagner, Daniel Delling

Publication date: 9 July 2009

Published in: Algorithmics of Large and Complex Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02094-0_7

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10)

Related Items

Bidirectional A* search on time-dependent road networks ⋮ Multiple-path selection for new highway alignments using discrete algorithms ⋮ GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU ⋮ A lower bound for the quickest path problem ⋮ Decremental algorithm for adaptive routing incorporating traveler information ⋮ Shells structure in uncorrelated scale-free networks ⋮ Finding near-optimal independent sets at scale ⋮ Point-to-point shortest paths on dynamic time-dependent road networks ⋮ Better Process Mapping and Sparse Quadratic Assignment ⋮ Unconstrained and curvature-constrained shortest-path distances and their approximation ⋮ Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication ⋮ Categorification of Negative Information using Enrichment ⋮ Optimization of heuristic search using recursive algorithm selection and reinforcement learning ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Line planning with user-optimal route choice ⋮ Time-dependent SHARC-routing ⋮ Shortest-path queries in static networks ⋮ Computation of the optimal value function in time-dependent networks ⋮ Core Routing on Dynamic Time-Dependent Road Networks ⋮ Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks ⋮ Candidate Sets for Alternative Routes in Road Networks ⋮ User-Constrained Multimodal Route Planning ⋮ Vertex labeling and routing for Farey-type symmetrically-structured graphs ⋮ Fast Computation of Point-to-Point Paths on Time-Dependent Road Networks ⋮ Efficient Large-Scale Multi-Drone Delivery using Transit Networks

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Planar graphs, negative weight edges, shortest paths, and near linear time
• The shortest route through a network with time-dependent internodal transit times
• Fast Routing in Road Networks with Transit Nodes
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Bidirectional A  ∗  Search for Time-Dependent Fast Paths
• Combining speed-up techniques for shortest-path computations
• Partitioning graphs to speedup Dijkstra's algorithm
• Efficient models for timetable information in public transportation systems
• Engineering Label-Constrained Shortest-Path Algorithms
• Fast and Compact Oracles for Approximate Distances in Planar Graphs
• Time-Dependent SHARC-Routing
• Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks
• Minimum time-dependent travel times with contraction hierarchies
• Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
• Engineering multilevel overlay graphs for shortest-path queries
• SHARC
• Engineering Highway Hierarchies
• Dijkstra's algorithm on-line
• Algorithms – ESA 2005
• Experimental and Efficient Algorithms
• Experimental and Efficient Algorithms
• Geometric containers for efficient shortest-path computation
• Algorithms - ESA 2003
• Integer priority queues with decrease key in constant time and the single source shortest paths problem