Improved TDCALT Algorithm Based On Pruning Strategy

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.

Key words:road network; shortest path algorithm; pruning strategy; time-dependent; speed up strategy