A Totally Astar-based Multi-path Algorithm for the Recognition of Reasonable Route Set in Vehicle Navigation Systems

摘要

Compared with a Dijkstra-based or partially Astar-based one, a totally Astar-based algorithm is proposed in the paper for vehicle navigation systems. It has a better performance such as computing speed and veracity in a large-scale road network than a Dijkstra-based one because the computational complexity of Astar algorithm has little connection with the overall scale of a road network. To recognize all the reasonable routes between a specific OD pair, this algorithm takes all the geometrically reasonable routes into account and considers several constraints that meet the drivers’ preferences like circuitous route, the number of turning and traffic control strategy like no left turn as well. Two numerical examples demonstrate the operation and efficiency of the algorithm.