The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network
The article is devoted to the study of the subproblem of distribution and merging of correspondence flows in separate zones of the backbone network, which arises when solving the general problem of optimizing the hierarchical structure of a multicommodity communication network with discrete flows an...
Saved in:
| Date: | 2024 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
PROBLEMS IN PROGRAMMING
2024
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/619 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-619 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/4f/9120ddc3a27e73b368d4951333d9c64f.pdf |
| spelling |
pp_isofts_kiev_ua-article-6192025-02-14T11:05:48Z The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network Задача розподілу і об'єднання дискретних потоків кореспонденцій в окремих зонах ієрархічної комунікаційної мережі Vasyanin, V.O. hierarchical communication networks; discrete flows and parameters; optimization problems; computer modelin UDC 519.168; 519.854.3 ієрархічні комунікаційні мережі; дискретні потоки і параметри; задачі оптимізації; комп'ютерне моделювання УДК 519.168; 519.854.3 The article is devoted to the study of the subproblem of distribution and merging of correspondence flows in separate zones of the backbone network, which arises when solving the general problem of optimizing the hierarchical structure of a multicommodity communication network with discrete flows and parameters. 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 in a package of a unified size, and for data transmission networks – by the number of bytes, kilobytes, etc. In the backbone network, all correspondence is transported in vehicles in transport units of a given size (capacity, volume) or transmitted via communication channels. The size of a transport block is measured by the number of units of correspondence that fit into it (for example, 40 packaged goods, 100 gigabytes). All trunk nodes are sorting centers in which correspondence is first sorted by destination addresses (nodes) and then packed as consolidated correspondence into transport blocks. Since the size of individual correspondence is much smaller than the size of the transport block, they can be combined (packed) with correspondence with other destination addresses several times and in different nodes during sorting. There are three levels of hierarchy in the network – backbone, zonal and internal and four types of nodes – trunk nodes of the first, second and third types, forming the backbone and zonal levels of the network and nodes of the fourth type, which are subordinate to each trunk node and form internal levels of the network. Node types differ from each other in functionality. The main task of the study is to develop a mathematical model and algorithms for solving the subproblem of optimizing the distribution and merging (sorting) of correspondence flows at the zonal levels of the network. It is shown that it can be formulated as a linear programming problem with a block structure of constraints and the Danzig-Wolf decomposition method and other methods of integer programming can be used to solve it. To solve the problem on real networks, approximate algorithms based on the construction of the shortest paths are proposed.Prombles in programming 2024; 2-3: 53-61 Стаття присвячена дослідженню підзадачі розподілу і об'єднання потоків кореспонденцій в окремих зонах магістральної мережі, яка виникає під час розв’язання загальної задачі оптимізації ієрархічної структури багатопродуктової комунікаційної мережі з дискретними потоками і параметрами. У багатопродуктовій мережі кожен вузол може обмінюватися кореспонденціями (продуктами, товарами, вантажами, повідомленнями) з іншими вузлами. Кореспонденція характеризується вузлом-джерелом, вузлом-стоком та величиною, яка для транспортних мереж задається кількістю тарно-штучних вантажів в упаковці уніфікованого розміру, а для мереж передачі даних – кількістю байт, кілобайт і т.п. У магістральній мережі всі кореспонденції транспортуються у транспортних засобах у транспортних блоках заданого розміру (ємності, обсягу), або передаються каналами зв’язку. Розмір транспортного блоку вимірюється кількістю одиниць кореспонденцій, що вміщуються в нього (наприклад, 40 тарноштучних вантажів, 100 гігабайт). Усі магістральні вузли є сортувальними центрами, в яких кореспонденції спочатку сортуються за адресами (вузлами) призначення, а потім пакуються як збірні кореспонденції в транспортні блоки. Оскільки величина окремих кореспонденцій значно менша за розмір транспортного блоку, вони у процесі сортування можуть кілька разів і в різних вузлах об'єднуватися (упаковуватися) з кореспонденціями, що мають інші адреси призначення. У мережі виділено три рівня ієрархії – магістральний, зональний і внутрішній та чотири типи вузлів – магістральні вузли першого, другого і третього типу, що утворюють магістральний і зональний рівні мережі і вузли четвертого типу, підлеглі кожному магістральному вузлу і утворюють внутрішні рівні мережі. Типи вузлів відрізняються один від одного функціональними можливостями. Основним завданням дослідження є розробка математичної моделі і алгоритмів вирішення підзадачі оптимізації розподілу і об'єднанню (сортуванню) потоків кореспонденцій на зональних рівнях мережі. Показано, що вона може бути сформульована як задача лінійного програмування з блоковою структурою обмежень і для її вирішення може бути застосовано метод декомпозиції Данцига-Вулфа й інші методи цілочислового програмування. Для вирішення задачі на реальних мережах запропоновані наближені алгоритми, що базуються на побудові найкоротших шляхів.Prombles in programming 2024; 2-3: 53-61 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/619 10.15407/pp2024.02-03.053 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 53-61 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 53-61 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 53-61 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/619/671 Copyright (c) 2024 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-02-14T11:05:48Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
hierarchical communication networks discrete flows and parameters optimization problems computer modelin UDC 519.168 519.854.3 |
| spellingShingle |
hierarchical communication networks discrete flows and parameters optimization problems computer modelin UDC 519.168 519.854.3 Vasyanin, V.O. The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| topic_facet |
hierarchical communication networks discrete flows and parameters optimization problems computer modelin UDC 519.168 519.854.3 ієрархічні комунікаційні мережі дискретні потоки і параметри задачі оптимізації комп'ютерне моделювання УДК 519.168 519.854.3 |
| format |
Article |
| author |
Vasyanin, V.O. |
| author_facet |
Vasyanin, V.O. |
| author_sort |
Vasyanin, V.O. |
| title |
The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| title_short |
The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| title_full |
The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| title_fullStr |
The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| title_full_unstemmed |
The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| title_sort |
problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network |
| title_alt |
Задача розподілу і об'єднання дискретних потоків кореспонденцій в окремих зонах ієрархічної комунікаційної мережі |
| description |
The article is devoted to the study of the subproblem of distribution and merging of correspondence flows in separate zones of the backbone network, which arises when solving the general problem of optimizing the hierarchical structure of a multicommodity communication network with discrete flows and parameters. 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 in a package of a unified size, and for data transmission networks – by the number of bytes, kilobytes, etc. In the backbone network, all correspondence is transported in vehicles in transport units of a given size (capacity, volume) or transmitted via communication channels. The size of a transport block is measured by the number of units of correspondence that fit into it (for example, 40 packaged goods, 100 gigabytes). All trunk nodes are sorting centers in which correspondence is first sorted by destination addresses (nodes) and then packed as consolidated correspondence into transport blocks. Since the size of individual correspondence is much smaller than the size of the transport block, they can be combined (packed) with correspondence with other destination addresses several times and in different nodes during sorting. There are three levels of hierarchy in the network – backbone, zonal and internal and four types of nodes – trunk nodes of the first, second and third types, forming the backbone and zonal levels of the network and nodes of the fourth type, which are subordinate to each trunk node and form internal levels of the network. Node types differ from each other in functionality. The main task of the study is to develop a mathematical model and algorithms for solving the subproblem of optimizing the distribution and merging (sorting) of correspondence flows at the zonal levels of the network. It is shown that it can be formulated as a linear programming problem with a block structure of constraints and the Danzig-Wolf decomposition method and other methods of integer programming can be used to solve it. To solve the problem on real networks, approximate algorithms based on the construction of the shortest paths are proposed.Prombles in programming 2024; 2-3: 53-61 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2024 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/619 |
| work_keys_str_mv |
AT vasyaninvo theproblemofdistributionandmergingofdiscretecorrespondenceflowsinindividualzonesofahierarchicalcommunicationnetwork AT vasyaninvo zadačarozpodíluíobêdnannâdiskretnihpotokívkorespondencíjvokremihzonahíêrarhíčnoíkomuníkacíjnoímereží AT vasyaninvo problemofdistributionandmergingofdiscretecorrespondenceflowsinindividualzonesofahierarchicalcommunicationnetwork |
| first_indexed |
2025-07-17T09:36:37Z |
| last_indexed |
2025-07-17T09:36:37Z |
| _version_ |
1850411873739997184 |
| fulltext |
Комп’ютерне моделювання
53
УДК 519.168; 519.854.3 http://doi.org/10.15407/pp2024.02-03.053
В.О. Васянін
ЗАДАЧА РОЗПОДІЛУ І ОБ'ЄДНАННЯ ДИСКРЕТНИХ
ПОТОКІВ КОРЕСПОНДЕНЦІЙ В ОКРЕМИХ ЗОНАХ
ІЄРАРХІЧНОЇ КОМУНІКАЦІЙНОЇ МЕРЕЖІ
Стаття присвячена дослідженню підзадачі розподілу і об'єднання потоків кореспонденцій в окремих
зонах магістральної мережі, яка виникає під час розв’язання загальної задачі оптимізації ієрархічної
структури багатопродуктової комунікаційної мережі з дискретними потоками і параметрами. У бага-
топродуктовій мережі кожен вузол може обмінюватися кореспонденціями (продуктами, товарами,
вантажами, повідомленнями) з іншими вузлами. Кореспонденція характеризується вузлом-джерелом,
вузлом-стоком та величиною, яка для транспортних мереж задається кількістю тарно-штучних ван-
тажів в упаковці уніфікованого розміру, а для мереж передачі даних – кількістю байт, кілобайт і т.п.
У магістральній мережі всі кореспонденції транспортуються у транспортних засобах у транспортних
блоках заданого розміру (ємності, обсягу), або передаються каналами зв’язку. Розмір транспортного
блоку вимірюється кількістю одиниць кореспонденцій, що вміщуються в нього (наприклад, 40 тарно-
штучних вантажів, 100 гігабайт). Усі магістральні вузли є сортувальними центрами, в яких кореспо-
нденції спочатку сортуються за адресами (вузлами) призначення, а потім пакуються як збірні корес-
понденції в транспортні блоки. Оскільки величина окремих кореспонденцій значно менша за розмір
транспортного блоку, вони у процесі сортування можуть кілька разів і в різних вузлах об'єднуватися
(упаковуватися) з кореспонденціями, що мають інші адреси призначення. У мережі виділено три рів-
ня ієрархії – магістральний, зональний і внутрішній та чотири типи вузлів – магістральні вузли пер-
шого, другого і третього типу, що утворюють магістральний і зональний рівні мережі і вузли четвер-
того типу, підлеглі кожному магістральному вузлу і утворюють внутрішні рівні мережі. Типи вузлів
відрізняються один від одного функціональними можливостями. Основним завданням дослідження є
розробка математичної моделі і алгоритмів вирішення підзадачі оптимізації розподілу і об'єднанню
(сортуванню) потоків кореспонденцій на зональних рівнях мережі. Показано, що вона може бути
сформульована як задача лінійного програмування з блоковою структурою обмежень і для її вирі-
шення може бути застосовано метод декомпозиції Данцига-Вулфа й інші методи цілочислового про-
грамування. Для вирішення задачі на реальних мережах запропоновані наближені алгоритми, що ба-
зуються на побудові найкоротших шляхів.
Ключові слова: ієрархічні комунікаційні мережі, дискретні потоки і параметри, задачі оптимізації,
комп'ютерне моделювання
V. Vasyanin
THE PROBLEM OF DISTRIBUTION AND MERGING
OF DISCRETE CORRESPONDENCE FLOWS IN INDIVIDUAL
ZONES OF A HIERARCHICAL COMMUNICATION NETWORK
The article is devoted to the study of the subproblem of distribution and merging of correspondence flows
in separate zones of the backbone network, which arises when solving the general problem of opt imizing the
hierarchical structure of a multicommodity communication network with discrete flows and parameters. 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 in a package of a unified size, and for data transmission
networks – by the number of bytes, kilobytes, etc. In the backbone network, all correspondence is transport-
ed in vehicles in transport units of a given size (capacity, volume) or transmitted via communication chan-
nels. The size of a transport block is measured by the number of units of correspondence that fit into it (for
example, 40 packaged goods, 100 gigabytes). All trunk nodes are sorting centers in which correspondence is
first sorted by destination addresses (nodes) and then packed as consolidated correspondence into transport
blocks. Since the size of individual correspondence is much smaller than the size of the transport block, they
can be combined (packed) with correspondence with other destination addresses several times and in differ-
ent nodes during sorting. There are three levels of hierarchy in the network – backbone,zonal and internal
© В.О.Васянін, 2024
ISSN 1727-4907. Проблеми програмування. 2024. №2-3
Комп’ютерне моделювання
54
and four types of nodes – trunk nodes of the first, second and third types, forming the backbone and zonal
levels of the network and nodes of the fourth type, which are subordinate to each trunk node and form inter-
nal levels of the network. Node types differ from each other in functionality.
The main task of the study is to develop a mathematical model and algorithms for solving the subproblem of
optimizing the distribution and merging (sorting) of correspondence flows at the zonal levels of the network.
It is shown that it can be formulated as a linear programming problem with a block structure of constraints
and the Danzig-Wolf decomposition method and other methods of integer programming can be used to solve
it. To solve the problem on real networks, approximate algorithms based on the construction of the shortest
paths are proposed.
Keywords: hierarchical communication networks, discrete flows and parameters, optimization problems, com-
puter modeling
Вступ
У більшості випадків існуючі і
проєктовані територіально-розподілені
комунікаційні мережі – транспортні, ін-
формаційно-обчислювальні, паливно-
енергетичні, поштові, телеграфні, теле-
фонні тощо. є багаторівневими і склада-
ються із децентралізованої розподіленої
мережі (магістральної) і низових фрагмен-
тарних мереж (зональних і внутрішніх) на
нижніх рівнях ієрархії. У цій роботі розг-
лядаються багатопродуктові транспортні
мережі і мережі передачі даних, для яких
характерна наявність множини джерел і
стоків потоків кореспонденцій (продуктів
або вимог). Під кореспонденцією розумі-
ється пара різних вузлів мережі, між якими
є спрямований (адресний) дискретний по-
тік елементів (наприклад, неділимих ван-
тажів уніфікованого розміру, біт або сим-
волів) заданої величини. У багатопродук-
товій мережі усі потоки кореспонденцій
підлягають одночасній передачі з джерел у
стоки. У загальному випадку на мережі
може бути задана деяка множина видів
(категорій) кореспонденцій, що відрізня-
ються вагою, габаритами і іншими харак-
теристиками, але мають загальні джерела і
стоки.
У мережі виділено три рівні ієрархії
– магістральний, зональний, внутрішній та
чотири типи вузлів – вузли першого, дру-
гого, третього та четвертого типів. Вузли
першого, другого і третього типу, що зна-
ходяться на транспортних магістралях
транспортної мережі або мережі передачі
даних, а також - з'єднують їх ділянки мар-
шрутів транспортних засобів або каналів
зв'язку, становлять магістральну мережу.
Усі магістральні вузли мають зони обслу-
говування, які утворюють зональні рівні
магістральної мережі. Вузли четвертого
типу знаходяться у внутрішній зоні обслу-
говування будь-якого магістрального вузла
і разом із ним утворюють внутрішню ме-
режу.
На рис. 1 показані фрагменти ієрар-
хічної мережі, де i , j , k – магістральні
вузли зі своїми магістральними зонами об-
слуговування (ЗОВ), m – вузли доставки
та збору кореспонденцій у внутрішній зоні
обслуговування кожного магістрального
вузла (внутрішні мережі).
Рис. 1. Фрагменти ієрархічної мережі
Магістральні вузли різного типу рі-
зняться між собою функціональними мож-
ливостями, рівнем технічної оснащеності,
кількістю обслуговуючого персоналу та ін.
Деякі з них можуть сортувати потоки до
всіх магістральних вузлів, інші – тільки до
магістральних вузлів у зоні свого обслуго-
вування. В окремих магістральних вузлах
може бути заборонено сортування транзи-
тних потоків кореспонденцій та обробка
транзитних потоків транспортних блоків.
У вузлах четвертого типу потоки не сор-
туються, а безпосередньо вирушають у
відповідний магістральний вузол.
Структура магістральної мережі
може бути відома, наприклад, спочатку
задана досвідченими диспетчерами тран-
спортної мережі, адміністраторами мере-
жі передачі даних або визначена в резуль-
Комп’ютерне моделювання
55
таті розв’язання задачі вибору структури
мережі.
У [1] розглядається узагальнена за-
дача упаковки та розподілу потоків корес-
понденцій в ієрархічній мережі,
розв’язання якої здійснюється в кілька
етапів. На першому етапі розв’язується за-
дача вибору ієрархічної структури магіс-
тральної мережі та схеми сортування коре-
спонденцій у вузлах мережі та пакування
їх у транспортні блоки [2]. На другому
етапі постає задача розподілу та маршру-
тизації потоків транспортних блоків зі збі-
рними кореспонденціями, які були сфор-
мовані у процесі розв’язання першої задачі
[3]. Під збірними кореспонденціями розу-
міються об'єднані в один транспортний
блок тарно-штучні вантажі або повідом-
лення (потоки даних) з різними адресами
призначення, які можуть не збігатися з ад-
ресою призначення транспортного блоку.
Збірні кореспонденції утворюються для
концентрації потоків у вузлах і ділянках
маршрутів і максимального скорочення кі-
лькості транспортних блоків, необхідних
для їх упаковки та транспортування або
передачі у магістральній мережі.
Розв’язання задачі оптимізації струк-
тури мережі дає можливість отримати
схему сортування потоків у вузлах мережі
і витрати на їх сортування, а також витра-
ти на навантаження-розвантаження вихід-
них і вхідних транспортних блоків.
У задачі вибору ієрархічної струк-
тури магістральної мережі виникає підза-
дача розподілу і об'єднання потоків корес-
понденцій із вузлів другого і третього типу
в зональних мережах. Згідно з принципами
зонально-вузлового сортування вихідні
потоки кореспонденцій з вузлів другого і
третього типу розсортовуються у вузли
першого типу, що лежать на межі зон їх
обслуговування. Аналогічно у відповідних
вузлах першого типу обробляються і пото-
ки, що входять у вузли другого і третього
типу, які надходять від вузлів з інших зон
обслуговування.
У статті розглядається математична
модель підзадачі розподілу і об'єднання
потоків кореспонденцій із вузлів другого і
третього типу в зональних мережах і алго-
ритми її вирішення. Показано, що структу-
рні особливості такої підзадачі дозволяють
використати для ії вирішення метод деко-
мпозиції Данцига-Вулфа [4] і отримати
нижні оцінки розв’язку. Враховуючи, що
реальні мережеві структури завжди функ-
ціонують в умовах невизначеності, дії ви-
падкових чинників, дефіциту ресурсів, що
динамічно змінюються з часом, а також за
недостатньо точної початкової інформації,
для практичного вирішення поставленої
підзадачі запропоновані наближені алго-
ритми, що ґрунтуються на методах побу-
дови найкоротших шляхів.
1. Постановка задачі
Нехай ( , )G N P – ієрархічна магіст-
ральна мережа з множиною неорієнтова-
них топологічних дуг P , p P= , множи-
ною вузлів N , n N= і
1 2 3N N N N= , де 1 2 3, ,N N N – множини
вузлів першого, другого і третього типу
відповідно. Під топологічною дугою розу-
міється фізичний відрізок лінії зв'язку, що
сполучає два будь-які вузли з множини N
так, що між даними вузлами на цьому від-
різку немає більше жодного вузла з N .
Вузли мережі відповідають пунктам відп-
равлення, отримання і перевантаження по-
токів. На мережі задана цілочислова мат-
риця потоків
nnijaA
= , у якій потоки
iia ni ,1= представляють внутрішні пото-
ки між вузлами четвертого типу в зоні об-
слуговування i -го вузла. Вони не підля-
гають розподілу по магістральній мережі,
але повинні враховуватися у процесі роз-
рахунку витрат на сортування дискретних
потоків у вузлах першого, другого і тре-
тього типу (передбачається, що число вуз-
лів четвертого типу у внутрішній зоні ко-
жного i -го вузла першого, другого і тре-
тього типу відомо). Потоки ija з джерел i
у стоки j , , 1,i j n= повинні транспортува-
тися в транспортних блоках (контейнерах)
об'єму ija і кожен потік може бути
упакований у транспортний блок тільки
цілком.
Комп’ютерне моделювання
56
Перетворення потокової матриці A
повинно враховувати принципи напряму
потоків для вузлів другого і третього типу,
згідно з якими вихідний потік із цих вузлів
спрямовується (розсортовується) у вузли
першого типу, що лежать на межі зон їх
обслуговування. Нехай
n
Y y= – век-
тор, в якому підсумовуються додаткові
об'єми обробки від перетворених потоків
вузлів другого і третього типів (спочатку
0Y = ); iZ – зона обслуговування (ЗО), по-
будована на мережі G для i -го вузла; l ,
k – вузли першого типу в ЗО j -го і i -го
вузлів, обслуговуючі відповідно
2 3j N N , 2 3i N N ; S – множина пар
ij , що кореспондуються. Тоді змістовна
постановка задачі розподілу і упаковки по-
токів для вузлів другого і третього типу в
зональних мережах полягає в перетворенні
матриці A . Виконується наступним чи-
ном:
1. ij S , 1,i j N відповідні потоки ija
не змінюються;
2. ij S , 1i N , 2 3j N N , l i вико-
нати:
il il ija a a + , lj lj ija a a + , l l ijy y a + ,
0ija ;
3. ij S , 2 3i N N , 1j N , k j вико-
нати:
ik ik ija a a + , kj kj ija a a + , k k ijy y a + ,
0ija ;
4. ij S , 2 3,i j N N , k l виконати:
ik ik ija a a + , kl kl ija a a + , lj lj ija a a + ,
k k ijy y a + , l l ijy y a + ,
0ija ;
5. ij S , 2 3,i j N N , k l= , ij Z ви-
конати п. 3;
6. ij S , 2 3,i j N N , k l= , ij Z пе-
ретворення ija не виконується.
Як видно з постановки задачі для
усіх кореспонденцій, потоки яких підля-
гають операції перетворення, необхідно
вказати вузли k і l . Покажемо, що задача
визначення цих вузлів може бути зведена
до задачі лінійного програмування без
урахування обмежень на пропускні здібно-
сті дуг.
2. Математична модель і
алгоритми вирішення задачі
Транспортування або передача по-
токів із вузлів другого і третього типу до
обслуговуючих їх вузлів першого типу і
навпаки повинна виконуватися транспорт-
ними засобами магістрального рівня або
магістральними каналами зв'язку, тому для
таких потоків обмеження на пропускні
здібності дуг будуть враховані в магістра-
льних моделях у процесі розподілу потоків
між усіма типами вузлів у мережі. Най-
більш суттєвими чинниками, що визнача-
ють якість схеми розподілу потоків вузлів
другого і третього типу, є витрати на їх
транспортування або передачу від вузла-
джерела до вузла-споживача і можливості
обробки потоків цих вузлів у вузлах пер-
шого типу. Оскільки в даній задачі здійс-
нюється тільки адресація потоків з вузлів
другого і третього типу в деякі вузли пер-
шого типу (що лежать на межі зон), а фак-
тичний розподіл потоків з урахуванням їх-
ніх обсягів та інших обмежень здійснюєть-
ся при вирішенні задачі розподілу потоків
на магістральному рівні, то транспортні
витрати можна вважати не залежними від
обсягу потоків і прийняти лінійними від
відстані. Приймемо також, що витрати на
додаткову обробку (пересортовування)
одиниці потоку з вузлів другого і третього
типу в обслуговуючих їх вузлах першого
типу однакові в усіх вузлах.
Нехай ij n n
R r
= – топологічна
матриця, де
довжині дуги, якщо ,
, якщо дуги не існує.
ij
ij
ij
p P
r
p
=
Розглянемо мережу ( , )D DG N P
отриману з ( , )G N P таким чином. Визна-
чимо на мережі DG використовуючи мат-
рицю R найкоротші шляхи від усіх вузлів
2 3i N N до вузлів першого типу, що
знаходяться в ЗО i -го вузла і найкоротші
шляхи між усіма вузлами першого типу. В
результаті отримаємо матрицю
Комп’ютерне моделювання
57
ij n n
D d
= в якій елементи нерівні не-
скінченності представляють множину дуг
DP мережі DG .
Твердження 1. Нехай виконується
одна з умов :
1 1 2 3( , ) (( , )iji j N d i N j N N
2 3 1) (( , )ij ijd i N N j N d (1)
= ijdNNjNi ),( 321 (2)
= ijdNjNNi ),( 132 (3)
iij ZjdNNji = ),( 32 (4)
тоді: 1) найкоротший шлях між будь-
якими вузлами, для яких виконується умо-
ва (1), складається з однієї дуги і співпадає
з найкоротшим шляхом між цими вузлами,
побудованими на мережі G ; 2) найкорот-
ший шлях між вузлами, для яких викону-
ється (2) або (3) складається з двох дуг; 3)
найкоротший шлях між вузлами, що задо-
вольняють умові (4) складається з двох або
трьох дуг.
Доведення. Для доведення 1) покажемо,
що довжина будь-якого шляху, побудова-
ного на мережі DG між вузлами 1,i j N і
що містить більше за одну дугу не менша,
ніж довжина шляху, що складається з од-
нієї дуги. Припустимо, що знайдений най-
коротший шлях ij від i до j , що містить
понад одну дугу. Нехай ij заданий пере-
рахуванням вузлів 1 2( , , ,..., , )ij i k k k j = .
Тоді довжина будь-якої дуги 1( , )i k ,
1 2( , )k k ,..., ( , )k j у мережі DG визначається
сумою довжин певної підмножини тополо-
гічних дуг мережі G . Якщо усі топологіч-
ні дуги, що становлять відрізки
1( , )i k ,..., ( , )k j є підмножиною множини
топологічних дуг, що входять в шлях *
ij ,
побудований на мережі G і представлений
в мережі DG однією дугою, то довжини
шляхів ij і *
ij співпадають. У разі неви-
конання останньої умови, довжина шляху
ij не може бути менше довжини *
ij ,
оскільки тоді шлях *
ij не був би найкоро-
тшим. Отримане протиріччя і той факт, що
в алгоритмі побудови найкоротших шля-
хів, серед декількох можливих найкорот-
ших шляхів між заданими вузлами, пер-
шим завжди буде визначений шлях, що
складається з меншого числа дуг, доводить
твердження 1). Доведення 2) і 3) виходить
з правил формування ЗО для вузлів, побу-
дови мережі DG , а також з міркувань, ана-
логічних наведеним для доведення твер-
дження 1).
Слід зазначити, що для випадків
(2)-(4) довжини найкоротших шляхів між
вузлами i і j , побудованих в мережі G і
DG , можуть не співпадати. У разі (4), коли
ij Z мають місце внутрішньо-зональні
кореспонденції, потоки яких не піддаються
додатковій переробці у вузлах першого
типу, тому вони не розглядаються під час
формування матриці A .
Далі вважатимемо, що кожна неорі-
єнтована дуга Dp P замінена на дві дуги з
протилежною орієнтацією і Dp означає
число усіх орієнтованих дуг в DG .
Нехай
Ti i
jX x= , 1, Dj p= , 1,i n=
– вектор-стовпець, що визначає потоки ко-
респонденцій, які виходять з вузла i по
усіх дугах мережі DG ; ij n n
A a
= – мат-
риця потоків, в якій збережені тільки ті
елементи ija , для індексів яких справедли-
ва одна з умов (2)-(4). Інші елементи в ма-
триці A замінені на нулі. Позначимо через
i i
jC c= , 1, Dj p= , 1,i n= вектор-рядок
витрат на транспортування одиниці потоку
кореспонденцій з i по дугах мережі DG .
Побудуємо для DG матрицю інцидентності
D
ij n p
E e
= вузли-дуги і визначимо мат-
риці
D
ij n p
W w
= , 1, n = ; вектори-
стовпці
Ti i
jV v= , 1,j n= , 1,i n= ; век-
тор-стовпець пропускних здатностей вуз-
лів TW
iH h= , 1,i n= . Знак « T » означає
транспонування. Де відповідно:
Комп’ютерне моделювання
58
1, якщо дуга спрямована до вузла ,
1, якщо дуга спрямована від вузла ,
0 в іншому випадку;
ij
j i
e j i
= −
1, якщо 1,
1, якщо 1 і ,
0 в іншому випадку;
ij
ij ij
e
w e i
=
= = − =
1
, якщо ,
, якщо .
n
iji
j
ij
a j i
v
a j
=
− ==
=
Розв'язання задачі розподілу пото-
ків у зональних мережах шукатимемо в
класі задач лінійного програмування виду:
1 1 [ ] [ ] ...D DMin Z C p X p= + +
[ ] [ ]n n
D DC p X p+ , (5)
1 1[ , ] [ ] ...D DW n p X p + +
[ , ] [ ] [ ]n n w
D DW n p X p H n+ , (6)
1 1[ , ] [ ] [ ]D DE n p X p V n= ,
. . . (7)
[ , ] [ ] [ ]n n
D DE n p X p V n= ,
[ ] 0i
DX p і цілі 1,i n= . (8)
Розглянемо особливості сформу-
льованої задачі. Із Твердження 1 ясно, що
для вирішення блокових задач, можна ви-
користати ефективні алгоритми побудови
найкоротших шляхів за одним критерієм –
мінімумом довжини шляху. Це витікає з
того, що будь-який шлях для кореспонде-
нцій з класу (2) або (3) складатиметься з
двох дуг, а для кореспонденцій класу (4) –
з двох або трьох дуг. Тому вибір оптима-
льного шляху завжди робитиметься серед
шляхів, що містять однакове число дуг,
тобто усі шляхи еквівалентні з точки зору
числа транзитних вузлів. Інша особливість
задачі (5)-(8) полягає в тому, що обмежен-
ня на пропускні здатності вузлів необхідно
враховувати тільки для вузлів першого ти-
пу, пов'язаних з вузлами другого і третього
типів в мережі DG хоча би однією дугою.
Верхня межа числа обмежень (6), що вра-
ховуються, дорівнює величині 1n – числу
вузлів в множині 1N . Остання обставина
забезпечує відносно невисоку розмірність
задачі (5)-(8) і дозволяє використати для
отримання нижніх оцінок її вирішення ме-
тод декомпозиції Данцига-Вулфа й інші
методи цілочислового програмування [4,
5].
Підкреслемо, що у разі неврахован-
ня обмеження (6), отримане вирішення у
процесі використання методу Данцига-
Вулфа буде завжди цілочисловим, оскіль-
ки матриці обмежень у приведеній моделі
є цілком унімодулярними, а праві частини
обмежень цілочисловими векторами і ви-
бір оптимального розв'язку здійснюється
на многограннику з цілочисловими вер-
шинами.
Оскільки реальні мережі функціо-
нують з ресурсами, що динамічно зміню-
ються з часом, і недостатньо точною поча-
тковою інформацією, для практичного ви-
рішення задачі можна відмовитися від то-
чних методів і використати алгоритми, за-
сновані на методах побудови найкоротших
шляхів. Приведемо алгоритми, що дозво-
ляють вирішити задачу у випадках заданих
і невідомих зон обслуговування вузлів.
Нехай * *
ij n n
C c
= – довідкова ма-
триця найкоротших шляхів, побудована
для мережі DG , де
2 3
*
0, якщо ( )
( , N ),
, якщо і
пов'язані однією дугою,
, якщо шлях від до
містить більше однієї дуги,
i
ij
i j
i j N j Z
i i j
c
k i
j
=
=
(9)
де k – передостанній вузол на найкорот-
шому шляху від i до j ; 1
iB – множина ву-
злів першого типу в iZ ; { | } – множина
для яких вірне твердження .
Відомо, що для побудованих найко-
ротших шляхів справедливе твердження
{ | \ }iji N j N i таке, що в j вхо-
дить не більше за одну дугу, яка належить
будь-якому найкоротшому шляху ij . Та-
ким чином, найкоротші шляхи ij побудо-
вані від вузла i є деревом з коренем в i ,
яке може бути однозначно описане рядком
довідкової матриці *C .
Комп’ютерне моделювання
59
Алгоритм 1. Розподіл потоків в
умовах заданих ЗОВ
1. Використовуючи матрицю R побудува-
ти в мережі G найкоротші шляхи від
2 3i N N до 1
ij B і між усіма вузла-
ми з множини 1N .
2. Використовуючи матрицю D , побудо-
вану в п. 1, знайти найкоротші шляхи в
мережі DG . У процесі побудови шляхів
сформувати довідкову матрицю *C відпо-
відно до (9).
3. 0C ; 0Y . *** C – довідкова мат-
риця об'єднання потоків
4. Для
* *{ , | ( 0) , , 1, }ij iji j c i c i j i j n= = = ви-
конати ijc i .
5. Для * *{ , | 0, , 1, }ij iji j c i c i j n = вико-
нати пп. 6-12.
6. j ; 0l ; 0k .
7. Поки *
ic i виконати пп. 8-10.
8. Якщо 0l = , то *
il c .
9. *
ik c .
10. *
ic . Перейти до п. 7.
11. Якщо k l= , то виконати перетворення
ik ik ija a a + , kj kj ija a a + , k k ijy y a + ,
0ija , інакше виконати
перетворення ik ik ija a a + kl kl ija a a +
lj lj ija a a + k k ijy y a +
l l ijy y a + , 0ija .
12. ijc k . Перейти до п. 5.
13. Стоп.
Запис в рядках 4 і 5 вираження
, 1,i j n= означає циклічну зміну індексів,
причому другий індекс змінюється швид-
ше за перший. Такий запис аналогічний
організації внутрішнього циклу по j і зо-
внішнього по i , коли обидва індекси змі-
нюються від одиниці до n з одиничним
кроком.
У результаті роботи Алгоритму 1
формуються матриці A , C і вектор Y . У
векторі Y підсумовуються додаткові обся-
ги обробки від перетворених потоків вуз-
лів другого і третього типу (спочатку
0C = і 0Y = ). Елементи довідкової мат-
риці об'єднання (сортування) потоків
ij n n
C c
= визначаються таким чином:
, якщо потік адресується в вузол ,
, якщо потік адресується в вузол ,
0, якщо .
ij
ij ij
i a j
c k a k
i j
=
=
Матриця C використовується для запам'я-
товування схеми адресації (сортування)
потоків у вузлах другого і третього типів.
Для роботи Алгоритму 1 необхідно
знати множини 1
iB , 2 3i N N . Раніше
відмічалося, що множини 1
iB визначаються
методом експертного аналізу із залучен-
ням досвідчених фахівців або автоматизо-
ваним способом після вирішення задачі
вибору структури мережі. У випадку, якщо
процедура уточнення структури мережі
експертами з будь-яких причин виконана
не була, може виявитися, що зони обслу-
говування для вузлів другого і третього
типу точно не відомі. Тому доцільно мати
алгоритм розподілу потоків у зональних
мережах, якщо заданий тільки вектор
i n
= що визначає типи вузлів, де 1i = ,
якщо 1i N і 0i = , якщо 2 3i N N .
Алгоритм 2. Розподіл потоків за
невідомих ЗОВ
1. Використовуючи матрицю R побудува-
ти на мережі G найкоротші шляхи між
усіма вузлами з одночасним формуванням
довідкової матриці *C згідно (9).
2. 0C ; 0Y . *** C – довідкова мат-
риця об'єднання потоків
3. Для { | 1, }i i n= виконати пп. 4-23.
4. Для { | 1, }j j n= виконати пп. 5-22.
5. Якщо i j перейти до п. 6, інакше пе-
рейти до п. 22.
6. Якщо 1 1i j = = виконати ijc i ; пе-
рейти до п. 22.
7. j ; 0l ; 0k .
8. Поки *
ic i виконати пп. 9-12.
9. Якщо * 1
ic
= виконати пп. 10-11, інакше
перейти до п. 12.
10. Якщо 0l = , то *
il c .
Комп’ютерне моделювання
60
11. *
ik c .
12. *
ic . Перейти до п. 8.
13. Якщо 0i = , то перейти до п. 14, інак-
ше до п. 21.
14. Якщо 0j = , то перейти до п. 15, інак-
ше до п. 19.
15. Якщо 0l , то перейти до п. 16, інакше
ijc i і перейти до п. 22.
16. Якщо l k , то виконати п. 17, інакше
перейти до п. 18.
17. kl kl ija a a + , lj lj ija a a + ,
l l ijy y a + ,
L1: ik ik ija a a + k k ijy y a + ijc k ,
L2: 0ija перейти до п. 22.
18. Виконати
L3: il il ija a a + lj lj ija a a + l l ijy y a +
ijc l перейти до L2.
19. Якщо 0k = , то ijc i перейти до п. 22.
20. kj kj ija a a + . Перейти до L1.
21. Якщо 0l = , то ijc i , інакше перейти
до L3.
22. Перейти до п. 4. *** кінець циклу по j
23. Перейти до п. 3. *** кінець циклу по i
24. Стоп.
У Алгоритмі 2 покажчики k і l ви-
значають відповідно перший і останній ву-
зли першого типу, що знаходяться на най-
коротшому шляху між i і j . Якщо між ву-
злами i і j немає вузлів першого типу,
або немає взагалі ніяких вузлів, значення
0k l= = .
В результаті роботи Алгоритмів 1 і
2 формуються: перетворена матриця пото-
ків кореспонденцій ij n n
A a
= ; елементи
довідкової матриці об'єднання потоків для
вузлів другого і третього типу (матриця
C ). У рядках і стовпцях перетвореної мат-
риці A для вузлів другого і третього типу
ненульові значення будуть присутніми
тільки для вузлів першого типу, які пере-
бувають у зоні обслуговування вузлів дру-
гого і третього типу, а в потоках між вуз-
лами першого типу будуть враховані усі
потоки вузлів другого і третього типу.
Порівнюючи трудомісткість Алго-
ритмів 1 і 2 з трудомісткістю вирішення
задачі (5)-(8) відзначимо, що використання
простих процедур, що ґрунтуються на по-
будові найкоротших шляхів дозволяє вка-
зати верхню межу асимптотичної трудомі-
сткості – 3( )O n , тоді як точне вирішення
цілочислової задачі (5)-(8) може мати екс-
поненціальну оцінку [6].
Висновки
Резюмуючи обговорення задачі ро-
зподілу потоків в зональних мережах, від-
значимо, що вона може бути сформульо-
вана як задача лінійного програмування з
блоковою структурою обмежень і для її
вирішення застосуємо метод декомпозиції
Данцига-Вулфа й інші методи цілочисло-
вого програмування. Для вирішення задачі
на реальних мережах запропоновані на-
ближені алгоритми, засновані на побудові
найкоротших шляхів. Верхня межа часової
складності наближених алгоритмів складає
3( )O n , тоді як точне вирішення цілочисло-
вої задачі може мати експоненціальну оці-
нку. Тому перевагу у вирішенні загальної
задачі вибору ієрархічної структури ма-
гістральної мережі слід віддати наближе-
ним алгоритмам з огляду на їхню просто-
ту, невелику трудомісткість і, як показали
практичні дослідження [2], прийнятну то-
чність розв'язку.
Література
1. O.M. Trofymchuk, V.A. Vasyanin,
Simulation of Packing, Distribution
and Routing of Small-Size Discrete
Flows in a Multicommodity Network,
Journal of Automation and Infor-
mation Sciences, 2015. 47(7). P. 15-
30.
https://doi.org/10.1615/JAutomatInfSc
ien.v47.i7.30.
2. А.Н. Трофимчук, В.А. Васянин,
Компьютерное моделирование
иерархической структуры комму-
никационной сети с дискретными
многопродуктовыми потоками,
УСиМ, 2016. № 2. С. 48-57.
https://doi.org/10.15407/usim.2016.0
2.048.
3. В.А. Васянин, Компьютерное моде-
лирование распределения и марш-
рутизации дискретных многопро-
дуктовых потоков в коммуникаци-
онной сети, УСиМ, 2016. № 3. С. 43-
53.
https://doi.org/10.15407/usim.2016.0
3.043.
4. G.B. Dantzig, Ph. Wolfe, Decomposi-
tion Algorithm for linear program-
ming, Econometrica, 1961. Vol. 29.
N. 4. P. 767-778.
5. C. Barnhart, N. Krishnan, P.H. Vange,
Multicommodity Flow Problems, In
Encyclopedia of Optimization: Second
Edition, C.A. Floudas and P.M. Parda-
los (Eds.). Springer, New York, 2009.
P. 2354-2362.
6. М. Гэри, Д. Джонсон, Вычисли-
тельные машины и труднорешае-
мые задачи, М.: Мир, 1982. 416 с.
Одержано: 10.04.2024
Внутрішня рецензія отримана: 15.04.2024
Зовнішня рецензія отримана: 15.04.2024
Про автора:
Васянін Володимир Олександрович,
Доктор технічних наук,
Старший науковий співробітник
https://orcid.org/0000-0003-4046-5243
Місце роботи автора:
Завідувач відділу прикладної інформатики
Інституту телекомунікацій і глобального
інформаційного простору НАН України,
м. Київ,
E-mail: archukr@meta.ua
Сайт: https://itgip.org/
Комп’ютерне моделювання
61
https://doi.org/10.15407/usim.2016.0
2.048.
3. В.А. Васянин, Компьютерное моде-
лирование распределения и марш-
рутизации дискретных многопро-
дуктовых потоков в коммуникаци-
онной сети, УСиМ, 2016. № 3. С. 43-
53.
https://doi.org/10.15407/usim.2016.0
3.043.
4. G.B. Dantzig, Ph. Wolfe, Decomposi-
tion Algorithm for linear program-
ming, Econometrica, 1961. Vol. 29.
N. 4. P. 767-778.
5. C. Barnhart, N. Krishnan, P.H. Vange,
Multicommodity Flow Problems, In
Encyclopedia of Optimization: Second
Edition, C.A. Floudas and P.M. Parda-
los (Eds.). Springer, New York, 2009.
P. 2354-2362.
6. М. Гэри, Д. Джонсон, Вычисли-
тельные машины и труднорешае-
мые задачи, М.: Мир, 1982. 416 с.
Одержано: 10.04.2024
Внутрішня рецензія отримана: 15.04.2024
Зовнішня рецензія отримана: 15.04.2024
Про автора:
Васянін Володимир Олександрович,
Доктор технічних наук,
Старший науковий співробітник
https://orcid.org/0000-0003-4046-5243
Місце роботи автора:
Завідувач відділу прикладної інформатики
Інституту телекомунікацій і глобального
інформаційного простору НАН України,
м. Київ,
E-mail: archukr@meta.ua
Сайт: https://itgip.org/
|