UNIFIED PARALLEL ALGORITHM AND PROGRAMMING COMPLEX OF OPTIMAL PLANNING OF NON-UNIFORM FLOWS IN THE NETWORKS
DOI:
https://doi.org/10.15802/stp2020/200748Keywords:
transport networks, maximum flows, parallel algorithms, non-uniform and competitive flows, softwareAbstract
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.
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)
Downloads
Published
How to Cite
Issue
Section
License
Copyright and Licensing
This journal provides open access to all of its content.
As such, copyright for articles published in this journal is retained by the authors, under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0). The CC BY license permits commercial and non-commercial reuse. Such access is associated with increased readership and increased citation of an author's work. For more information on this approach, see the Public Knowledge Project, the Directory of Open Access Journals, or the Budapest Open Access Initiative.
The CC BY 4.0 license allows users to copy, distribute and adapt the work in any way, provided that they properly point to the author. Therefore, the editorial board of the journal does not prevent from placing published materials in third-party repositories. In order to protect manuscripts from misappropriation by unscrupulous authors, reference should be made to the original version of the work.
