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

Improved TDCALT Algorithm Based On Pruning Strategy

摘要:

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

Abstract:

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