Дослідження задачі оптимізації структури ієрархічної комунікаційної мережі при зміні її параметрів

Автор(и)

  • В.О. Васянін Доктор технічних наук, старший науковий співробітник, завідувач відділу прикладної інформатики, Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна https://orcid.org/0000-0003-4046-5243
  • О.М. Трофимчук Член-кореспондент НАН України, доктор технічних наук, професор, директор, Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна https://orcid.org/0000-0003-3358-6274
  • Л.П. Ушакова Провідний інженер відділу прикладної інформатики, Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна https://orcid.org/0000-0002-9020-1329

DOI:

https://doi.org/10.32347/2411-4049.2024.1.99-125

Ключові слова:

ієрархічні комунікаційні мережі, дискретні потоки і параметри, задачі оптимізації, комп'ютерне моделювання

Анотація

Стаття присвячена дослідженню задачі оптимізації ієрархічної структури багатопродуктової комунікаційної мережі з дискретними потоками при зміні її важливих параметрів, таких як пропускна спроможність дуг мережі у транспортних блоках та розмір транспортного блоку для перевезення дискретних вантажів або передачі даних у мережі цифрового зв’язку. У мережі виділено три рівні ієрархії – магістральний, зональний і внутрішній і чотири типи вузлів – магістральні вузли першого, другого і третього типу, що утворюють магістральний і зональний рівні мережі, і вузли четвертого типу, які підлеглі кожному магістральному вузлу і утворюють внутрішні рівні мережі. Типи вузлів відрізняються один від одного функціональними можливостями. Основним завданням дослідження є встановити, як змінюється структура магістральної мережі (кількість і розташування магістральних вузлів першого, другого і третього типу), схема обробки і розподілу потоків і техніко-економічні показники функціонування мережі для різних значень її параметрів. Наведено принципи організації сортування і розподілу потоків в трирівневій мережі і її математична модель. Сформульовано математичну модель задачі оптимізації структури магістральної мережі і схеми сортування і розподілу потоків. Алгоритми розв’язання задачі засновані на запропонованому раніше авторами дискретному аналогу методу локального спуску, коли околиці метричного простору можливих розв’язків вибираються з евристичних міркувань з урахуванням особливостей розв'язуваної задачі. Проведено комп'ютерне моделювання задачі на мережі, що містить 10 вузлів при заданій зміні обох параметрів. Моделювання проводилося на прикладі транспортної мережі перевезення вантажів за допомогою комп'ютерної програми, яка є частиною інструментальних програмних засобів інформаційно-аналітичної системи підтримки прийняття рішень (ІАС ППР), що розробляється в Інституті телекомунікацій і глобального інформаційного простору НАН України. Експериментальне дослідження розв’язання задачі показало, що структура мережі слабко залежить від зміни пропускної спроможності її дуг і розміру транспортного блоку. Запропонована комп'ютерна технологія розв'язання задачі при зміні параметрів мережі дозволяє проєктувальнику в інтерактивному режимі моделювати її різні варіанти, змінюючи топологію, ієрархічну структуру, потоки, параметри і обмеження моделі, і з множини отриманих розв’язків вибирати найкращий варіант з урахуванням обраної функції мети і прийнятих обмежень; розраховувати попередні техніко-економічні показники функціонування мережі, оцінювати вартість додаткових ресурсів і планувати величину потрібних інвестицій на модернізацію та будівництво її структурних елементів, що в кінцевому підсумку дає можливість підвищити ефективність функціонування мережі за рахунок оптимізації використання її ресурсів і зниження експлуатаційних витрат на обробку і транспортування потоків.

Посилання

Vasyanin, V.A. (2011). Models and algorithms for the distribution of discrete multicommodity flows in zonal networks of hierarchical structures. Environmental safety and natural resources: Zb. Sciences. prats, 8, 176-190 [in Russian]. http://dspace.nbuv.gov.ua/handle/123456789/58222

Vasyanin, V.A. & Trofimchuk, A.N. (2012). The problem of choosing the hierarchical structure of a multicommodity communication network with small batch discrete flows. Environmental safety and natural resources: Zb. Sciences. Prats, 10, 182-204 [in Russian]. http://dspace.nbuv.gov.ua/handle/123456789/57543

Trofimchuk, A.N. & Vasyanin, V.A. (2013). Optimization of the processing and distribution of small-lot cargo flows in a hierarchical multiproduct transport network. Sisteme de transport şi logistică: Materialele Conferinţei Internaţionale, Chişinău, 11-13 decembrie 2013 / red. resp.: Dumitru Solomon; col. red.: Dumitru Gortolomei [et al.]. Chişinău: Evrica, ATIC, (Tipogr. AŞM). 317-331. Antetit.: Academia de Transporturi, Informatică şi Comunicaţii.

Trofymchuk, O.M., Ushakova, L.P. & Vasyanin, V.A. (2014). Management and decision making in hierarchical communication networks with discrete flows. V International Conference on Optimization Methods and Applications «Optimization and applications» (OPTIMA-2014) held in Petrovac, Montenegro, September 28 - October 4, Petrovac, Montenegro: Proceedings. Moscow, Russia: ESC Dorodnicyn Computing Centre of RAS, Russia, 187-188.

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

Trofimchuk, A.N., Ushakova, L.P. & Vasyanin, V.A. (2016). Computer technology for modeling the hierarchical structure of a network with discrete flows. Modelare matematică, optimizare şi tehnologii informaţionale: Materialele Conferinţei Internaţionale, Volumul II, Chişinău, 22-25 martie 2016 / red. resp.: Dumitru Solomon; col. red.: Dumitru Lozovanu [et al.]. Chişinău: Evrica, ATIC, (Tipogr. AŞM), 2, 354-365. Antetit.: Academia de Transporturi, Informatică şi Comunicaţii.

Vasyanin, V.A., Trofimchuk, A.N. & Ushakova L.P. (2016). Economic and mathematical models of the problem of distribution of flows in a multicommodity communication network. Mathematical modeling in economics, 2, 5-21 [in Russian]. http://dspace.nbuv.gov.ua/handle/123456789/131848

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 management 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

Trofimchuk, A.N., Vasyanin, V.A. & Ushakova, L.P. (2021). Analysis of the solution of the problem of optimizing the hierarchical structure of a sparse and dense communication network. In International Scientific Conference Mathematical modeling, optimization and information technologies (7th ed., pp. 333-334). Chişinău – Kyiv – Batum [in Russian]. https://www.youtube.com/watch?v=pNLRCmVeRbI (video report).

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. Cybern Syst Anal, 58, 966–976. https://doi.org/10.1007/s10559-023-00531-z. https://rdcu.be/c2Vh9

Cohn, A., Root, S., Wang, A. & Mohr, D. (2007). Integration of the Load Matching and Routing Problem with Equipment Balancing for Small Package Carriers. University of Michigan Industrial and Operations Engineering, Technical Report number 05-04. - 2005. 31. (see also 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 multi-commodity network design problem. Computers & Operations Research, 136, 105511. https://doi.org/10.1016/j.cor.2021.105511

Alessio Trivella, Francesco Corman, David F. Koza & David Pisinger. (2021). The multi-commodity 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. Cybern. Syst. 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. Cybern. Syst. Analysis, 52(2), 258–268. https://doi.org/10.1007/s10559-016-9822-5

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

Vasyanin, V.A. (2014). Reference Matrix of Flow Merging in Packing Optimization Problems on Multicommodity Networks. System follow-up and information technologies, 3, 42-49 [in Russian]. http://dspace.nbuv.gov.ua/bitstream/handle/123456789/85552/05-Vasyanin.pdf?sequence=1

Vasyanin, V.A. & Trofimchuk, A.N. (2010). Automation of decision-making processes in multi-product communication networks with small batch discrete flows. Environmental safety and natural resources: Zb. Sciences. prats, 5, 172-213 [in Russian]. http://dspace.nbuv.gov.ua/handle/123456789/19407

Trofimchuk, A.N. & Vasyanin, V.A. (2015). Information technologies for decision support in communication networks with discrete flows. In 14 International scientific and practical conference "Modern information technologies for the management of environmental safety, environmental protection, visits in extreme situations" (pp. 64-70). Kyiv [in Russian].

Certificate of copyright registration for the work "Computer program for optimizing the hierarchical structure of a multi-product communication network with discrete flows". Applicant and owner O.M. Trofymchuk, V.O. Vasyanin, L.P. Ushakova; A. p. dated 07/20/2016 No. 66791, State Intellectual Property Service of Ukraine; application dated 05/25/2016 No. 67221 on registration of copyright to the work.

Vasyanin, V.A. & Ushakova, L.P. (2015). Balancing the matrix of container flows in the problem of small-lot cargo transportation. Environmental safety and natural resources: Zb. Sciences. prats, 17, 98-115 [in Russian]. http://nbuv.gov.ua/UJRN/ebpk_2015_1_13

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

##submission.downloads##

Опубліковано

2024-03-29

Як цитувати

Васянін, В., Трофимчук, О., & Ушакова, Л. (2024). Дослідження задачі оптимізації структури ієрархічної комунікаційної мережі при зміні її параметрів. Екологічна безпека та природокористування, 49(1), 99–125. https://doi.org/10.32347/2411-4049.2024.1.99-125

Номер

Розділ

Інформаційні технології та математичне моделювання