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

На правах рукописи

КРЫГИН АНДРЕЙ АЛЕКСАНДРОВИЧ

РАЗРАБОТКА МОДЕЛЕЙ, МЕТОДОВ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ПЛАНОВ РЕМОНТОВ СЕТЕЙ ИНЖЕНЕРНОЙ ИНФРАСТРУКТУРЫ ГОРОДА

Специальность:

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

г ОКТ 2014

| Москва 2014 005553011

005553011

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт проблем управления им. В.А. Трапезникова Российской академии наук (ИПУ РАН)

Научный руководитель:

Гребенюк Георгий Григорьевич

доктор технических наук.

Официальные оппоненты:

Трояновский Владимир Михайлович

доктор технических наук, профессор кафедры «Информатика и программное обеспечение вычислительных систем» национального исследовательского

института «МИЭТ».

Симаков Игорь Павлович

кандидат технических наук доцент кафедры «Системный анализ и управление» института информационных технологий и управления.

Ведущая организация:

Московский институт электроники и математики НИУ ВШЭ.

Защита диссертации состоится 20 октября 2014 г. в 14 часов на заседании Диссертационного Совета Д002.226.01 в Институте проблем управления им. В.А. Трапезникова РАН по адресу: г. Москва, ул. Профсоюзная, д. 65. Телефон/факс Совета (495) 33493-29.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В.А. Трапезникова РАН и на сайте http://www.ipu.ru/sites/default/files/news/OptimizaciyaPlanovRemontov.pdf

Автореферат разослан « »_2014 г.

Ученый секретарь диссертационного Совета доктор технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Среди задач управления инженерными системами крупного города одной из важнейших продолжает оставаться задача обеспечения населения коммунальными услугами с требуемыми показателями качества. Инфраструктура инженерной системы состоит из источников энергии и ресурсов, приемных устройств потребителей и инженерных сетей (ИС). Энерго- и ресурсоснабжающие организации (PCO) решают задачи водо-, газо-, тепло-, электро- и других видов обеспечения населения, предприятий промышленности и сферы услуг.

В системе управления функционированием ИС большой интерес представляет эффективность эксплуатационной деятельности, осуществляемой PCO, а также коммунальными службами, несущими ответственность перед населением за качество предоставляемых услуг. Рост городов и требований к качеству услуг вызывают необходимость постоянного развития сетевого хозяйства, его модернизации, применения современных принципов технического обслуживания. В то же время анализ состояния ИС показывает, что в настоящее время значительная часть сетевой инфраструктуры перестала удовлетворять запросам по пропускной способности; кроме того, из-за превышения нормативных сроков эксплуатации часть сетей находится в ветхом состоянии с низким уровнем надежности.

Для Москвы такая тенденция наиболее ярко проявляется в центральной части города - в Центральном административном округе, где часть инженерных коммуникаций проложена более 50 лет назад и каждый год проводится несколько тысяч разрытий по устранению аварий и перекладке коммуникаций. Проведение разрытий связано со значительными трудностями и неудобствами для населения, обусловленными закрытием проездов, изменением маршрутов пассажирского транспорта, перерывами в энергообеспечении и др. Сокращение числа аварий на ИС при оптимальном планировании капитальных ремонтов, исключение повторных разрытий совместно расположенных коммуникаций позволяют получить значительную экономию денежных средств. Поэтому эффективное управление планированием и проведением ремонтных работ на ИС является важнейшей задачей эксплуатационной деятельности, а разработка методов решения

указанных задач обуславливает актуальность темы диссертационной работы.

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

- организационно-экономические методы;

- методы объемного планирования;

- методы календарного планирования.

Применяемые в организационно-экономических методах способы повышения эффективности эксплуатационной деятельности основаны на введении на предприятиях рыночных механизмов, стимулировании притока инвестиций, а также тестирования и внедрения в практическую деятельность различных инновационных разработок (например, полимерных трубопроводов для сетей горячего водоснабжения). Проблемы в этой области нашли отражение в работах П.Г. Грабового, Д. Кейнса, М.А. Кирилюк, А.Д. Кочегаров, В.Я. Осташко, В.П. Пилявского, M.JI. Разу и других ученых.

Задачи объемного и календарного планирования направлены на оптимизацию и повышения качества графика ремонтных работ.

На этапе объемного планирования требуется определить виды ремонтных работ по каждому объекту, при этом суммарные финансовые, материальные, трудовые и др. средства, должны удовлетворять заданным ограничениям. Эта задача может быть решена методами динамического программирования, которые широко освещены в литературе (И.Л. Акулич, Р. Беллман, Р. Габасов, Ф. М. Кирилова, А. Куликов, Р. Штайн, и другие).

При календарном планировании необходимо распределить общий объем ремонтных работ по календарным отрезкам времени. Эта задача относится к классу задач, решаемых в теории расписаний (М.Я. Ковалев, Д.Ф. Мут, A.A. Лазарев, Е.Ф. Гафаров и другие ученые).

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

Цель работы. Целью диссертационной работы является повышение эффективности эксплуатационной деятельности

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

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

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

- разработка математических моделей ИС, методов и алгоритмов, необходимых для эффективного (в отличие от планирования, использующего существующие методики) решения задач планирования и проведения ремонтных работ;

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

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

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

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

Научная новизна. В результате анализа объекта исследования и процессов планирования ремонтных работ на ИС выявлены особенности протяженных коммуникаций (невысокая точность оценки текущего состояния объектов ИС, совместная прокладка

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

• определение оптимального времени планового ремонта протяженной коммуникации;

• определение оптимального графика плановых ремонтов для группы совместно расположенных коммуникаций;

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

По указанным задачам были получены следующие научные результаты:

1. Определение оптимального времени планового ремонта протяженной коммуникации.

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

2. Определение оптимального графика плановых ремонтов группы совместно расположенных коммуникаций.

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

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

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

Практическая значимость определяется:

- разработкой моделей и методов, направленных на оптимизацию планирования ремонтных работ на ИС и получение экономического эффекта от применения этих методов;

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

реконфигурации тепловых и электрических распределительных сетей (снижение потерь энергии, балансировка нагрузки и др.);

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

Реализация и внедрение результатов работы. Разработанные модели, методы и принципы построения информационного обеспечения были использованы при проектировании производственной компанией «Шерна» информационно-аналитической системы в части оценки необходимости проведения ремонтных работ на участках теплосети и тренинга персонала организации в задачах определения оптимальной конфигурации сети.

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

Основные положения, выносимые на защиту диссертации:

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

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

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

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

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

систему классификации сетевых объектов; модели хранения данных на основе централизованного хранилища данных;

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

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

3-й Всероссийской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» УКИ-2012;

20-й международной конференции «Проблемы управления безопасностью сложных систем» 2012 г.;

Международной конференции «Технические и программные средства систем управления, контроля и измерения» УКИ-2008;

Научной сессии МИФИ (МИФИ-2000).

По результатам исследований опубликовано 9 печатных работ (3 работы - без соавторов), из них 3 - в изданиях, входящих в перечень, рекомендованный ВАК РФ.

Структура и содержание работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа изложена на 138 страницах, содержит 39 рисунков и 11 таблиц.

Структура диссертационной работы представлена на рис. 1.

Рис. 1. Структура диссертационной работы.

Содержание диссертации.

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

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

1. составление списка объектов, подлежащих ремонту;

2. объемное планирование;

3. календарное планирование.

На каждом этапе проводится обзор математических методов решения задач.

1. Для составления списка ремонтируемых объектов необходимо выбрать метод определения срока службы объекта. Анализ экспертных, экспериментально-аналитических и экономико-статистических методов определения срока службы различных видов объектов показал необходимость разработки способа определения срока службы для протяженных инженерных коммуникаций.

2. На этапе объемного планирования были выделены две специфические для рассматриваемых объектов задачи: нахождение оптимального графика ремонтов нескольких совместно расположенных коммуникаций и определение оптимальной конфигурации сети на время проведения ремонтных работ.

3. Математический аппарат календарного планирования хорошо изучен и не требует какой-либо корректировки для ИС.

В первой главе формулируются три основных направления исследования:

- определение оптимального времени планового ремонта объекта И С;

- определение оптимального графика плановых ремонтов группы совместно расположенных объектов ИС;

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

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

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

Уточним, что для решения поставленных задач рассматривались два основных вида ремонтных работ, выполняемых на коммуникациях:

- Плановый (капитальный) ремонт осуществляется периодически по заранее составленному плану и заключается в проведении разрытий и полной или частичной замене участков ИС большой протяженности. Под термином «участок планового

ремонта» (участок ПР) далее будем понимать участок инженерной сети, который после проведения планового ремонта полностью заменяется на новый.

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

Для составления математической модели обслуживания одного участка ПР были приняты следующие допущения по каждому виду ремонтов.

Плановый ремонт

- различают зимний (осеннее-знмний) и летний (весеннее-летний) периоды эксплуатации ПС. Плановый (капитальный) ремонт проводится в летний период. Аварийные (планово-предупредительные) ремонты также проводятся в летний период, за исключением редких аварий «разрыв трубопровода». Поэтому будем считать, что стоимость планового ремонта участка ПР является постоянной величиной и не зависит от календарного времени;

- время проведения планового ремонта пренебрежимо мало по сравнению с ресурсом участка ПР.

Аварийный ремонт

- время до возникновения аварии является случайной величиной, которая описывается конкретным законом распределения. Будем считать, что функция распределения F(t) имеет вид распределения Вейбулла, параметры которого заданы.

-¿Г

F(t) = 1-е h

Это допущение принято на основании работ Савина В.Н., в которых отмечается, что вероятность возникновения аварии на трубопроводах хорошо описывается распределением Вейбулла.

- аварии, возникающие на ИС, локализованы по месту своего возникновения. Общая протяженность участка ПР во много раз превышает длину аварийного участка, поэтому считается, что состояние всего участка ПР не изменяется после проведения на нем аварийного ремонта.

Обозначим:

F(t)~ вероятность возникновения аварии за время t на всем участке ПР,

S - стоимость планового ремонта,

Sa — стоимость аварийного ремонта,

S(t) - общие затраты на ремонт за время t,

о ,• ад

-lim--удельные затраты на обслуживание участка ПР

в единицу времени,

Т - период планового ремонта.

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

Рассматривается процесс обслуживания одного участка ПР, который состоит из последовательного проведения плановых или аварийных ремонтов, стоимости которых соответственно S и Sü.

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

Для решения этой задачи были доказаны два утверждения. Утверждение 2.1

В промежутке времени между двумя плановыми ремонтами с периодом Т среднее число аварий в интервале времени (0,/) равно

- 1п(1 - F(t )), где t = 0 — момент проведения планового ремонта и t < Т.

Утверждение 2.2

Для объекта с описанным процессом обслуживания удельные затраты S v будут составлять

Sr-SJn(\-F(T)) *,=-f-•

На основании этих утверждений получено выражение оптимального периода:

5„ у

Т0=Ь(-£—У'-.

(с-1)5/

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

Обозначим:

^(0, вероятности возникновения аварии за время /на

каждом участке ПР,

5/ стоимость планового ремонта каждого участка ПР, без учета затрат на разрытие, т.е. стоимость замены,

, - стоимость аварийного ремонта каждого участка ПР,

Я - стоимость разрытия,

5\.(Т),31(Т) - функции удельных затрат на ремонт в зависимости от периода планового ремонта,

7*,, Г, - оптимальные периоды планового ремонта каждого участка ПР.

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

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

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

Утверждение 2.3

Удельные затраты достигают минимума при одинаковых интервалах между отдельными ремонтами участка ПР в группе.

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

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

- определение на заданном интервале времени оптимального графика методом перебора вариантов;

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

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

В первой постановке, соответствующей стационарному поведению параметров, было доказано следующее утверждение, дающее также и метод нахождения оптимальной последовательности ремонтов:

Утверждение 2.4

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

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

Задачи реконфигурации сети на время проведения ремонтных работ удобно решать на графе, множество вершин которого V

описывается четверкой < Б, Р, С,и >, где Б, Р , С, £/, соответственно, - множество вершин генерации ресурса (источники), потребления, коммутации движения ресурса и перераспределения ресурса (ветвления путей).

У = 5иРиСиг7.

Сеть передает ресурсы от вершин множества 51 к вершинам множества Р . Маршруты передачи определяются состоянием вершин коммутации: С = С+ иС",

где С + - подмножество вершин-коммутаторов в состоянии «открыто», С ~ - подмножество вершин-коммутаторов в состоянии «закрыто».

Каждый вариант реконфигурации однозначно задается подмножеством С + или С ~ . Проведение ремонтных работ на объекте, а также его авария вызывает переход соответствующей вершины в запрещенное состояние уа .

Особенностями многих сетей снабжения является обеспечение одного потребителя от одного источника и обеспечение от одного источника нескольких потребителей. Поэтому в работе рассматривались графы, обладающие следующими свойствами (свойства 1)^1)):

1) вершина множества С имеет один вход и один выход;

2) в графе соблюдается требование достижимости каждой вершины множества Р из единственной вершины множества 5";

3) в графе параллельные ветви, не содержащие вершин множества С , можно свести к одной эквивалентной ветви;

4) в графе с двумя параллельными ветвями, каждая из которых содержит вершину множества С, одна из вершин должна быть в состоянии С " . Это свойство обеспечивает резервирование каждой ветви.

Под достижимостью вершины множества Р из вершины множества 5" понимается существование пути между ними, не содержащего вершин множества С ~ .

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

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

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

Для связного графа сети, описываемого множеством вершин < Б, Р, С, и >, при переходе одной или нескольких вершин

множества С, и в запрещенное состояние V а, нарушающее достижимость вершин Р из 5", требуется найти минимальное количество переключений (переходов вершин из множества С + в множество С ~ и наоборот), обеспечивающее достижимость максимального множества вершин Р из 5 при выполнении свойств 1)-4) и минимальную величину дефицита мощности.

Для решения задачи вводится ряд определений.

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

Граф сети, в котором все вершины-коммутаторы находятся в состоянии «открыто», будем называть условным графом 3+

Для условного графа С = С+, С" = 0 .

Запрещенным подграфом условного графа 3+ назовем подграф

3(,+, содержащий запрещенную вершину уа и ближайшие к ней

вершины множества С+ , находящиеся на путях, ведущих из вершин множества 5" и вершин множества Р к запрещенной вершине уа.

Разрешенным подграфом условного графа 3+ назовем подграф

, не содержащий подграф Зн' .

Таким образом, 3 + = и 3/ .

Разрешенным подграфом исходного графа 3 назовем подграф 3,., не содержащий вершин запрещенного подграфа 3((+. Таким

образом, подграфы Зг и 3* различаются только состоянием вершин множества С.

Вершину множества Р назовем восстанавливаемой, если в

разрешенном подграфе 3(+ к ней существует хотя бы один путь из вершин множества 5. Множество восстанавливаемых вершин подграфа 3* обозначим как Рг, где Рг с: Р .

Графом реконфигурации назовем любой из подграфов 3^., у > О подграфа 3^, в котором множество Р совпадает с множеством восстанавливаемых вершин Рг графа 3^ и содержащий только те вершины из С, и , которые лежат на путях из 5 к Рг.

Полное множество вершин из С реконфигурированной сети, находящихся в состоянии С + назовем вариантом реконфигурации.

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

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

Два варианта реконфигурации называются идентичными, если у них совпадают множества активных вершин. Это определение эквивалентно следующему: два варианта реконфигурации называются идентичными, если они соответствуют одному и тому же графу реконфигурации.

( + У'т

Предельным графом , / > 0 назовем такой граф

реконфигурации 3^-, в котором при изменении состояния хотя бы одной вершины из множества С^, найдется вершина множества

Рг, у которой связь с вершинами из 51 будет разорвана; [г*.]

является подграфом 3;Т, (г^) с

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

Общая схема решения:

1. Находится разрешенный подграф 3*

2. Находится полное множество графов реконфигурации 3*,

удовлетворяющих свойствам 1)^).

3. Среди полученного множества графов реконфигурации выбирается наилучший по критерию дефицита мощности источников.

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

Метод нахождения множества графов реконфигурации основан на свойстве достижимости любой вершины Р из единственной вершины множества 5 . Доказано следующее утверждение:

Утверждение 2.5

Граф реконфигурации, обладающий свойствами 1)-4), тогда и только тогда является предельным, когда выполняется следующее условие:

граф реконфигурации либо вообще не содержит циклов, либо в таких г\иклах нет вершин-коммутаторов.

При выполнении сформулированного условия (для рассматриваемого класса инженерных сетей оно выполняется)

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

Для получения множества предельных графов предложена последовательность операций (преобразования 1-4) и доказано соответствующе утверждение:

Утверждение 2.6

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

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

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

В качестве исходных данных рассматривается фрагмент городской тепловой сети. В 2012 году для четырех совместно расположенных участков коммуникации на основе статистики аварий были рассчитаны их параметры и определен оптимальный график ремонтов на период планирования (2013-2016г.). Анализ данных и последующие расчеты показали, что для исследуемых участков оптимальным являлось проведение одновременного ремонта всех четырех объектов. Определена дата оптимального ремонта, наступившая на 2 года раньше периода планирования (в 2011-м году). Однако, в реальной эксплуатации из-за отсутствия оптимальной стратегии выполнялись аварийные ремонты, что вызвало рост затрат на эксплуатацию исследуемых участков. Был проведен расчет затрат на эксплуатацию при оптимальном варианте (одновременная замена четырех объектов в 2011-м году) и варианте, в котором проведен одновременный ремонт всех участков в начале периода планирования (одновременная замена четырех объектов в 2013-м году). Гипотетическая выгода составила более 50 тыс. руб. для 4-х участков длиной 115 метров.

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

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

Четвертая глава посвящена вопросам построения системы информационной поддержки принятия решения при планировании ремонтных работ на инженерных сетях. Глава состоит из трех разделов, посвященных алгоритмическому, информационному и программному обеспечению системы информационной поддержки принятия решений (СИППР). В разделе, посвященном алгоритмическому обеспечению, для определения места созданных модулей в СИППР приведен общий алгоритм составления графика ремонтов; также рассматриваются алгоритмы определения списка объектов, подлежащих ремонту и алгоритм нахождения оптимальной конфигурации сети. Обсуждение информационного обеспечения СИППР включает в себя разделы по классификации объектов ИС и структурированию информации, необходимой для работы системы. В разделе, посвященном программному обеспечению, приведены примеры кода отдельных функций, описания классов и интерфейсы подсистемы учета объектов.

Основные результаты и выводы

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

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

• определение оптимального времени планового ремонта протяженной коммуникации;

• определение оптимального графика плановых ремонтов группы совместно расположенных коммуникаций;

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

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

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

4. Разработаны и программно реализованы алгоритмы нахождения оптимального графика плановых ремонтов трех и более совместно расположенных коммуникаций для статического и динамического характера параметров модели. Разработан метод сведения нескольких коммуникаций с одинаковыми параметрами к одному эквивалентному объекту.

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

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

7. Основные результаты исследования были использованы производственной компанией «Шерна» при проектировании информационно-аналитической системы планирования ремонтных работ.

Основные труды по теме диссертации

1. Гребенюк Г.Г., Крыгин A.A. Разработка алгоритмов, повышающих надежность доставки энергоресурсов потребителям. Труды 3-й Всероссийской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (УКИ-2012, Москва). 2012.

2. Крыгин A.A. Методика составления графиков ремонтов инженерных сетей на основе оценки безопасности. Труды 20-й международной конференции «Проблемы управления безопасностью сложных систем» (Москва, 2012). 2012. С. 300-304.

3. Крыгин A.A. Оптимизация графиков плановых ремонтов совокупности участков инженерных сетей. Автоматика и телемеханика. 2010. № 9. С. 83-102.

4. Крыгин A.A. Оптимизация графика плановых ремонтных работ для совокупности городских коммуникаций. Доклады российской конференции с международным участием "Технические и программные средства систем управления, контроля и измерения УКИ'08". 2008.

5. Гребенюк Г.Г., Крыгин A.A. Алгоритмы оптимизации числа переключений при реконфигурации сетей теплоснабжения. Автоматика и телемеханика. 2007. С. 101-112.

6. Гребенюк Г.Г., Крыгин A.A. Алгоритмизация решения задач управления теплосетью в аварийных ситуациях. Датчики и системы. 2004. №10. С. 46-51.

Личный вклад автора в работах, опубликованных в соавторстве, заключается в следующем: в [5,6] автору принадлежит постановка и доказательство всех лемм, теорем и утверждений.

Научное издание

Крыгин Андрей Александрович

Разработка моделей, методов и алгоритмов оптимизации планов ремонтов сетей инженерной инфраструктуры города

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 27.05.2014. Формат 60x90/16. Усл. печ. л. 1,37. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 33.

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук 117997, ул. Профсоюзная, д. 65 Россия, Москва E-mail: snv@ipu.ru http://www.ipu.ru