ОПРЕДЕЛЕНИЕ МАКСИМАЛЬНОГО ПОТОКА В НЕЧЕТКОМ ПЕРИОДИЧЕСКОМ ГРАФЕ
Аннотация
Предложен метод нахождения максимального значения динамического потока с использо-
ванием периодических графов, представленном в виде обобщенной сети. Интерес к сетям такого
вида объясняется их широким практическим применением в местах, где есть периодичность, на-
пример управление периодическими пассажирскими перевозками на различных видах транспорта,
грузовые перевозки, в том числе товаров с коротким сроком годности, управление дорожно-
транспортным потоком, а именно регулирование светофоров, с учетом периодичности и загру-
женности. В то же время значения пропускной способности дуг рассматриваемых сетей могут
варьироваться в зависимости от времени отправления потока и возможных циклов, поэтому мы
переходим к динамическим сетям. Параметры сети представлены в нечеткой форме из-за влия-
ния факторов окружающей среды и деятельности человека. А выбор именно периодических гра-
фов обусловлен наличием циклов и периодичностью временных интервалов. Рассмотренные типы
сетей могут быть реализованы на реальных дорогах в процессе транспортировки. Для решения
выявленной проблемы, в рамках представленной работы приведен краткий обзор литературных
источников, позволяющий оценить современный уровень развития систем подобного назначения.
В результате выполнения данного обзора установлено, что наиболее эффективными методами
решения поставленной проблемы, является применение методов нечетких периодических графов.
В связи с этим принято решение о проведении исследования указанных методов. Новизна данной
работы определяется исходя из применения периодических темпоральных нечетких графов в рам-
ках решения задачи нахождения максимального потока динамической сети.
Литература
Nostrand Reinhold, 1985.
2. Inuiguchi M., Romik J. Probabilistic linear programming: A brief overview of fuzzy mathematical
programming and comparison with stochastic programming in portfolio selection, Fuzzy Sets and Systems,
2000, Vol. 111, No. 1, pp. 3-28.
3. Buckley J., Fearing T. Fuzzy Mathematics in Economics and Finance. Heidelberg: Physica-Verlag,
2000.
4. Zadeh L.A. Fuzzy sets, Information and control, 1965, Vol. 8, No. 3, pp. 338-353.
5. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley
Longman Publishing Co., Inc., Boston, MA, 1989.
6. Holland J. Adaptation in Natural and Artificial Systems: An Introductory Analysis with applications
to biology, Management and Artificial Intelligence. University of Michigan Press, Ann Arbor, Michigan,
1975.
7. Kureichik V, Gerasimenko E Approach to the minimum cost flow determining in fuzzy terms considering
vitality degree, Advances in Intelligent Systems and Computing, 2017, 573, pp. 200-210. DOI:
10.1007/978-3-319-57261-1_20.
8. Bozhenyuk A.V., Gerasimenko E.M., Kacprzyk J., and Rozenberg I.N. Flows in Networks Under Fuzzy
Conditions. Springer International Publishing, Switzerland, 2017.
9. Bozhenyuk A., Kosenko O., Knyazeva M., and Dolgiy A. The Comparative Approach to Solving Temporal-
Constrained Scheduling Problem Under Uncertainty, Lecture Notes in Computer Science, 2021,
Vol. 13068, pp. 173-183.
10. Bozhenyuk A., Belyakov S., Gerasimenko E., and Savelyeva M. Fuzzy optimal allocation of service
centers for sustainable transportation networks service, Intelligent Systems Reference Library, 2017,
Vol. 113, pp. 415-437.
11. Gorbachev S., Bozhenyuk A., Nikashina P. Optimization of Traffic Flow Based on Periodic Fuzzy
Graphs. Springer Tracts in Human-Centered Computing (STHC), 2023. – 374-383. Available at:
https://doi.org/10.1007/978-981-99-3478-2_32.
12. Knyazeva M., Bozhenyuk A., Kaymak U. Managing temporal uncertainty in multi-mode Z-number
fuzzy graph structures, Proceedings of the 2019 Conference of the International Fuzzy Systems Association
and the European Society for Fuzzy Logic and Technology, 2019, Vol. 1, pp. 580-587.
Available at: https://doi.org/10.2991/eusflat-19.2019.80.
13. Çakır E., Ulukan Z., Acarman T. Shortest Fuzzy Hamiltonian Cycle on Transportation Network Using
Minimum Vertex Degree and Time-dependent Dijkstra’s Algorithm, IFAC-PapersOnLine, 2021,
54 (2), pp. 348-353. Available at: https://doi.org/10.1016/j.ifacol.2021.06.048.
14. Wayne K.D., Fleische L. Faster approximation algorithms for generalized flow, Proceedings of 10th
Annual ACM-SIAM Symposium on Discrete Algorithms. Baltimore, MD, USA, 1998.
15. Eguchi A., Fujishige S., Takabatake T. A polynomial-time algorithm for the generalized independentflow
problem, J. Oper. Res., 2004, 47 (1), pp. 1-17.
16. Krumke S.O., Zeck C. Generalized max flow in series–parallel graphs, Discrete Optimization, 2013,
10 (2), pp. 155-162. Available at: https://doi.org/10.1016/j.disopt.2013.01.001.
17. Kartikasari R. Optimization of Traffic Light Control Using Fuzzy Logic Sugeno Method, International
Journal of Global Operations Research, 2020, pp. 51-61.
18. Belyakov S., Bozhenyuk A., Samoylov L., Nikashina P. Geoinformation Model for Smart Grid
Sustainability Management, Intelligent and Fuzzy Systems. INFUS 2023. Lecture Notes in Networks
and Systems, 2023, Vol. 759, pp. 651-658.
19. Umare P.R.; Jayswal S.G.; Tambakhe S.R.; Upadhye P.D.; Gulhane N.D. Smart Solution for Traffic
Control, In Proceedings of the 2019 IEEE 4th International Conference on Computer and
Communication Systems (ICCCS), 2019, pp. 721-724.
20. Kutlimuratov K., Khakimov S., Mukhitdinov A., Samatov R. Modelling trffic flow emissions at
signalized intersection with PTV vissim, Mezhdunarodnaya nauchnaya konferentsiya «Stroitel'naya
mekhanika, gidravlika i gidrotekhnika» [International scientific conference "Structural mechanics, hydraulics
and hydraulic engineering"], 2021, pp. 12.
