Solution of the Steiner problem in the search for optimal network structure using population optimization methods

Full Text

ВВЕДЕНИЕ

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

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

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

В настоящее время широко используются ГИС для проектирования инженерных объектов [1-5]. Для ГИС объекты генерации, распределения и потребления представляются в виде графа $G=(V, E)$, где объекты представляются в виде узлов (вершин) $V$, а линии электропередачи, связывающие их, – в качестве ребер $E$. В подобном описании задача сводится к решению задачи Штейнера, т. е. обобщенной задаче поиска минимального остовного дерева.

Задача Штейнера формулируется как поиск наименьшего дерева, соединяющего все вершины $T$. Возможны два случая: а) $T\subseteq V$; б) $T\ne V$ (рисунок 1). В первом случае задача сводится к поиску минимального остовного дерева для графа $G$, которую можно решить классическими алгоритмами Прима и Краскала. Во втором случае задача отличается от поиска минимального остовного дерева тем, что необходимо выбрать (найти) дополнительные точки в пространстве для минимизации стоимости дерева [6].

Рисунок 1. Задача Штейнера а) $T\subseteq V$; б) $T\ne V$

Стоит отметить, что задача построения технических коммуникаций усложняется наличием на территории размещения как объектов техногенного характера, так и природных, естественных преград, в худшем случае, – территория описывается дискретно заданными характеристиками. Таким образом, сложность задачи определяется как NP-мерная.

Для решения поставленной задачи предлагается использовать эвристические алгоритмы популяционной оптимизации [7]. Генетические алгоритмы позволяют производить анализ множества решений, ранжируя их по выбранному пользователем критерию. Данные алгоритмы дают достаточно «хорошие» решения, в том числе, при заданных дискретно начальных условиях, что делает их пригодными для поиска структуры электрической сети не только на территориях городской застройки, но и для построения межсистемных связей, в том числе, связей в рамках построения микрогрид на резконеоднородном ландшафте территорий Крайнего Севера.

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

Рисунок 2. Задача Штейнера.

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

РЕЗУЛЬТАТЫ И ОБСУЖДЕНИЕ

Для проведения эксперимента была выбрана область 400 км² [8]. Ценовая поверхность рассматриваемой области представлена в таблице 1.

Таблица 1. Ценовая поверхность рассматриваемой области.

На данной территории располагаются 15 пунктов потребления электроэнергии. Необходимо произвести поиск точки Штейнера для расположения в ней узла генерации, через который идет связывания всех пунктов в единую электрическую сеть. Исходные данные и более подробное рассмотрение работы генетического алгоритма представлены в [9].

В результате работы производился поиск точки генерации, построение путей от неё к пунктам потребления (линий электропередачи), производился выбор проводников линий, оценка общей стоимости строительства и потерь мощности элементами сети. Примеры поиска представлены на рисунке 3. Оценка успешности решения представлена в таблице 2.

Рисунок 3. Промежуточные результаты поиска точки Штейнера генетическим алгоритмом: а) оптимальный вариант; б) неоптимальный вариант; в) классический подход.

Таблица 2. Ценовая поверхность рассматриваемой области.

ЗАКЛЮЧЕНИЕ И ВЫВОДЫ

В результате работы был предложен подход к определению точки Штейнера, позволяющей построить электрическую сеть, обладающую наименьшими потерями с применением алгоритмов популяционной оптимизации. На примере области площадью 400 км² с использованием предлагаемого подхода была построена электрическая сеть. В результате применение генетического алгоритма позволило найти такую структуру сети, которая, в отличие от сети, полученной классическим методом, позволила сократить потери мощности на 4 %. Сокращение величины потерь свидетельствует о применимости данного подхода к оптимизации структуры электрической сети как следствие решения задачи Штейнера.

About the authors

Vsevolod A. Tkachenko

Author for correspondence.
Email: v_tkachenko@ugrasu.ru

Lecturer of the Polytechnic School

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Figure 1. Steiner's problem

Download (51KB)

Indexing metadata

3. Figure 2. Steiner problem.

Download (36KB)

Indexing metadata

4. Figure 3. Intermediate results of searching for the Steiner point using a genetic algorithm: a) optimal option; b) non-optimal option; c) classical approach.

Download (148KB)

Indexing metadata

5. Table 1. Price surface of the area under consideration.

Download (267KB)

Indexing metadata