测绘学报

• 学术论文 • 上一篇    下一篇

顾及转向延误的时间依赖A*最短路径算法

郑年波; 陆锋; 李清泉; 段滢滢   

  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-10-25 发布日期:2010-10-25

The Adaption of A* Algorithm for Least-Time Paths in Time-Dependent Transportation Networks with Turn Delays

  • Received:1900-01-01 Revised:1900-01-01 Online:2010-10-25 Published:2010-10-25

摘要: 现有的动态路径规划算法通常只考虑当前时刻交通信息,而忽略了路段行程时间依赖于进入该路段的时刻这一现实。而且,转向延误的存在使得传统的基于节点标号的最短路径算法不再有效。本文建立了基于路段的时间依赖网络模型,将转向延误时间引入到FIFO(先进先出)条件的定义中,并给出了满足FIFO条件的路段到达时间和转向延误时间计算式。以此模型为基础,并通过将时间因子引入到启发式评价函数中,发展了基于路段标号的时间依赖A*最短路径算法。实验表明,所提出的算法能预测并回避即将发生的交通拥堵,有效节省用户的出行时间。而其平均计算时间仅比传统算法增加了10%左右。此外,由于不再需要进行频繁的路径重优化,该算法能大幅提高路径规划的整体效率。

Abstract: The shortest path algorithms used widely by dynamic route planners only consider traffic information at some definite moment so as to ignore the fact that the travel time along a link is dependent on the time to enter it. Besides, those traditional node-labelling shortest path algorithms are no longer effective in view of turn delays at intersections (or nodes). In this paper, a link-based time-dependent network model is built by re-defining the First-In-First-Out (FIFO) condition with turn delay time introduced into, and then a link-labelling time-dependent A* shortest path algorithm is developed by expanding the evaluation function to time dimension and applying Euclidian distance divided by maximum possible driving speed as the heuristic evaluator. An experiment on the real road network shows that the proposed algorithm is capable of forecasting and bypassing those forthcoming traffic congestions and then shortening travel time, only with a cost of about 10 percent more computational time than the traditional algorithms. Moreover, it is able to improve overall efficiency of route planning heavily because of its no longer need to the frequent path re-optimization processes.