Нахождение потоков в транспортных сетях в условиях нечеткости и частичной неопределенности

• Автор: Герасименко, Евгения Михайловна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Таганрог
• Количество страниц: 219 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА 1 ПОТОКОВЫЕ ЗАДАЧИ В ТРАНСПОРТНЫХ СЕТЯХ В ЧЕТКИХ УСЛОВИЯХ

1.1 Основные понятия теории потоков

1.2 Описание методики расчета пропускных способностей дуг транспортной сети

1.2.1 Факторы, ведущие к постановкам потоковых задач в нечетких условиях

1.3 Нечеткая логика как основной инструмент оперирования неопределенностью

1.4 Потоковые задачи в транспортных сетях

1.4.1 Нахождение максимального потока в транспортной сети

1.4.2 Нахождение максимального потока в транспортной сети с учетом ненулевых нижних потоковых границ
1.4.3 Нахождение потока минимальной стоимости в транспортной сети
1.4.4 Нахождение потока минимальной стоимости в транспортной сети с учетом ненулевых нижних потоковых границ
1.5 Потоковые задачи в динамических транспортных сетях
1.5.1 Нахождение максимального потока в динамической транспортной сети с учетом нулевых и ненулевых нижних потоковых границ
1.5.2 Нахождение потока минимальной стоимости в динамической транспортной сети с учетом нулевых и ненулевых нижних потоковых границ
1.6 Выводы по главе
ГЛАВА 2 НАХОЖДЕНИЕ МАКСИМАЛЬНОГО ПОТОКА И ПОТОКА МИНИМАЛЬНОЙ СТОИМОСТИ В ТРАНСПОРТНОЙ СЕТИ В НЕЧЕТКИХ УСЛОВИЯХ
2.1 Нахождение максимального потока в транспортной сети с нечеткими пропускными способностями
2.2 Методика выполнения арифметических операций над нечеткими числами
2.3 Нахождение максимального потока в транспортной сети с учетом ненулевых нижних и верхних потоковых границ, представленных в нечетком виде
2.4 Нахождение потока минимальной стоимости в транспортной сети с нечеткими
пропускными способностями и стоимостями
2.4.1 Метод потенциалов для нахождения потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями
2.5 Нахождение потока минимальной стоимости в транспортной сети с учетом нечетких ненулевых нижних, верхних границ потоков и стоимостей
2.6 Выводы по главе

ГЛАВА 3 РЕШЕНИЕ ПОТОКОВЫХ ЗАДАЧ В ДИНАМИЧЕСКИХ ТРАНСПОРТНЫХ СЕТЯХ С НЕЧЕТКИМИ НИЖНИМИ, ВЕРХНИМИ ГРАНИЦАМИ ПОТОКОВ И СТОИМОСТЯМИ..
3.1 Определение нечеткой динамической транспортной сети
3.2 Нахождение максимального потока в динамической транспортной сети с нечеткими пропускными способностями, зависящими от времени
3.3 Нахождение максимального потока в динамической транспортной сети с учетом нечетких ненулевых нижних и верхних потоковых границ, изменяющихся во времени
3.4 Нахождение потока минимальной стоимости в динамической транспортной сети с зависящими от времени пропускными способностями и стоимостями, заданными в нечетком виде
3.5 Нахождение потока минимальной стоимости в динамической транспортной сети с учетом нечетких ненулевых нижних, верхних потоковых границ и стоимостей, зависящих от времени
3.6 Выводы по главе
ГЛАВА 4 РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ, РЕАЛИЗУЮЩЕГО РЕШЕНИЕ ПОТОКОВЫХ ЗАДАЧ В ТРАНСПОРТНЫХ СЕТЯХ В НЕЧЕТКИХ УСЛОВИЯХ
4.1 Функциональное назначение разработанного программного модуля
4.2 Описание логической структуры программного модуля
4.3 Подготовка входных данных с использованием ГИС О^есШапб
4.4 Оценка временной сложности
4.5 Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ А Численные примеры, реализующие решение потоковых задач
ПРИЛОЖЕНИЕ Б Свидетельство о государственной регистрации программ для ЭВМ
ПРИЛОЖЕНИЕ В Акты внедрения

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

Определение 2.
Нечеткая остаточная (инкрементальная) транспортная сеть СИ — это нечеткая сеть, заданная в виде нечеткого ориентированного графа, которая каждой дуге (х,,*,) исходного
графа (3 ставит в соответствие две дуги: (х(,х^) с остаточной пропускной способностью йд=йи—£я и [х1' ,х(‘) с остаточной пропускной способностью ^. Таким образом,
нечеткая остаточная сеть содержит только дуги с положительными пропускными способностями.
Тогда модель задачи определения максимального потока в нечеткой транспортной сети [101] задается как:
В модели (2.1)-(2.3) V - максимальная величина потока в нечеткой транспортной сети; ^ - нечеткая величина потока, протекающего по дуге (х,.,ху); начальная вершина графа (источник); I - конечная вершина графа (сток); Г(х1) - множество вершин, в которое идут дуги из вершины х1.6 X; Г~' (х.) - множество вершин, из которого идут дуги в вершины х}. е X; йи - максимальное количество потока, которое может протекать по дуге (х1, ) (нечеткая
пропускная способность).
Необходимо представить алгоритм решения данной задачи в нечетких условиях. Для этого введем метод поиска увеличивающего пути в транспортной сети с помощью поиска в ширину [102], модифицированный для применения в нечетких условиях и позволяющий находить кратчайший по количеству ребер нечеткий путь.
Метод поиска увеличивающего пути с помощью поиска в ширину в нечетких условиях
1. Формируем очередь, состоящую из вершин <2. На первом шаге 2 содержит только вершину-источник 5.
2. Помечаем вершину 5 как посещённую, не имеющую предка. Остальные вершины помечаем как непосещённые.
3. Осуществляем проверку вершин в очереди:
3.1. Если очередь пуста, останавливаемся и выходим из алгоритма, так как пути нет.
(2.1)
Х]еГ(!) хкеГ~'а)
(2.2)
) хк£Г~'{х,)
0,Х; Ф 5,?,
(2.3)