Graph-Based Route Planning for Map Navigation Using Shortest-Path Algorithms

Abstract

Map navigation and graph-based path planning are the foundations of intelligent transportation systems today, supporting all kinds of applications in daily life, logistics and emergency rescue. A spatially weighted graph of the real road network is built in the system, and then the best path is selected based on the weights of these factors. This paper will introduce the main methods of the study and first present road-network models that combine static data from sources such as OpenStreetMap with dynamic Global Positioning System (GPS) trajectory data to construct and update weighted directed graphs. Next, this paper will introduce the basic and advanced shortest-path algorithms for static and dynamic urban environments, such as Dijkstra's algorithm, A* algorithm, etc., and compare their strengths and weaknesses. The following are the steps of the whole navigation workflow, as well as data preprocessing, multi-source fusion and execution of multi-objective path search. Lastly, this paper will also discuss the current deficiencies and problems in the above methods, such as missing data, algorithmic complexity of large-scale networks, trade-offs in multi-objective optimisation, GPS errors and user privacy, etc. Graph theory, spatial data science and optimisation algorithms have been combined to provide the theoretical basis for intelligent path planning in this paper and offer a reference for future research on lightweight, high-efficiency dynamic navigation.