时变公路网络的动态路径规划算法

摘要 为解决时变公路网络的路径规划问题，以地标导向技术和动态最短路径树为基础，提出一种改进的三角启发式算法.在预处理阶段构造各地标的最短路径树，并计算地标与其它节点之间的距离；在点对点的启发式路径规划过程中使用最短路径树优化查询；当网络发生边权值变化时，动态更新最短路径树，同时利用树的结构特性减少冗余计算.实验结果表明，所提算法不仅在查询效率上取得了比三角启发式算法等经典静态最短路径算法更好的表现，并且拥有比传统动态最短路径树更新算法更高效的更新策略.理论分析证明了此算法在动态应用场景中的鲁棒性和准确性