Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
KIBERNETYKA TA SYSTEMNYI ANALIZ
International Theoretical Science Journal
-->


DOI 10.34229/KCA2522-9664.25.2.8
UDC 519.168; 519.854.3
V.A. Vasyanin1, O.M. Trofymchuk2, L.P. Ushakova3


1 Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine

archukr@meta.ua

2 Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine

itgis@nas.gov.ua

3 Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine

archukr@ukr.net

METHODOLOGY OF MATHEMATICAL MODELING FOR PERSPECTIVE DEVELOPMENT
OF NODES AND TRANSPORT ROUTES IN A MULTICOMMODITY HIERARCHICAL
NETWORK. II. EXPERIMENTAL RESEARCH

Abstract. This article is the second part of the work, which proposes a methodology for mathematical modeling of the step-by-step development of nodes and transport routes in a hierarchical network with multicommodity discrete correspondence flows. As a rule, such networks consist of a decentralized trunk network and networks in the internal service areas of trunk nodes. In a multicommodity network, each node can exchange correspondence (products, goods, cargo, messages) with other nodes. In the trunk network, all correspondence is transmitted via communication channels or transported in vehicles in transport blocks of a given size (capacity, volume). In this part of the work, using the example of transport networks, it is experimentally shown that the step-by-step solution of the problems of optimizing the structure of the trunk network and the distribution and routing of flows allows obtaining initial data for building dynamic deterministic and stochastic models of their development. It is also shown how these tasks can be used for operational redistribution of flows in case of equipment failures in nodes and on communication lines (exceeding the throughput capacities of nodes and communication channels, the carrying capacity of vehicles, etc.).

Keywords: multicommodity hierarchical networks, discrete flows, combinatorial optimization problems, mathematical models, computer modeling.


full text

REFERENCES

  • 1. Vasyanin V.A., Trofymchuk O.M., Ushakova L.P. 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. 2024. Vol. 60, N 1. P. 72–83. https://doi.org/10.1007/ .

  • 2. Nagy G., Salhi S. Location-routing: Issues, models and methods. European Journal of Operational Research. 2007. Vol. 177, Iss. 2. P. 649–672. https://doi.org/10.1016/ .

  • 3. Prodhon C., Prins C. A survey of recent research on location-routing problems. European Journal of Operational Research. 2014. Vol. 238, Iss. 1. P. 1–17. https://doi.org/10.1016/ .

  • 4. Cuda R., Guastaroba G., Speranza M.G. A survey on two-echelon routing problems. Computers & Operations Research. 2015. Vol. 55. P. 185–199. https://doi.org/10.1016/ .

  • 5. Drexl M., Schneider M. A survey of variants and extensions of the location-routing problem. European Journal of Operational Research. 2015. Vol. 241, Iss. 2. P. 283–308. https://doi.org/10.1016/ .

  • 6. Guastaroba G., Speranza M.G., Vigo D. Intermediate facilities in freight transportation planning: A survey. Transportation Science. 2016. Vol. 50, N 3. P. 763–789. https://doi.org/10.1287/ .

  • 7. Schneider M., Drexl M. A survey of the standard location-routing problem. Annals of Operations Research. 2017. Vol. 259, Iss. 1–2. P. 389–414. https://doi.org/10.1007/ .

  • 8. Mirhedayatian S., Crainic T., Guajardo M., Wallace S. A two-echelon location-routing problem with synchronisation. Journal of the Operational Research Society. 2019. Vol. 72, Iss. 1. P. 145–160. https://doi.org/10.1080/ .

  • 9. Rodrigue J.-P. The distribution network of Amazon and the footprint of freight digitalization. Journal of Transport Geography. 2020. Vol. 88. Article number 102825. https://doi.org/10.1016/ .

  • 10. Mara S.T.W., Kuo R.J., Asih A.M.S. Location-routing problem: a classification of recent research. International Transactions in Operational Research. 2021. Vol. 28, Iss. 6. P. 2941–2983. https://doi.org/10.1111/ .

  • 11. Sluijk N., Florio A.M., Kinable J., Dellaert N., Woensel T.V. Two-echelon vehicle routing problems: A literature review. European Journal of Operational Research. 2023. Vol. 304, Iss. 3. P. 865–886. https://doi.org/10.1016/ .

  • 12. Hamidi M., Farahmand K., Sajjadi S., Nygard K. A heuristic algorithm for a multiproduct four-layer capacitated location-routing problem. International Journal of Industrial Engineering Computations. 2014. N 5. P. 87–100. https://doi.org/10.5267/ .

  • 13. Janjevic M., Winkenbach M., Merchan D. Integrating collection-and-delivery points in the stra-tegic design of urban last-mile e-commerce distribution networks. Transportation Research. Part E. 2019. Vol. 131. P. 37–67. https://doi.org/10.1016/ .

  • 14. Boccia M., Crainic T., Sforza A., Sterle C. Multi-commodity location-routing: Flow intercepting formulation and branch-and-cut algorithm. Computers and Operations Research. 2018. Vol. 89. P. 94–112. https://doi.org/10.1016/ .

  • 15. Ahmed S. A three echelon location routing problem with multiple commodities and courier delivery. A thesis for the degree of master of applied science (industrial engineering). Concordia University MontrБal, QuБbec, Canada 2021. https://spectrum.library.concordia.ca/ .

  • 16. Dellaert N., Woensel T.V., Crainic T.G., Saridarq F.D. A multi-commodity two-echelon capacitated vehicle routing problem with time windows: Model formulations and solution approach. Computers & Operations Research. 2021. Vol. 127. Article number 105154. https://doi.org/10.1016/ .

  • 17. Gu W., Archetti C., Cattaruzza D., Ogier M., Semet F., Speranza M. A sequential approach for a multi-commodity two-echelon distribution problem. Computers & Industrial Engineering. 2022. Vol. 163. P. 107793. hal-03167379, version 1. https://hal.archives-ouvertes.fr/ .

  • 18. Jia S., Deng L., Zhao Q., Chen Y. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. JIMO. 2022. Vol. 19, Iss. 2. P. 1187–1210. https://doi.org/10.3934/ .

  • 19. Barnhart C., Hane C.A., Vance P.H. Integer multicommodity flow problems. In: Network Optimization. Pardalos P.M., Hearn D.W., Hager W.W. (Eds.). Lecture Notes in Economics and Mathematical Systems. Berlin; Heidelberg: Springer, 1997. Vol. 450. P. 17–31. https://doi.org/10.1007/ .

  • 20. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research. 2000. Vol. 48, N. 2. P. 318–326. https://doi.org/10.1287/ .

  • 21. Encyclopedia of optimization. Second ed. Floudas C.A., Pardalos P.M. (Eds.). New York: Springer, 2009. 4626 p.

  • 22. Wang I-L. Multicommodity network flows: A survey, part I: Applications and formulations. International Journal of Operations Research. 2018. Vol. 15, N. 4. P. 145–153. https://doi.org/10.6886 .

  • 23. Wang I-L. Multicommodity network flows: A survey, part II: Solution methods. International Journal of Operations Research. 2018. Vol. 15, N. 4. P. 155–173. https://doi.org/10.6886/ .

  • 24. Cohn A., Root S., Wang A., Mohr D. Integration of the load-matching and routing problem with equipment balancing for small package carriers. Transportation Science. 2007. Vol. 41, N 2. P. 238–252. https://doi.org/10.1287/ .

  • 25. Hellsten E., Koza D.F., Contreras I., Cordeau J.F., Pisinger D. The transit time constrained fixed charge multi-commodity network design problem. Computers & Operations Research. 2021. Vol. 136. Article number 105511. https://doi.org/10.1016/ .

  • 26. Trivella A., Corman F., Koza D.F., Pisinger D. The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping. Transportation Research Part E: Logistics and Transportation Review. 2021. Vol. 150. Article number 102342. https://doi.org/10.1016/ .

  • 27. Vasyanin V.O., Trofymchuk O.M., Ushakova L.P. Problems of constructing circular routes of vehicles in a multi-product hierarchical network. International scientific and technical journal "Problems of control and computer science". 2023. Vol. 67, N 3. P. 37–55. https://doi.org/10.34229/ .

  • 28. 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. Vol. 47, Iss. 7. P. 15–30. https://doi.org/10.1615/ .

  • 29. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Complexity of one packing optimization problem. Cybernetics and Systems Analysis. 2016. Vol. 52, N 1. P. 76–84. https://doi.org/10.1007/ .

  • 30. 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. Vol. 52, N 2. P. 258–268. https://doi.org/10.1007/ .

  • 31. 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, Iss. 2. P. 56–69. https://doi.org/10.1615/ .

  • 32. A. p. № 66791. Computer program for optimizing the hierarchical structure of a multi-product communication network with discrete flows / O.M. Trofymchuk, V.O. Vasyanin, L.P. Ushakova. № 67221; appl. 25.05.2016; publ. 28.10.2016, bull. N 42.

  • 33. A. p. № 66794. Computer program for optimizing the distribution and routing of discrete flows in a multi-product communication network / V.O. Vasyanin. № 67224; appl. 25.05.2016; publ. 28.10.2016, bull. N 42.




© 2025 Kibernetika.org. All rights reserved.