The purpose of this work is to introduce and characterize the Bounded Acceleration Shortest Path (BASP) problem, a generalization of the Shortest Path (SP) problem. This problem is associated to a graph: the nodes represent positions of a mobile vehicle and the arcs are associated to pre-assigned geometric paths that connect these positions. BASP consists in finding the minimum-time path between two nodes. Differently from SP, we require that the vehicle satisfy bounds on maximum and minimum acceleration and speed, that depend on the vehicle position on the currently traveled arc. We prove that BASP is NP-hard and define solution algorithm that achieves polynomial time-complexity under some additional hypotheses on problem data.
翻译:这项工作的目的是介绍和说明“环绕加速最短路径”问题,即“最短路径”问题的一般化问题。这个问题与图表有关:节点代表移动车辆的位置,弧与连接这些位置的预先指定的几何路径有关。“最短路径”是指在两个节点之间找到最短时间路径。与“最短路径”不同,我们要求车辆在最大和最低加速速度方面满足限制,这取决于目前行驶弧上的车辆位置。我们证明,“最短路径”是“最硬”的,我们确定解决方案算法,在问题数据的某些额外假设下实现多米时间兼容性。