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

doi:10.1109/ACCESS.2021.3053169

Return

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

2021-01-01

Zhu, Dan-Dan *

Sun, Jun-qing

DOI：10.1109/ACCESS.2021.3053169

Original

Save

View PDF

Abstract

En 中文

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:

Roads

Heuristic algorithms

Optimization

Transportation

Path planning

Machine learning algorithms

Particle swarm optimization

Path planning

intersection attribute

reverse labeling Dijkstra algorithm

deterministic network

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.