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

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

扫码查看
针对大规模路网中求解最短路问题的低效性与非实时性,通过时间依赖性路网来刻画路网和交通状况信息,构造时间依赖性路网下的高效最短路算法.以目前效率较高的TDCALT(time dependent core-based A* landmarks triangle inequality)算法为基础,提出动态优化上限值的改进措施,并首次引入和改进静态路网下最短路算法中的剪枝策略,形成ITDCALT(improved TDCALT)算法,在广州市路网上的试验表明:ITDCALT算法在算法运行时间和搜索空间上均优于TDCALT算法和TDIJKSTRA(time-dependent DIJKSTRA)算法;ITDCALT算法具有计算效率高、搜索空间小、性能稳定的优点.
Improved TDCALT Algorithm Based on Pruning Strategy
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 (TDLJKSTRA) in time-dependent road network of Guangzhou shows that the proposed algorithm outperforms the others in terms of the efficiency, the search space and the stability.

shortest path algorithmpruning strategy, time-dependentspeed up strategy

钟慧玲、章梦、石永强、蔡文学

展开 >

华南理工大学经济与贸易学院,广东广州510006

路网最短路算法 剪枝策略 时间依赖性 加速策略

广东省自然科学基金教育部人文社会科学研究规划项目教育部人文社会科学研究规划项目广东省现代信息服务业发展专项资金扶持项目

S201101000127412YJAZH20910YJC79011606120840B0450124/2

2012

同济大学学报(自然科学版)
同济大学

同济大学学报(自然科学版)

CSTPCDCSCD北大核心EI
影响因子:0.88
ISSN:0253-374X
年,卷(期):2012.40(8)
  • 2
  • 1