Решение задачи Штейнера в рамках поиска оптимальной структуры сети с применением методов популяционной оптимизации

Обложка

Цитировать

Полный текст

Аннотация

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

Цель исследования: заключается в оценке пригодности применения генетических алгоритмов для поиска схемы соединения сети с наименьшими суммарными потерями активной мощности.

Методы и объекты исследования: эвристические методы популяционной оптимизации.

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

Полный текст

ВВЕДЕНИЕ

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

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

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

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

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

 

Рисунок 1. Задача Штейнера а) TV; б) TV

 

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

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

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

 

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

 

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

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

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

 

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

 

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

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

 

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

 

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

 

Потери мощности, МВт

Оптимальный вариант

0,620

Неоптимальный вариант

0,847

Классический подход

0,646

 

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

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

×

Об авторах

Всеволод Андреевич Ткаченко

Югорский государственный университет

Автор, ответственный за переписку.
Email: v_tkachenko@ugrasu.ru

Преподаватель Политехнической школы

Россия, Ханты-Мансийск

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

  1. ГИС ВЛЭП – новые возможности для предприятий электрических сетей // Электроэнергия. Передача и распределение. – 2022. – № 2(71). – С. 50-51. – Текст: непосредственный.
  2. Вайсблат, Н. Э. ГИС как инструмент мониторинга объектов энергетики / Н. Э. Вайсблат, И. С. Перемитин, К. В. Иконникова. – Текст: непосредственный // Проблемы геологии и освоения недр : Труды XVIII Международного симпозиума имени академика М.А. Усова студентов и молодых учёных, посвященного 115-летию со дня рождения академика Академии наук СССР, профессора К. И. Сатпаева, 120-летию со дня рождения члена-корреспондента Академии наук СССР, профессора Ф.Н. Шахова, Томск, 07–11 апреля 2014 года. Том 1. – Томск: Национальный исследовательский Томский политехнический университет, 2014. – С. 597-600.
  3. Трипутина, В. В. Моделирование и разработка ГИС-сервисов для задач исследований в области энергетики* / В. В. Трипутина. – Текст: непосредственный // Вычислительные технологии. – 2008. – Т. 13, № S1. – С. 78-87.
  4. Применение ГИС-технологий в электроэнергетических системах / С. Г. Слюсаренко, К. И. Заподовников, С. А. Субботин, А. В. Скворцов. – Текст: непосредственный // Геоинформатика-2000 : труды Международной научно-практической конференции, Томск, 12–14 сентября 2000 года / Под редакцией А.И. Рюмкина, Ю.Л. Костюка, А.В. Скворцова. – Томск: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет, 2000. – С. 234-236.
  5. Смирнов, С. В. Краткое описание разработки алгоритма автоматической трассировки кратчайшего пути и подсистемы решения оптимизационных задач / С. В. Смирнов. – Текст: непосредственный // The Scientific Heritage. – 2020. – № 55-1(55). – С. 64-66.
  6. Скиена, С. С. Алгоритмы. Руководство по разработке. – 3-е изд.: Пер. с англ. – СПб.: БХВ-Петербург, 2023. – 848 с.: ил. – Текст: непосредственный.
  7. Дэн Саймон, Алгоритмы эволюционной оптимизации / пер. с англ. А.В. Логунова. – М.: ДМК Пресс, 2020. – 1002 с.: ил. – Текст: непосредственный.
  8. J. Shu, L. Wu, Z. Li, M. Shahidehpour, L. Zhang and B. Han, “A New Method for Spatial Power Network Planning in Complicated Environments,” in IEEE Transactions on Power Systems, vol. 27, no. 1, pp. 381-389, Feb. 2012, doi: 10.1109/TPWRS.2011.2161351.
  9. Ткаченко, В. А. Разработка методов и алгоритмов оптимизации схемно-режимных параметров электрических систем, включая минигрид: специальность 2.4.3. Электроэнергетика: диссертация на соискание ученой степени кандидата технических наук / Ткаченко Всеволод Андреевич, 2023. – 223 с. – Текст: непосредственный.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Рисунок 1. Задача Штейнера

Скачать (51KB)
3. Рисунок 2. Задача Штейнера.

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

Скачать (148KB)
5. Таблица 1. Ценовая поверхность рассматриваемой области.

Скачать (267KB)

© Югорский государственный университет, 2024

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-ShareAlike 4.0 International License.