СОВЕРШЕНСТВОВАНИЕ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЗИРОВАННОГО ПЛАНИРОВАНИЯ СЕТИ ЛЕСНЫХ ДОРОГ

|Ш Инженерный вестник Дона. №4 (2020) НИ ivdon.ru/ru/magazine/arcliive/n4y2020/6428

Совершенствование методов решения задачи автоматизированного

планирования сети лесных дорог

Д.С. Пятин

Петрозаводский государственный университет, Петрозаводск

Аннотация: В статье представлен усовершенствованный численный метод решения задачи автоматизированного планирования сети лесных дорог, на основе графовой математической модели со сведением к задаче Штейнера, при этом исходная модель дополнена возможностью учета существующей транспортной сети в качестве вершины Штейнера и сформулирована в виде потоковой задачи линейного программирования. Результаты апробации метода позволяют говорить о существенном сокращении времени расчета на данных большого размера без значительной потери качества решения. Ключевые слова: лесозаготовительное производство, сеть лесных дорог, теория графов, оптимизация, задача Штейнера, линейное программирование, локальный поиск.

Введение

Актуальность поиска эффективных методов решения задач логистики в лесной отрасли значительно выросла в России за последние несколько лет. Одной из наиболее важных задач для лесопромышленного комплекса является строительство новых лесных дорог. Существующая лесная база истощается, обуславливая растущую нехватку сырья, что во многих случаях вынуждает вести заготовку древесины в зимний период. В тоже время развитая сеть лесных дорог является предпосылкой эффективного лесоводства, конкурентоспособности лесозаготовок и низких затрат на транспортировку леса, позволяет круглогодично поставлять сырье на предприятия отрасли. Лесные дороги имеют важное рекреационное значение и способствуют развитию туристского потенциала региона. Основной проблемой остается высокая себестоимость строительства лесных дорог. Один из способов снижения стоимости - это применение эффективных методов планирования на основе геоинформационных систем (ГИС), современных математических методов оптимизации и автоматизации при помощи электронно-вычислительных машин (ЭВМ).

Одновременно с этим, непрерывно нарастающий объем данных и сокращение допустимого времени принятия решений требуют необходимости использования наиболее быстрых численных методов.

Содержание задачи

Задача планирования сети лесных дорог заключается в оптимальном соединении заранее определенных точек местности (центров запасов древесины) с существующей транспортной сетью, согласно набору критериев и требуемых ограничений. В качестве критериев оптимальности рассматриваются: минимизация затрат на строительство и содержание сети дорог, крутизны поворотов, уровня наклона поверхности, экологического ущерба, максимизация вывозки древесины и рекреационного эффекта. Ограничения формируются геологическим типом местности, водными преградами, правовыми нормами. Вводятся различные типы дорог и дополнительные сооружения. Важным является учет уже существующей на местности сети дорог. Множество критериев и ограничений задачи создает трудность для ее решения. Трудность решения обуславливает обширное использование подходов на основе ГИС, математических моделей и методов для решения данной задачи с помощью ЭВМ.

Предлагаются различные подходы и математические методы для решения задачи планирования сети лесных дорог. В работах [1, 2] представлен способ решения со сведением к задаче Штейнера на графе и применением метода динамического программирования, апробированный на базе крупного лесозаготовительного предприятия Ленинградской области.

В [3, 4] на местности северной Финляндии испытан метод, в котором каждая дорога сети последовательно строится жадной эвристической процедурой. В [5] метод дополнен средствами динамического программирования для выбора оптимального расположения одной дороги. В [6] предлагается подход оптимизации строительства сети лесных горных

дорог Швейцарии, с высокой детализацией, путем сведения к задаче Штейнера на графе, и ее решением жадной эвристикой. Модель целочисленного линейного программирования для похожей задачи разработана в [7] для горных дорог Ирана. В обзоре [8] представлен обширный перечень современных достижений в области оптимизации строительства лесных дорог.

В данной работе предлагается улучшение подхода, описанного в [1, 2], позволяющее учитывать существующую дорожную сеть в качестве отдельной вершины Штейнера. Математическая модель задачи Штейнера была сформулирована в виде задачи целочисленного линейного программирования, что позволило применить более совершенные методы ее решения.

Основа подхода, описанного в работах [1,2] - это дискретизация рассматриваемой местности регулярной решеткой с некоторой точностью. Каждый узел решетки соединяется со всеми восемью соседними узлами, образуя граф:

О =< V, Е >

где V - множество вершин V еV - узлов решетки, Е - множество ребер е = (и,V), е е Е, и,V е V графа, определяющих атомарные участки дорожной сети. Требуемые к соединению центры запасов отображаются на ближайшие вершины графа и формируют множество Т, Т е V терминальных вершин. К графу применяются свойства и ограничения модели. Для каждого ребра определяется его вес. Для этого на основе ГИС карт местности производится оценка стоимости атомарного участка дороги в зависимости от типа поверхности. Существуют различные методики оценки стоимости строительства участков [9, 10], включающие в себя множество факторов. Кроме оценки стоимости, на основе ГИС определяется достижимость

вершин, удаляются или переоцениваются ребра, соответствующие крутым склонам и водным преградам.

Рис. 1. - Граф регулярной решетки с центрами запасов

В граф могут быть добавлены ребра, представляющие дополнительные сооружения, например мосты. На рис.1 показан пример решетки с отмеченными центрами запасов (выделены красным цветом). Для более точной оценки при значительном отдалении узлов решетки, ребро дополнительно делится на равные отрезки. Далее, на уже взвешенном графе решается задача Штейнера, в которой терминальные вершины являются центрами запасов. Полученное в результате решения дерево Штейнера определяет оптимальную сеть лесных дорог.

Учет существующей дорожной сети

Описанный подход был дополнен возможностью учета существующей дорожной сети в качестве отдельной вершины Штейнера. Дорожная сеть отображается на ребра графа решетки аналогично тому, как центры запасов отображаются на вершины графа. Для каждой точки дорожной сети на графе

|Ш Инженерный вестник Дона. №4 (2020) НИ ivdon.ru/ru/magazine/arcliive/n4y2020/6428

определяется ближайшая вершина, множество таких вершин и соединяющих их ребер формирует подграф существующей дорожной сети:

Оо =< К, Еп > , ^ е V, Е0 е Е Затем происходит сжатие подграфа Ов графа О в новую вершину ё

образующее граф:

О =< V&,Е > V& = V \\ VD и {ё}

Е&= Е \\ Ев \\ Е1 и Е2 (1)

Е1 = {(и, у)| и е VD, V е )}

Е2 = {(ё, v)|v е Мо&^)},

где ЫО,(уГ)) - множество вершин, смежных с вершинами из множества VD на

Рис. 2. - Сжатие подграфа ОD

Вершина ё добавляется во множество терминальных вершин графа.

Т = Т \\ VD и {ё} , (2)

В результате, мы получаем аналогичную задачу на новом графе. Такой подход позволяет сократить число рассматриваемых вершин и определить оптимальные дорожные развилки, применив методы решения обычной задачи Штейнера на графе.

Потоковая формулировка задачи

Пусть О * =< V *, Е * > - ориентированный граф, полученный из неориентированного графа О&, путем замены ребра е = (и,V) на два ориентированных ребра ех = (и, V), е2 = (V, и) при этом веса ребер не меняются,

Т. е. ^ = We2 = ^е

Тогда для каждой вершины V е V* можно определить: 5т (V) - множество ребер, входящих в вершину V. 5Ш (V) - множество ребер, исходящих из вершины V. Выделим среди множества Т вершину г, назовем ее корневой. Пусть Р, р е Р множество продуктов, где каждый продукт р соответствует паре (г, г), г е Т& \\{г}. Введем неизвестные факторы:

хе - показатель принятия ребра е в остовное дерево, соответствующее

принятию атомарного участка дороги, определяемого ребром е к строительству, хе равен 1, если участок принят к строительству, 0 иначе.

ур - количество потока продуктар по ребру е.

Теперь математическую модель задачи можно записать следующим образом:

Минимизировать:

X ^еХе ^

При ограничениях:

X ур + X У1.

-1, V е Т \\{г} 0, V е V*\\ Т&

- ограничение баланса сети;

Хе > Уе , ее Е *, р е Р,

еедаи, еед

- ограничение связи потока с показателем строительства дороги;

уР > 0 , е е Е*, р е Р, (6)

- ограничение не отрицательности потока;

хе е {0,1} , е е Е*, (7)

- ограничение на показатель строительства участка дороги.

Решением является множество ребер: {е | хе = 1,е е Е }. Нетрудно показать, что применив к решению операции, обратные (1) - (2) мы получим искомое решение исходной задачи. Оптимальная развилка от существующей дороги будет определена автоматически.

Таким образом, выражения (3) - (7) формируют математическую модель задачи планирования лесных дорог с учетом существующей транспортной сети в виде многопродуктовой потоковой формулировки задачи Штейнера на графе [11].

Методы решения задачи

Задача Штейнера на графе хорошо изучена. Она относится к классу КР-трудных задач [12], поэтому не существует эффективных точных алгоритмов ее решения за полиномиальное время. Известные методы решения задачи основаны на использовании алгоритмов перебора и динамического программирования [13], жадных эвристических процедур [14,15], методов линейного программирования [16, 17] и различных метаэвристических алгоритмов [18-21]. Для случая планарных графов разработана схема приближения полиномиального времени [22, 23].

В работе [2] к решению задачи Штейнера был применен метод динамического программирования по подмножествам, известный как алгоритм Дрейфуса-Вагнера [13]. Метод дает оптимальное решение задачи. Недостатком метода является его экспоненциальная сложность относительно числа терминальных вершин | Т |, составляющая 0(3|т|).

Кроме того, данная асимптотическая оценка скрывает квадрат числа вершин в графе, и уже при 10 терминальных вершинах на решетке с 103 узлами требует порядка 1010 операций или около часа выполнения на персональном компьютере. Поэтому актуальны эвристики, дающие хорошие, близкие к оптимальным, решения на больших решетках за меньшее время.

Математическая модель, записанная в виде (3) - (7) позволяет применить методы решения задач целочисленного линейного программирования, как точные, так и приближенные. В частности, эвристический метод релаксации (ослабления) целочисленной задачи с последующим округлением полученного решения.

В [17] доказано, что решение задачи Штейнера на графе в ослабленной многопродуктовой потоковой формулировке (3) - (7) (при замене ограничения (7) на хе е [0,1]) с последующим итеративным округлением дает

в худшем случае результат, не более чем в 2 раза отличающийся от оптимального (2орг). При этом в [24] отмечается, что для графов дорожных сетей такой подход часто приводит к нахождению именно оптимального решения. Асимптотическая сложность метода пропорциональна сложности решения задачи линейного программирования с 0(| V |) переменными и 0(1 Е || Т |) ограничениями, где | V | - число вершин, | Е | - число ребер графа. При использовании симплекс метода она полиномиальна в среднем, что при эффективной реализации позволяет рассчитывать решетки с 104 узлами и 20 терминалами за нескольких минут. Недостатком метода является то, что добавление одного терминала, порождает | Е | новых ограничений, поэтому для большого числа терминалов расчет может быть достаточно долгим.

Ускорение в случае большего числа терминалов может быть получено с помощью применения метаэвристических алгоритмов. Одна из лучших

метаэвристик для решения задачи Штейнера это итеративный локальный поиск с операциями включения и исключения вершин Штейнера [18]. Асимптотическая сложность одной итерации данного метода при рассмотрении полной окрестности решений составляет O(| V || T |) с предварительным расчетом кратчайших путей между всеми парами вершин и O(| E | log | V |) без него. При рассмотрении окрестности, ограниченной N,N << V вершинами, метод работает гораздо быстрее. На тестах из библиотеки SteinLib решения найденные данным методом всего на 2 - 3 % отличаются от оптимальных. Основным недостатком итеративного локального поиска является невозможность теоретической оценки эффективности.

Задача Штейнера на графах еще большего размера может быть решена при помощи жадных эвристик с доказанной эффективностью. Наиболее известная из них это эвристика 2opt [14], основанная на построении минимального остовного дерева на метрическом замыкании графа терминальных вершин. Асимптотическая сложность эвристики составляет O(| T || E | log | V |), что позволяет рассчитывать примеры с 104 вершинами за несколько секунд. Значительной проблемой является то, что эвристика 2opt не вводит в решение дополнительные вершины и часто находит сравнительно слабые результаты. Эвристика 11/6opt [15], рассматривающая по одной дополнительной вершине в рамках трехсвязных компонент, более эффективна ценой существенного увеличения времени расчета.

Для решеток с более чем 105 вершинами, при условии планарности графа, может использоваться схема приближения полиномиального времени (PTAS) [22] за O(| V | log | V |), дающая результаты сопоставимые с жадной 2opt эвристикой, однако гораздо быстрее [23].

Обширный перечень методов с различными характеристиками не подразумевает наличия однозначно правильного выбора в условиях конкретной практической задачи. Однако существует тенденция быстрого нахождения жадными эвристиками менее качественных решений в то время, как релаксация ЛП-задачи и итеративный локальный поиск более перспективны с точки зрения нахождения оптимальных решений. Проблемой является то, что они имеют большую сложность вычислений.

Для решения данной проблемы автором предлагается комбинированный алгоритм последовательного приближения, показавший хорошие результаты:

Алгоритм 1 - последовательное приближение дорожной сети

Шаг 1. Решить задачу Штейнера на графе решетки меньшего размера с помощью алгоритма ослабления задачи ЛП (ЛП-релаксации) или при помощи итеративного локального поиска, определив дополнительные вершины Штейнера.

Шаг 2. По исходному набору терминалов и полученным вершинам Штейнера на графе исходной решетки построить метрическое замыкание и найти на нем минимальное остовное дерево, которое будет решением задачи (рис.2).

Рис. 2. - Последовательное приближение дорожной сети

Предполагается, что за счет использования более эффективных вычислительно-затратных методов решения задачи на первом шаге может быть найдено конструктивно более хорошее дерево Штейнера, которое будет опорным на втором шаге. При этом итоговое решение будет получено быстрее непосредственного применения этих методов к исходной решетке, а также будет более качественным по сравнению с решением, полученным на исходной решетке жадными эвристиками.

Результаты

Автором были рассмотрены следующие методы нахождения опорного дерева: алгоритм Дрейфуса-Вагнера, 2opt жадная эвристика , 11/6opt жадная эвристика, линейная релаксация задачи о многопродуктовом потоке с итеративной схемой округления и итеративный локальный поиск с операциями добавления и удаления вершины Штейнера. Алгоритмы были реализованы на языке программирования C#, запускались на компьютере с конфигурацией: Intel Core i7-6700HQ, 2.60 GHz, 24Gb RAM, на 9 тестах c установленными различными размерами решетки и количеством центров

запасов (терминальных вершин). Каждый из тестов включал в себя 10 процедурно сгенерированных при помощи симплекс шума карт местности. Для создания водных преград на картах использовался специализированный алгоритм на основе комбинации поиска кратчайшего пути и случайного шума. Существующие дороги были размечены вручную после генерации карт, переправы через реки определялись автоматически в процессе решения.

Каждая карта содержала до 6 типов поверхности с установленными затратами на строительство. Недетерминированный алгоритм ITS был запущен 10 раз на каждой карте, и в таблице приводится усредненный результат, для алгоритма было установлено ограничение в 200 итераций. Расчет модели линейного программирования проводился с помощью решателя Gurobi. Тестировались следующие показатели:

«честному» расчету дорожной сети на исходной решетке алгоритмом на основе ЛП-релаксации Clpr и 2opt эвристикой Cgr.

Результаты тестирования с малым количеством терминалов и возможностью нахождения оптимального решения показывают, что все рассмотренные жадные эвристические алгоритмы в среднем находят решения в районе 10 - 15% от оптимального. Метаэвристический алгоритм итеративного локального поиска дает решение с отклонением 1 - 2%. Алгоритм на основе ЛП-релаксации дает оптимальные решения (таблица №1). На основе сравнительного анализа и экстраполяции полученных

результатов можно предположить, что для тестов большего размера эта

тенденция сохраняется.

Рис. 3. - Рассчитанные сети лесных дорог Время работы алгоритмов, определенное на практике, согласуется с теоретическими оценками и представлено в таблице №2.

Таблица № 1

Стоимость полученной дорожной сети при выполнении 1 шага

Тест п т БЖ, тыс. руб. 2ор1, тыс. руб. 11/борг, тыс. руб. ЬРЯ, тыс. руб. 1ТБ, тыс. руб.

N Инженерный вестник Дона, №4 (2020) ivdon.ru/ru/magazine/arcliive/n4y2020/6428

Таблица № 2

Время выполнения алгоритмов на 1 шаге

Тест п т БЖ, сек. 2ор1, сек. 11/борг, сек. ЬРЯ, сек. т, сек.

Другим результатом является экспериментальное подтверждение того, что использование алгоритма ЛП-релаксации на решетке с меньшим количеством узлов и перенос результатов на исходную решетку позволяет найти лучшее решение, чем использование 2ор1 жадной эвристики на исходной решетке. В частности стоимость сети С&1рг, найденная на решетке с

больше на 17,45% (таблица №3).

Таблица № 3

Отношение итоговой стоимости дорожной сети после 2 шага

П1- П2 С ^1рг 5 тыс. руб. тыс. руб. % С& тыс. руб. %

Выводы

Улучшенные методы решения задачи Штейнера позволяют эффективно планировать сети лесных дорог на регулярных решетках с большим количеством узлов и рассматриваемых центров запасов. Определение существующей дорожной сети в качестве вершины Штейнера позволяет естественно учитывать ее в модели, применяя для решения известные методы. Математическая модель и предложенные численные методы планирования сети лесных дорог могут использоваться при синтезе расписаний заготовки [25] и транспортировки леса [26]. Дальнейшими перспективными направлениями исследования могут являться анализ применения к решению задачи Штейнера других алгоритмов, в особенности учитывающих структуру графа, а также использование стохастического разбиения карт местности.

Литература

References