The use of various algorithms for finding paths in graphs to solve problems of spatial development of transport infrastructure
- Authors: Kuzmin D.V.1
-
Affiliations:
- The Russian University of Transport (RUT MIIT)
- Issue: No 2 (2025)
- Pages: 53-63
- Section: Modeling systems and processes
- URL: https://journals.rcsi.science/0201-727X/article/view/363097
- DOI: https://doi.org/10.46973/0201-727X_2025_2_53
- ID: 363097
Cite item
Full Text
Abstract
The question of the applicability of the Dijkstra algorithm, A* and Breadth-first search for solving pathfinding problems in environments with obstacles is considered. These algorithms can be used to solve problems of spatial development of linear objects of land transport infrastructure.
A series of simple experiments were conducted with the algorithms in order to quantify their asymptotic complexity, i.e. the number of operations performed and the execution time of the algorithm in conditions of pathfinding in environments with obstacles. The series of experiments has a different configuration, determined by the direction of the search (unidirectional and bidirectional) and the method of cell passage (direct and mixed) and a variant of the search algorithm. When considering the A* algorithm, various metrics such as Chebyshev, Manhattan, and Euclidean distances were used as an additional parameter configuring the algorithm's operation.
About the authors
D. V. Kuzmin
The Russian University of Transport (RUT MIIT)
Author for correspondence.
Email: kuzminmiit@yandex.ru
Candidate of Engineering Sciences, Associate Professor, Chair Logistics and Management of Transport Systems
References
- Erdinç A. İ., Ünal Ö., Aydın C. C. Automatic Pipeline Route Design with Multi-Criteria Evaluation Based on Least-Cost Path Analysis and Line-Based Cartographic Simplification: A Case Study of the Mus Project in Turkey // International Journal of Geo-Information (IJGI). – 2019. – Vol. 8 (4), No. 173. – doi: 10.3390/ijgi8040173.
- Kang J. Y., 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. – Vol. 9. – doi: 10.3390/ijgi8040173.
- Scaparra M. P., Church R. L., Medrano F. A. Corridor location: the multigateway shortest path // Journal of Geographical Systems. – 2014. – Vol. 16, No. 3. – P. 287–309. – doi: 10.1007/s10109-014-0197-8.
- Yu C., Lee J., Munro-Stasiuk M. Extensions to least-cost path algorithms for roadway planning // International Journal of Geographical Information Science. – 2003. – Vol. 17. – doi: 10.1080/1365881031000072645.
- Jamali A. A., 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. – Vol. 31. – doi: 10.1007/s41324-023-00539-9.
- Stefano B., Davide G., Francesco O. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts // Environmental Impact Assessment Review. – 2011. – Vol. 31, No. 3. – P. 234–239. – doi: 10.1016/j.eiar.2010.10.003.
- Monteiro C., Ramírez-Rosado I., Miranda V. [et al.]. GIS Spatial Analysis Applied to Electric Line Routing Optimization // IEEE Transactions on Power Delivery. – 2005. – Vol. 20. – P. 934–942. – doi: 10.1109/TPWRD.2004.839724.
- Antikainen H. Comparison of different strategies for determining raster-based least-cost paths with a minimum amount of distortion // Transactions in GIS. – 2013. – Vol. 17. – doi: 10.1111/j.1467-9671.2012.01355.x.
- Tomlin D. C. Propagating radial waves of travel cost in a grid // International Journal of Geographical Information Science. – 2010. – Vol. 24, Iss. 9. – P. 1391–1413. – doi: 10.1080/13658811003779152.
- Федеральный закон от 14.03.1995 № 33-ФЗ (ред. от 08.08.2024) «Об особо охраняемых природных территориях» (с изм. и доп., вступ. в силу с 01.03.2025). Статья 2. Категории особо охраняемых природных территорий, особенности их создания и развития // КонсультантПлюс. – URL: https://www.consultant.ru/document/cons_doc_LAW_6072/ce98ed9bc2fc35acee2232585948a2b4bc927850
- (дата обращения: 26.03.2025).
Supplementary files
