基于剪枝策略的改进TDCALT算法

Improved TDCALT Algorithm Based on Pruning Strategy

针对大规模路网中求解最短路问题的低效性与非实时性,通过时间依赖性路网来刻画路网和交通状况信息,构造时间依赖性路网下的高效最短路算法.以目前效率较高的TDCALT(time dependent core-based A*landmarks triangleinequality)算法为基础,提出动态优化上限值的改进措施,并首次引入和改进静态路网下最短路算法中的剪枝策略,形成ITDCALT(improved TDCALT)算法.在广州市路网上的试验表明:ITDCALT算法在算法运行时间和搜索空间上均优于TDCALT算法和TDIJKSTRA(time-dependent DIJKSTRA)算法;ITDCALT算法具有计算效率高、搜索空间小、性能稳定的优点.

To address the inefficiency and non-real time of shortest path problem with large scale traffic road network, an efficient algorithm is developed under time-dependent road network which represents road network and traffic information. Based on time dependent core-based A＊ landmarks triangle inequality （TDCALT） algorithm which outperforms the other algorithms, improvement including updating upper bound dynamically and combining improved pruning strategy used in static shortest path algorithm is proposed. Finally a new algorithm called improved TDCALT （ITDCALT） is formed. Comparative analysis between ITDCALT, TDCALT and time-dependent DUKSTRA （TDIJKSTRA） in time-dependent road network of Gnangzhou shows that the proposed algorithm outperforms the others in terms of the efficiency, the search space and the stability.