Автоматика и телемеханика, № 5, 2021

Робастное, адаптивное и сетевое

управление

А.А. КРЫГИН, канд. техн. наук (andreyakr@yandex.ru)

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

МЕТОДЫ ПОИСКА КОНФИГУРАЦИЙ

РАСПРЕДЕЛИТЕЛЬНЫХ СЕТЕЙ

Рассматривается задача нахождения полного множества допустимых

конфигураций распределительной сети. При ее решении используется ап-

парат теории графов для нахождения предельных графов. Предложен

новый, по сравнению с известными в литературе, метод нахождения пол-

ного множества предельных графов, доказаны ряд свойств этого метода

и его корректность. На качественном уровне выполнено сравнение эф-

фективности различных методов и показано, что предложенный метод

отличает существенно более высокая скорость вычислений.

Ключевые слова: распределительные сети, поиск конфигурации сети, гра-

фовые модели сетей, предельные графы.

DOI: 10.31857/S0005231021050032

1. Введение

Поиск конфигураций физических сетей распределения энергии и ресурсов

от их источников к потребителям осуществляется при решении различных

задач, среди которых выделим две: структурная оптимизация режимов рас-

пределительных сетей (в частности, электрических) и определение степени

уязвимости потребителей из-за прерывания их снабжения энергией и ресур-

сами при негативных воздействиях на сеть поставки.

К задаче структурной оптимизации диспетчерские службы обращаются в

режимах балансировки нагрузки, минимизации потери электроэнергии, ана-

лиза устойчивости, противоаварийного управления и в других случаях [1-9].

Оптимизация сети выполняется на взвешенном графе, вершины которого со-

ответствуют узлам коммутации, а ребра линиям связи. Решение задачи

заключается в поиске и выборе оптимальной конфигурации посредством под-

ключения узлами коммутации тех или иных связей к сети передачи и распре-

деления энергии и ресурсов. Для рассматриваемых сетей поиск оптимальной

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

дача:

• Поиск возможных конфигураций;

• Выбор оптимальной конфигурации.

Далее рассмотрен первый этап поиск возможных конфигураций посред-

ством подключения узлами коммутации тех или иных связей к сети распре-

деления энергии и ресурсов.

Вторая задача, также рассматриваемая далее, это определение степени

уязвимости потребителей из-за прерывания снабжения энергии и ресурсов

при негативных воздействиях на сеть. Решение этой задачи рассматривается

в разрезе нахождения вариантов присоединения потребителей к распредели-

тельной сети и представляет интерес при выработке мер противодействия

негативным воздействиям на элементы сетевой инфраструктуры.

Значительная избыточность, вводимая в распределительные сети для по-

вышения надежности, создает определенные трудности в поиске конфигура-

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

изложенный в [8]. Также в [8] доказаны корректность метода и ряд свойств

предельных графов, в [9] показано применение метода для структурной оп-

тимизации электрических сетей.

В данной статье указаны недостатки метода [8], расширено понятие пре-

дельных графов, предложен более эффективный метод их построения, дока-

зана его корректность и проведена качественная сравнительная оценка двух

методов.

2. Графы распределительных сетей

Рассматриваются распределительные сети, которые обладают следующим

свойством: каждый потребитель снабжается от одного источника. Как пра-

вило, данное свойство выполняется для большинства распределительных се-

тей. Такие сети характеризуются разомкнутой структурой электроснабже-

ния, формируемой узлами коммутации. Пример графа распределительной

некоммутируемой сети приведен на рис. 1,а, вершины S1 и P 1 соответствуют

источнику и потребителю. Обозначим множество всех вершин графа, исклю-

чая вершины источники и вершины потребители через U, через |U| обозначим

мощность множества U.

В задаче структурной оптимизации вершины U1 - U3 соответствуют эле-

ментам сети, таким как подстанции, тепловые пункты и другие сооружения,

в составе которых находятся узлы коммутации. Обозначим множество ком-

мутаторов через C и расположим эти коммутаторы на тех связях, которыми

они управляют. Граф, соответствующей коммутируемой сети, изображен на

рис. 1,б .

Рассмотрим следующие графовые модели распределительных сетей.

Некоммутируемую распределительную сеть представим в виде графа I

со свойствами:

множество вершин этого графа V состоит из трех непересекающихся

подмножеств V = S ∪ P ∪ U. Множество S будем называть множеством вер-

шин источников, множество P

множеством вершин потребителей, U

определено выше;

для каждой вершины p ∈ P существует путь s → p хотя бы из одной

вершины s ∈ S.

Рис. 1. Примеры некоммутируемого (а) и коммутируемого (б ) графов распре-

делительных сетей.

Коммутируемую распределительную сеть будем представлять в виде

графа I со свойствами:

множество вершин I описывается четверкой V = S ∪ P ∪ C ∪ U, где

множество C составляют вершины коммутаторы, а множество U

все

остальные вершины, исключая вершины множеств S, P и C;

маршруты передачи определяются состоянием вершин коммутации:

C = C⁺ ∪ C^-, где C⁺ подмножество вершин коммутаторов в состоянии

“открыто”, C^- подмножество вершин коммутаторов в состоянии “закры-

то”;

свойство существования пути аналогично графам некоммутируемых се-

тей;

степень каждой вершины c ∈ C равна двум; степень каждой вершины

p ∈ P равна единице;

каждое ребро, выходящее из вершины источника, соединено с вершиной

коммутатором.

При решении описанных выше задач удобно использовать общие (расши-

ренные по сравнению [8]) определения графа конфигурации и предельного

графа.

Обозначим через Z подмножество вершин графа, Z ⊆ U ∪ C. Для ком-

мутируемых сетей Z = C, для некоммутируемых сетей Z = U. Для любого

подмножества вершин W , W ⊆ Z определим следующую операцию:

• удалим из графа подмножество W ;

• после этого также удалим из графа все вершины, не лежащие ни на од-

ном пути s → p, где s ∈ S, p ∈ P . Удаляемой вершиной может быть и вершина

источник ŝ ∈ S, если для любого p ∈ P нет ни одного пути ŝ → p.

Назовем описанную операцию “построением W подграфа”.

Получившийся в результате описанной операции W подграф будем на-

зывать графом конфигурации, если для каждой вершины p ∈ P существует

путь s → p хотя бы из одной вершины s ∈ S.

Граф конфигурации будем называть предельным графом, если при удале-

нии из него любой вершины z ∈ Z\W найдется вершина p ∈ P , для которой

не будет ни одного пути s → p, где s ∈ S.

Таким образом, нахождение всех графов конфигурации и всех предельных

графов сводится к нахождению соответствующих им подмножеств W или

подмножеств Z\W .

3. Описание метода поиска конфигураций

в графах распределительных сетей

Так как граф конфигурации, согласно определению, содержит пути от ис-

точников к потребителям, то в комбинациях этих путей могут содержаться

циклы и присутствовать пути с избыточным количеством вершин множе-

ства U, при удалении которых сохраняется достижимость вершин множе-

ства P из S.

Далее предлагается метод построения графов конфигурации сети, которые

после операции проверки на поглощение (также описанной ниже) преобразу-

ются в полное множество предельных графов.

Предлагаемый метод формирования графов конфигурации (далее компо-

нентный метод) использует поиск в ширину (BFS ) при движении от вершин

из множества P против направления потока к вершинам из множества S.

В процессе движения формируются пути, образующие компоненту. При пе-

ресечении одного пути с другим происходит слияние путей и формируются

деревья. Как и в BFS, у каждого дерева есть активная вершина, из которой

происходит движение (развитие), но в отличие от BFS используется двойная

очередь: очередь компонент и очередь активных вершин компоненты.

Опишем метод. Предварительно введем ряд определений.

Компонента структура, состоящая из деревьев и очереди активных вер-

шин. Очередь активных вершин соответствует вершинам каждого дерева, из

которых происходит движение, при этом у активной вершины хранится ссыл-

ка на дерево, к которому она принадлежит.

Выходной массив компонент конечный результат, представленный в

виде массива.

Операция клонирования заданной компоненты создание новой компо-

ненты и копирование в нее заданной компоненты, т.е. всех деревьев и очереди

активных вершин.

Начальная инициализация формирование начальной компоненты, со-

стоящей из |P | вершин потребителей и очереди активных вершин, в которую

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

в которую заносится начальная компонента, и создание выходного массива

компонент (нулевого для начальной инициализации).

Алгоритм.

Шаг 0. Начальная инициализация.

Шаг 1. Из очереди компонент отбирается компонента, которую обозначим

через I.

Шаг 2. Из очереди активных вершин компоненты I отбирается вершина i,

i ∈ K, где K дерево:

2.1. Для i определяются ее вершины потомки;

2.2. Для каждой вершины потомка j выполняется клонирование компонен-

ты I с добавлением к дереву K вершины j. После клонирования компонента I

удаляется;

2.3. Обработка клонированной компоненты:

2.3.1. Клонированная компонента удаляется, если дерево K содержало вер-

шину j еще до его клонирования в п. 2.2. Переход к шагу 3;

2.3.2. В очередь активных вершин клонированной компоненты добавля-

ется вершина j, если она не является вершиной источником и не является

вершиной другого дерева;

2.3.3. Если вершина j является вершиной другого дерева M, то все дере-

во K присоединяется к дереву M.

2.4. Если в клонированной компоненте нет активных вершин, то она поме-

щается в выходной массив, если активные вершины есть, то она помещается

в очередь компонент.

Шаг 3. Если очередь активных вершин компоненты I не пуста, то переход

к шагу 2.

Шаг 4. Если очередь компонент не пуста, то переход к шагу 1.

Конец.

4. Свойства компонентного метода

Перечислим необходимые для дальнейших доказательств результаты пуб-

ликации [8].

В [8] приведен алгоритм получения полного множества предельных гра-

фов, использующий построение комбинаций всех путей от вершин источников

до вершин потребителей. Этот алгоритм включал следующие этапы:

1. Формирование списков всех возможных путей до каждой вершины мно-

жества P от вершин множества S. Общее число списков равно |P |.

2. Составление всех комбинаций путей из списков. Комбинация представ-

ляет собой объединение вершин из |P | путей, l-й путь выбирается из l-го спис-

ка. Каждой j-й комбинации соответствуют граф конфигурации τ_j и подмно-

жества C^+j и C^-j, C^+j вершины коммутаторы, принадлежащие τ_j, C^-j

остальные вершины коммутаторы.

3. Построение предельных графов. Выполняется последовательное срав-

нение между собой комбинаций и удаление тех из них, в которые осуществ-

ляется вложение вершин множества C⁺. Так, если для m-й и k-й комбина-

ций выполняется условие C^+k ⊆ C^+m, то удаляется m-я комбинация. Графы,

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

ми τ^limj. Будем называть такую операцию “проверкой на поглощение”, а весь

алгоритм

“методом простых комбинаций”.

Рис. 2. Фрагмент исходного графа.

В [8] были доказаны следующие утверждения:

1. Корректность алгоритма построения комбинаций.

2. Массив, состоящий из графов конфигурации и содержащий полное мно-

жество предельных графов, после выполнения проверки на поглощение будет

содержать только полное множество предельных графов.

Для каждой компоненты I выходного массива построим W подграф, вы-

брав W = Z\I и соответственно для коммутируемых сетей C⁺ = I ∩ Z.

Справедливы три утверждения:

Утверждение 1. Каждый W подграф является графом конфигурации,

а массив W подграфов содержит полное множество предельных графов.

Утверждение 2. При выполнении шага 1 и шага 2 компонентного ме-

тода порядок выбора компоненты и активной вершины может быть про-

извольным.

Утверждение 3. Если в исходном графе каждая вершина ветвления

(вершина, степень которой больше двух) окружена вершинами коммута-

торами (или в случае некоммутируемых сетей вершинами степени 2,

рис. 2), то массив графов будет содержать только полное множество пре-

дельных графов без других графов конфигурации.

Доказательства утверждений 1-3 приведены в Приложении.

5. Качественное сравнение вычислительной сложности компонентного

метода и метода простых комбинаций

Результаты моделирования показали, что компонентный метод существен-

но превосходит по скорости метод простых комбинаций. При этом во многих

случаях наиболее быстро работал следующий метод:

Рис. 3. Пример исходного графа.

сначала выполнялось построение компонент от одной выбранной вер-

шины потребителя. В этом случае каждая компонента состояла из пути от

выбранной вершины потребителя до вершины источника;

после этого продолжалось построение компонент от остальных вершин

потребителей.

Корректность этого метода вытекает из утверждения 2.

Количественная оценка вычислительной сложности обоих методов выхо-

дит за рамки данной статьи. Укажем здесь на качественное преимущество

компонентного метода.

Основной недостаток метода простых комбинаций заключается в том, что

количество предельных графов составляет малую долю от количества всех

комбинаций и операция проверки на поглощение требует значительных вы-

числительных ресурсов. Причина такого соотношения состоит в вершинах

ветвления множества U. Рассмотрим это на примере, приведенном на рис. 3.

Очевидно, что у этого графа будет 3 предельных графа, в каждом из

которых имеется единственная вершина источник. На 1-м этапе метода про-

стых комбинаций определяется по 3 пути для каждой вершины потребителя.

Множество всех возможных комбинаций этих путей (2-й этап) состоит из

27 комбинаций (часть из которых будут одинаковыми). Появление комбина-

ции (на 2-м этапе), не соответствующей предельному графу, возникает всякий

раз, когда объединяются два пути, проходящие через вершину ветвления u₁,

у которых фрагменты от вершины источника до вершины ветвления различ-

ны. Проведем следующую упрощенную оценку. Пусть d степень некоторой

вершины ветвления u, P множество вершин потребителей, у которых суще-

ствуют пути из вершин источников, проходящие через u, p = |P |. Пусть для

каждой вершины r ∈ P существует единственный путь u - r. Для приведен-

ного примера d = 5, p = 2. Тогда из всех (d - p)^p возможных комбинаций на

этом фрагменте только (d - p) могут соответствовать предельным графам.

Общее количество комбинаций, не соответствующее предельным графам, уве-

личится как минимум в [(d - p)^p - (d - p)] раз. Аналогичная ситуация будет

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

ответствующая предельным графам, так мала в общем количестве всех ком-

бинаций. Компонентный метод лишен этого недостатка из-за операции при-

соединения деревьев (п. 2.3.3).

6. Заключение

Предложен компонентный метод поиска конфигураций распределитель-

ных сетей, который может применяться в задачах повышения безопасности,

управления режимами сетей и др.

Доказана корректность метода, а также предложены его модификации и

дополнительные условия на распределительные сети, при которых скорость

метода существенно возрастает.

На качественном уровне показано, что компонентный метод позволяет по-

строить варианты конфигураций с меньшим числом операций, чем метод про-

стых комбинаций путей от вершин источников до вершин потребителей [8].

Доказательство утверждения 1. Рассмотрим компоненту I вы-

ходного массива. Она является лесом, так как связность каждого дерева об-

условлена построением, а отсутствие циклов гарантируется процедурой кло-

нирования и проверкой на циклы (п. 2.3.1). В соответствии с начальной ини-

циализацией (шаг 0) I содержит все вершины потребители, а каждое дерево

в компоненте содержит вершину источник, так как только в этом случае ком-

понента помещается в выходной массив. Следовательно, I и построенный по

ней W подграф являются графами конфигурации. Очевидно, что для каждо-

го предельного графа можно явно указать последовательность выбора вер-

шин потомков (п. 2.2), приводящую к появлению этого графа в выходном

массиве. В соответствии с доказанным в [8] утверждением, приведенным вы-

ше (утверждение 2), после выполнения проверки на поглощение останется

только полное множество предельных графов. Утверждение 1 доказано.

Доказательство утверждения 2. Докажем справедливость этого

утверждения для следующего случая:

выберем одну вершину потребителя;

будем строить компоненты и при этом игнорировать выбранную верши-

ну, т.е. пропускать все действия метода, связанные с ней;

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

строить компоненты, рассматривая пути от выбранной вершины.

Покажем, что выходные массивы в этом случае и в методе построения ком-

понент совпадают. Пусть M максимальная длина пути к вершине источни-

ку среди всех вершин потребителей кроме выбранной. Рассмотрим граф Γ ,

полученный из исходного графа H по следующему принципу: к выбранной

вершине потребителю добавляется “хвост” из M обычных (не коммутаторов)

вершин, соединенных последовательно. Метод построения компонент для Γ

даст такие же результаты, что и для H, с точностью до “хвоста”. С другой

стороны, последовательность выбора вершин потребителей в методе построе-

ния компонент для Γ будет такой же, как в описанном случае.

Обобщим это рассуждение: очевидно, что выходной массив не изменит-

ся, если такие “хвосты” добавить к нескольким вершинам потребителям, при

этом длина хвостов может быть произвольной. И таким образом каждую

вершину потребителя можно “подключить” на любом шаге работы компо-

нентного метода. Аналогичным образом можно показать, что и очередность

выбора компонент на шаге 1 не важна. Утверждение 2 доказано.

Доказательство утверждения 3. Компонента I выходного мас-

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

утверждение, показав, что при поставленных условиях на вершины ветвле-

ния построенный по I W подграф будет совпадать с I. Рассмотрим дерево T

в I и любое ребро исходного графа, у которого одна из инцидентных вершин

принадлежит T (обозначим ее t), а вторая не принадлежит (обозначим

ее q). Покажем, что вершина q это вершина множества C. Если t ∈ U, то

ее степень строго больше двух: как минимум два ребра принадлежат дере-

ву плюс рассматриваемое ребро, т.е. t вершина ветвления и она окружена

вершинами коммутаторами. Если t ∈ S, то по свойствам рассматриваемых

графов q ∈ C t не может быть вершиной потребителем, так как единственное

ее ребро принадлежит I. По условиям построения W подграфа эти вершины

множества C удаляются. Отсюда следует, что W подграф, построенный по I,

будет совпадать с I. Утверждение 3 доказано.

СПИСОК ЛИТЕРАТУРЫ

1. Phyu E.E., Lin K.M., Moe T.T. Loss Reduction and Reliability Improvement of

Industrial Distribution System through Network Reconfiguration // Int. J. Energy

and Power Engineer. 2018. V. 12. No. 11. P. 822-828.

2. Sudhakara Reddy A.V., Satish Kumar Reddy M. Network Reconfiguration of Distri-

bution System for Loss Reduction using GWO Algorithm // Int. J. Electric. and

Comp. Engineer. 2017. V. 7. No. 6. P. 3226-3234.

3. Sedighizadeh M., Esmaili M., Mahmoodi M. Reconfiguration of Distribution Systems

to Improve Reliability and Reduce Power Losses using Imperialist Competitive Algo-

rithm // Iranian J. Electric. & Electronic Engineer. 2017. V. 13. No. 3. P. 287-302.

4. Sambaiah K.S. A Review on Optimal Allocation and Sizing Techniques for DG in

Distribution Systems // IJRER. 2018. V. 8. No. 3. P. 1236-1256.

5. Landeros A., Koziel S. Distribution Network Reconfiguration using Feasibility-

Preserving Evolutionary Optimization // J. Mod. Power Syst. Clean Energy. 2019.

V. 7. No. 3. P. 589-598.

6. Kayal V., Chanda C.K. A Simple and Fast Approach for Allocation and Size Eval-

uation of Distributed Generation // IJEEE. 2013. V. 4. No. 7. P. 2-10.

7. Christine E., Doig C. Analysis on Voltage Stability Indices. Master Thesis. Aachen

Germany: RWTH Aachen University. 2012. P. 1-106.

8. Grebenyuk G.G., Krygin A.A. Algorithms for Optimization of the Number of Switch-

ings in Heat Supply Networks Reconfiguration // Autom. Remote Control. 2007.

V. 68. No. 12. P. 2187-2197.

Гребеннюк Г.Г., Крыгин А.А. Алгоритмы оптимизации числа переключений при

реконфигурации сетей теплоснабжения // АиТ. 2007. № 12. С. 101-112.

9. Grebenyuk G.G., Krygin A.A. Limit Graphs in Structural Optimization of Modes in

Distribution Networks // Autom. Remote Control. 2015. V. 76. No. 1. P. 120-132.

Гребеннюк Г.Г., Крыгин А.А. Предельные графы в структурной оптимизации

режимов распределительных сетей // АиТ. 2015. № 1. С. 147-162.

Статья представлена к публикации членом редколлегии В.М. Вишневским.

Поступила в редакцию 25.06.2020

После доработки 31.10.2020

Принята к публикации 08.12.2020