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

Аннотация

А.В. Боженюк, Е.М. Герасименко

Дата поступления статьи: 30.03.2013

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

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Введение
Задачи, рассматриваемые на транспортных сетях, в частности, потоковые задачи являются актуальными, поскольку позволяют решать широкий круг практических задач, а именно, задач нахождения максимального количества потока, которое можно передать по дугам сети, нахождения минимального по стоимости маршрута перевозки заданного количества единиц товара и пр. Потоковые задачи нахождения максимального потока и потока минимальной стоимости в транспортных сетях широко освещались в литературе авторами [1, 2, 3]. Но в условиях реальной жизни в данных задачах необходимо учитывать, что такие параметры транспортных сетей, как пропускные способности и стоимости перевозок не могут быть точно известны. На данные параметры влияют различные экзогенные и эндогенные виды неопределенности [4], в частности, пробки на дорогах, ремонтные работы, колебания в ценах на бензин, следовательно, мы приходим к потоковым задачам в транспортных сетях в нечетких условиях [5]. Данная область является менее исследованной, подобные задачи были рассмотрены в [6].
Потовые задачи, описанные ранее, можно отнести к статическим, так как при их рассмотрении не учитывается параметр времени прохождения потока по дугам сети. В действительности, поток затрачивает определенное время, чтобы добраться от начальной вершины дуги к конечной. Следовательно, мы приходим к «стационарно-динамическим» задачам. Данные модели предполагают не мгновенное прохождение потока по дугам сети. Данные задачи рассматривались в литературе авторами [1, 7].
Рассматриваемые в литературе задачи на динамических сетях, которые мы будем называть «стационарно-динамическими» задачами учитывают не мгновенное прохождение потока по дугам сети и не принимают во внимание возможность параметров транспортных сетей меняться во времени. Действительно, пропускные способности, стоимости перевозок и параметры времени прохождения потока по дугам сети могут изменяться в зависимости от времени отправления потока. Будем называть такие задачи «динамическими». Данная область исследования является малоизученной. Учитывая это, а также нечеткий характер параметров, присущий транспортным сетям, приходим к рассмотрению потоковых задач в динамических транспортных сетях в нечетких условиях [8]. В частности, рассмотрим в данной статье задачу определения потока минимальной стоимости в нечеткой динамической транспортной сети.
Задача нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети
Рассмотрим постановку задачу нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети:

(1)

(2)

(3)

(4)

(5)

Выражение (1) означает, что необходимо найти минимальный маршрут перевозки максимального количества потока в транспортной сети за заданное количество моментов времени. Выражение (2) показывает, что максимальное количество потока  за p периодов времени, равно потоку, выходящему из источника за p периодов времени  Выражение (4) показывает, что максимальное количество потока  за p периодов времени равно потоку, входящему в сток за p периодов времени  Количество потока , входящее в источник за p периодов времени, равно количеству потока, покидающему сток  за p периодов времени и равно . В (3) утверждается, что для каждого узла , кроме источника и стока, и каждого момента времени  количество потока , вошедшее в в момент времениравно числу единиц потока , выходящему из  в момент . Неравенство (5)показывает, что потоки  для всех моментов времени должны быть меньше пропускных способностей по соответствующим дугам.
Иными словами, необходимо перевезти  единиц потока с минимальными затратами в динамической транспортной сети, так, чтобы последняя единица потока вошла в сток в момент времени не позднее p.
Формальный алгоритм решения данной задачи:
Этап 1. Перейти от заданного нечеткого динамического графа  к «растянутому во времени» на p интервалов нечеткому статическому графу  путем «растягивания во времени» исходного динамического графа за заданное количество временных интервалов путем создания отдельной копии каждой вершины  в каждый рассматриваемый момент времени . Пусть  представляет собой «растянутый во времени» граф исходного динамического графа. Множество вершин  графа  задается как  Множество дуг  состоит из дуг, идущих из каждой пары «вершина-время»  в каждую пару «вершина время» вида где  и . Пропускные способности , соединяющие пары «вершина-время»  с  равны , стоимость перевозки  единицы потока по дуге, соединяющей пару «вершина-время»  с , равна  Вводим искусственный источник  и сток  и соединяем  дугами с каждым истинным источником, а  с каждым истинным стоком. Фиктивные дуги, идущие от искусственных вершин, имеют бесконечную пропускную способность и нулевую стоимость. Ищем максимальный поток от  к .
Этап 2. Строим нечеткую остаточную сеть  для «растянутого во времени графа»  в зависимости от величин, идущих по дугам графа потоков. Нечеткая остаточная сеть  строится по «растянутой во времени» сети  в зависимости от величин потоков , (далее ), идущих по дугам последней следующим образом: каждая дуга в остаточной нечеткой сети , соединяющая пару «вершина-время»  с парой «вершина-время» , по которой поток  отправляется в момент времени  имеет нечеткую остаточную пропускную способность , стоимость  с временем прохождения  и обратную дугу, соединяющую  с  с остаточной пропускной способностью , стоимостью  и временем прохождения потока по данной дуге  
Этап 3. Ищем путь  минимальной стоимости по алгоритму Форда из искусственного источника  в искусственный сток  в построенной нечеткой остаточной сети, начиная с нулевых значений потоков.
(I) Если путь  найден, переходим к этапу 4.
(II) Если пути не удалось найти, то получен максимальный поток  минимальной стоимости  в растянутом во времени статическом нечетком графе из  в , и переходим к шагу 5.
Этап 4. Пускаем по найденному пути максимальное количество единиц потока в зависимости от ребра в остаточной сети с минимальной остаточной пропускной способностью .
Этап 5. Обновляем значения потоков в графе : для дуг, соединяющих пару «вершина-время»  с  в  с неположительной модифицированной стоимостью  изменяем поток  по соответствующим дугам, идущим из  в  из  с  на . Для дуг, соединяющих пару «вершина-время»  с  в  с неотрицательной модифицированной стоимостью  изменяем поток  по дугам, идущим из  в  из  с  на  и переходим к этапу 2, начиная с нового значения потока по дугам и заменяя значение потока в графе : .
Этап 6. Если найден максимальный поток  минимальной стоимости  в графе  из фиктивного источника  в фиктивный сток , определяемый множеством путей , переходим к первоначальному динамическому графу  следующим образом: отбрасываем искусственные вершины ,  и дуги, соединяющие их с другими вершинами. Таким образом, в исходном динамическом графе  получен максимальный поток  минимальной стоимости, эквивалентный потоку из источников (начальная вершина исходного графа, растянутая на p интервалов) в стоки (конечная вершина, растянутая на p интервалов) в графе  после удаления фиктивных вершин, а каждый путь, соединяющий вершины  и , по которому идет поток  стоимости  соответствует потоку . стоимости .
Численный пример, реализующий работу алгоритма
Рассмотрим пример, иллюстрирующий реализацию описанного алгоритма. Пусть транспортная сеть, являющаяся частью железнодорожной карты, представлена в форме нечеткой транспортной сети, полученной из ГИС «Object Land» [9] , как показано на рис.1. Понятие «ГИС» представлено в [10].

Рис.  1. – Исходный динамический граф

Вершина  представляет собой источник, вершина  – сток. Нечеткие пропускные способности и стоимости, а также параметры времени прохождения потока по дугам, зависящие от момента отправления потока представлены в виде таблиц № 1, 2 и 3. Необходимо найти минимальную стоимость перевозки максимального количества единиц потока . Правила оперирования с нечеткими треугольными числами представлены в [6].
Строим остаточную сеть, как показано на рис.2. Так как остаточная сеть на первом шаге совпадает с исходным «растянутым во времени» графом, находим в ней путь минимальной стоимости от  к  по алгоритму Форда в . Получаем путь  стоимости  условных единиц и передаем по нему  общей стоимости  единиц потока, что показано на рис.3.
Таблица № 1
Нечеткие пропускные способности, зависящие от момента отправления потока

Момент времени	Нечеткие пропускные способности по дугам графа , ед.
0
1
2
3

Таблица № 2
Нечеткие стоимости, зависящие от момента отправления потока

Момент времени	Нечеткие стоимости по дугам граф , условные ед.
0
1
2
3

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

Таблица № 3
Параметры времени прохождения потока по дугам

Момент времени	Время прохождения потока по дугам графа , ед. времени
0	1	4	4	2	5	1
1	1	3	1	4	4	4
2	3	1	3	1	3	1
3	2	1	3	2	3	1

Рис.  2. –  – «растянутый во времени» вариант графа

Рис.  3. – Граф  с потоком  единиц

Рис.  4. – Остаточная сеть  после нахождения потока

Рис.  5. – Граф  с новым значением потока

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

Рис.  6. – Остаточная сеть  после нахождения потока

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

Литература:

1. Форд, Л.Р. Потоки в сетях [Текст] / Л.Р. Форд, Д.Р. Фалкерсон. – М: Мир, 1966. – 276 с.
2. Крисофидес, Н. Теория графов. Алгоритмический подход [Текст] / Н. Кристофидес. – М: Мир, 1978. – 432 с.
3. Майника, Э. Алгоритмы оптимизации на сетях и графах [Текст] / Э. Майника – М: Мир, 1981. – 326 с.
4. Целигоров, Н.А., Целигорова, Е.Н., Мафура, Г.В. Математические модели неопределенностей систем управления и методы, используемые для их исследования [Электронный ресурс] // «Инженерный вестник Дона», 2012, №4. – Режим доступа: http://ivdon.ru/magazine/archive/ n4p2y2012/1340 (доступ свободный) – Загл. с экрана. – Яз. рус.
5. Bozhenyuk, A., Gerasimenko, E., Rozenberg, I. The task of minimum cost flow finding in transportation networks in fuzzy conditions [Text] // Proceedings of the 10th International FLINS Conference on Uncertainty Modeling in Knowledge Engineering and Decision Making Word Scientific, Istanbul, Turkey, 26-29 August 2012. – pp. 354-359
6. Bozhenyuk, A., Gerasimenko, E., Rozenberg, I. The methods of maximum Flow and minimum cost flow finding in fuzzy network [Text] // Proceedings of the Concept Discovery in Unstructured Data Workshop (CDUD 2012) co-located with the 10th International Conference on Formal Concept Analysis (ICFCA 2012) May 2012, Katholieke Universiteit Leuven, Leuven, Belgium 2012. – pp. 1-12.
7.  Боженюк, А.В. Анализ и исследование потоков и живучести в транспортных сетях при нечетких данных [Текст] // А.В. Боженюк, И.Н. Розенберг, Т.А. Старостина – М: Научный мир, 2006. – 136 с.
8. Bozhenyuk, A., Gerasimenko, E., Rozenberg, I. Algorithm of maximum dynamic flow finding in a fuzzy transportation network [Text] // Proceedings of East West Fuzzy Colloquium 2012 19th Zittau Fuzzy Colloquium, September 5 – 7, pp. 125-132.
9.  Rozenberg, I., Gittis, C., Svyatov, D. Geoinformation system Object Land [Text] // Proceedings of IPI RAN Systems and Means of Informatics. – Science, Moscow, 2000.
10. Клаус, Н.Г., Клаус, А.И. Практика интеграции геоинформационных систем и многоагентных моделей в исследовании социальных конфликтов [Электронный ресурс] // «Инженерный вестник Дона», 2011, №1. – Режим доступа: http://ivdon.ru/magazine/archive/ n1y2011/400 (доступ свободный) – Загл. с экрана. – Яз. рус.