doctoral candidate from 01.01.2012 until now
Moscow, Moscow, Russian Federation
UDC 656.022
Russian Library and Bibliographic Classification 398
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.
algorithm A*, tracing, development, transport infrastructure, system, theory, graphs
1. Automatic pipeline route design with multi-criteria evaluation based on least-cost path analysis and line-based cartographic simplification: case study of the Mus project in Turkey [Internet]. 2023 [cited 2023 Oct 23]. Available from: https://www.mdpi.com/2220-9964/8/4/173
2. Kang JY, Lee B. Optimisation of pipeline route in the presence of obstacles based on a least cost path algorithm and laplacian smoothing. International Journal of Naval Architecture and Ocean Engineering. 2017;9.
3. Scaparra MP, Church RL, Medrano FA. Corridor location: the multi-gateway shortest path model. Journal of Geographical Systems. 2014;16(3):287-309.
4. Yu C, Lee J, Munro-Stasiuk M. Extensions to least-cost path algorithms for roadway planning. International Journal of Geographical Information Science – GIS. 2003;17.
5. Jamali AA, Esmailian A, Mokhtarisabet S, He S. Path selection by topographic analysis: vector re-classification versus raster fuzzification as spatial multi-criteria using cost-path. Spatial Information Research. 2023;31.
6. Stefano B, Davide G, Francesco O. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts | Request PDF: Environmental Impact Assessment Review. 2011;31(3):234-239.
7. Monteiro C, Ramírez-Rosado I, Miranda V, Zorzano-Santamaria PJ, García-Garrido E, Fernandez-Jimenez L. GIS spatial analysis applied to electric line routing optimization. Power Delivery, IEEE Transactions. 2005;20:934-942.
8. Antikainen H. Comparison of different strategies for determining raster‐based least‐cost paths with a inimum amount of distortion. Transactions in GIS. 2013;17.
9. Dana T. Propagating radial waves of travel cost in a grid. International Journal of Geographical Information Science. 2010;24(9):1391-1413.
