Shortest path with acceleration constraints: complexity and approximation algorithms

S. Ardizzoni, L. Consolini, M. Laurini and M. Locatelli ()
Additional contact information
S. Ardizzoni: Università degli Studi di Parma
L. Consolini: Università degli Studi di Parma
M. Laurini: Università degli Studi di Parma
M. Locatelli: Università degli Studi di Parma

Computational Optimization and Applications, 2022, vol. 83, issue 2, No 6, 555-592

Abstract: Abstract We introduce a variant of the Shortest Path Problem (SPP), in which we impose additional constraints on the acceleration over the arcs, and call it Bounded Acceleration SPP (BASP). This variant is inspired by an industrial application: a vehicle needs to travel from its current position to a target one in minimum-time, following pre-defined geometric paths connecting positions within a facility, while satisfying some speed and acceleration constraints depending on the vehicle position along the currently traveled path. We characterize the complexity of BASP, proving its NP-hardness. We also show that, under additional hypotheses on problem data, the problem admits a pseudo-polynomial time-complexity algorithm. Moreover, we present an approximation algorithm with polynomial time-complexity with respect to the data of the original problem and the inverse of the approximation factor $$\epsilon$$ ϵ . Finally, we present some computational experiments to evaluate the performance of the proposed approximation algorithm.

Keywords: Shortest path; Speed planning; Complexity; Approximation algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00403-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:83:y:2022:i:2:d:10.1007_s10589-022-00403-w

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-022-00403-w

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().