An efficient algorithm for computing least cost paths with turn constraints

DOI10.1016/S0020-0190(98)00134-3MaRDI QIDQ293389zbMATHOpenAlexFDO

Authors Ali Boroujerdi, Jeffrey Uhlmann

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001343?np=y

zbMATH Keywords

computational complexityrange searchingshortest pathsroutingDijkstra's algorithmleast cost pathsturn constraints

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• Fast computation of optimal paths using a parallel Dijkstra algorithm with embedded constraints
• A Shortest Path Algorithm Based on Limited Search Heuristics
• Route planning with turn restrictions: A computational experiment
• scientific article; zbMATH DE number 1870068
• Computing the shortest path: \(A^\ast\) search meets graph theory

Cites work

• Dynamic fractional cascading

Cited in

(11)

• Traversing a set of points with a minimum number of turns
• Solving an urban waste collection problem using ants heuristics
• Optimal on-line algorithms for walking with minimum number of turns in unknown streets
• scientific article; zbMATH DE number 1870068 (Why is no real title available?)
• An algorithm to determine a path with minimal cost/capacity ratio
• Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment
• Route planning with turn restrictions: A computational experiment
• Terracost: computing least-cost-path surfaces for massive grid terrains
• Trajectory planning for unmanned aerial vehicles: a network optimization approach
• Traversing a set of points with a minimum number of turns
• Customizable contraction hierarchies with turn costs

This page was built for publication: An efficient algorithm for computing least cost paths with turn constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293389)