[
На правах рукописи
Воронова Анна Михайловна
МЕТОДЫ ПОКРЫТИЯ ГИПЕРСЕТИ КОРНЕВЫМ ДЕРЕВОМ
ДЛЯ ОПТИМИЗАЦИИ СИСТЕМЫ ТРАНСПОРТНЫХ ПУТЕЙ
Специальность 05.13.18 – Математическое моделирование,
численные методы и комплексы программ.
Автореферат
диссертации на соискание ученой степени кандидата технических наук
Петрозаводск – 2013
Работа выполнена на кафедре прикладной математики и кибернетики ФГБОУ ВПО «Петрозаводский государственный университет»
Научный руководитель: Щеголева Людмила Владимировна, доктор технических наук, доцент
Официальные оппоненты: Рогов Александр Александрович, доктор технических наук, профессор, заведующий кафедрой теории вероятностей и анализа данных ФГБОУ ВПО «Петрозаводский государственный университет», Григорьев Игорь Владиславович, доктор технических наук, профессор, профессор кафедры технологии лесозаготовительных производств ФГБОУ ВПО «Санкт-Петербургский государственный лесотехнический университет им. С. М. Кирова»
Ведущая организация: ФГБОУ ВПО «Московский государственный университет леса»
Защита состоится «19» декабря 2013 г. в 12:00 часов на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО «Петрозаводский государственный университет» по адресу: 185910, г. Петрозаводск, пр.
Ленина, 33.
С диссертацией можно ознакомиться в библиотеке Петрозаводского государственного университета.
Автореферат разослан «14» ноября 2013 г.
Ученый секретарь диссертационного совета Р. В. Воронов
Общая характеристика работы
Актуальность темы исследования В практических приложениях для моделирования задач со сложной сетевой структурой все большее применение находят иерархические гиперсети. К таким задачам относят строительство инженерных сетей электросвязи, сетей автомобильных дорог, нефтепроводных, газопроводных сетей и прочих.
Частным видом гиперсетей являются двухуровневые гиперсети. На первом уровне такой гиперсети находится гиперграф, на втором уровне – ориентированный граф, в котором дуги соединяют гиперребра первого уровня. Такая структура может быть применена для моделирования транспортной сети лесосеки и решения задачи проектирования схемы первичного транспорта леса при проведении лесозаготовительных работ. Это позволит учесть ряд факторов, не используемых в более простых моделях, таких как ограничение на форму лесосеки, форму и размеры территории набора пачки древесины, неравномерность размещения эксплуатационного запаса леса на территории лесосеки, маневренность трелевочной техники.
Схожие модели могут быть применены в задачах построения системы пожаротушения больших зданий, проектирования нефтепроводных, газопроводных сетей, линий электропередач, ирригационных сооружений.
Важной задачей является разработка методов построения покрывающих деревьев гиперсети. Таким образом, актуальным является разработка и совершенствование моделей и методов покрытия иерархических гиперсетей.
Степень разработанности В работах В. К. Попкова, Г. Ы. Токтошова и др. введены основные понятия теории гиперсетей, рассмотрены задачи оптимизации некоторых систем сетевой структуры, приведены формальные постановки задач построения транспортных сетей, сетей связи, инженерных сетей и др.
Актуальной задачей остается разработка методов адаптации существующих алгоритмов к применению на гиперсетях, разработка специальных алгоритмов покрытия гиперсетей, в частности покрытия корневыми деревьями.
Целью работы является повышение эффективности территориального размещения транспортных путей на лесосеке при помощи оптимального покрывающего дерева гиперсети с учетом дополнительных ограничений.
Для достижения поставленной цели требуется решить следующие задачи:
1. Построить математическую модель путей первичного транспорта леса при помощи покрывающего дерева двухуровневой гиперсети специального вида.
2. Разработать алгоритмы построения покрывающих деревьев двухуровневой гиперсети с минимальным весом.
3. Разработать программное обеспечение, реализующее алгоритмы построения покрывающих деревьев двухуровневой гиперсети.
Научная новизна работы состоит в следующем:
1. Предложен подход к решению задачи оптимизации системы транспортных путей в виде совместного решения двух подзадач:
покрытия территории областями и связывания областей единой сетью.
Для реализации этого подхода предлагается моделирование территории в виде двухуровневой гиперсети специального вида и построении транспортной сети в виде корневого покрывающего дерева гиперсети.
Введено понятие корневого покрывающего дерева двухуровневой гиперсети. Особенностью покрывающего дерева является то, что вес каждого узла зависит от числа потомков в дереве.
2. Разработаны приближенные методы покрытия гиперсети корневым деревом минимального веса с учетом ограничений специального вида.
3. Разработан комплекс программ, реализующий предложенные в работе алгоритмы.
Теоретическая значимость работы Предложенные в работе математические модели развивают теоретические и прикладные аспекты моделирования поверхности территории с неоднородным рельефом и свойствами грунта в виде гиперграфов и гиперсетей. Предложенные в работе алгоритмы покрытия гиперсетей развивают теорию гиперграфов и гиперсетей, пригодны для решения широкого класса задач проектирования транспортных сетей.
Разработанные математические модели и алгоритмы расширяют возможности теоретических исследований инженеров-исследователей в области оптимального проектирования транспортных сетей и могут применяться для моделирования первичных путей транспорта леса с учетом минимизации негативного воздействия лесозаготовительной техники на почвогрунты лесосеки.
Практическая значимость работы Разработанная информационная система поддержки принятия решений может быть использована лесозаготовительными предприятиями, которые осуществляют разработку заболоченных лесосек, ведут работы в весеннеосенний и летний периоды, когда ухудшается пластичность грунта в связи с повышением влажности.
Разработанные математические модели и предложенные алгоритмы могут быть применены для проектирования сетей пожаротушения в зданиях, когда накладываемая сеть труб покрывает некоторую область, которая орошается гасящей жидкостью; также в задачах проектирования нефтепроводных, газопроводных сетей, линий электропередач, ирригационных сооружений.
Методология и методы исследования В диссертационной работе используются методы математического моделирования, теории графов, гиперграфов, гиперсетей, дискретной математики, аналитической геометрии, имитационного моделирования, методы разработки алгоритмов, объектно-ориентированное программирование. Программы написаны в среде разработке Microsoft.NET на языке C#.
Положения, выносимые на защиту 1. Предложен метод математического моделирования путей первичного транспорта леса при помощи покрывающего дерева двухуровневой гиперсети специального вида.
2. Разработан алгоритм построения покрывающего дерева минимального веса двухуровневой гиперсети.
3. Разработан программный комплекс, предназначенный для построения системы транспортных путей, покрывающих заданную территорию.
Степень достоверности Адекватность математической модели и сходимость алгоритмов покрытия гиперсети проверены экспериментально. Расчет временных транспортных сетей покрытия лесосек произведен на данных лесозаготовительных предприятий Республики Карелия, собранных в реальных условиях.
Апробация результатов Материалы диссертационного исследования докладывались и обсуждались на следующих конференциях:
VII Всероссийская школа-семинар «Прикладные проблемы управления макросистемами» (Апатиты, 2008).
VIII международная научно-техническая конференция «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (Петрозаводск, 2008).
Международная научно-техническая конференция «Актуальные проблемы развития лесного комплекса» (Вологда, 2008).
16 Международная конференция серии "Математика. Компьютер.
Образование" (Пущино, 2009).
X Международная молодежная научная конференции "СевергеоэкотехУхта, 2009).
I республиканская научно-практическая конференция молодых ученых, аспирантов, докторантов «Повышение эффективности лесного комплекса Республики Карелия» (Петрозаводск, 2009).
IX международная научно-техническая конференция «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (Петрозаводск, 2010).
X международная научно-техническая конференция «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (Петрозаводск, 2012).
По теме диссертации опубликовано 15 научных работ, из них 5 статей в научных журналах и изданиях, которые включены в перечень российских рецензируемых научных журналов и изданий для опубликования основных научных результатов диссертаций.
зарегистрирована в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 17756 от 27.12.2011 г.
Информационно-аналитическая система «Расчет схемы волоков на лесосеке с учетом минимизации отрицательного воздействия трелюющей техники на грунты» зарегистрирована в Реестре программ для ЭВМ № 2013614304 от 29.04.2013.
Информационно-аналитическая система «Составление схемы путей первичного транспорта леса на лесосеке с учетом минимизации расходов на топливо» зарегистрирована в Реестре программ для ЭВМ № 2013614105 от 23.04.2013.
Структура и объем диссертации. Диссертация состоит из введения, глав, заключения и библиографического списка использованной литературы (95 наименований), имеет объем 125 страниц машинописного текста, включая 14 страниц приложений, содержит 22 рисунка и 7 таблиц.
Во введении содержится обоснование актуальности темы диссертации, формулируются цель и задачи диссертации, представлены основные результаты, научная новизна, практическая и теоретическая значимость работы, описание структуры диссертации.
В первой главе приведен обзор методов моделирования и алгоритмов для решения задач сетевой структуры, включая описание графовых, гиперграфовых и гиперсетевых структур, транспортной задачи, задачи покрытия, метода динамического программирования, жадных алгоритмов.
Примером задачи сетевой структуры является задача проектирования схемы первичного транспорта леса при осуществлении лесозаготовительных работ.
В работах Э. О. Салминена, С. В. Гурова, Б. М. Большакова, И. В. Григорьева, А. И. Никифоровой и др. исследована задача определения схемы волоков на лесосеке с учетом некоторых свойств грунта. Для решения этой задачи территория лесосеки разбита на непересекающиеся квадратные участки – участки набора пачки древесины. Каждому участку поставлено в соответствие число – обобщенный коэффициент, характеризующий степень воздействия трелевочного трактора на грунт участка по следующему правилу: чем больше коэффициент, тем слабее грунт, следовательно, тем сильнее негативное воздействие трелевочного трактора. Рассматривается оптимизационная задача построения схемы волоков с широким фронтом погрузки или одним погрузочным пунктом с краю лесосеки с минимальным негативным воздействием на грунты лесосеки. В качестве метода решения применятся динамическое программирование.
Недостатками применения такого подхода являются ограничения на форму лесосеки, форму и размеры территории набора пачки древесины, привязка к конкретному погрузочному пункту. Математическая модель не учитывает неравномерность произрастания леса, рельеф территории лесосеки, маневренность трелевочной техники. Кроме того, участок сбора пачки древесины имеет достаточно большие размеры и не может быть однозначно охарактеризован одним значением, показывающим свойства грунта.
В диссертации предлагается метод моделирования системы транспортных путей на основе гиперсетевых моделей, учитывающий перечисленные выше ограничения задачи.
В работах В. К. Попкова, Г. Ы. Токтошова и др. рассмотрена теория иерархических гиперсетей и применение этой теории для моделирования задач со сложной сетевой структурой, предложена гиперсетевая технология формализации задачи оптимизации инженерной сети на земной поверхности с неоднородной территорией и сведение ее к решению соответствующей задачи на иерархической гиперсети.
В диссертации описано применение теории гиперграфов, гиперсетей и гиперсетевой технологии для моделирования и проектирования схемы первичного транспорта древесины при осуществлении лесозаготовительных работ.
В работе задача построения транспортной сети на лесосеке рассматривается в виде двух связанных подзадач. Первая из них включает формирование покрытия всей территории на области набора пачки древесины трактором. Вторая подзадача заключается в связывании выделенных областей в единую транспортную сеть, определяющую направление и порядок обхода областей территории лесосеки при трелевке.
Традиционный подход предполагает решение двух подзадач отдельно друг от друга. В классической постановке эти подзадачи формулируются так.
Взвешенная задача о покрытии конечного множества V подмножествами W множества V, такими что w V, и заданной весовой функцией на подмножествах h : W R, заключается в поиске подмножества S W, при котором весовая функция h( w) принимает минимальное значение.
Задача поиска минимального покрывающего дерева графа G (W, E), с заданной весовой функцией на дугах h : E R, заключается в поиске подграфа графа G, который является деревом, содержит все вершины графа G и имеет минимальный вес.
Решение исходной задачи предполагает совместное решение вышеизложенных подзадач, так как параметры проектируемой транспортной сети зависят как от найденного покрытия территории областями, так и от порядка и направления их обхода. Моделирование транспортной сети лесосеки в виде двухуровневой гиперсети позволяет связать две подзадачи и сформулировать одну задачу покрытия гиперсети корневым деревом.
Применение гиперграфов и гиперсетей для проектирования транспортных сетей на лесосеке позволяет одновременно учитывать параметры транспортной сети, которые не учтены в рассмотренных выше работах: особенности рельефа и грунта лесосеки, взаимное расположение основных транспортных путей, направления движения по сетям транспорта, нагрузку на территорию, покрытие всей территории.
Новым подходом к решению задачи проектирования схемы первичного транспорта леса стало применение аппарата гиперсетей и разработка методов поиска покрывающих деревьев гиперсети.
Во второй главе приведено описание задачи размещения покрывающей сети на лесосеке, рассмотрены общие рекомендации по размещению погрузочных пунктов и сети волоков на лесосеке, а также освещены основные вопросы сбора показателей лесосеки и применения рассчитанных схем волоков при проведении подготовительных и основных работ на лесосеке.
При проведении сплошных рубок леса сваленные деревья доставляются на погрузочный пункт по временным транспортным путям, называемых волоками, которые образуют транспортную сеть, покрывающую всю территорию лесосеки. Транспортную сеть необходимо проектировать с учетом особенностей рельефа местности, свойств грунта и параметров трелевочной техники.
При проектировании транспортной сети лесосеки необходимо минимизировать воздействие, оказываемое трелевочной техникой на грунты, направлять основные транспортные потоки через участки с сильными грунтами, способными выдерживать большие нагрузки, и разгрузить участки со слабым грунтом.
Существуют стандартные схемы транспортных путей, которые имеют регулярную структуру: с параллельным, диагональным, радиальным, веерным размещением волоков. Однако такие схемы не учитывают особенности рельефа и свойства грунта конкретных лесосек. Применение стандартных схем волоков приводит к значительному повреждению почвы и разрушает экосистему подлеска.
В третьей главе описаны разработанные математические модели для представления временной транспортной сети на местности в виде графовых, гиперграфовых и гиперсетевых структур. Сформулирована задача поиска покрывающего дерева на графе, гиперграфе и гиперсети.
В диссертации используется понятие гиперсети и введено понятие корневого покрывающего дерева гиперсети.
Под двухуровневой гиперсетью понимается A V, W, E, F /, F //, G, в которой:
V – множество вершин, W – множество гиперребер, E – множество дуг, F / : W 2V, F // : W 2V – отображения, ставящие в соответствие каждому гиперребру w W два подмножества F / w V и F // w V его вершин, отображение F / и F // не является инъективным.
G : E W W – инъективное отображение, ставящее в соответствие каждой дуге e E упорядоченную пару Ge w1, w2 гиперребер множества W, w1 и w2 – обозначения для первого и второго элементов пары Ge.
гиперграфами, а тройка A2 W, E, G – орграфом. В орграфе A2 гиперребра множества W будем называть узлами.
Пусть T S, r, p – корневое дерево в орграфе A2, в котором:
S W – множество узлов дерева, r S – корень дерева, p : S S – отображение, ставящее в соответствие каждому узлу s S его родителя ps в дереве. Это означает, что если дереву T принадлежит дуга w1, w2, то pw1 w2 (все дуги корневого дерева направлены к корню).
Отображение p должно обладать следующими свойствами:
Второе свойство означает, что из любого узла дерева существует путь до корня, состоящий из дуг дерева.
Будем говорить, что дерево T S, r, p покрывает вершину v V, если существует s S, для которого v F // s.
Назовем дерево T корневым покрывающим деревом гиперсети A, если объединение гиперебер нижнего уровня гиперсети, соответствующих узлам дерева, равно множеству вершин: F // s V. Таким образом, покрывающее дерево гиперсети покрывает все его вершины.
Будем говорить, что дуга верхнего уровня инцидентна гиперребру нижнего уровня, если это гиперребро соответствует узлу верхнего уровня, инцидентному данной дуге.
Будем говорить, что дуга верхнего уровня покрывает вершину нижнего уровня, если вершина принадлежит гиперребру, инцидентному этой дуге.
Опишем правила построения гиперсети для содержательной задачи определения системы транспортных путей на лесосеке, включающие правила построения множества вершин V, множества гиперребер нижнего уровня W, множества дуг E.
Пусть область D представляет собой проекцию территории лесосеки на плоскость xOy. Разобьем область D регулярной сеткой с шагом l (м.), образованной двумя семействами прямых: параллельных оси Oy и параллельных оси Ox. Для каждой ячейки сеточной модели с координатами номера строки и столбца row, col заданы:
zrow, col – запас леса участка row, col (м3), hrow, col – высота центральной точки участка row, col (м), k row, col – консистенция грунта участка row, col k row, col J, считать, что при увеличении индекса тип консистенции грунта будет ухудшаться.
Каждой ячейке сетки с запасом zrow, col 0 взаимно однозначно сопоставим вершину гиперсети нижнего уровня v V : для вершины v будем обозначать row v, col v – координаты соответствующей ей ячейки сетки.
Введем обозначения для набора весов вершин гиперсети:
фрагменты делянки.
Определим правила построения множества гиперребер W и отображений F и F //. Пусть заданы длина length (м), две ширины width / и width // (м). Если для некоторых вершин u, v V евклидово расстояние между точками X row u, col u и Y row v, col v меньше или равно length, то добавляется гиперребро w и строятся множества F / w и F // w, соответствующие этой паре вершин u и v. Вершина q V принадлежит F / w ( F // w ), если расстояние от точки Z row q, col q до прямой, содержащей отрезок X, Y не превосходит width / ( width // ) и ближайшая к точке Z точка прямой принадлежит отрезку X, Y. Для построенного гиперребра w введем обозначения beg (w) u и end (w) v. Отметим, что гиперребру w соответствуют два подмножества вершин F / w и F // w.
В содержательной интерпретации модели F / w определяет множество трелевочного трактора, F w – множество вершин, соответствующих участкам, которые попадают в зону охвата манипулятора трелевочного трактора, width // – вылет манипулятора трактора, width / – полуширину волока, length – длину волока. Гиперребрам соответствуют участки сбора леса, двигаясь по которым трактор полностью загружается и трелюет древесину на погрузочный пункт.
Определим правила построения множества дуг E. Пусть заданы два узла Если расстояние между точкой Y1 и отрезком X 2, Y2 меньше len, а угол (w1, w2 ) между прямыми, содержащими отрезки X 1, Y1 и X 2, Y2, не больше заданного, тогда узлы w1, w2 верхнего уровня гиперсети соединим дугой В содержательной интерпретации модели пара вершин (beg (w), end (w)) гиперребра w определяет направление движения трелевочного трактора при сборе пачки древесины с территории, соответствующей гиперебру w, len – расстояние между смежными волоками в месте примыкания, угол – максимально возможный угол поворота трелевочного трактора.
Для каждого гиперебра w W определим значение K w J как наихудшее значение k w J по всем вершинам множества F / w :
Пусть w F / w – мощность множества F / w, w W. Обозначим Q v1, v2,, v w F / w – последовательность вершин вдоль направленного отрезка beg w, end w из множества F / w для гиперребра w W.
Для каждого гиперребра w W определим перепады высоты для соседних вершин последовательности Q :
Маневренность трелевочного трактора определяет перепады высоты, которые он может преодолевать в нагруженном состоянии. Перепады высоты при движении ограничены углами up и down, up – максимальный угол наклона при движении вверх трелевочного трактора, down – максимальный угол наклона при движении вниз трелевочного трактора.
Пусть t S – мощность множества S. Назовем корневое дерево T помеченным, если все его узлы пронумерованы числами от 1 до t. Тогда для каждого узла s S обозначим через s множество узлов дерева T, у которых номера меньше, чем номер узла s.
В модели номера узлов S показывают порядок обхода трелевочным трактором территории, соответствующей узлам, при сборе древесины.
Множество s соответствует территории, которая обходится трелевочным трактором раньше, чем территория s.
Для каждого узла s S дерева T определим остаточное множество:
Для каждого узла s S дерева T определим остаточный запас:
Остаточный запас на территории, соответствующей узлу гиперсети, формирует пачку древесины, которая ограничена грузоподъемностью трелевочного трактора P. P – максимально допустимый объем пачки древесины (м3).
Обозначим N s – число потомков узла s S в дереве T, включая сам узел s. N s определяет количество проездов по территории волока, соответствующего узлу s S.
Для сортиментной технологии заготовки расчет N s производится с учетом видов сортиментов древесины. Обозначим C – индексное множество видов сортиментов C,, u. c, v – доля сортимента c для вершины v, c C, v V. Тогда c, s – доля сортимента c для узла s, c C, s S рассчитывается по формуле Пусть Os – множество потомков узла s в дереве T, s S, тогда Опишем правило построения целевой функции. Обозначим I – индексное множество категорий глубины колеи, I,, n. Будем считать, что при увеличении индекса категория глубины колеи будет ухудшаться.
Пусть задана функция : J I, такая, что для фиксированного j J j, g как функция от g Z является неотрицательной возрастающей вогнутой функцией. Функция определяет зависимость образования категории колеи для каждой консистенции грунта в зависимости от числа проездов трелевочного трактора.
В качестве критерия оптимальности определим целевую функцию y1,, yn min, которая в лексикографическом порядке минимизирует количество узлов покрывающего дерева, соответствующих территории пролегания участков волока, в порядке возрастания индекса категории колеи.
Компонента вектора y i – число узлов множества S дерева T, соответствующих волокам с индексом категории глубины колеи i, i,, n : Назовем вектор y1,, y n оценочной функцией покрывающего дерева, а компоненты вектора параметрами оценочной функции.
Сформулируем оптимизационную задачу. Для заданной гиперсети A и чисел P,, l, up, down требуется найти корневое помеченное покрывающее лексикографический минимум и, при этом:
1. Для каждого узла s S дерева T остаточный запас Z s P, s S.
2. Для каждой пары смежных узлов s1, s 2 дерева T угол между соответствующими им направленными отрезками ограничен 3. Для каждого узла s S дерева T соответствующие перепады высот В четвертой главе приведены описание алгоритма покрытия гиперсети с заданными параметрами корневым покрывающим деревом, описание разработанного алгоритма поиска корня покрывающего дерева на гиперсети. Для алгоритма построения покрывающего дерева приведены псевдокоды основных функций. Приведены примеры работы алгоритма и сравнение получаемых схем для задачи размещения транспортных путей на территории лесосеки для моделей в виде графа и гиперсети. Особенностью реализации представленных алгоритмов является то, что гиперребра и дуги гиперсети строятся динамически по мере необходимости по описанным выше правилам.
В главе рассмотрен обобщенный алгоритм покрытия гиперсети корневым покрывающим деревом с разной глубиной вложенности, приведен анализ временной сложности алгоритма, рассмотрены методы уменьшения временной сложности алгоритма, приведены условия существования решения.
Приведем обобщенный алгоритм покрытия гиперсети корневым деревом с параметром глубины вложенности d. Алгоритм основан на поиске с возвратом. Вначале корневое дерево состоит из одного узла. Затем на каждой итерации ищется дуга, добавление которой в дерево приведет к наименьшему увеличению значения целевой функции. Поиск такой дуги осуществляется перебором всех возможных вариантов добавления не более чем d дуг в дерево.
Приведем псевдокод предложенного алгоритма построения покрывающего дерева гиперсети T с корнем r.
FindTree T, r, d return T В начале алгоритма FindTree дерево T состоит из одного корня r. Затем на каждой итерации цикла перебираются все возможные варианты траекторий добавления в дерево не более чем d дуг. Лучшей признается та траектория, для которой отношение приращения целевой функции задачи к приращению числа покрытых вершин будет минимальным. В результате в дерево добавляется первая дуга лучшей траектории. Этот процесс повторяется до тех пор, пока дерево не покроет все вершины гиперсети.
Множество первых дуг траекторий генерируется при помощи функции set E, T. Функция add T, e формирует новое дерево с добавленной в него дугой e. Функция area T возвращает множество вершин, покрытых деревом T. Функция g перебирает траектории добавления дуг.
Опишем подробнее вспомогательные функции алгоритма.
Рекурсивная функция g T, M, f 0, Q, d предназначена для перебора траекторий добавления не более чем d дуг, возвращает отношение приращения целевой функции задачи к приращению числа покрытых вершин. Пусть T S, r, p.
Функция f T предназначена для расчета значения целевой функции для дерева T S, r, p : s, N s, где – вес узла s S дерева, вес узла зависит от количества потомков узла N s в дереве.
Функция tree r построения начального дерева T, состоящего из Функция cov T, V предназначена для проверки обработанности вершин, возвращает истину, если все вершины обработаны ( area T V ), иначе – ложь.
Функция set E, T предназначена для определения множества дуг E /, начало которых не принадлежит дереву T, а конец принадлежит дереву Функция add T, e предназначена для формирования нового дерева T / при помощи добавления в дерево T дуги e w1, w2, возвращает дерево Функция area T предназначена для построения множества вершин Q, покрываемых деревом T S, r, p : Q F // s.
Рассмотрим частный случай алгоритма построения покрывающего дерева с учетом дополнительных ограничений рассматриваемой задачи и параметром глубины вложенности d 1.
Приведем описание алгоритма построения корневого покрывающего дерева гиперсети минимального веса для решения рассматриваемой задачи для заданного корня r.
Шаг 1. Пометить все вершины V как непокрытые. Покрывающее дерево T пусто.
Шаг 2. Добавить корень r в покрывающее дерево T.
Шаг 3. Пока есть непокрытые вершины V и множество гиперебер W не пусто выполнить шаг 4, иначе шаг 10.
Шаг 4. Присвоить переменной record Yrec 1,, Yrec n большое значение.
Шаг 5. Пока множество гиперребер не пусто, выполнить шаг 6, иначе выполнить шаг 9.
Шаг 6. Выбрать пробное гиперребро wtest W в соответствии с правилами построения множеств гиперсети. Рассчитать остаточный запас гиперребра Z wtest, угол примыкания направленного отрезка гиперебра (wtest, s1 ), pwtest s1, s1 S, перепады высот H q1 wtest, q 2.. wtest. Если выполняются ограничения 1 3 модели, то выполнить шаг 7, иначе переходим на шаг 5.
Шаг 7. Рассчитать K wtest. Пробно добавить узел, соответствующий гиперребру, и дугу в покрывающее дерево. Пробно пересчитать количество потомков N stest для всех предков узла stest Owtest. Рассчитать оценочную функцию покрывающего дерева y1,, y n. Если оценочная функция меньше значения переменной record, то переходим на шаг 8, иначе переходим на шаг Шаг 8. Присвоить переменной record текущее значение оценочной функции record y 1,, yn, запомнить текущее гиперребро как рекордное wRe c wtest. Переходим на шаг 5.
Шаг 9. Добавить рекордное гиперребро в покрывающее дерево S wRe c S. Выполнить перерасчет количества потомков N s s S для узлов дерева, оценочной функции дерева y1,, y n. Обновить множество гиперребер W, не участвующих в покрытии, обновить множество покрытых вершин V гиперсети. Переходим на шаг 3.
Проиллюстрируем результат работы алгоритма на примере (Рисунок 1).
Построено корневое дерево на гиперсети с 562 вершинами, 409 гиперребрами (узлами), более чем 2000 дуг. Для примера использованы данные лесозаготовительного предприятия республики Карелия. Консистенция узлов K s показана оттенками серого цвета: чем гуще цвет, тем выше индекс консистенции грунта J. Толщина линий отрезков покрывающего дерева определяет показатель глубины колеи: чем толще линия, тем выше индекс глубины колеи I. Черным квадратом отмечен корень покрывающего дерева.
Рисунок 1 – Пример построения покрывающего дерева гиперсети Небольшие модификации алгоритма позволяют получить покрывающие деревья с более регулярной структурой: с параллельным, диагональным или веерным размещением направленных отрезков покрывающих узлов. Так, введение ограничения на количество поворотов (больших некоторого угла) при примыкании направленных отрезков гиперребер позволяет регулировать вложенность направленных отрезков покрывающего дерева. Задание ограничений на примыкание направленных отрезков гиперребер под примерно равными углами к направленному отрезку родительского гиперребра позволяет получить схему покрывающего дерева с параллельным размещением направленных отрезков покрывающих узлов. На рисунке 2 приведены примеры покрывающих деревьев с регулярной структурой.
Рисунок 2 – Примеры покрывающих деревьев гиперсети с регулярной Для поиска корня r покрывающего дерева необходимо выполнить шаги алгоритма построения корневого покрывающего дерева гиперсети минимального веса для разных вариантов размещения корня и выбрать тот, который соответствует наименьшему значению целевой функции.
Алгоритм FindTree является эвристическим и в общем случае может давать не оптимальные решения.
Если конец любой дуги e E равен корню ( w2 e r ), то рассмотренная задача превращается в задачу построения минимального взвешенного покрытия множества V подмножествами вершин F // w V. Каждое из подмножеств F // w, wW имеет вес w, 1. В этом случае алгоритм FindTree при d 1 дает решение, хуже оптимального не более чем в ln(| V |) 1 раз.
Если для любой гипердуги wW функция w, N w линейна и все подмножества F // w попарно не пересекаются, то рассмотренный алгоритм при d 1 совпадает с алгоритмом Дейкстры поиска кратчайших путей и дает точное решение поставленной задачи.
Если для любой гипердуги wW функция w, N w постоянна, все подмножества F // w попарно не пересекаются, и для каждой дуги e E имеется обратная дуга, указанный алгоритм при d 1 совпадает с алгоритмом Прима построения минимального покрывающего дерева неориентированного графа и также дает точное решение.
Временная сложность алгоритма FindTree в худшем случае равна ), так как на каждом шаге перебирается не более чем V траекторий добавления не более чем d дуг и добавление каждой дуги должно покрыть как минимум одну новую вершину.
При d 1 получаем сложность алгоритма O( V ).
Для уменьшения времени работы алгоритма предлагается использовать структуру данных «двоичная куча» для хранения узлов гиперсети. В качестве ключа используется приращения целевой функции или отношения приращения целевой функции к приращению числа обработанных вершин.
В таком случае на первом шаге построения схемы волоков необходимо построить «двоичную кучу», состоящую из E элементов по числу возможных вариантов дуг, значение элемента кучи содержит приращение целевой функции, которое вызовет добавление дуг в покрывающее дерево.
Временная сложность операции построения кучи составляет O E.
Далее на каждом шаге алгоритма будем выбирать элемент с минимальным приращением целевой функции, который находится в корне двоичного дерева. И соответствующую дугу добавлять в граф верхнего уровня. При этом потребуется пересчитать значения тех элементов двоичной кучи, которые соответствуют дугам, инцидентным только что выбранной дуге. Обозначим константой C – максимальную полустепень исхода гиперребр w W. Тогда при пересчете C элементов двоичной кучи потребуется выполнить C операций по восстановлению основного свойства кучи. Кроме того при извлечении корневого элемента из кучи происходит назначение самого правого листа дерева новым корневым элементом и проталкиванием его вниз по дереву насколько это возможно. Временная сложность процедуры восстановления основного свойства кучи составляет Olog E.
В самом худшем случае при каждом добавлении дуги в граф верхнего уровня гиперсети происходит покрытие только одной вершины V нижнего уровня гиперсети. Тогда для покрытия всех вершин V процедуру наращивания дуг в графе верхнего уровня придется выполнить в худшем случае V раз.
Таким образом, получаем общее время работы алгоритма O E V C log E. Заметим, что E C V. Таким образом, время работы алгоритма построения покрывающего дерева с использованием двоичной кучи при d 1 равно OV C log E, что меньше, чем O( V ).
Опишем необходимые условия существования покрывающего дерева гиперсети.
Для любой вершины нижнего уровня v V гиперсети должно существовать содержащее эту вершину гиперребро верхнего уровня (узел гиперсети) w W, для которого существует путь до корня r, состоящий из дуг верхнего уровня E орграфа A2.
Опишем процедуру проверки условия существования решения, которая является модификацией алгоритма обхода графа в ширину, применительно к гиперсетям. Поиск необработанных вершин идет в ширину, сначала выбираются все смежные узлы (соседи) для выделенного узла r, а затем соседи соседей. Для запоминания еще не обработанных узлов используется очередь, для запоминания уже обработанных узлов – вспомогательный список.
Вспомогательный список сделаем пустым.
Далее зададим стартовый узел r. Включим стартовый узел в очередь.
До тех пор пока очередь не пуста, выполним следующие шаги:
Извлечем из очереди очередной узел wadd W. Проверим по вспомогательному списку обработанность этого узла: если узел уже обработан, то извлечем из очереди следующий узел; если узел еще не обработан, то обработаем его и поместим в список обработанных Пометим как обработанные все вершины v F // wadd, которые принадлежат обработанному узлу (гиперребру) wadd.
Поместим в очередь все не обработанные узлы w1 e W, которые являются началом дуг e E, концом которых является текущий узел Если после выполнения процедуры проверки существования решения все вершины v V окажутся обработанными, то покрывающее дерево T гиперсети может быть построено, иначе построение покрывающего дерева невозможно.
В пятой главе рассмотрены результаты проведения тестовых испытаний сходимости алгоритма, оценки времени работы алгоритма покрытия гиперсети на псевдослучайных данных. Для проведения имитационных экспериментов разработан генератор входного параметра консистенции k (v) вершин v V для алгоритма покрытия гиперсети, который представляет собой алгоритм построения матрицы с заданным значением строк и столбцов и содержит значения разыгрываемой псевдослучайной величины k (v) с заданным законом распределения.
Представим общий принцип генерации значений псевдослучайной величины. Разыгрываем равновероятно распределенную дискретную случайную величину на отрезке 1, 10. Разбиваем отрезок 1, 10 на четыре интервала (по числу возможных значений k (v) ), длина которых равна частоте встречаемости значений консистенции грунта. Каждому интервалу ставим в соответствие значение случайной величины. Далее в зависимости от того, в какой интервал попала разыгранная величина, таким и будет соответствующее значение k (v).
Сгенерировано по 10 экспериментов для каждого из пяти наборов консистенций, содержащих разное соотношение твердых, твердопластичных, мягкопластичных, текучих грунтов. Рельеф участков лесосеки не учитывался. Размер моделируемой лесосеки 100 м 200 м. При накладывании сетки с шагом l 10 м получаем территорию 10 20 участков. Ликвидный запас древесины составляет 120 м га. Лес распределен равномерно на территории лесосеки. Объем пачки древесины P 11 м 3. На основе данных о консистенции участков территории лесосеки, выдаваемых генератором, построены графы нижнего уровня гиперсети. Сгенерировано экспериментов с 200 вершинами, примерно 200 гиперребрами (гиперребро объединяет 9 вершин гиперсети), более 1500 дугами.
Эксперимент произведен на компьютере с процессором Intel 2,5 Ггц, оперативная память 4 Гб. Алгоритм реализован в среде в среде Microsoft Visual Studio.NET 2012 на языке программирования С#.
Имитационные эксперименты проведены для анализа зависимости следующих параметров от глубины вложенности алгоритма (количества дуг d в пробно добавляемых траекториях): времени работы алгоритма, процента покрытия вершин гиперсети, процентного уменьшения числа узлов с недопустимо глубокой и критической колеей.
В таблице 1 приведено среднее время работы алгоритма, процент покрытия вершин гиперсети и процентное выражение уменьшения числа узлов покрывающего дерева с недопустимо глубокой и критической колеей по сравнению с d 1 на 50 экспериментах с разным значением параметра Проведенные испытания и анализ покрывающих деревьев гиперсети показали устойчивость работы алгоритма построения покрывающих деревьев гиперсети. Процент покрытых вершин при d 1 в среднем составляет 87,4%.
Для 95% всех испытаний при d 1 процент покрытия вершин гиперсети принимает значение в диапазоне от 80 до 93%.
По таблице подтверждается экспоненциальный рост времени работы алгоритма в зависимости от глубины вложенности алгоритма d. Отмечается небольшое увеличение среднего количества покрытых вершин при d 2, при дальнейшем росте параметра d рост среднего числа покрытых вершин незначителен. Также отмечается небольшое уменьшение числа узлов покрывающего дерева с недопустимо глубокой и критической колеей при d 2, при дальнейшем росте параметра d уменьшение числа узлов незначительно. Поэтому рекомендуется применять алгоритм покрытия гиперсети с параметром d, равным 1 или 2. Дальнейшее увеличение глубины вложенности алгоритма нецелесообразно.
Также в пятой главе описывается информационная система, которая предназначена для проведения комплексного проектирования временной транспортной сети, используемой для трелевки древесины с учетом основных показателей лесосеки и технических характеристик трелевочного оборудования.
Данный программный комплекс позволяет решать следующие задачи:
1. Проектирование схемы первичных транспортных путей на территории лесосеки с учетом консистенции грунта, запаса леса, рельефа, грузоподъемности и маневренности техники.
2. Поиск места размещения погрузочного пункта на территории лесосеки с учетом не только свойств грунта в непосредственном месте размещения склада, но и с учетом области прилегающей к территории склада, на которую приходится наибольшая нагрузка за счет большего числа проездов техники. Поиск осуществляется с возможностью выбора по всей территории лесосеки, а также выбора из нескольких возможных мест размещения, указанных мастером после осмотра 3. Визуализация получаемых схем размещения погрузочно-транспортных объектов на лесосеке включает реализацию алгоритмов вывода территории лесосеки в виде участков, раскрашенных разными оттенками цвета, оттенки цвета характеризуют категории свойств грунта, также реализацию алгоритмов вывода получаемых схем волоков разной толщины, толщина волока характеризует получаемую глубину колеи после проезда трелевочного оборудования.
4. Расчет основных параметров получаемой схемы освоения лесосеки:
средней длины трелевочных путей от места погрузки до места выгрузки; общей длины трелевочных путей; отношения площади территории лесосеки, занимаемой волоками к общей территории лесосеки; количество волоков по категориям глубины колеи:
рекомендуемой, глубокой, недопустимо глубокой и критической.
В заключении формулируются результаты диссертационного исследования:
1. Предложен метод математического моделирования системы транспортных путей сбора продукции при помощи двухуровневой гиперсети специального вида.
2. Разработан алгоритм построения системы транспортных путей в виде корневого покрывающего дерева двухуровневой гиперсети, предназначенной для сбора продукции с учетом консистенции грунта, рельефа, ограничений на взаимное расположение элементов транспортной сети.
3. Разработаны модификации алгоритма построения покрывающего дерева двухуровневой гиперсети минимального веса для поиска корня покрывающего дерева, для получения покрывающих деревьев с регулярной структурой.
4. Разработан обобщенный алгоритм покрытия гиперсети корневым деревом с параметром глубины вложенности.
5. Разработан программный комплекс, реализующий предложенные алгоритмы и позволяющий оценивать различные технико-экономические показатели транспортных путей сбора продукции.
Список работ, опубликованных автором по теме диссертации 1. Воронова, А. М. Исследование и классификация действительных схем размещения волоков на лесосеке при сортиментной технологии заготовки леса / А. М. Воронова, М. А. Пискунов // Вестник Московского государственного университета леса: Лесной вестник. – 2011. – № 3. – С. 77 – 80.
2. Воронова, А. М. Моделирование схемы волоков при помощи покрытия гиперсети взвешенным корневым деревом / А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Ученые записки Петрозаводского государственного университета. Сер.
«Естественные и технические науки». 2012. № 2 (123). С. 114–117.
3. Воронова, А. М. Задача покрытия гиперсети взвешенным корневым деревом и ее приложение для оптимального проектирования схем волоков на лесосеках / А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Информатика и системы управления. 2012. № 1 (31). С. 56–64. 9 с.
4. Воронова, А. М. Распределение проходов по длине волока и расчёт рейсовых нагрузок трелёвочного трактора при движении по грунтам с низкой несущей способностью на примере хлыстовой технологии заготовки леса / А. М. Воронова, Р. В. Воронов, М. А. Пискунов, В. Н. Васильев // Научный журнал Кубанского государственного аграрного университета. [Электронный ресурс].
– Краснодар: КубГАУ, 2012. – №77(03). – Шифр Информрегистра:
0421200012/0202.
http://ej.kubagro.ru/2012/03/pdf/43.pdf. 11 с.
5. Воронова, А. М. Алгоритм оптимального размещения волоков из условия минимизации повреждения грунта / А. М. Воронова, Р. В. Воронов, М. А. Пискунов, Л. В. Щеголева // Тракторы и сельхозмашины. 2013. № 9. С. 33–35.
6. Воронова, А. М. Математическая модель размещения волоков на лесосеке / А. М. Воронова // Материалы VIII международной научнотехнической конференции «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (22 сентября – 26 сентября 2008 года.). – Петрозаводск: изд-во ПетрГУ, 2008. С. 39-41.
7. Воронова, А. М. Об одном подходе к моделированию размещения погрузочного пункта и схемы волоков на лесосеке / А. М. Воронова, М. А. Пискунов // Актуальные проблемы развития лесного комплекса:
материалы международной научно-технической конференции. – Вологда: ВоГТУ, 2009. С. 14-16.
8. Воронова, А. М. Обоснование использования нечетких структур для моделирования размещения погрузочных пунктов и сети волоков на лесосеке / А. М. Воронова, Р. В. Воронов // Актуальные вопросы современной науки: Сборник научных трудов (Выпуск 7) / Под общ.
ред. С.С. Чернова. – В 2-х кн. – Кн. 1. – Новосибирск: ЦРНС, 2009. С.
9. Воронова, А. М. Математическое моделирование схемы волоков на лесосеке с учетом особенностей грунта / А. М. Воронова // Математика.
Компьютер. Образование. Тезисы XVI международной конференции. – Пущино, 19 – 24 января 2009. С. 85.
10.Воронова, А. М. Задача размещения волоков и погрузочных пунктов на лесосеке и вопросы применения оптимальных схем на практике / А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. № 9 (103). Петрозаводск: Изд-во ПетрГУ, 2009. С.
11.Воронова, А. М. Моделирование размещения погрузочных пунктов и схемы волоков на лесосеке в виде нечеткого гиперграфа / А. М. Воронова // Материалы X международной молодежной научной конференции «Севергеоэкотех-2009» (18-20 марта): в 4 ч.; ч. 4. – Ухта:
УГТУ, 2009. С. 58-61.
12.Воронова, А. М. Гиперграфовая модель задачи размещения погрузочных пунктов и сети волоков на лесосеке с нечетким описанием свойств грунта / А. М. Воронова, Р. В. Воронов // Материалы IX международной научно-технической конференции «Новые информационные технологии в ЦБП и энергетике». Петрозаводск: Издво ПГУ, 2010. С. 30–34.
13.Воронова, А. М. Методы и модели построения схем волоков на лесосеке / А. М. Воронова, М. А. Пискунов // Опыт лесопользования в условиях Северо-запада РФ и Фенноскандии: Материалы международной научно-технической конференции, (20 – 22 сентября) – Петрозаводск: ПетрГУ, 2011. C. 28 – 29.
14.Воронова, А. М. Перспективы создания и использования систем автоматизированного проектирования схем волоков на лесосеке / А. М. Воронова, М. А. Пискунов // Актуальные проблемы лесного комплекса: Сборник научных трудов Брянской государственной инженерно-технологической академии. Вып. 29. Брянск. 2011. С. 38 – 15.Воронова, А. М. Применение гиперсети для моделирования и построения схемы волоков с учетом свойств грунта и рельефа на лесосеке / А. М. Воронова // Материалы X юбилейной международной научно-технической конференции «Новые информационные технологии в ЦБП и энергетике». Петрозаводск: Изд-во ПетГУ, 2012.
С. 31–33.
16.Воронова, А. М. Свидетельство о регистрации электронного ресурса.
Программа «Планирование схемы волоков на лесосеке» / А. М. Воронова, Р. В. Воронов // Петрозаводский государственный университет. Регистрация в Объединенном фонде электронных ресурсов "Наука и образование" № 17756 от 27.12.2011.
17.Воронова, А. М. Свидетельство о государственной регистрации программы для ЭВМ. Информационно-аналитическая система «Расчет схемы волоков на лесосеке с учетом минимизации отрицательного воздействия трелюющей техники на грунты» / А. М. Воронова, Л. В. Щеголева // Петрозаводский государственный университет.
Регистрация в Реестре программ для ЭВМ № 2013614304 от 29.04.2013.
18.Воронова, А. М. Свидетельство о государственной регистрации программы для ЭВМ. Информационно-аналитическая система «Составление схемы путей первичного транспорта леса на лесосеке с учетом минимизации расходов на топливо» / А. М. Воронова, Р. В. Воронов // Петрозаводский государственный университет.
Регистрация в Реестре программ для ЭВМ № 2013614105 от 23.04. Подписано в печать 08.11.2013. Формат 60х84 1/16.
Уч.-изд.л. 1,0. Тираж 120 экз. Изд. № 395.
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«