DOI: https://doi.org/10.15802/stp2020/200748

UNIFIED PARALLEL ALGORITHM AND PROGRAMMING COMPLEX OF OPTIMAL PLANNING OF NON-UNIFORM FLOWS IN THE NETWORKS

V. V. Skalozub, L. А. Panik, A. D. Panarin

Abstract


Purpose. The purpose of the article is to develop a universal unified parallel synchronous algorithm for the implementation of tasks for calculation of maximum one- and multicommodity flows, as well as the creation of a software complex that provides the formation of surface graph models of flows and performs optimal planning of non-uniform flows in transport and other networks. Methodology. The paper investigates the possibilities of previously created and comprehensively verified heuristic parallel synchronous algorithm for calculating maximum one- and multicommodity flows in the networks, establishes its potential limitations, and determines additional advanced procedures that transform the algorithm into a universal parallel algorithm. The proposed parallel synchronous algorithm uses a width-first search strategy while simultaneously identifying possible paths of flows through the network with an estimation of their throughput. Herewith the possibility of analyzing several incremental flows across the network in one iteration was studied. Findings. The article proposes a universal unified parallel synchronous algorithm for calculating maximum flows in networks and develops a unified procedure and software package for planning of non-uniform as well as competitive flows in transport and other networks. The developed software complex implements the problems of formation of surface graph models of networks, for which the problem of optimal planning of non-uniform and competitive multicriteria flows in transport networks is solved. Originality. The article develops a new universal unified parallel synchronous algorithm and procedure for the calculation of optimal uniform, multicommodity and competitive flows in transport networks. Practical value. The practical value of the obtained results is determined by the universal capabilities and efficiency of the procedure for planning non-uniform flows in the networks based on the application of a new parallel synchronous algorithm, as well as the developed software complex, which provides the ability to solve the problems of analysis and planning of uniform and multicommodity flows in transport networks, as well as the implementation of calculation tasks of competitive models of transport and information flows formation. The software complex has a built-in editor of interactive network modeling and a toolbar, which provides both creation of new and downloading existing graphs of networks from the modeling libraries, preservation of optimum flows in the network in the form of an image and a text file, output of errors when working with the program.


Keywords


transport networks; maximum flows; parallel algorithms; non-uniform and competitive flows; software

References


Gasnikov, V. A. (2013). Vvedenie v matematicheskoe modelirovanie transportnykh potokov: Uchebnoe posobie. Moscow: MTSNMO. (in Russian)

Kormen, T. K., Leyzerson, C. I., Rivest, R. L., & Shtayn, K. (2011). Algoritmy: Postroenie i analiz. Moskow: Williams. (in Russian)

Skalozub, V. V., Tseytlin, S. Y., & Cherednichenko, M. S. (2016). Intellektualnye informatsionnye tekhnologii i sistemy zheleznodorozhnogo transporta: monografiya. In A. I. Mikhaleva (Ed.). Sistemnye tekhnologii modelirovaniya slozhnykh protsessov. Dnipro. (in Russian)

Skalozub, V. V., & Panik, L. А. (2016). The construction of generalized models for planning heterogeneous transport flows. System technologies, 5(106), 94-101. (in Russian)

Skalozub, V. V., & Panik, L. O. (2017). Parallel Synchronous Algorithms of Analysis and Planning of Inhomogeneous Flows in Transpotnic Networks. System technology, 5(112), 183-197. (in Ukranian)

Skalozub, V. V., & Panik, L. O. (2018). Implementation of the dynamic, competitive and fuzzy models for planning of the multi-product flows in transport networks. Science and Transport Progress, 3(75), 113-127. (in Russian)

Fillips, D. I., & Garsia-Dias, A. (1984). Metody analiza setey. Moscow: Mir. (in Russian)

Bozhenyuk, А. & Gerasimenko, E. (2013). Algorithm for Monitoring Minimum Cost in Fuzzy Dynamic Networks. Information Technology and Management Science, 16(1), 53-59. DOI: https://doi.org/10.2478/itms-2013-0008 (in English)

Bozhenyuk, A. V., Gerasimenko, E. M., Kacprzyk, J., & Rozenberg, I. N. (2016). Maximum and Minimum Cost Flow Finding in Networks in Fuzzy Conditions. Flows in Networks Under Fuzzy Conditions, 346, 23-75. Cham: Springer. DOI: https://doi.org/10.1007/978-3-319-41618-2_2 (in English)

Capuni, I., Zhuri, N., & Dardha, R. (2019). TimeStream: Exploiting video streams for clock synchronization. Ad Hoc Networks, 91, 236-248. DOI: https://doi.org/10.1016/j.adhoc.2019.101878 (in English)

Holzhauser, M., Krumke, S. O., & Thielen, C. (2016). Maximum flows in generalized processing networks. Journal of Combinatorial Optimization, 33(4), 1226-1256. DOI: https://doi.org/10.1007/s10878-016-0031-y (in English)

Kovacs, P. (2013). Minimum-cost flow algorithms: An experimental evaluation EGRES Technical Report. EGRES Technical Report, 4, 1-40. Retrieved from https://web.cs.elte.hu/egres/tr/egres-13-04.pdf (in English)

Reardon, L. (2018). Networks and problem recognition: advancing the Multiple Streams Approach. Policy Sciences, 51(4), 457-476. DOI: https://doi.org/10.1007/s11077-018-9330-8 (in English)

Rezende, P., Kianpisheh, S., Glitho, R., & Madeira, E. (2019). An SDN-Based Framework for Routing Multi-Streams Transport Traffic Over Multipath Networks. ICC 2019–2019 IEEE International Conference on Communications (ICC), 1-6. DOI: https://doi.org/10.1109/ICC.2019.8762061 (in English)

Schiopu, C., & Ciurea, E. (2016). The Maximum Flows in Planar Dynamic Networks. International Journal of Computers Communications & Control, 11(2), 282-291. DOI: https://doi.org/10.15837/ijccc.2016.2.2444 (in English)

Sifaleras, A. (2013). Minimum cost network flows: Problems, algorithms, and software. YUJOR, 23(1), 3-17. DOI: https://doi.org/10.2298/YJOR121120001S (in English)


GOST Style Citations


  1. Гасников В. А. Введение в математическое моделирование транспортных потоков : Учебное пособие. Москва : МЦНМО, 2013. 428 с.
  2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы : построение и анализ. Пер. с англ. 2-е изд. Москва : Вильямс, 2005. 1296 с.
  3. Скалозуб В. В., Цейтлин С. Ю., Чередниченко М. С. Интеллектуальные информационные технологии и системы железнодорожного транспорта : монография. «Системные технологии моделирования сложных процессов». Днепр, 2016. С. 560–589.
  4. Скалозуб В. В., Паник Л. А. О построении обобщенных моделей планирования неоднородных транспортных потоков. Системные технологии. 2016. № 5 (106). С. 94–101.
  5. Скалозуб В. В., Панік Л. О. Паралельні синхронні алгоритми аналізу та планування неоднорідних потоків у транспортних мережах. Системные технологии. 2017. № 5 (112). С. 183–197.
  6. Скалозуб В. В., Паник Л. А. Реализация динамических, конкурентных и нечетких моделей планирования многопродуктовых потоков в транспортных сетях. Наука и прогрес транспортy. 2018. № 3 (75). С. 113–127. DOI: https://doi.org/10.15802/stp2018/133742
  7. Филлипс Д. И., Гарсиа-Диас А. Методы анализа сетей. Москва : Мир, 1984. 496 с.
  8. Bozhenyuk А., Gerasimenko E. Algorithm for Monitoring Minimum Cost in Fuzzy Dynamic Networks. Information Technology and Management Science. 2013. Vol. 16. Iss. 1. P. 53–59. DOI: https://doi.org/10.2478/itms-2013-0008
  9. Bozhenyuk А. V., Gerasimenko E. M., Kacprzyk J. Maximum and Minimum Cost Flow Finding in Networks in Fuzzy Conditions. Flows in Networks Under Fuzzy Conditions. 2016. Vol. 346. P. 23–75. DOI: https://doi.org/10.1007/978-3-319-41618-2_2
  10. Capuni I., Zhuri N., Dardha R. TimeStream: Exploiting video streams for clock synchronization. Ad Hoc Networks. 2019. Vol. 91. P. 236–248. DOI: https://doi.org/10.1016/j.adhoc.2019.101878
  11. Holzhauser M., Sven O. Krumke, Clemens Thielen. Maximum flows in generalized processing networks. Journal of Combinatorial Optimization. 2016. Vol. 33. Iss. 4. P. 1226–1256. DOI: https://doi.org/10.1007/s10878-016-0031-y
  12. Kovacs P. Minimum-cost flow algorithms : An experimental evaluation EGRES Technical Report. EGRES Technical Report. 2013. No. 4. P. 1–40. URL : https://web.cs.elte.hu/egres/tr/egres-13-04.pdf (дата звернення: 17.05.2018).
  13. Reardon L. Networks and problem recognition: advancing the Multiple Streams Approach. Policy Sciences. 2018. Vol. 51. Iss. 4. P. 457–476. DOI: https://doi.org/10.1007/s11077-018-9330-8
  14. Rezende P., Kianpisheh S., Glitho R., Madeira E. An SDN-Based Framework for Routing Multi-Streams Transport Traffic Over Multipath Networks. ICC 2019 – 2019 IEEE International Conference on Communications (ICC). Shanghai. China. 2019. P. 1–6. DOI: https://doi.org/10.1109/ICC.2019.8762061
  15. Schiopu C., Ciurea E. The Maximum Flows in Planar Dynamic Networks. Intern. Journal of Computers Communications&Control. 2016. Vol. 11. Iss. 2. P. 282–291. DOI: https://doi.org/10.15837/ijccc.2016.2.2444
  16. Sifaleras A. Minimum cost network flows: problems, algorithms, and software. YUJOR. 2013. Vol. 23. Iss. 1. DOI: https://doi.org/10.2298/YJOR121120001S




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN 2307–3489 (Print)
ІSSN 2307–6666 (Online)