摘要：AbstractCompared 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 turns and traffic control strategy (for example, no left turn). Two numerical examples demonstrate the operation and efficiency of the algorithm.
关键词：Multi-path Algorithm;A-star;Route navigation systems
