РЕШЕНИЕ ЗАДАЧИ МОДЕЛИРОВАНИЯ ЧАСТИЧНО РЕВЕРСИВНОГО ПОТОКА МИНИМАЛЬНОЙ СТОИМОСТИ В НЕЧЕТКИХ УСЛОВИЯХ

  • Е.М. Герасименко Южный федеральный университет
Ключевые слова: Частично реверсивный поток, нечеткий поток минимальной стоимости, транспортные сети

Аннотация

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

Литература

1. 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, pp. 269-291.
2. Zadeh L.A. Fuzzy sets, Information and Control, 1965, Vol. 8 (3), pp. 338-353.
3. Novák V., Perfilieva I., Močkoř J. Mathematical principles of fuzzy logic. Dordrecht: Kluwer
Academic, 1999.
4. Rebennack S., Arulselvan A., Elefteriadou L., Pardalos P.M. Complexity analysis of maximum
flow problem with arc reversal, Journal of Combinatorial Optimization, 2010, Vol. 29,
pp. 200-216.
5. Cova T., Johnson J.P. A network flow model for lane-based evacuation routing, Transp. Res.
Part Policy Pract., 2003, Vol. 37, pp. 579-604.
6. Pyakurel U., Nath H.N., Dempe S., Dhamala T.N. Efficient Dynamic Flow Algorithms for Evacuation
Planning Problems with Partial Lane Reversal, Mathematics, 2019, Vol. 7 (10), pp. 1-29.
7. Pyakurel U. Dhamala T.N. Dempe S. Efficient continuous contraflow algorithms for evacuation
planning problems, Ann. Oper. Res., 2017, Vol. 254, pp. 335-364.
8. Köhler E., Langkau, K. Skutella, M. Time expanded graphs for flow depended transit times, European
Symposium on Algorithms. Springer: Berlin/Heidelberg, Germany, 2002, pp. 599-611.
9. Dhamala T.N. A survey on models and algorithms for discrete evacuation planning network
problems, J. Ind. Manag. Optim., 2015, Vol. 11, pp. 265-289.
10. Bozhenyuk A. Gerasimenko E. Rozenberg I. Algoritm nakhozhdeniya nechetkogo potoka v
transportnoy seti s nechetkimi stoimostyami i propusknymi sposobnostyami [Algorithm of the
fuzzy flow finding in the transportation network with fuzzy costs and arc capacities], Izvestiya
YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 5 (130),
pp. 118-122.
11. Gerasimenko E. Nakhozhdenie potoka minimal'noy stoimosti v transportnoy seti metodom
ranzhirovaniya matematicheskogo ozhidaniya nechetkikh funktsiy stoimostey [Minimum cost
flow finding in the network by the method of expectation ranking of fuzzy cost functions],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 4
(129), pp. 247-251.
12. 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,
pp. 200-209.
13. Bozhenyuk A.V., Gerasimenko E.M., Rozenberg I.N. Razrabotka metoda opredeleniya potoka
minimal'noy stoimosti v transportnoy seti s nechetkimi propusknymi sposobnostyami i
stoimostyami s pomoshch'yu metoda potentsialov [Development of the minimum cost flow
method with fuzzy arc capacities and costs by the potential method], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6 (167), pp. 138-149.
14. 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,
Russia, pp. 294-298.
15. Gerasimenko E., Rozenberg I. Earliest arrival dynamic flow model for emergency evacuation
in fuzzy conditions, IOP Conference Series: Materials Science and Engineering, 2020, Vol.
734 (1), pp. 1-6.
16. Gerasimenko E., Kureichik V. The Maximum Lexicographic Contraflow Finding in a Fuzzy
Dynamic Network, Advances in Intelligent Systems and Computing, 2021, Vol. 1197,
pp. 981-989.
17. Dijkstra E. A note on two problems in connection with graphs, Numerische Mathematik, 1959,
Vol. 1, pp. 269-271.
18. Ganesan K., Veeramani P. Fuzzy Linear Programs with Trapezoidal Fuzzy Numbers, Ann
Oper Res., 2006, pp. 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, 2010, 6:1, pp. 37-41.
Опубликован
2020-11-22
Выпуск
Раздел
РАЗДЕЛ I. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НЕЧЕТКИЕ СИСТЕМЫ