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 ϵ. Finally, we present some computational experiments to evaluate the performance of the proposed approximation algorithm.

Shortest path with acceleration constraints: complexity and approximation algorithms / Ardizzoni, S.; Consolini, L.; Laurini, M.; Locatelli, M.. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 83:2(2022), pp. 555-592. [10.1007/s10589-022-00403-w]

Shortest path with acceleration constraints: complexity and approximation algorithms

Ardizzoni S.;Consolini L.;Laurini M.;Locatelli M.
2022-01-01

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 ϵ. Finally, we present some computational experiments to evaluate the performance of the proposed approximation algorithm.
2022
Shortest path with acceleration constraints: complexity and approximation algorithms / Ardizzoni, S.; Consolini, L.; Laurini, M.; Locatelli, M.. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 83:2(2022), pp. 555-592. [10.1007/s10589-022-00403-w]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2932183
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact