КіСА | Зміст

Том 61 >>> № 2 БЕРЕЗЕНЬ — КВІТЕНЬ 2025

-->

УДК 519.168; 519.854.3

В.О. ВАСЯНІН
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна, archukr@meta.ua

О.М. ТРОФИМЧУК
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна, itgis@nas.gov.ua

Л.П. УШАКОВА
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна, archukr@ukr.net

МЕТОДОЛОГІЯ МАТЕМАТИЧНОГО МОДЕЛЮВАННЯ
ПЕРСПЕКТИВНОГО РОЗВИТКУ ВУЗЛІВ І ТРАНСПОРТНИХ
МАРШРУТІВ У БАГАТОПРОДУКТОВІЙ ІЄРАРХІЧНІЙ МЕРЕЖІ.
ІІ. ЕКСПЕРИМЕНТАЛЬНІ ДОСЛІДЖЕННЯ

Анотація. Ця стаття є другою частиною роботи, в якій запропоновано методологію математичного моделювання поетапного розвитку вузлів і транспортних маршрутів у ієрархічній мережі з багатопродуктовими дискретними потоками кореспонденцій. Як правило, такі мережі складаються з децентралізованої магістральної мережі та мереж у внутрішніх зонах обслуговування магістральних вузлів. У багатопродуктовій мережі кожен вузол може обмінюватися кореспонденціями (продуктами, товарами, вантажами, повідомленнями) з іншими вузлами. У магістральній мережі всі кореспонденції передають каналами зв’язку або перевозять транспортними засобами у транспортних блоках заданого розміру (ємності, обсягу). У цій частині роботи на прикладі транспортних мереж експериментально продемонстровано, що поетапне розв’язання задач оптимізації структури магістральної мережі та розподілу і марш- рутизації потоків дає змогу отримати початкові дані для побудови динамічних детермінованих і стохастичних моделей їхнього розвитку. Також показано, в який спосіб можна використати ці задачі для оперативного перерозподілу потоків у разі відмов устаткування у вузлах і на лініях зв’язку (перевищення пропускних спроможностей вузлів і каналів зв’язку, вантажопідйомності транспортних засобів тощо).

Ключові слова: багатопродуктові ієрархічні мережі, дискретні потоки, задачі комбінаторної оптимізації, математичні моделі, комп’ютерне моделювання.

повний текст

СПИСОК ЛІТЕРАТУРИ

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. Васянін В.О., Трофимчук О.М., Ушакова Л.П. Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі. Міжнародний науково-технічний журнал «Проблеми керування та інформатики». 2023. T. 67, № 3. С. 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. А. с. № 66791. Комп’ютерна програма оптимізації ієрархічної структури багатопродуктової комунікаційної мережі з дискретними потоками / О.М. Трофимчук, В.О. Васянін, Л.П. Ушакова. № 67221; заявл. 25.05.2016; опубл. 28.10.2016, бюл. № 42.

33. А. с. № 66794. Комп’ютерна програма оптимізації розподілу та маршрутизації дискретних потоків в багатопродуктової комунікаційної мережі / В.О. Васянін. № 67224; заявл. 25.05.2016; опубл. 28.10.2016, бюл. № 42.