Введение к работе
Актуальность темы. В настоящее время бурное развитие информационных технологий обусловило использование теории нечетких множеств и нечеткой логики в качестве инструмента для решения самого широкого круга задач принятия решений в условиях недостаточной определенности и субъективности информации об условиях окружающей среды. К таким задачам относятся проблемы нахождения и увеличения живучести транспортных сетей, нахождение максимальных потоков с заданной степенью живучести, а также задачи размещения центров обслуживания с наиболее возможной степенью живучести. Для транспортных систем различного назначения живучесть имеет важное значение для соответствующего управления и принятия решений при сбоях в работе или плохом функционировании. Рассмотрение этих задач в нечетких условиях, когда некоторые параметры сети заданы неточно, или приблизительно, позволяет находить такие решения, получение которых традиционными (четкими) методами было бы затруднительно или вообще не возможно. Детальное изложение особенностей, характерных свойств, отличающих одни объекты и связи между объектами транспортной сети от других, а также использование относящихся к ним числовых данных, дают возможность представления исходной информации в нечетком виде. Следовательно, задачи формализации, моделирования и анализа транспортных сетей в нечетких условиях являются актуальными.
При решении данных задач используются элементы теории графов, нечетких множеств, представленные работами Л. Заде, Р. Беллмана, А.Н. Мелихова, Л.С. Берштейна, А.Н. Борисова, Н. Кристофидеса, А. Кофмана, Т. Саати, Х.-Ю. Циммерманна и других авторов. Работы перечисленных ученых относятся к ряду фундаментальных работ по теории графов, нечеткой логике и теории нечетких множеств, положенных в основу исследований, проводимых в данной работе.
Целью диссертационной работы является разработка и исследование методов и алгоритмов определения и увеличения живучести транспортных сетей в геоинформационных системах (ГИС) с учетом нечетких данных об объектах сетей на основе нечетких графов.
Поставленная цель определяет следующие основные задачи диссертационного исследования:
1. Обобщение понятий ГИС. Обоснование представления приблизительной и недостаточно достоверной информации в геоинформационной базе данных (ГБД) в виде нечетких чисел или лингвистических переменных. Исследование построения графовых моделей на основе ГИС. Рассмотрение необходимости решения задач нахождения и увеличения живучести транспортной сети, а также задач размещения центров и транспортных задач, с использованием нечетких графов второго рода.
2. Разработка и исследование методов решения задач живучести транспортной сети. В частности:
а) разработка метода нахождения степени живучести транспортной сети, представленной нечетким графом второго рода, что позволяет учесть информацию как об объектах сети, так и о связях между рассматриваемыми объектами;
б) разработка метода увеличения степени живучести транспортной сети представленной нечетким графом второго рода;
в) разработка метода увеличения степени живучести транспортной сети с минимальными затратами.
3. Разработка и исследование метода определения центров обслуживания с заданной степенью живучести в транспортной сети, представленной нечеткими графами второго рода.
4. Разработка и исследование метода нахождения центров обслуживания на нечетких интервальных графах.
5. Разработка и исследование метода нахождения максимальных потоков транспортной сети с определенной степенью живучести.
Методы исследования основаны на применении теории нечетких множеств, теории графов и нечеткой логики.
Научная новизна диссертационной работы:
1. Введено понятие степени живучести нечетких графов второго рода, которое позволило обосновать подход к анализу и синтезу транспортных сетей, представленных нечеткими графами.
2. На основе введенного понятия разработаны и теоретически обоснованы методы определения и увеличения степени живучести нечетких графов второго рода.
3. Разработаны и обоснованы методы размещения центров обслуживания на нечетких графах второго рода и нечетких интервальных графах.
4. Разработан метод определения максимального потока в транспортной сети с заданной степенью живучести.
Достоверность полученных в диссертации результатов подтверждается математическими доказательствами, результатами практического внедрения, а также апробацией на международных и всероссийских конференциях.
Практическая значимость. Прикладными результатами являются разработанные в диссертационной работе:
1. Алгоритм и программа нахождения степени живучести нечетких графов второго рода.
2. Алгоритм и программа увеличения степени живучести нечетких графов второго рода.
3. Алгоритм и программа увеличения степени живучести нечетких графов второго рода с минимальными затратами.
4. Алгоритм и программа нахождения центров обслуживания на нечетких графах второго рода.
5. Алгоритм поиска центров обслуживания на нечетких интервальных графах.
6. Определение максимального потока в транспортной сети с заданной степенью живучести.
Практическая значимость полученных в диссертации результатов заключается в том, что разработанные алгоритмы учитывают особенности различных оптимизационных прикладных задач таких, как задачи нахождения и увеличения живучести, задачи размещения, потоковые задачи. Практическое применение предложенных в работе методов допускает использование числовых характеристик объектов транспортных сетей.
Реализация результатов работы. Результаты диссертации внедрены в Научно-техническом центре «Информационные технологии» федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» (НТЦ «Интех»), на железнодорожной станции «Майкоп» Краснодарского отделения Северо-Кавказской железной дороги, что подтверждено соответствующими актами.
Также результаты диссертационной работы были использованы при выполнении научно-исследовательских работ, в том числе:
- при выполнении гос.бюджетной НИР НТЦ «Интех» ЮФУ № гос.регистрации 01200504744;
- при выполнении гранта РФФИ № 10-01-00029а.
Апробация работы. Основные результаты работы представлены на региональной научно-практической конференции «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2006 г.), на 18-й международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании (МК-58-96)» (Пенза, 2006 г.), на международной научно-технической конференции «Интеллектуальные системы» (AIS’06) и «Интеллектуальные САПР»(CAD-2006) (с.Дивноморское, 2006 г.), на VIII всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2006 г.), на IV всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2006 г.), на IV Международной научно-технической конференции «Искусственный интеллект в XXI веке. Решения в условиях неопределенности» (Пенза,2006), на международной научно-технической конференции «Интеллектуальные системы» (AIS’07) и «Интеллектуальные САПР» (CAD-2007) (с.Дивноморское, 2007 г.), на VIII Всероссийском симпозиуме по прикладной и промышленной математике (Сочи-Адлер, 2007 г.), на IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2008 г.), на IX Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2008 г.), на 15th Zittau East-West Fuzzy Colloquium (Циттау, Германия, 2008 г.), на научно-практической конференции студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (Коломна, 2009 г.), на международной научно-технической конференции «Интеллектуальные системы» (AIS’09) и «Интеллектуальные САПР» (CAD-2009) (с.Дивноморское, 2009 г.), на 17th East-West Zittau Fuzzy Colloquium (Циттау, Германия, 2010 г.)
Публикации. Результаты диссертации отражены в 22 печатных работах, в том числе в 8 работах, опубликованных в изданиях, рекомендованных ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, выводов по главам, заключения, списка литературы и приложений. Работа выполнена на 161 странице машинописного текста, содержит 46 рисунков и 6 таблиц. Список использованной литературы включает 113 наименований.
