Использование различных алгоритмов поиска пути в графах для решения задач пространственного развития транспортной инфраструктуры
- Авторы: Кузьмин Д.В.1
-
Учреждения:
- Российский университет транспорта (РУТ МИИТ)
- Выпуск: № 2 (2025)
- Страницы: 53-63
- Раздел: Моделирование систем и процессов
- URL: https://bakhtiniada.ru/0201-727X/article/view/363097
- DOI: https://doi.org/10.46973/0201-727X_2025_2_53
- ID: 363097
Цитировать
Полный текст
Аннотация
Рассмотрен вопрос применимости алгоритмов Дейкстры, A* и поиска в ширину для решения задач поиска пути в средах с препятствиями. Данные алгоритмы могут быть использованы при решении задач пространственного развития линейных объектов наземной транспортной инфраструктуры.
С алгоритмами проведена серия простых экспериментов с целью определения количественных показателей их асимптотической сложности, т. е. количества выполняемых операций и времени выполнения алгоритма в условиях поиска пути в средах с препятствиями. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленный), способом прохода ячеек (прямой и смешанный) и вариантом алгоритма поиска. При рассмотрении алгоритма A* в качестве дополнительного параметра, конфигурирующего работу алгоритма, были использованы различные метрики – расстояния Чебышева, манхэттенское, евклидово.
Об авторах
Д. В. Кузьмин
Российский университет транспорта (РУТ МИИТ)
Автор, ответственный за переписку.
Email: kuzminmiit@yandex.ru
кандидат технических наук, доцент, кафедра Логистика и управление транспортными системами
Список литературы
- 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).
Дополнительные файлы
