关键词: 智能交通, 动态规划, 路径索引, 路况感知, 最短路径

Abstract: 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.

Key words: intelligent transportation, dynamic planning, path indexing, traffic condition awareness, shortest path