Статья

Название статьи ПОДХОД К НАХОЖДЕНИЮ МАКСИМАЛЬНОГО ДВУХПРОДУКТОВОГО ПОТОКА В НЕЧЕТКОЙ ТРАНСПОРТНОЙ СЕТИ
Автор Е. М. Герасименко
Рубрика РАЗДЕЛ II. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НЕЧЕТКИЕ СИСТЕМЫ
Месяц, год 04, 2018
Индекс УДК 519.178
DOI
Аннотация Данная статья посвящена решению задачи нахождения максимального двухпродуктового потока в нечеткой транспортной сети. Задача определения объема многопродуктового потока, проходящего по транспортной сети, является актуальной задачей при транспортном планировании и оптимизации перевозок. Данная статья описывает разновидность такой задачи – в частности, проблему определения потока двух продуктов в транспортной сети. Основной сложностью данной задачи является тот факт, что теорема о максимальном потоке и минимальном разрезе не выполняется для такого рода задач, однако, она выполняется для нахождения протока двух продуктов в неориентированной транспортной сети. Особенностью данной задачи является возможность первого потока блокировать поток второго продукта таким образом, что мы можем не получить оптимальный результат. Центральной частью данной задачи являются параметры транспортной сети, представленные в нечеткой форме, такие как пропускные способности ее дуг. Разработанный метод использует модифицированный алгоритм поиска увеличивающего пути, позволяющий учитывать нечеткие параметры сети, приписанные дугам графа. Описанный метод может применяться при планировании перевозок двух типов товаров, каждый из которых имеет свой источник и сток, например, в случае пассажирских и грузовых поездов или легковых и грузовых машин. Рассмотрен метод оперирования нечеткими числами, не приводящий к «размытию» границ результирующего числа и позволяющий оперировать нечеткими границами на последних итерациях, в то время как на остальных предшествующих итерациях производятся вычислениями только с центрами нечетких чисел. Рассмотрен численный пример, который иллюстрирует работу предложенного алгоритма.

Скачать в PDF

Ключевые слова Двухпродуктовый поток; нечеткий граф; нечёткий двойной путь.
Библиографический список 1. Hu T. Multi-commodity network flows // Oper. Res. – 1963. – No. 11. – P. 344-360.
2. Itai A. Two-commodity flow // Journal of the Association for Computing Machinery. – 1978.
– Vol. 25, No. 4. – P. 596-611.
3. Rajagopalan S. Two-commodity flow // Oper. Res. Lett. – 1994. – Vol. 15. – P. 151-156.
4. Costa M., Letocart L., Roupin F. Minimal multicat and maximal integer multiflow: A survey // Eur. J. Oper. Res. – 2005. – Vol. 162 (1). – P. 55-69.
5. Kureichik V., Gerasimenko E. Approach to the Minimum Cost Flow Determining in Fuzzy Terms Considering Vitality Degree. In Silhavy R., Senkerik R., Kominkova Oplatkova Z., Prokopova Z., Silhavy P. (eds) // Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. – Springer, Cham, 2017. – Vol. 573.
– P. 200-209.
6. Bozhenyuk A., Gerasimenko E., Kacprzyk J., Rozenberg I. Flows in networks under fuzzy conditions // Studies in Fuzziness and Soft Computing. – Heidelberg: Springer-Verlag, 2017.
– Vol. 346. – P. 269-291.
7. Боженюк А.В., Герасименко Е.М., Розенберг И.Н. Разработка метода определения потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями с помощью метода потенциалов // Известия ЮФУ. Технические науки. – 2015. – № 6 (167). – С. 138-149.
8. Bozhenyuk A, Gerasimenko E., Rozenberg I. Determining the Minimum Cost Flow in Fuzzy Dynamic Network with GIS «ObjectLand» // Proceedings of 9th International Conference on Application of Information and Communication Technologies, AICT 2015. – Rostov on Don, 2015. – P. 294-298.
9. Kolman P., Scheideler C. Improved bounds for the unsplittable flow problem // J. Algor.
– 2006. – Vol. 61 (1). – P. 20-44.
10. Barnhart C., Krishnan N., Vance P.H. Multicommodity Flow Problems. In Floudas C., Pardalos P. (eds) // Encyclopedia of Optimization. Springer, Boston, MA, 2008.
11. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems // Oper Res. – 2000. – Vol. 48 (2).
– P. 318-326.
12. Karakostas G. Faster approximation schemes for fractional multicommodity flow problems // Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms.
– 2002. – P. 166-173.
13. McBride R.D., Carrizosa E. Conde E. Munoz-Marquez M. Advances in solving the multi-commodity flow problem // Interfaces. – 1998. – Vol. 28 (2). – P. 32-41.
14. Sedeño-Noda A., González-Martín C., Alonso-Rodríguez S. A new strategy for the undirected two-commodity maximum flow problem // Computational Optimization and Applications.
– 2010. – Vol. 47 (2). – P. 289-305.
15. Kureichik V., Gerasimenko E. Multi-Commodity Maximum Flow Determining in a Fuzzy Graph with Vitality Degrees // Proceedings of 11th International Conference on Application of Information and Communication Technologies, AICT 2017, Moscow, Russia. – P. 347-351.
16. Bozhenyuk A., Gerasimenko E., Rozenberg I. Method of Maximum Two-Commodity Flow Search in a Fuzzy Temporal Graph // Proceedings of the 10th Conference of the European Society for Fuzzy Logic of and Technology EUSFLAT-2017, September 11-15, 2017, Warsaw, Poland. – P. 249-260.
17. Cormen T.H, Leiserson C.E, Rivest R.L., Stein C. Introduction to Algorithms (3rd ed.). MIT Press and McGraw–Hill, 2009.
18. Ganesan K., Veeramani P. Fuzzy Linear Programs with Trapezoidal Fuzzy Numbers // Ann Oper Res. – 2006. – P. 305-315.
19. Kumar A., Kaur J., Singh P. Fuzzy Optimal Solution of Fully Fuzzy Linear Programming Problems with Inequality Constraints // International Journal of Mathematical and Computer Sciences 6:1, 2010. – P. 37-41.
20. Боженюк А. Герасименко Е., Розенберг И. Алгоритм нахождения нечеткого потока в транспортной сети с нечеткими стоимостями и пропускными способностями // Известия ЮФУ. Технические науки. – 2012. – № 5 (130). – C. 118-122.
21. Герасименко Е. Нахождение потока минимальной стоимости в транспортной сети методом ранжирования математического ожидания нечетких функций стоимостей // Известия ЮФУ. Технические науки. – 2012. – № 4 (129). – C. 247-251.

Comments are closed.