SOLVING THE PROBLEM OF SPATIAL DEVELOPMENT OF GROUND TRANSPORTATION INFRASTRUCTURE USING PATHFINDING ALGORITHM A*
Dmitriy Kuz'min · Transport engineering · 2025
Problem. The issue of applying A* algorithm for solving pathfinding problems in spatial development of linear objects of land transport infrastructure is considered. Study objective. Determining the most preferred configuration of pathfinding algorithm for solving the problem of spatial development of linear transport infrastructure. Research methods. A* algorithm is widely used for various graph theory applications, including tracing and path planning. The novelty of the work. A number of simple experiments were carried out with the algorithm in order to determine quantitative indicators of its asymptotic complexity, i.e. the number of operations performed and the algorithm time. The set of experiments has a different configuration, determined by the direction of the search (unidirectional and bidirectional), the search metric (Euclidean distance, Manhattan distance, Chebyshev distance) and the method of cell passing (direct and mixed). Research results and conclusions. In general, it can be concluded that bidirectional search requires about 19.17% fewer operations than unidirectional search. Manhattan distance and Chebyshev distance show similar results in terms of path length and execution time. Euclidean distance allows finding a shorter path, but it may take longer to complete.