АНАЛИЗ АЛГОРИТМОВ ДЕКОМПОЗИЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЗАЦИИ УПРАВЛЕНИЯ ТРУБОПРОВОДОМ

ВВЕДЕНИЕ

Использование различных нефтепродуктов уже давно стало неотъемлемой частью жизни большинства людей. Пластмасса, бензин, газ на плите, - это лишь малая часть из них. Также экспорт нефти и газа является важным источником дохода нашей страны. По данным Росстата за 2012 г. общая протяжённость нефтепродуктоводов составляла 250 тыс. км. На сегодняшний день это число значительно больше. По этим трубопроводам перекачиваются тысячи тонн нефти и газа по стране и в зарубежные страны, такие как Турция, Белоруссия, Грузия или страны западной Европы. Сейчас в России построено более двадцати крупных нефте- и газопроводов, в их числе: Крупнейший нефтепровод «Дружба», который перекачивает 66,5 млн. т. нефти в год в страны восточной Европы, «Балтийская трубопроводная система», ежегодно передающая более 74 млн. т. или «Голубой поток», протяжённостью более 1200 км., по которому ежегодно в Турцию продаётся примерно 16 млрд. кубических метров газа. В крупных компаниях, таких «Газпром», «Транснефть», «Сургутнефтегаз» и некоторых других работают тысячи человек, обслуживая и обеспечивая работу нефтегазовых трубопроводов России.

Но трубопровод – не просто линия на карте или труба в поле. Это огромная система, представляющая собой сотни нефтеперекачивающих станций (НПС), задвижек, резервных парков и прочих объектов, необходимых для правильной транспортировки и хранения нефтегазовых продуктов. В связи с огромными размерами системы в целом, актуальной становится проблема автоматизации управления трубопроводом, встаёт вопрос: как эффективнее разделить весь трубопровод на области так, чтобы упростить контроль всего потока. И в решении данной задачи может помочь применение алгоритмов декомпозиции графов. Каждый трубопровод можно представить в виде ориентированного графа, где рёбрами являются трубы, а вершинами – объекты (НПС, задвижки и т.д.). Если правильно подобрать (или скомбинировать из нескольких алгоритмов) алгоритм декомпозиции, то огромную систему, тянущуюся на тысячи километров, можно эффективно разделить сначала между территориальными диспетчерскими пунктами (ТДП, например, Уфа-Камбарка), а затем между контрольными пунктами (КП, например, 18 км. трассы Салават-Уфа).

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Изложить определения, необходимые для решения последующих задач.
2. Рассмотреть существующие алгоритмы.
3. Сформулировать критерии, исходя из предметной области, и сравнить рассмотренные алгоритмы по данным критериям.
4. Выбрать наиболее подходящий алгоритм или предложить альтернативный вариант.

ОСНОВНЫЕ ПОНЯТИЯ

Рассмотрим некоторые определения теории графов:

Сетевой граф – орграф, среди вершин которого выделены особые группы вершин – источники (вершины, имеющие только выходящие рёбра) и стоки (вершины, имеющие только входящие рёбра).[2]

Простой путь – путь, в котором ни одна вершина не может появиться дважды.[2]

Цикл – подграф исходного графа, для любой вершины v которого существует хотя бы один простой путь в саму вершину v.

Сильно связный граф (сильный) – граф, для любых двух различных вершин v1,v2 которого существует по крайней мере один путь, соединяющий v1 и v2.[1]

Компонента сильной связности – сильно связный подграф исходного графа.[1]

Клика – подграф исходного графа, любые две вершины которого соединены ребром.[3]

Хроматическое число – минимальное количество цветов, в которое можно окрасить вершины графа так, чтобы любые две смежные вершины имели разные цвета.

Домен – множество объектов, объединённых по определённому признаку.

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

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

БАЗОВЫЕ АЛГОРИТМЫ

Теперь рассмотрим несколько алгоритмов декомпозиции графов:

Алгоритм 1: Декомпозиция сетевого графа.

Декомпозиция сетевого графа заключается в разбиении исходного графа на простые пути от источника к стоку и циклы. На рисунке 1 представлена блок-схема рассматриваемого алгоритма. На рисунке 2 показано, как сетевой граф разбивается на два потока и три цикла.

Рисунок 1. Блок-схема алгоритма декомпозиции сетевого графа

Алгоритм прост: достаточно последовательно применять алгоритмы нахождения потока в сетях и циклов. Спустя несколько итераций, граф удастся декомпозировать на простые пути от источника к стоку и простые циклы.

Рисунок 2. Реализация алгоритма декомпозиции на сетевом графе[1]

В исходном сетевом графе находятся простые пути: s-x2-x4-t и s-x1-x3-x2-x4-t. Затем из исходного графа выделяются в качестве подграфов следующие циклы: x1-x3-x2, x4-x5-x6-x7 и x5-x6-x7. Таким образом, исходный сетевой граф можно разделить на пять подграфов.

Алгоритм 2: Декомпозиция по связности.

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

На рисунке 3 представлена блок-схема алгоритма.

Рисунок 3. Блок-схема алгоритма декомпозиции по связности

После применения алгоритма граф разбивается на компоненты сильной связности, клики и не вошедшие в них вершины исходного графа.

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

Алгоритм 3: Распределение вершин и рёбер по доменам.

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

Рисунок 4. Блок-схема алгоритма декомпозиции по доменам

Рассмотрим возможные критерии, по которым происходит добавление вершины в домен:

Минимизация (максимизация) веса рёбер вне или внутри доменов. Данный критерий позволяет собрать в домены наиболее близкие друг к другу вершины. На примере конкретной предметной области это означает, что наиболее близкие или наиболее уязвимые участки будут объединены в домен.

Каждой вершине графа, помимо номера, можно присвоить набор параметров, который можно использовать в качестве критерия для разделения на домены. Это может быть: надёжность, важность объекта, тип объекта, пропускная способность и т.д.

В качестве критерия можно использовать хроматическое число графа.

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

КРИТЕРИИ ОЦЕНКИ АЛГОРИТМОВ

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

Первым критерием, несомненно, должна быть возможность применения для нефтепровода или газопровода.

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

С алгоритмом 1 (декомпозиция сетевого графа), однако, не всё так ясно. Чаще всего в реальной схеме трубопровода сложно выделить источник и сток, или их довольно много. Также может оказаться, что один и тот же участок трубы может оказаться в ведении нескольких диспетчеров, что нежелательно. В больших системах источник и сток могут физически находиться на большом расстоянии друг от друга, что значительно затруднит работу с трубопроводом, например, во время аварии.

Однако и для первого алгоритма можно найти применение на практике. Примером может служить нефтепровод «Дружба», который для удобства был разделён на два потока: северный и южный. Именно такое разделение и подразумевает декомпозиция сетевого графа. При необходимости разбить «вытянутый» трубопровод со множеством ответвлений на несколько отдельных потоков можно использовать данный алгоритм.

Таким образом, все три рассмотренных алгоритма применимы к заданной предметной области.

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

Существует несколько вариантов алгоритмов нахождения потоков в сетях. В данной работе будет оцениваться алгоритм Форда-Фалкерсона [2], чья сложность составляет O(V²*E), где V – число вершин, а Е – число рёбер. Нахождение циклов решается при помощи обхода в глубину. Сложность алгоритма обхода меньше, чем сложность поиска потока, следовательно общая сложность алгоритма составляет O(S*T*V²*E), где S – число истоков, а T – число стоков.

Алгоритм 2 состоит из последовательного соединения метода Косарайю нахождения максимальной компоненты сильной смежности и алгоритма Брона-Кербоша для нахождения клик. Метод Косарайю имеет сложность O(V²). Алгоритм Брона-Кербоша является np-полным, однако в 2004 году было доказано, что сложность алгоритма в худшем случае равна O(3^V/3). Поскольку сложность алгоритма нахождения клик гораздо больше сложности алгоритма нахождения компоненты сильной смежности, общая сложность алгоритма равна O(3^V/3).

В случае алгоритма 3 реализация заметно усложняется. Суть в том, что добиться разделения по критерию можно разными путями, каждый из которых может делать декомпозицию более или менее эффективной. Например, если задать в качестве критерия минимизацию веса рёбер в домене, то удаление какого-либо ребра из домена (вследствие удаления вершин этого ребра) может привести к уменьшению суммарного веса рёбер в одном домене, но к увеличению в другом. Поэтому в дополнение к простым действиям самого алгоритма, чья сложность равна O(K(V+E)), где K – количество различных критериев, необходимо решить задачу оптимизации (в частном случае – линейного программирования). Это означает, что достижения оптимального разделения исходного графа алгоритм 3 придётся выполнять несколько раз (количество проходов невозможно предсказать, можно только оценить). Реализация алгоритма усложняется из-за необходимости учитывать множество разнообразных критериев в одной программе.

Третьим критерием рассмотрим эффективность хранения результатов декомпозиции.

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

В отличие от алгоритма 1, алгоритм 2 не хранит ненужных копий рёбер или вершин. Каждая клика или компонента сильной связности может быть стянута в одну вершину без добавления лишних данных.

Хотя алгоритм 3 проводит с графом те же манипуляции, что и второй алгоритм, для его корректной работы необходим куда больший объём памяти, чем алгоритм 2 из-за решения задачи оптимизации.

Четвёртым критерием рассмотрим, насколько широко алгоритмы могут быть применены к данной предметной области.

Алгоритм 1 может применяться для решения только одной задачи декомпозиции: разделения исходного графа на потоки. Для решения других задач на декомпозицию он неприменим.

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

В отличие от первых двух алгоритмов, алгоритм 3 универсален. Задавая различные критерии, можно добиться какого угодно разбиения.

Ниже приведена таблица 1, где представлены все рассмотренные критерии.

Таблица 1.

Сводная таблица сравнения алгоритмов

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

КОМБИНИРОВАННЫЙ АЛГОРИТМ

В качестве результирующего алгоритма можно рассмотреть следующий:

1. Исходный граф, при помощи алгоритма декомпозиции сетевого графа разбивается на потоки и циклы, что упрощает дальнейшую работу с получившимися подграфами (в случае, если трубопровод не вытянут на большие расстояния, данный шаг можно пропустить).
2. Выбирается необходимый критерий.
3. Если критерий основан на географическом положении объектов, целесообразно применить алгоритм 2, так как он работает эффективнее.
4. В противном случае применяется алгоритм 3, а затем решается оптимизационная задача.

На рисунке 5 представлена блок-схема результирующего алгоритма.

Рисунок 5. Блок-схема алгоритма декомпозиции по доменам

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

ВЫВОД

Таким образом, в данной работе были изложены несколько понятий теории графов, рассмотрены существующие алгоритмы (декомпозиция сетевого графа, по смежности и по доменам), произведено сравнение алгоритмов по сформулированным критериям, сформулирован комбинированный алгоритм.

В следующем исследовании планируется провести исследование эффективности сформулированного комбинированного алгоритма.

Список литературы:

1. Карпов Д.В. Теория графов [Текст]: учебник / Д.В. Карпов. – СПб: СПбГУ, 2007. – 475 с.
2. Кондрашкин А.А. Построение резервных маршрутов в ориентированном невзвешенном графе [Текст] / А.А. Кондрашкин // - Сфера образования. -  2016. - № 2(4). с. 115-119.
3. Кристофидес Н. Теория графов. Алгоритмический подход [Текст]: монография / Н.Кристофидес. – Москва: изд-во «Мир», 1978. – 427 с.
4. Методические указания по проведению лабораторных работ «Задачи декомпозиции графов» [Текст]: уч. пособие для студ. вузов – Нижний Новгород.: Нижегородский государственный университет им. Н.И. Лобачевского, 2001.
5. Статистики Росстата [Электронный ресурс]. - www.gks.ru
6. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий [Текст]: уч. пособие для студ. вузов / С.Д. Шапорев. – СПб.: Министерство образования и науки Российской Федерации Балтийский государственный технический университет «Военмех», 2004. – 396 с.
7. J. Ian Munro. Computing and Combinatorics [Текст] / J. Ian Munro. – Korea.: 10^th Annual International Conference, August 2004.