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