算法研究探讨 | 优化时间窗改进Dijkstra算法的无人驾驶磁悬浮车路径规划
算法研究探讨 | 优化时间窗改进Dijkstra算法的无人驾驶磁悬浮车路径规划
摘要:针对无人驾驶磁悬浮车同轨道多车运营及车辆密度大的特点,研究了一种基于优化时间窗改进Dijkstra算法的磁浮车路径规划算法,考虑了路径冲突、调度成本等一系列现实问题,将Dijkstra算法与时间窗相结合,顺序规划各磁浮车的路径。首先,在路径规划前预处理地图信息,根据地图节点生成最短路径索引,按照索引寻找路径。其次,利用时间窗校验路径冲突;然后,对冲突路径具体分析,冲突时间较短的路径通过车辆变速方式实现避让,避免了路径重规划,在无碰撞的基础上订单运行时间得到了优化。最后,利用OpenTCS进行算法仿真。结果表明:优化时间窗后的Dijkstra算法平均执行时间为 0.328ms ,车辆每千米运行时间为 36.64s 。在无路径冲突的前提下,提高了订单执行的实时性及车辆运行效率,且随着运行里程数的增加,算法的优势越明显,能满足无人驾驶磁悬浮车的无碰撞路径规划要求。