An Efficient Approach for Shortest Path Planning in Automotive Navigation System

Abstract

Emerging automotive engineering solutions extensively rely on navigation tools. Shortest path evaluation is core competency of optimal path planning, one of the most critical component of any navigation application. Fibonacci heap variant of state-of-the-art Dijkstra’s algorithm solve single source shortest path problems in asymptotic O(E + V log V) worst-case time. In spite Fibonacci heap is theoretically dominant in time efficiency, it might not work much better empirically with real-world data, because although large and intricate, the real-world road network graphs are sparse and the graph topology greatly affects the performance of the algorithms. SGO algorithm, a more efficient approch to address single source shortest path problem, is applied to solve optimal path planning problem in automotive navigation applications. Each road segment of the road graph leads to a particular location thus will hold unique distance values all the time. The SGO calculates the total distance from start location to the end of the each road segment and evaluates shortest path based on these calculations. The SGO algorithm and the Fibonacci and Binary heap variants of Dijkstra’s algorithm were tested on real-world intercity and intra-city road network graphs to evaluate running time efficiency of the algorithms in automotive navigation systems. The experimental results show that the SGO algorithm outperformed both the variants. The empirical superiority of the SGO algorithm suggests its usefulness in automotive navigation systems.