A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network
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 str...
Збережено в:
| Дата: | 2025 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Kyiv National University of Construction and Architecture
2025
|
| Теми: | |
| Онлайн доступ: | https://es-journal.in.ua/article/view/343553 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Environmental safety and natural resources |
Репозитарії
Environmental safety and natural resources| id |
es-journalinua-article-343553 |
|---|---|
| record_format |
ojs |
| institution |
Environmental safety and natural resources |
| baseUrl_str |
|
| datestamp_date |
2025-11-17T08:22:59Z |
| collection |
OJS |
| language |
English |
| topic |
multicommodity hierarchical networks discrete flows problems of combinatorial optimization mathematical models computer modeling |
| spellingShingle |
multicommodity hierarchical networks discrete flows problems of combinatorial optimization mathematical models computer modeling Trofymchuk, Oleksandr Vasyanin, Volodymyr A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| topic_facet |
багатопродуктові ієрархічні мережі дискретні потоки задачі комбінаторної оптимізації математичні моделі комп’ютерне моделювання multicommodity hierarchical networks discrete flows problems of combinatorial optimization mathematical models computer modeling |
| format |
Article |
| author |
Trofymchuk, Oleksandr Vasyanin, Volodymyr |
| author_facet |
Trofymchuk, Oleksandr Vasyanin, Volodymyr |
| author_sort |
Trofymchuk, Oleksandr |
| title |
A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| title_short |
A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| title_full |
A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| title_fullStr |
A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| title_full_unstemmed |
A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| title_sort |
two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| title_alt |
A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network |
| description |
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. |
| publisher |
Kyiv National University of Construction and Architecture |
| publishDate |
2025 |
| url |
https://es-journal.in.ua/article/view/343553 |
| work_keys_str_mv |
AT trofymchukoleksandr atwostepproblemofoptimizingthestructureandroutingofflowsinahierarchicalmulticommoditynetwork AT vasyaninvolodymyr atwostepproblemofoptimizingthestructureandroutingofflowsinahierarchicalmulticommoditynetwork AT trofymchukoleksandr twostepproblemofoptimizingthestructureandroutingofflowsinahierarchicalmulticommoditynetwork AT vasyaninvolodymyr twostepproblemofoptimizingthestructureandroutingofflowsinahierarchicalmulticommoditynetwork |
| first_indexed |
2025-11-16T02:11:42Z |
| last_indexed |
2025-11-18T02:18:16Z |
| _version_ |
1849545236690239488 |
| spelling |
es-journalinua-article-3435532025-11-17T08:22:59Z A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network Trofymchuk, Oleksandr Vasyanin, Volodymyr багатопродуктові ієрархічні мережі дискретні потоки задачі комбінаторної оптимізації математичні моделі комп’ютерне моделювання multicommodity hierarchical networks discrete flows problems of combinatorial optimization mathematical models computer modeling 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. У роботі розглядається методологія математичного моделювання двоетапної задачі оптимізації магістральної ієрархічної комунікаційної мережі з багатопродуктовими дискретними потоками і параметрами. Методологія заснована на послідовному розв’язанні задачі оптимізації структури мережі і задачі розподілу і маршрутизації потоків дискретних кореспонденцій. Як правило, такі мережі складаються з децентралізованої магістральної мережі та фрагментарних мереж у внутрішніх зонах обслуговування магістральних вузлів. Визначається чотири типи вузлів мережі і три рівні її ієрархії. У багатопродуктовій мережі кожен вузол може обмінюватися кореспонденціями (продуктами, товарами, вантажами, повідомленнями) з іншими вузлами. Кореспонденція характеризується вузлом-джерелом, вузлом-стоком та величиною, яка для транспортних мереж задається кількістю тарно-штучних вантажів в упаковці уніфікованого розміру, а для мереж передачі даних – кількістю байт, кілобайт і т.п. У транспортній магістральній мережі всі кореспонденції спочатку сортуються за адресами призначення, пакуються у транспортні блоки (контейнери), а потім транспортуються у транспортних засобах по транспортних магістралях. У мережах передачі даних кореспонденції також сортуються за адресами призначення (мультиплексуються), пакуються у віртуальні транспортні блоки, а потім передаються по магістральних каналах зв’язку. Розмір (ємність, обсяг) транспортного блоку задається параметром і визначається кількістю одиниць кореспонденцій, що у нього вміщуються. Наведено математичні моделі задач оптимізації структури мережі, розподілу і маршрутизації потоків та приклад числового моделювання розв’язання задач на транспортній мережі, що містить 120 вузлів і 300 неорієнтованих дуг. Експериментальні дослідження показали високу обчислювальну ефективність запропонованих алгоритмів і програм. Вони можуть бути рекомендовані для практичного вирішення задач оптимізації процесів обробки і транспортування потоків у комунікаційних мережах великої розмірності. Kyiv National University of Construction and Architecture 2025-09-30 Article Article application/pdf https://es-journal.in.ua/article/view/343553 10.32347/2411-4049.2025.3.8-32 Environmental safety and natural resources; Vol. 55 No. 3 (2025): Environmental safety and natural resources; 8-32 Екологічна безпека та природокористування; Том 55 № 3 (2025): Екологічна безпека та природокористування; 8-32 2616-2121 2411-4049 10.32347/2411-4049.2025.3 en https://es-journal.in.ua/article/view/343553/331378 Copyright (c) 2025 Oleksandr Trofymchuk, Volodymyr Vasyanin http://creativecommons.org/licenses/by/4.0 |