A shortest path algorithm with novel heuristics for dynamic transportation networks

Abstract

Finding an optimal route in dynamic real-time transportation networks is a critical problem for vehicle navigation. Existing approaches are either too complex or incapable of managing complex circumstances where both the location of a mobile object and traffic conditions change over time. In this paper, we propose an incremental search approach with novel heuristics based on a variation of the A* algorithm-Lifelong Planning A*. In addition, we suggest using an ellipse to prune the unnecessary nodes to be scanned in order to speed up the dynamic search process. The proposed algorithm determines the shortest-cost path between a moving object and its destination by continually adapting to the dynamic traffic conditions, while making use of the previous search results. Experimental results evince that the proposed algorithm performs significantly better than the well-known A* algorithm.