Укр
Eng
Журнал
Автору

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

УДК 004.942

Volume 66, Issue 1, 2021, pages 5-21

DOI: https://doi.org/10.34229/0572-2691-2021-1-1

Завантажити статтю

Трофимчук Олександр Миколайович, член-кореспондент НАН України, доктор технічних наук, професор, директор Інституту телекомунікацій і глобального інформаційного простору НАН України, м. Київ

Ушакова Людмила Павлівна, провідний інженер Институту телекомунікацій і глобального інформаційного простору НАН України, м. Київ

Васянін Володимир Олександрович, доктор технічних наук, старший науковий співробітник, провідний науковий співробітник Інституту телекомунікацій і глобального інформаційного простору НАН України, м. Київ

ABSTRACT

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

REFERENCES

  1. Васянин В.А., Трофимчук А.Н. Автоматизация процессов принятия решений в многопродуктовых коммуникационных сетях с мелкопартионными дискретными потоками. Екологічна безпека та природокористування: зб. наук. праць. Київ : ТОВ «Видавництво «Юстон», 2010. Вип. 5. С. 172–213. http://dspace.nbuv.gov.ua/handle/123456789/19407.
  2. Trofymchuk A.N., Ushakova L.P., Vasyanin V.A. 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, 2014. Montenegro : Petrovac. Proceedings. Russia : Moscow. ESC Dorodnicyn Computing Centre of RAS, Russia, 2014. P. 187–188.
  3. Трофимчук А.Н., Васянин В.А. Информационные технологии поддержки принятия решений в коммуникационных сетях с дискретными потоками. 14 Міжнародна науково-прак­тична конференція «Сучасні інформаційні технології управління екологічною безпекою, природокористуванням, заходами в надзвичайних ситуаціях». Київ : МП «Леся», 2015. С. 64–70.
  4. Трофимчук А.Н., Васянин В.А., Ушакова Л.П. Концептуальные основы взаимодействия задач текущего планирования и оперативного управления в иерархических коммуникационных сетях. Інформаційні технології управління екологічною безпекою, природокористуванням, заходами в надзвичайних ситуаціях: Колективна монографія за матеріалами XVII Міжнародної науково-практичної конференції. Київ, 25–26 вересня 2018. За заг. ред. С.О. Довгого. Київ : ТОВ «Видавництво «Юстон», 2018. С. 95–99.
  5. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Complexity of one packing optimization problem. Cybernetics and Systems Analysis. 2016. 52(1). P. 76–84. DOI: 10.1007/s10559-016-9802-9.
  6. 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. DOI: 10.1007/s10559-016-9822-5.
  7. Васянин В.А. Модели и алгоритмы распределения дискретных многопродуктовых потоков в зональных сетях иерархических структур. Екологічна безпека та природокористування: зб. наук. праць. Київ : ТОВ «Видавництво «Юстон», 2011. Вип. 8. С. 176–190. http://dspace.­nbuv.gov.ua/handle/123456789/58222.
  8. 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. DOI: 10.1615/JAutomatInfScien.v47.i7.30.
  9. Vasyanin V.A. Problem of distribution and routing of transport blocks with mixed attachments and its decomposition. Journal of Automation and Information Sciences. 2015. 47(2). P. 56–69. DOI: 1615/JAutomatInfScien.v47.i2.60.
  10. Васянин В.А., Трофимчук А.Н. Задача выбора иерархической структуры многопродуктовой коммуникационной сети с мелкопартионными дискретными потоками. Екологічна безпека та природокористування: зб. наук. праць. Київ : ТОВ «Видавництво «Юстон», 2012. Вип. 10. С. 182–204. http://dspace.nbuv.gov.ua/handle/123456789/57543.
  11. Трофимчук А.Н., Ушакова Л.П., Васянин В.А. Компьютерная технология моделирования иерархической структуры сети с дискретными потоками. Modelare matematică, optimizare şi tehnologii informaţionale: Materialele Conferinţei Internaţionale, Volumul II, Chişinău, 22-25 mar­tie 2016 / red. resp.: Dumitru Solomon; col. red.: Dumitru Lozovanu [et al.]. Chişinău: Evrica, ATIC, 2016 (Tipogr. AŞM). 2. P. 354–365. Antetit. : Academia de Transporturi, Informatică şi Comunicaţii.
  12. 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. DOI: 10.1007/s10559-014-9666-9.
  13. Трофимчук А.Н., Васянин В.А. Компьютерное моделирование иерархической структуры коммуникационной сети с дискретными многопродуктовыми потоками. Управляющие системы и машины. 2016. № 2. С. 48–57. DOI: https://doi.org/10.15407/usim.2016.02.048.
  14. Свідоцтво про реєстрацію авторського права на твір «Компʼютерна програма оптимізації ієрархічної структури багатопродуктової комунікаційної мережі з дискретними потоками» / заявник і власник О.М. Трофимчук, В.О. Васянін, Л.П. Ушакова; А.с. від 20.07.2016 № 66791, Державна служба інтелектуальної власності України; заявка від 25.05.2016 № 67221 про реєстрацію авторського права на твір.