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

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

Садыков Артур Мунавирович

Методы и алгоритмы поиска и оценки вариантов размещения технических объектов на городских территориях

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

13 МАЙ 2015

Санкт-Петербург - 2015

005568945

005568945

Работа выполнена на кафедре программного обеспечения компьютерных систем в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования (ФГБОУВПО) «Ивановский государственный энергетический университет имени В.И. Ленина».

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

доктор технических наук, профессор Косяков Сергей Витальевич

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

Костров Алексей Владимирович, доктор технических наук, профессор, ФГБОУВПО «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых», г. Владимир, профессор кафедры «Информационные системы и программная инженерия»

Кроль Татьяна Яковлевна, кандидат технических наук, Ивановский центр информационных технологий — филиал ОАО «Электроцен-тромонтаж», г. Иваново, директор

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

ФГБОУВПО «Костромской государственный университет имени Н.А. Некрасова», г. Кострома

Защита диссертации состоится «29» июня 2015 г. в 14-00 часов на заседании диссертационного совета Д 212.238.07 при ФГАОУ ВО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» по адресу: 197376, г. Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке ФГАОУ ВО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» и на сайте: www.eltech.ru.

Автореферат разослан «28» апреля 2015 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.238.07

В.В. Цехановский

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

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

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

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

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

Рассматриваемые в работе проблемы связаны с исследованиями, которые проводятся в рамках нескольких научных направлений. Различные методы моделирования сложных явлений и процессов отражены в работах ученых Ю. Б. Гермейера, Н. Н. Моисеева, В. Н. Буркова, Ю. М. Горского, И. В. Пран-гишвили, М. Месаровича и Дж. Клира, Б. Ф. Фомина, Б. Я. Советова и др. Теоретические основы решения задач размещения в оптимизационной постановке освещены в работах отечественных и зарубежных ученых В. Л. Берес-нева, Ю. А. Кочетова, Э. X. Гимади и др. В России существует несколько широко известных научных школ отраслевой направленности. В частности, проблемы оптимизации размещения объектов энергетики представлены в

трудах Д. А. Арзамасцова, Н. И. Воропая. Задачи географического анализа в среде ГИС исследованы в работах А. В. Кошкарева, В. С. Тикунова и др.

Данная работа выполнена в рамках деятельности научной группы под руководством д.т.н., проф. С. В. Косякова, которая проводит научные исследования и разработки в области применения математических методов системного анализа в комплексе с методами пространственного анализа средствами ГИС.

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

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

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

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

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

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

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

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

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

Задачи диссертационного исследования:

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

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

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

4. Разработать комплекс программных средств для решения задач размещения технических объектов в среде ГИС и создания компонентов СППР для инвестиционного планирования и развития территорий городов.

Научная новизна работы:

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

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

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

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

Теоретическая значимость исследования обоснована следующим:

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

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

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

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

Практическая значимость работы:

- обеспечена возможность практического решения задач размещения технических объектов на городских территориях с использованием комплексной модели зонирования в составе опытного образца СППР;

- продемонстрирована на практике возможность построения в среде ГИС модели зонирования территории города по критерию стоимости технологического присоединения объекта к инженерным сетям;

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

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

Положения, выносимые на защиту:

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

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

3. Алгоритмы расчета в среде ГИС стоимости технологического присоединения объектов к существующим сетям инженерных коммуникаций, которые включают построение новых трасс коммуникаций на карте города.

Степень достоверности результатов исследования обусловлена тем,

что:

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

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

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

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

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

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

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

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

Апробация результатов

Основные результаты диссертации были получены и использованы в рамках реализации Федеральной целевой программы (ФЦП), а также ряда госбюджетных и хоздоговорных научно-исследовательских работ (НИР), в том числе:

- «Разработка моделей, методов и программных средств агрегирования информации в процессах управления территориальными организационно-техническими системами» (по Государственному контракту с Минобрнауки РФ от 18 августа 2009 г. № П871 в рамках реализации ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы);

-«Разработка моделей и методов пространственного моделирования территориально распределенных технических систем» (Государственное задание Минобрнауки РФ на 2012-2014 годы № 8.5067.2011);

- «Разработка и внедрение новой подсистемы ГИС в составе АИС «ИЗК» для ведения распределенной базы пространственных данных средствами СУБД» (Договор с Комитетом по управлению имуществом Администрации г. Иваново от 19 апреля 2013 г. № 53/13);

- «Разработка информационной системы категорированного учета населения и объектов жилищного фонда» (Договор с Администрацией г. Иваново от 1 октября 2012 г. № 82/12);

- «Разработка программных средств формирования карты электрических сетей Костромской области и анализа условий технологического присоединения потребителей» (Договор субподряда № 499/12 от 1 декабря 2012 г. Заказчик — филиал ОАО МРСК-Центр «Костромаэнерго») и другие НИР.

Разработанные методы и средства внедрены в Администрации города Иваново; в Филиале ОАО МРСК-Центр «Костромаэнерго»; в Ивановском городском комитете по управлению имуществом; в учебном процессе на кафедре «Программное обеспечение компьютерных систем» ИГЭУ. Акты внедрения результатов исследования приведены в Приложении.

Результаты научных исследований представлены:

- в опубликованных работах (I монография (Косяков C.B., Садыков A.M., Иваново, ИГЭУ, 2014), 5 научных статей в изданиях, рекомендованных ВАК (2011-2014), 6 тезисах докладов и материалов конференций (20112013);

- в учебно-методических разработках по курсу «Геоинформационные системы», ИГЭУ (2012, 2013);

- в отчетах по НИР, выполненных по государственному контракту с Минобрнауки РФ (2009—2013), государственному заданию Минобрнауки РФ (2012—2014), хозяйственному договору с региональной администрацией г. Иваново, хозяйственному договору с Администрацией г. Кострома, хозяйственному договору с ОАО МРСК-Центр «Костромаэнерго».

Диссертационная работа включает введение, четыре главы, заключение, список литературы из 146 наименований, 6 приложений. Объем диссертации - 161 страница, включены также 57 рисунков, 11 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

3 = £3( ->тт;Р = ^ -»max. (1)

i j

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

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

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

К = {к; | i = l,I} заключается в сведении всех исходных данных, альтернатив и решений к унифицированным моделям зонирования М„ каждая из которых представляется в виде множеств непересекающихся полигонов в слое карты. Каждый полигон определяется вектором координат gj, который указывает на карте границу однородной области по значению критерия к;. Это значение представляется в виде атрибута aj, в котором записывается усредненное по площади полигона значение этого критерия. Таким образом, распределение значения каждого критерия оценки kj по территории представляется в виде модели зонирования (2):

Mi ={<gj>aj >| j = i7J}, (2)

где j — номер полигона в слое.

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

F({M;})->M*, (3)

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

А = {ajj | i = М, j = 1 > J } > (4)

где i — номер пространственного критерия (слоя); j - номер полигона в слое.

Функция F формируется средствами теоретико-множественных операций над полигональными слоями, реализуемыми в ГИС. Многокритериальный анализ сводится к использованию известных методов оптимизации: определению главного критерия, суммированию взвешенных критериев, построению области Парето и др.

В качестве примера в работе рассмотрена задача выбора участка для размещения промышленного объекта на территории города Иваново по трем критериям: 1) близость к существующим газопроводам среднего давления; 2) нахождение в зонах промышленного использования; 3) минимальная из возможных стоимость присоединения к электрической сети нагрузки мощностью 150 кВт. Площадь требуемого участка составляла 1500 м2. В результате была построена карта комплексного зонирования города по трем выбранным критериям и предложен оптимальный вариант, соответствующий данным условиям.

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

Исходными данными для построения моделей зонирования в общем случае служит множество точечных, линейных и площадных географических объектов ej? представленных на карте в виде множества слоев S. Каждому слою з,={е^ = 0}, S; еS сопоставлен вектор атрибутов А-= < ап,...а;„ > . Задача построения модели зонирования может быть

представлена как алгоритмически определенная функция вида (3). Вычисление агрегированных для зон значений атрибутов aj сводится к суммированию или некоторому пространственному интегралу по площади участка для непрерывных величин.

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

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

В общем виде задачу выбора способа подключения потребителя к инженерной сети можно записать выражением (5)

Z = z0 + F(L X W X Q) ->■ min , (5)

где zo - некоторая фиксированная часть затрат, которая не зависит от местоположения; L, W, Q ~ множества допустимых вариантов маршрутов нового участка сети, источников и используемого оборудования.

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

г = с[1 + с2м, (6)

где С] - стандартизированные тарифные ставки на покрытие расходов на строительство единицы длины новых линий сети; 1 - протяженность строящейся линии; с2 — стандартизированные тарифные ставки на покрытие расходов на строительство единицы новых мощностей в местах присоединения; N - величина недостатка резерва мощности в точке подключения.

Недостаток резерва N определяется по формуле

[о,№>мр

N4 , (7)

где — величина доступной резервной мощности в точке подключения к сети; Мр — величина присоединяемой мощности.

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

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

^ Эмжтр поастилцин ^ Потребитель

ШШ а»»-«

Дероги ---Прямом рассто«»*«о

Рисунок 1 - Фрагмент

карты для оценки длины кабеля

Математические модели и методы решения задач построения кратчайших путей известны. Однако они решают задачу построения пути как одно-критериальную с учетом только стоимости пути. При использовании критерия (6) и учета имеющихся в точках возможного присоединения резервов мощности математическая постановка задачи приобретает следующий вид (8):

ЕЕсцГц + Е^.Ь^ ->тш ;

I 1 1 } > J

где в и I — номера узлов истока и стоков; ^ >=0 - поток через дугу сети; Су - стоимость прохождения потока через дугу сети; Ь, - стоимость использования стока I из множества доступных стоков Т. Для этого случая необходимы специальные алгоритмы, позволяющие учитывать введенное в данной постановке второе слагаемое критерия.

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

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

При поиске точек присоединения к трубопроводным сетям и сетям дорог, в которые можно осуществлять «врезки», количество возможных мест присоединения становится большим (все точки растровой модели, через которые проходит трубопровод) и быстрые алгоритмы направленного поиска пришлось бы выполнять большое число раз. Поэтому для случая источников ресурса, имеющих линейный тип пространственной локализации, разработан другой алгоритм расчета стоимости, в основе которого лежит известный алгоритм Дейкстры. Этот алгоритм осуществляет стратегию поиска в ширину и работает существенно медленнее, чем А*, но за один проход находит оптимальный путь и выбирает оптимальную точку присоединения из большого количества возможных точек. Диаграмма, показывающая работу данного алгоритма, приведена на рисунке 2.

Формирование растровой модели и графа для трассировки. Формирование множеств возможных мест размещения потребителей Р= (р£} и мест подключения

Сформировать

модель у, зонирования

Положить pi в Open, n=p¡. n.parent = null, n.cost = 0, minzj =maxz Отметить все w, как нерассмотренные

У

Орпеделить длину пути и стоимость присоединения zw¡j = Cilwj+QjNwj Mark W; as an analyzed

h

[очередь Open не пуста]

извлечь из Open n, где n.cost = min

[n совпадает с одним из нерассмотренных w¡ ]

Взять очередного

наследника, newcost = n.cost ■+■ cost(n.n')_

[есть

(-нераспределенные-наследники]

n'.parent = п n'.cost = newcost

[п' находится в Open и n\cost<=newcost либо препятствие]

[ п' не находится-в Open ]

( добавить п' ^ в Open J

Рисунок 2 — Алгоритм построения модели зонирования по стоимости присоединения потребителя к трубопроводной сети

Этот алгоритм осуществляет просмотр всех вершин графа, отмечая просмотренные вершины в очереди Open. В отличие от известно алгоритма Дейкстры он не останавливается на первой найденной целевой точке Wj, а выполняет поиск «в ширину» и пытается уменьшить стоимость присоединения zwj при нахождении новых источников Wj. Поиск осуществляется до тех пор, пока не найдется источник мощности с резервом Nwj, который превышает требуемую для присоединения мощность Np. В этом случае дальнейший поиск теряет смысл, поскольку все другие варианты будут иметь более длинный путь при отсутствии возможности уменьшения второго слагаемого функции (6). Если ни одного маршрута построить не удалось, искомое значение стоимости minz остается равным начальному заведомо большому числу maxz. Это свидетельствует о невозможности построения маршрута и необходимости корректировки растровой модели в окрестности р,

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

На рисунке 3 приведен фрагмент отображения модели зонирования территории города по стоимости технологического присоединения к электрическим сетям низкого напряжения (0,4 кВ) в виде тематической карты. На карте совмещены исходные данные и результаты анализа. Линиями показаны границы земельных участков с имеющимися на них зданиями, специальные символы - электрические подстанции, для которых известны установленные мощности и величины резервов (данные раскрытия информации).

Рисунок 3 - Фрагмент модели зонирования по стоимости присоединенеия потребителей к электрической сети

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

Инструментальный программный комплекс «Геоинформационная система моделирования и анализа территориально распределенных технических систем (ГИС МодА)», в состав которого включена библиотека программных средств, реализующих разработанные методы и алгоритмы, создан в рамках проекта Федеральной целевой программы «Научно-педагогические кадры инновационной России». Программа зарегистрирована в Роспатенте и внедрена на ряде предприятий. Проданы несколько неисключительных лицензий на ее использование в различных организациях.

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

ЗАКЛЮЧЕНИЕ

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

Основные теоретические и практические результаты работы:

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

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

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ АВТОРОМ ПО ТЕМЕ ДИССЕРТАЦИИ

Научные статьи, опубликованные в изданиях перечня ВАК

1. Косяков, C.B. Метод зонирования территории по стоимости технологического присоединения к электрическим сетям [Текст] / С. В. Косяков, А. М. Садыков // Вестник ИГЭУ. - 2013. - Вып. 5. - С. 77-81.

2. Косяков, C.B. Построение и публикация в сети Интернет карт зонирования систем энергоснабжения территорий [Текст] / С. В. Косяков, Е.Р.Пантелеев, A.M. Садыков // Вестник ИГЭУ. - 2012. - Вып. 5.

- С. 59-62.

3. Косяков, C.B. Моделирование пространственных данных при решении задач дискретной оптимизации в среде ГИС [Текст] / С. В. Косяков, А.Б. Гадалов, A.M. Садыков // Информационные технологии. - 2012. - № 7. -С. 27-31.

4. Косяков, C.B. Моделирование и анализ систем энергоснабжения территорий методами зонирования и агрегирования информации [Текст] / C.B. Косяков, A.M. Садыков // Вестник ИГЭУ. - 2011. - Вып. 4. - С. 55-60.

5. Косяков, C.B. О подходе к реализации распределенной ГИС для ведения единой карты инженерных сетей города [Текст] / C.B. Косяков, А.Б. Гадалов, A.M. Садыков // Вестник ИГЭУ. № 5. - 2014. - Вып. 5.

- С.64-70.

Публикации в других изданиях

6. Косяков, C.B., Садыков A.M. Поддержка принятия решений по размещению объектов недвижимости в ГИС на основе моделей зонирования: Науч. издание / ФГБОУВПО «Ивановский государственный энергетический университет имени В.И. Ленина». - Иваново, 2014. - 135 с.

7. Косяков, С. В. Мягкие вычисления в построении карт зонирования территорий по параметрам систем энергоснабжения [Текст] / С. В. Косяков, С. С. Новосельцева, А. М. Садыков // Состояние и перспективы развития электротехнологии (XVII Бенардосовские чтения) : материалы междунар. науч.-техн. конф. / Иван. гос. энерг. ун-т; Академия электротехн. наук РФ.

- Иваново, 2013. - С. 338-341.

8. Садыков, А. М. Метод поддержки принятия решения по размещению промышленных объектов на основе моделей зонирования [Текст] / А. М. Садыков // Энергия 2013 : тез. докл. регион, науч.-техн. конф. студентов, аспирантов и молодых ученых / Иван. гос. энерг. ун-т. - Иваново, 2013.-С. 238-240.

9. Садыков, А. М. Пространственное моделирование и анализ систем энергоснабжения территорий [Текст] / А. М. Садыков // Вузовская наука — региону : материалы X всерос. науч.-техн. конф. / Вологод. гос. ун-т. -Вологда, 2012. - Т. 1.-С. 161-163.

10. Косяков, С. В. Разработка методов и средств анализа проектных рисков при выборе мест размещения производственных и энергетических объектов на базе ГИС и интернет-технологий [Текст] / С. В. Косяков, А. М. Садыков // Модернизация отраслевой производственной инфраструктуры : тез. докл. науч.-практ. конф. / КГУ им. Н. А. Некрасова.

- Кострома, 2012. - С. 76-80.

11. Садыков, А. М. Дискретные задачи размещения объектов в геоинформационных системах [Текст] / А. М. Садыков // Инновационные проекты молодых ученых за 2011 г. : сб. отчетов / Иван. гос. энерг. ун-т. -Иваново, 2012.-Т. 2.-С. 148-151.

12. Косяков, С. В. Разработка метода поддержки принятия решений по реконструкции городских систем энергоснабжения с учетом пространственных факторов [Текст] / С. В. Косяков, А. М. Садыков // Состояние и перспективы развития электротехнологии (XVI Бенардосовские чтения) : материалы междунар. науч.-техн. конф. / Иван. гос. энерг. ун-т; Академия электротехн. наук РФ. — Иваново, 2011. — С. 360-362.

Свидетельства на программные продукты

13. Свидетельство о государственной регистрации программы для ЭВМ. Геоинформационная система моделирования и анализа территориально распределенных технических систем (ГИС МодА) / А. М. Садыков [и др.] ; № 2012616621. 24.07.2012. - М. : ФИПС.

14. Свидетельство о государственной регистрации программы для ЭВМ. Геоинформационная система учета и анализа технологических присоединений к электрическим сетям «ЭнерГИС» / А. М. Садыков [и др.] ; №2014610605. 15.01.2014.-М. : ФИПС.

Подписано в печать 27.04.2015 г. Формат 60x84'/,6 Печать плоская. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 11