vrgupВестник Ростовского государственного университета путей сообщенияVestnik Rostovskogo Gosudarstvennogo Universiteta Putej Soobshcheniya0201-727XРостовский государственный университет путей сообщения10.46973/0201-727X_2025_2_53vrgup-260Research ArticleМОДЕЛИРОВАНИЕ СИСТЕМ И ПРОЦЕССОВMODELING SYSTEMS AND PROCESSESИспользование различных алгоритмов поиска пути в графах для решения задач пространственного развития транспортной инфраструктурыThe use of various algorithms for finding paths in graphs to solve problems of spatial development of transport infrastructureКузьминД. В.KuzminD. V.

Кузьмин Дмитрий Владимирович, кафедра «Логистика и управление транспортными системами», кандидат технических наук, доцент

Kuzmin Dmitry Vladimirovich, Chair “Logistics and Management of Transport Systems”, Candidate of Engineering Sciences, Associate Professor

kuzminmiit@yandex.ruРоссийский университет транспорта (РУТ МИИТ)The Russian University of Transport (RUT MIIT)202530062025025363Copyright © Кузьмин Д.В., 20252025Кузьмин Д.В.Kuzmin D.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.rgups.ru/jour/article/view/260

Рассмотрен вопрос применимости алгоритмов Дейкстры, A* и поиска в ширину для решения задач поиска пути в средах с препятствиями. Данные алгоритмы могут быть использованы при решении задач пространственного развития линейных объектов наземной транспортной инфраструктуры.

С алгоритмами проведена серия простых экспериментов с целью определения количественных показателей их асимптотической сложности, т. е. количества выполняемых операций и времени выполнения алгоритма в условиях поиска пути в средах с препятствиями. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленный), способом прохода ячеек (прямой и смешанный) и вариантом алгоритма поиска. При рассмотрении алгоритма A* в качестве дополнительного параметра, конфигурирующего работу алгоритма, были использованы различные метрики – расстояния Чебышева, манхэттенское, евклидово.

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 al gorithm's operation.

алгоритмы поиска путиалгоритм Дейкстрыалгоритм A*алгоритм поиска в ширинутрассированиепространственное развитие транспортной инфраструктурытранспортные системытеория графовpathfinding algorithmsDijkstra's algorithmA* algorithmBreadth-first search algorithmtracingspatial development of transport infrastructuretransport systemsgraph theoryReferencesErdinç, A. İ. 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 / Ali İhsan Erdinç Örsan Ünal, Cevdet Coşkun Aydın // International Journal of Geo-Information (IJGI). – 2019. – Vol. 8 (4), No. 173. – DOI 10.3390/ijgi8040173Erdinç, A. İ. 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 / Ali İhsan Erdinç Örsan Ünal, Cevdet Coşkun Aydın // International Journal of Geo-Information (IJGI). – 2019. – Vol. 8 (4), No. 173. – DOI 10.3390/ijgi8040173Kang, J. Y. Optimisation of pipeline route in the presence of obstacles based on a least cost path algorithm and Laplacian smoothing / J. Y. Kang, B. Lee // International Journal of Naval Architecture and Ocean Engineering. – 2017. – Vol. 9. – DOI 10.3390/ijgi8040173.Kang, J. Y. Optimisation of pipeline route in the presence of obstacles based on a least cost path algorithm and Laplacian smoothing / J. Y. Kang, B. Lee // International Journal of Naval Architecture and Ocean Engineering. – 2017. – Vol. 9. – DOI 10.3390/ijgi8040173.Scaparra, M. P. Corridor location: the multigateway shortest path / M. P. Scaparra, R. L. Church, F. A. Medrano // Journal of Geographical Systems. – 2014. – Vol. 16, No. 3. – P. 287–309. – DOI 10.1007/s10109-014-0197-8.Scaparra, M. P. Corridor location: the multigateway shortest path / M. P. Scaparra, R. L. Church, F. A. Medrano // Journal of Geographical Systems. – 2014. – Vol. 16, No. 3. – P. 287–309. – DOI 10.1007/s10109-014-0197-8.Yu, C. Extensions to least-cost path algorithms for roadway planning / C. Yu, J. Lee, M. Munro-Stasiuk // International Journal of Geographical Information Science. – 2003. – Vol. 17. – DOI 10.1080/1365881031000072645.Yu, C. Extensions to least-cost path algorithms for roadway planning / C. Yu, J. Lee, M. Munro-Stasiuk // International Journal of Geographical Information Science. – 2003. – Vol. 17. – DOI 10.1080/1365881031000072645.Path selection by topographic analysis: vector re-classification versus raster fuzzification as spatial multi-criteria using cost-path / A. A. Jamali, A. Esmailian, S. Mokhtarisabet, S. He // Spatial Information Research. – 2023. – Vol. 31. – DOI 10.1007/s41324-023-00539-9.Path selection by topographic analysis: vector re-classification versus raster fuzzification as spatial multi-criteria using cost-path / A. A. Jamali, A. Esmailian, S. Mokhtarisabet, S. He // Spatial Information Research. – 2023. – Vol. 31. – DOI 10.1007/s41324-023-00539-9.Stefano, B. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts / B. Stefano, G. Davide, O. Francesco // Environmental Impact Assessment Review. – 2011. – Vol. 31, No. 3. – P. 234–239. DOI 10.1016/j.eiar.2010.10.003. –Stefano, B. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts / B. Stefano, G. Davide, O. Francesco // Environmental Impact Assessment Review. – 2011. – Vol. 31, No. 3. – P. 234–239. DOI 10.1016/j.eiar.2010.10.003. –GIS Spatial Analysis Applied to Electric Line Routing Optimization / C. Monteiro, I. Ramírez-Rosado, V. Miranda [et al.] // IEEE Transactions on Power Delivery. – 2005. – Vol. 20. – P. 934–942. – DOI 10.1109/TPWRD.2004.839724.GIS Spatial Analysis Applied to Electric Line Routing Optimization / C. Monteiro, I. Ramírez-Rosado, V. Miranda [et al.] // 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 / H. Antikainen // Transactions in GIS. – 2013. – Vol. 17. – DOI 10.1111/j.14679671.2012.01355.x.Antikainen, H. Comparison of different strategies for determining raster‐based least‐cost paths with a minimum amount of distortion / H. Antikainen // Transactions in GIS. – 2013. – Vol. 17. – DOI 10.1111/j.14679671.2012.01355.x.Tomlin, D. C. Propagating radial waves of travel cost in a grid / Dana C. Tomlin // International Journal of Geographical Information Science. – 2010. – Vol. 24, Iss. 9. – P. 1391–1413. – DOI 10.1080/13658811003779152.Tomlin, D. C. Propagating radial waves of travel cost in a grid / Dana C. Tomlin // 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/ce98ed9bc2fc35acee2232585948a2b4b927850 (дата обращения: 26.03.2025).Federal Law No. 33-FZ of 03/14/1995 (as amended on 08/08/2024) “On Specially Protected Natural Territories” (as amended and supplemented, effective from 03/01/2025). Article 2. Categories of specially protected natural territories, peculiarities of their creation and development // ConsultantPlus. – URL: https://www.consultant.ru/document/cons_doc_LAW_6072/ce98ed9bc2fc35acee2232585948a2b4bс927850 (date of access: 03/26/2025).

The authors declare that there are no conflicts of interest present.