A New Algorithm Based on Dijkstra for Vehicle Path Planning Considering Intersection Attribute

Abstract

Vehicle path planning is a key issue for car navigation systems. When path planning, considering the time spent at intersections is more in line with the actual situation, so it is of practical significance to study the path planning problem take account intersection attributes. In this article, we study the problem in a deterministic network, taking the minimization of travel time from the origin to the destination as the optimization goal. For this purpose, we construct a mathematical model for the problem. This paper proposes a reverse labeling Dijkstra algorithm (RLDA) based on traditional Dijkstra algorithm to solve the problem, it is proved that the correctness of the RLDA algorithm theoretically, and analyze that the RLDA algorithm has a lower polynomial time complexity. Finally, we selected the actual road network as the simulation experiment object to verify the effectiveness of the algorithm searching for the optimal path. And select 10 groups of networks of different sizes and conduct extensive experiments to compare the convergence efficiency and calculation speed between RLDA and PSO, GA, ACO, NNA, OPABRL. The statistical results show that the convergence rate of the RLDA algorithm is better than that of ACO, NNA, and GA. When the number of network nodes is less than 350, the algorithm has the smallest running time.

Keywords

• Path planning
• intersection attribute
• reverse labeling Dijkstra algorithm
• deterministic network