交通路况感知下的自适应动态路径规划方法

Adaptive Dynamic Path Planning Method Under Traffic Condition Awareness

针对传统路径规划算法在动态网络中的时效性和可用性不足,本文提出一种适用于时变路网环境下的自适应动态路径规划方法。通过引入动态网络流式图划分思想,构建一种分层路网的状态树索引,有效降低了动态路网中路径查找的计算代价,并扩展了传统路径规划算法在动态路网中的普适性。在此基础上,将区域路况的时空变化信息融合到索引树中,进一步提出一种基于时空层次网络的路径映射方法。并按照访问节点的距离逐步收缩最小包含区域来减少路径查找视野,将路径查找过程转化为在层次图中的小范围寻址。为适应路网动态变化特征,路径映射采用多路并行的双向探测策略,使得路径搜索迅速收敛于一个最优解,在动态路况变化和旅行代价之间寻求平衡。最后,结合北京市实时交通路网数据集进行实验评估,在查询性能和自适应调整方面验证了所提出方法的有效性。

Due to the lack of timeliness and usability of traditional path planning algorithms in dynamic networks,this paper proposes an adaptive path planning method applied to path selection under time-varying road conditions.By introducing a dynamic network flow graph partition,a state tree for hierarchical road network is constructed,which effectively reduces the computational cost of path finding and improves the usability of traditional path planning models in the dynamic road network.Then a path mapping method based on hierarchical network is further proposed by integrating the spatiotemporal variation of region conditions into the index.The path finding field of view can be reduced by gradually shrinking the minimum containment area according to the distance of the visited nodes,so that the path finding process can be transformed into small-scale addressing in the hierarchical graph.In order to accommodate the dynamic changes of the road network,the path finding adopts a forward and backward detection strategy with multiple parallel paths,which makes the path search converge rapidly to an optimal solution and seeks a balance between dynamic road condition and travel cost.Finally,we conduct an experimental evaluation with Beijing traffic dataset to verify the effectiveness of the proposed method in terms of the query performance and the adaptive adjustment.