A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network
DOI:
https://doi.org/10.32347/2411-4049.2025.3.8-32Keywords:
multicommodity hierarchical networks, discrete flows, problems of combinatorial optimization, mathematical models, computer modelingAbstract
The paper discusses the methodology of mathematical modeling of the two-stage problem of optimization of the backbone hierarchical communication network with multicommodity discrete flows and parameters. The methodology is based on the sequential solution of the problem of optimizing the network structure and the problem of distribution and routing of discrete correspondence flows. As a rule, such networks consist of a decentralized backbone network and fragmented networks in the internal service areas of the backbone nodes. There are four types of network nodes and three levels of its hierarchy. In a multicommodity network, each node can exchange correspondence (products, goods, cargo, messages) with other nodes. Correspondence is characterized by a source node, a drain node and a value, which for transport networks is given by the number of packaged goods, cargo in a package of a unified size, and for data transmission networks – by the number of bytes, kilobytes, etc. In the transport backbone network, all correspondence is first sorted by destination addresses, packed in transport blocks (containers), and then transported in vehicles along the transport highways. In data networks, correspondence is also sorted by destination addresses (multiplexed), packaged in virtual transport blocks, and then transmitted over trunk communication channels. The size (capacity, volume) of the transport blockt is set by the parameter, and is determined by the number of units of correspondence that fit into it. Mathematical models of problems of optimization of network structure, distribution and routing of flows, and an example of numerical modeling of solving problems on a transport network containing 120 nodes and 300 unoriented arcs are presented. Experimental studies have shown high computational efficiency of the proposed algorithms and programs, and they can be recommended for the practical solution of problems of optimizing the processes of processing and transporting flows in communication networks of large dimensions.
References
Assad, A. A. (1978). Multicommodity network flows: A survey. Networks, 8(1), 37–91.
Kennington, J. L. (1978). A survey of linear cost multicommodity network flows. Operations Research, 26(2), 206–236.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Upper Saddle River, NJ: Prentice Hall.
Barnhart, C., Hane, C. A., & Vance, P. H. (1997). Integer multicommodity flow problems. In P. M. Pardalos, D. W. Hearn, & W. W. Hager (Eds.), Network optimization (Lecture Notes in Economics and Mathematical Systems, Vol. 450, pp. 17–31). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-59179-2_2
Barnhart, C., Hane, C. A., & Vance, P. H. (2000). Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research, 48(2), 318–326. https://doi.org/10.1287/opre.48.2.318.12378
Floudas, C. A., & Pardalos, P. M. (Eds.). (2009). Encyclopedia of optimization (2nd ed.). New York: Springer.
Wang, I.-L. (2018). Multicommodity network flows: A survey, Part I: Applications and formulations. International Journal of Operations Research, 15(4), 145–153. https://doi.org/10.6886/IJOR.201812_15(4).0001
Wang, I.-L. (2018). Multicommodity network flows: A survey, Part II: Solution methods. International Journal of Operations Research, 15(4), 155–173. https://doi.org/10.6886/IJOR.201812_15(4).0002
Cohn, A., Root, S., Wang, A., & Mohr, D. (2007). Integration of the load matching and routing problem with equipment balancing for small package carriers. Transportation Science, 41(2), 238–252. https://doi.org/10.1287/trsc.1060.0174
Hellsten, E., Koza, D. F., Contreras, I., Cordeau, J.-F., & Pisinger, D. (2021). The transit time constrained fixed charge multicommodity network design problem. Computers & Operations Research, 136, 105511. https://doi.org/10.1016/j.cor.2021.105511
Trivella, A., Corman, F., Koza, D. F., & Pisinger, D. (2021). The multicommodity network flow problem with soft transit time constraints: Application to liner shipping. Transportation Research Part E: Logistics and Transportation Review, 150, 102342. https://doi.org/10.1016/j.tre.2021.102342
Trofymchuk, O. M., & Vasyanin, V. A. (2015). Simulation of packing, distribution and routing of small-size discrete flows in a multicommodity network. Journal of Automation and Information Sciences, 47(7), 15–30. https://doi.org/10.1615/JAutomatInfScien.v47.i7.30
Vasyanin, V. A. (2015). Problem of distribution and routing of transport blocks with mixed attachments and its decomposition. Journal of Automation and Information Sciences, 47(2), 56–69. https://doi.org/10.1615/JAutomatInfScien.v47.i2.60
Trofymchuk, O. M., Vasyanin, V. A., & Kuzmenko, V. N. (2016). Complexity of one packing optimization problem. Cybernetics and Systems Analysis, 52(1), 76–84. https://doi.org/10.1007/s10559-016-9802-9
Trofymchuk, O. M., Vasyanin, V. A., & Kuzmenko, V. N. (2016). Optimization algorithms for packing of small-lot correspondence in communication networks. Cybernetics and Systems Analysis, 52(2), 258–268. https://doi.org/10.1007/s10559-016-9822-5
Trofimchuk, A. N., & Vasyanin, V. A. (2016). Computer simulation of the hierarchical structure of a communication network with discrete multicommodity flows. USiM, (2), 48–57. (In Russian). https://doi.org/10.15407/usim.2016.02.048
Vasyanin, V. A. (2016). Computer modeling of distribution and routing of discrete multicommodity flows in a communication network. USiM, (3), 43–53. (In Russian). https://doi.org/10.15407/usim.2016.03.043
Trofymchuk, O. M., & Vasyanin, V. A. (2019). Choosing the capacity of arcs with constraint on flow delay time. Cybernetics and Systems Analysis, 55(4), 561–569. https://doi.org/10.1007/s10559-019-00165-09
Trofimchuk, A. N., Vasyanin, V. A., & Ushakova, L. P. (2021). Study of the problem of optimizing the hierarchical structure of a sparse and dense communication network. Problems of Control and Informatics, (1), 5–21. (In Russian). https://doi.org/10.34229/0572-2691-2021-1-1. http://nbuv.gov.ua/UJRN/PUI_2021_1_3
Vasyanin, V. A., Trofymchuk, O. M., & Ushakova, L. P. (2022). Problem of groupage cargo routing in the multicommodity transport network with given tariffs and delivery time constraints. Cybernetics and Systems Analysis, 58, 966–976. https://doi.org/10.1007/s10559-023-00531-z. https://rdcu.be/c2Vh9
Trofymchuk, O., Vasyanin, V., Sokolov, V., Chikrii, A., & Ushakova, L. (2022). On the use of Gray codes for solving 0–1 combinatorial problems of optimization in environmental and economic systems. Cybernetics and Computer Technologies, 4, 15–32. https://doi.org/10.34229/2707-451X.22.4.2
Vasyanin, V., Trofymchuk, O., & Ushakova, L. (2023). Exact and approximate solution problem of managing the reserve of capacity of arcs a communication network. In 2023 5th International Conference on Problems of Cybernetics and Informatics (PCI) (pp. 1–5). IEEE. https://ieeexplore.ieee.org/document/10325953
Trofymchuk, O. M., & Vasyanin, V. A. (2014). A technique to solve packing problem for the management of perspective development of communication network nodes. Cybernetics and Systems Analysis, 50(4), 560–569. https://doi.org/10.1007/s10559-014-9644-2
Vasyanin, V. A., Trofymchuk, O. M., & Ushakova, L. P. (2024). A methodology of the mathematical modeling for perspective development of nodes and transport routes in the multicommodity hierarchical network. I. Optimization problems. Cybernetics and Systems Analysis, 60, 72–83. https://doi.org/10.1007/s10559-024-00648-9
Vasyanin, V. A., Trofymchuk, O. M., & Ushakova, L. P. (2024). A methodology of the mathematical modeling for perspective development of nodes and transport routes in the multicommodity hierarchical network. II. Experimental studies. Cybernetics and Systems Analysis, 60, 103–117. https://doi.org/10.1007/s10559-024-00648-9
Vasyanin, V. A., & Ushakova, L. P. (2015). Balancing the matrix of container flows in the problem of small-lot cargo transportation. Ecological Safety and Environmental Protection, 17, 98–115. (In Russian). http://nbuv.gov.ua/UJRN/ebpk_2015_1_13
Vasyanin, V. A. (2014). Reference matrix of flow merge in package optimization problems on multiproduct networks. Systematic Support and Information Technologies, 3, 42–49. (In Russian). http://dspace.nbuv.gov.ua/handle/123456789/85552
Vasyanin, V. A. (2017). Methodology for designing multicommodity communication networks with discrete flows (Doctoral thesis). Kyiv. (In Russian). https://itgip.org/wp-content/uploads/2017/03/dis_Vas.pdf
Vasyanin, V. A. (2014). A two-criterion lexicographic algorithm for finding all shortest paths in networks. Cybernetics and Systems Analysis, 50(5), 759–767. https://doi.org/10.1007/s10559-014-9666-9
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York, NY: W. H. Freeman & Co.
Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Great Britain: Wiley.
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin Heidelberg: Springer-Verlag. https://doi.org/10.1007/978-3-540-24777-7
Vasyanin, V., & Trofymchuk, O. (2024). Conceptual bases for managing the processing and distribution of discrete flows in a multicommodity communication network. Problems of Control and Informatics, 1, 5–21. https://doi.org/10.34229/0572-2691-2021-1-1
Trofymchuk, O. M., Vasyanin, V. A., & Ushakova, L. P. (2016, July 20). Computer program for optimizing the hierarchical structure of a multi-product communication network with discrete flows [Certificate of copyright registration No. 66791]. State Intellectual Property Service of Ukraine. https://itgip.org/wp-content/uploads/2017/03/dis_Vas.pdf
Vasyanin, V. A. (2016, July 20). Computer program for optimization of distribution and routing of discrete flows in a multi-product communication network [Certificate of copyright registration No. 66794]. State Intellectual Property Service of Ukraine.
Trofimchuk, A. N., & Vasyanin, V. A. (2015). Operation time of the Kraskala algorithm with a tree and list structure of data. Systematic Support and Information Technologies, 3, 48–61. (In Russian). http://dspace.nbuv.gov.ua/bitstream/handle/123456789/123488/05-Trofimchuk.pdf?sequence=1
Vasyanin, V. A., Trofymchuk, O. M., & Ushakova, L. P. (2022). Problem of building ring routes of vehicles in a multi-product hierarchical network. Problems of Control and Informatics, 67(3), 37–55. (In Ukrainian). https://journals.indexcopernicus.com/search/article?articleId=3664741
Vasyanin, V., & Ushakova, L. (2024). Mathematical models of the problem of constructing delivery routes of cargo in the internal zones of trunk nodes of a hierarchical transport network. Cybernetics and Computer Technologies, 2, 15–32. https://doi.org/10.34229/2707-451X.22.4.2
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Oleksandr Trofymchuk, Volodymyr Vasyanin
This work is licensed under a Creative Commons Attribution 4.0 International License.
The journal «Environmental safety and natural resources» works under Creative Commons Attribution 4.0 International (CC BY 4.0).
The licensing policy is compatible with the overwhelming majority of open access and archiving policies.
