Использование различных алгоритмов поиска пути в графах для решения задач пространственного развития транспортной инфраструктуры
https://doi.org/10.46973/0201-727X_2025_2_53
Аннотация
Рассмотрен вопрос применимости алгоритмов Дейкстры, A* и поиска в ширину для решения задач поиска пути в средах с препятствиями. Данные алгоритмы могут быть использованы при решении задач пространственного развития линейных объектов наземной транспортной инфраструктуры.
С алгоритмами проведена серия простых экспериментов с целью определения количественных показателей их асимптотической сложности, т. е. количества выполняемых операций и времени выполнения алгоритма в условиях поиска пути в средах с препятствиями. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленный), способом прохода ячеек (прямой и смешанный) и вариантом алгоритма поиска. При рассмотрении алгоритма A* в качестве дополнительного параметра, конфигурирующего работу алгоритма, были использованы различные метрики – расстояния Чебышева, манхэттенское, евклидово.
Об авторе
Д. В. Кузьмин
Российский университет транспорта (РУТ МИИТ)
Россия
Россия
Кузьмин Дмитрий Владимирович, кафедра «Логистика и управление транспортными системами», кандидат технических наук, доцент
Список литературы
1. Erdinç, 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/ijgi8040173
2. 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.
3. 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.
4. 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.
5. 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.
6. 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. –
7. 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.
8. 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.
9. 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.
10. Федеральный закон от 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).
Рецензия
Для цитирования:
Кузьмин Д.В. Использование различных алгоритмов поиска пути в графах для решения задач пространственного развития транспортной инфраструктуры. Вестник Ростовского государственного университета путей сообщения. 2025;(2):53-63. https://doi.org/10.46973/0201-727X_2025_2_53
For citation:
Kuzmin D.V. The use of various algorithms for finding paths in graphs to solve problems of spatial development of transport infrastructure. Vestnik Rostovskogo Gosudarstvennogo Universiteta Putej Soobshcheniya. 2025;(2):53-63. (In Russ.) https://doi.org/10.46973/0201-727X_2025_2_53
Просмотров:
11
JATS XML
Послать статью по эл. почте 