Бондарь Е.Е.
ПОИСК КРАТЧАЙШЕГО МАРШРУТА В УСЛОВИЯХ БЕЗДОРОЖНОЙ МЕСТНОСТИ *
Аннотация:
в работе рассматривается подход к поиску оптимального маршрута в условиях бездорожной местности, включающий в себя два основных метода: предварительную обработку цифровой карты и многокритериальный поиск кратчайшего пути.
Ключевые слова:
поиск кратчайшего пути, бездорожная местность, алгоритм Дейкстры, функция линейной свёртки, графы, многокритериальный поиск, геоинформационные системы
Поиск оптимального маршрута в условиях бездорожной местности является важной задачей в различных областях: ресурсодобывающей промышленности, в мониторинге окружающей среды, сельскохозяйственной отрасли и других, в которых применяется логистика. Традиционные методы поиска маршрута, основанные на классических алгоритмах, не учитывают особенности бездорожной местности, такие как рельеф, погодные условия и специфические (предметные) ограничения. Это может привести к неоптимальным решениям и увеличению времени и затрат на логистику. Поэтому, разработка эффективного метода поиска кратчайшего пути в условиях бездорожной местности является актуальной задачей. В данной работе (в рамках продолжения предыдущих исследований) предлагается разработать новый подход к решению рассматриваемой задачи.Для поиска кратчайшего маршрута на бездорожной местности были разработан алгоритм применения двух методов: метод предварительной обработки цифровой карты и метод многокритериального поиска кратчайшего пути (см. Рис. 1).Рис. 1. Схематическое описание алгоритма. Метод предварительной обработки карты. Этот метод преобразует цифровую геодезическую карту в граф бездорожной местности, путем выполнения следующих шагов:Определение входных параметров:цифровая геодезическая карта — это множество географических объектов, представленных в цифровом формате. Каждый географический объект описывается геометрическим представлением (линия или многоугольник) и набором атрибутов. Координаты преобразуемой карты имеют компоненту высоты для переноса рельефа местности,множество обусловленных областей — это множество областей, которые необходимо учитывать при поиске оптимального пути. Каждая область определяется как многоугольник и имеет набор атрибутов, которые описывают условия или ограничения, действующие в этой области. Например, обусловленная область может быть задана как зона с ограниченным доступом (заповедник или частная собственность), зона с опасными условиями (зона с высоким уровнем радиации или зона с опасными погодными условиями), зона с ограниченной проходимостью, и др,делитель шага сетки — действительное число, которое используется для формирования сетки при дискретизации географических объектов,множество предобработчиков — функций, которые применяются к графу местности для добавления классифицированных весов к ребрам графа.PP = f : (G, Rrules) -> G’где G — граф, представляющий бездорожную местность, Rrules — множество обусловленных областей, G’ — изменённый граф местности, ребрам e которого могут добавляться множество классифицированных весов W = {w1, w2, ...., wn}, где n — количество рассчитанных весов данным предобработчиком для ребра e, wi = (C, W) — пара из C — классификационного номера веса, W >= 0 — значения веса.Преобразование карты в граф путём дискретизации множества географических объектов в сетчатый граф местности, выполняя следующие шаги:Разбиение контуров объектов на точки и формирование вершин графа из них.Соединение контурных вершин ребрами.Дискретизация областей внутри контуров точками и формирование вершин графа из них.Объединение всех вершин и ребер в один подграф объекта.Переход к следующему объекту.После обработки всех объектов, оставшиеся «пустоты» также дискретизируются для устранения несвязности графа.Предобработка:Применение множества обусловленных областей Rrules к графу G осуществляется путем однократного применения каждой функции предобработчика PP:G’ = PPi+1(PPi(... PP1(G, Rrules)...), Rrules)Функция PPi выделяет среди множества правил Prules, такое множество Prules’, по атрибуту A, для которого k = «rule_number», а v = i, что означает применимость для функции Ppi., G’ — итоговый предварительно обработанный граф, содержащий ребра e, с множеством классифицированных весов W.Нормализация весов. Для каждого множества классифицированных весов рёбер e, wi необходимо произвести нормализацию значения весов W, среди весов с тем же классифицированным номером веса C.Метод многокритериального поиска оптимального пути. Данный метод включает в себя следующие шаги (см. Рис. 2):Определение входных параметров: сетчатый граф местности, точка начала и конца маршрута, оценки классифицированных весов, максимальное количество попыток поиска дополнительных путей.Определение начальной и конечной вершины.Поиск кратчайшего пути по заданным критериям между вершинами, используя метод Дейкстры. Веса ребер вычисляются с помощью функции линейной свёртки, используя заданные оценки классифицированных весов, таким образом получается учесть множество критериев для каждого ребра [1] [2].Повтор поиска кратчайшего пути с частичным исключением предыдущих вершин найденных путей.Рис. 2. Схематическое описание метода многокритериального поиска.В заключении, разработанный подход поиска кратчайшего маршрута в условиях бездорожной местности позволяет учитывать бездорожную местность, различные факторы и критерии, необходимые при решении задачи. Метод предварительной обработки карты и метод многокритериального поиска кратчайшего маршрута обеспечивают эффективное решение задачи поиска оптимального пути, используя алгоритм Дейкстры и функцию линейной свёртки. Разработанный метод необходимо автоматизировать в рамках дальнейшего исследования разработки соответствующей подсистемы ГИС.
Номер журнала Вестник науки №5 (86) том 4
Ссылка для цитирования:
Бондарь Е.Е. ПОИСК КРАТЧАЙШЕГО МАРШРУТА В УСЛОВИЯХ БЕЗДОРОЖНОЙ МЕСТНОСТИ // Вестник науки №5 (86) том 4. С. 1316 - 1321. 2025 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/23433 (дата обращения: 08.07.2025 г.)
Вестник науки © 2025. 16+