2025, issue 3, p. 22-36
Received 06.05.2025; Revised 12.07.2025; Accepted 02.09.2025
Published 29.09.2025; First Online 30.09.2025
https://doi.org/10.34229/2707-451X.25.3.2
Data Structures and Route Reduction Procedures in the Problem of Distribution Transport Flows in a Communication Network
Volodymyr Vasyanin * 
, Oleksandr Trofymchuk , Liudmyla Ushakova
Institute of Telecommunications and Global Information Space of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. In the problems of the distribution and routing of flows in communication networks, the input data is vehicle routes or data transmission channels. For the distribution of flows in this problems in optimization algorithms use special data structures – abstract data types, which describe the relationship between distributed flows and routes, as well as route reduction procedures, which can significantly reduce the number of such connections. The paper develops data structures and route reduction algorithms that allow solving the problem of distribution of flows in the case when the number of specified routes is very large, and the amount of computer RAM is limited. Estimates of the time complexity of the algorithm for reducing routes by nodes and arcs, as well as the algorithm for generating a reference data structure, have been obtained. The proposed algorithms were tested on networks with the number of nodes from 50 to 500 and the number of routes from 1225 to 124750, which showed their performance, good computational efficiency and they can be used in practical problems of distribution and routing of flows on large-dimensional networks.
Purpose. We present an effective algorithm for the route reduction that allow solving the problem of distribution of flows in the case when the number of specified routes is very large, and the amount of computer RAM is limited.
The technique. To get our estimators of time complexity of developed algorithms, we use numerical examples and simulations.
Results. Our proposed algorithms it is shown that is sufficient accuracy and speed, which allows us to assert their practical applicability for engineering calculations on large-scale networks.
Scientific novelty and practical significance. We demonstrate robustness and efficiency of proposed algorithms through rigorous computer simulations.
Keywords: multicommodity networks, discrete flows, problems of combinatorial optimization, computer modelling.
Cite as: Vasyanin V., Trofymchuk O., Ushakova L. Data Structures and Route Reduction Procedures in the Problem of Distribution Transport Flows in a Communication Network. Cybernetics and Computer Technologies. 2025. 3. P. 22–36. https://doi.org/10.34229/2707-451X.25.3.2
References
1. Trofymchuk O.M., Vasyanin V.A. Simulation of Packing, Distribution and Routing of Small-Size Discrete Flows in a Multicommodity Network. Journal of Automation and Information Sciences. 2015. 47 (7). P. 15–30. https://doi.org/10.1615/JAutomatInfScien.v47.i7.30
2. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Optimization Algorithms for Packing of Small-Lot Correspondence in Communication Networks. Cybernetics and Systems Analysis. 2016. 52 (2). P. 258–268. https://doi.org/10.1007/s10559-016-9822-5
3. Trofimchuk A.N., Vasyanin V.A. Computer Modeling of the Hierarchical Structure of a Communication Network with Discrete Multiproduct Flows. USiM. 2016. No. 2. P. 48–57. (in Russian) https://doi.org/10.15407/usim.2016.02.048
4. Trofimchuk A.N., Vasyanin V.A., Ushakova L.P. Study of the Problem of Optimizing the Hierarchical Structure of a Sparse and Dense Communication Network. Problems of Control and Informatics. 2021. No. 1. P. 5–21. (in Russian) https://doi.org/10.34229/1028-0979-2021-1-1
5. Vasyanin V.A. Problem of Distribution and Routing of Transport Blocks with Mixed Attachments and Its Decomposition. Journal of Automation and Information Sciences. 2015. Vol. 47, Issue 2. P. 56–69. https://doi.org/10.1615/JAutomatInfScien.v47.i2.60
6. Vasyanin V.A. Computer Modeling of Distribution and Routing of Discrete Multiproduct Flows in a Communication Network. USiM. 2016. No. 3. P. 43–53. (in Russian) https://doi.org/10.15407/usim.2016.03.043
7. Vasyanin V.A., Trofymchuk O.M., Ushakova L.P. Problem of Groupage Cargo Routing in the Multicommodity Transport Network with Given Tariffs and Delivery Time Constraints. Cybern Syst Anal. 2022. 58. P. 966–976. https://rdcu.be/c2Vh9; https://doi.org/10.1007/s10559-023-00531-z
8. Cormen T., Leiserson C., Rivest R., Stein С. Introduction to Algorithms, 2nd Edition. Cambridg: McGraw-Hill Book Company, 2001. 1296 p.
9. Sedgwick R.. Fundamental algorithms in C++. Algorithms on graphs. St.Pt.: DiaSoftUP LLC. 2002. 496 p. (in Russian)
10. Vasyanin V.A. A Two-Criterion Lexicographic Algorithm for Finding All Shortest Paths in Networks. Cybernetics and Systems Analysis. 2014. 50 (5). P. 759–767. https://doi.org/10.1007/s10559-014-9666-9
11. Certificate of copyright registration for the work "Computer Program for Optimization of Distribution and Routing of Discrete Flows in a Multi-Product Communication Network" / applicant and owner V.O. Vasyanin; A. S. dated 20.07.2016. No. 66794, State Intellectual Property Service of Ukraine; application dated 25.05.2016. No. 67224 on registration of copyright for the work. (in Ukrainian)
12. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Company, 1979. 338 p.
13. Trofymchuk O.M., Vasyanin V.A. Choosing the Capacity of Arcs with Constraint on Flow Delay Time. Cybernetics and Systems Analysis. 2019. 55 (4). P. 561–569. https://doi.org/10.1007/s10559-019-00165-0
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)