Shortest path with acceleration constraints: complexity and approximation algorithms

DOI10.1007/S10589-022-00403-WMaRDI QIDQ2082550zbMATH OpenOpenAlexWikidataFDO

Authors S. Ardizzoni, Luca Consolini, M. Laurini, Marco Locatelli

Publication date 4 October 2022

Published in Computational Optimization and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10589-022-00403-w

zbMATH Keywords

approximation algorithmscomplexityshortest pathspeed planning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Experimental and Efficient Algorithms
• Solution Algorithms for the Bounded Acceleration Shortest Path Problem
• Computing almost shortest paths (extended abstract)
• On Accuracy of Approximation for the Resource Constrained Shortest Path Problem
• Computing constrained shortest-paths at scale
• Computing almost shortest paths
• Shortest‐path methods: Complexity, interrelations and new propositions
• On the complexity of time-dependent shortest paths
• On the complexity of time-dependent shortest paths
• scientific article; zbMATH DE number 1114039

Cites work

• A dual algorithm for the constrained shortest path problem
• A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
• A reoptimization algorithm for the shortest path problem with time windows
• A solution of the minimum-time speed planning problem based on lattice theory
• An Appraisal of Some Shortest-Path Algorithms
• An optimal complexity algorithm for minimum-time velocity planning
• Bottleneck extrema
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Solution Algorithms for the Bounded Acceleration Shortest Path Problem
• The \(k\)-centrum shortest path problem
• The shortest path problem with forbidden paths
• Time-dependent shortest path problems with penalties and limits on waiting
• Time-dependent shortest paths with discounted waits
• Variants of shortest path problems

Cited in

(2)

• Delay-constrained shortest paths: approximation algorithms and second-order cone models
• Experimental and Efficient Algorithms

This page was built for publication: Shortest path with acceleration constraints: complexity and approximation algorithms

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