докторант с 01.01.2012 по настоящее время
Москва, г. Москва и Московская область, Россия
УДК 656.022 Служба движения. Линии. Маршруты. Трассы
ББК 398 Городской транспорт
Задача. Рассмотрен вопрос применимости алгоритма A* для решения задач поиска пути в контексте пространственного развития линейных объектов наземной транспортной инфраструктуры. Цель исследования. Определение наиболее предпочтительной конфигурации алгоритма поиска пути для решения задачи пространственного развития линейной транспортной инфраструктуры. Методы исследования. Алгоритм A*, широко используется для различных прикладных задач теории графов, в том числе трассирования и планирования пути. Новизна работы. С алгоритмом проведен ряд простых экспериментов с целью определения количественных показателей его асимптотической сложности, т.е. количества выполняемых операций и времени выполнения алгоритма. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленны), метрикой поиска (Евклидова метрика, Манхэттенское расстояние, расстояние Чебышева) и способом прохода ячеек (прямой и смешанный). Результаты исследования и выводы. В целом можно заключить, что двунаправленный поиск требует примерно на 19,17% меньше операций чем однонаправленный. Манхэттенская метрика и расстояние Чебышева показывают схожие результаты по длине пути и времени выполнения. Евклидова метрика позволяет найти более короткий путь, но может потребовать больше времени на выполнение.
алгоритм A*, трассирование, развитие, транспортная инфраструктура, система, теория, графы
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.
