ISSN 2307–3489 (Print), ІSSN 2307–6666 (Online)

Наука та прогрес транспорту. Вісник Дніпропетровського
національного університету залізничного транспорту, 2020, № 1 (85)

ІНФОРМАЦІЙНО-КОМУНІКАЦІЙНІ ТЕХНОЛОГІЇ
ТА МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ

Вступ

У багатьох сучасних сферах діяльності завдання з аналізу, планування та керування потоками в мережах є надзвичайно поширеними. Розвиток сучасних мережевих технологій потребує вдосконалення методів управління потоками. Виходячи з потреб і вимог до головних характеристик досліджуваних процесів, представлених моделями мереж, а також під час планування та раціональної організації транспортних потоків, формують однорідні або багатопродуктові моделі таких процесів [1–3, 7]. Розроблено різноманітні математичні моделі транспортних, інформаційних, фінансових та інших потоків у мережах, у тому числі як відображень задач оптимального або раціонального планування [1, 3, 7]. Одним із головних завдань під час формування та аналізу транспортних та інших мереж є визначення максимальних потоків. Його результати широко застосовують для вирішення багатьох практичних завдань планування, моделювання тощо [4, 7, 11–14]. При цьому таких використовують різноманітні кількісні та якісні властивості мереж. Розрахунки максимальних потоків також застосовують для реалізація завдань планування багатопродуктових і багатокритеріальних потоків, завдань пошуку розподільних множин ребер графових моделей транспортних та багатьох інших мереж [2, 7, 10, 16].

Для розрахунків максимальних однопродуктових цілочисельних потоків у мережних моделях базовим є метод Форда–Фалкерсона [2, 7, 9, 15]. Загалом існує понад двадцять інших алгоритмів для розрахунку максимальних потоків у мережах. Серед них одними з перших і найбільш поширених є алгоритми Форда–Фалкерсона, Едмондса–Карпа [3], Дініца [4]. На сьогодні проведено аналіз особливостей, переваг і недоліків алгоритмів, також визначено оцінки складності таких алгоритмів, що наведені в дослідженнях [2–4] та ін. Завдання розрахунку максимального потоку потребує досить значних обчислювальних ресурсів. Разом із цим можливі певні структури моделей мереж, для яких ці алгоритми мають слабку збіжність [1, 2]. Зараз відомо багато програмних засобів реалізації зазначених алгоритмів, при цьому реалізовано послідовні та паралельні версії алгоритмів [5, 6]. Відзначається суттєве зростання складності завдань із програмної реалізації алгоритмів аналізу неоднорідних і компромісних потоків у мережах [2, 5, 7].

Необхідно зазначити, що питання формування паралельних алгоритмів, призначених для розрахунків максимальних потоків (МП) у мережах, потребує подальшого дослідження. У статті [6] розроблено та досліджено можливості паралельного синхронного алгоритму (ПСА) розрахунку максимальних неоднорідних потоків у транспортних мережах, який придатний для розрахунку однопродуктових, багатопродуктових та формування компромісних потоків за рахунок застосування моделей раціонального вибору. Також наведено приклади, що демонструють придатність, ефективність і широкі можливості застосування ПСА для вирішення завдань аналізу та оптимального планування неоднорідних потоків у транспортних мережах.

Моделі та завдання аналізу великої кількості різноманітних процесів можуть бути представлені у формі графів. Це призводить до поширення саме завдань із аналізу, оптимального планування й управління потоками в мережах [3]. На практиці часто потоки в транспортних та інших мережах є неоднорідними, зокрема багатопродуктовими, а також динамічними (урахування терміну передачі, зміна параметрів у часі та ін. [4]), об’єкти потоків у мережах можуть мати різні властивості за функціональним призначенням, вимогами до сервісів тощо [3]. Зростання потреб щодо передачі та обробки інформації, яка надходить мережами, призводить до завдань організації та оптимізації функціонування мережевих інформаційних систем (МІС). При цьому важливу роль відіграють завдання розподілу конкурувальних потоків. Такі завдання, як правило, потребують окремих моделей та методів реалізації. Застосування до них паралельних алгоритмів типу ПСА також представлено в зазначеній роботі.

Мета

У попередніх дослідженнях авторів було розроблено нову уніфіковану процедуру планування однорідних, нечітких багатопродуктових і динамічних, а також конкурувальних потоків у транспортних мережах і мережевих інформаційних системах із використанням можливості ПСА, що базується на евристичному базисі. Разом із високою універсальністю та ефективністю алгоритми на основі ПСА мають певну обмеженість застосування, яка визначається їх евристичною сутністю. Через ці обставини потенційно можливі структури мереж не можуть бути ефективно досліджені на основі ПСА. Вирішенню питань забезпечення універсальності паралельного алгоритму розрахунку МП, достовірності результатів аналізу, а також уніфікації форми ПСА та можливості його розширення і присвячена представлена стаття.

Метою статті є розробка уніфікованого паралельного синхронного алгоритму розрахунку максимальних потоків та створення програмного забезпечення, призначеного для оптимального планування неоднорідних потоків у транспортних та інших мережах.

Методика

Розглянемо базові засади ПСА, а також можливості застосування евристичного паралельного синхронного алгоритму розрахунку МП у мережах із метою встановлення його можливих обмежень і визначення шляхів удосконалення процедур, які забезпечують перетворення цього алгоритму до універсального (УПСА). На основі УПСА розроблено програмний комплекс, який достовірно та ефективно реалізує завдання з оптимального планування неоднорідних потоків у транспортних мережах.

Формально транспортна мережа – це орієнтований граф G = (V, E), у якому кожне ребро (u, v) має позитивну пропускну здатність c (u, v) > 0 і потік f (u, v) [2]. Виділяють дві вершини: витік s та стік t, причому будь-яка інша вершина мережі лежить на шляху з вершини s до вершини t. Позначимо через

(1)

транспортну мережу (далі також мережу), у якій c (u, v) – пропускна здатність; а f (u, v) – потік через ребро (u, v); V – множина вузлів;
E – множина ребер.

Для пояснення сутності ПСА та його специфіки щодо визначення МП наведемо схему алгоритму Едмондса–Карпа (А–ЕК) [2]. Для цього пояснимо поняття залишкової мережі (ЗМ), що формується за ітераціями, як мережі, пропускні здатності ребер якої модифікуються на основі величин визначених та збільшувальних потоків. А–ЕК визначають такі етапи. Спочатку беруть, що всі потоки мережі дорівнюють нулю, а ЗМ збігається із заданою транспортною мережею. У ЗМ на підставі дерева маршрутів знаходять найкоротший шлях (НКШ) із витоку до стоку. Якщо такого шляху не існує – МП знайдено, зупинитися. Через НКШ (збільшувальний шлях) пускають максимально можливий потік таким чином: на НКШ у ЗМ знаходять ребро з мінімальною пропускною здатністю , для кожного ребра на НКШ збільшують потік на , а на протилежному йому ребрі зменшують на . Модифікують ЗМ для всіх ребер НКШ, а також для протилежних, розраховують нову пропускну здатність, змінюючи на . Якщо така пропускна здатність дорівнює нулю, ребро вилучають з графа мережі, якщо ж здатність стала позитивною – додають ребро до ЗМ. Виконують перехід до пошуку НКШ з витоку до стоку. Складність алгоритму Едмондса–Карпа дорівнює [2, 4].

Під час формування математичних моделей із розрахунку МП розмірності відповідних оптимізаційних задачах, як правило, дорівнюють числу ребер у мережах (1). Умови неперервності потоків досягаються за допомогою застосування спеціальних методів представлення та забезпечення відповідних рівнянь [2, 3, 7]. В алгоритмах розрахунку максимального багатопродуктового потоку (МБП) припускається можливість існування кількох неоднакових витоків і стоків, окремих для потоків різних продуктів [7]. У моделях МБП також додатково враховуються обмеження на одночасні загальні оцінки величин потоків усіх продуктів відповідними ребрами мереж. У рішеннях завдань МБП структури оптимальних потоків окремих продуктів також можуть залежати від уведеної нумерації потоків продуктів та послідовності їх урахування під час розрахунків. При цьому значення загального потоку залишаються постійними. За умов конкуренції окремих потоків продуктів такі рішення щодо МБП не можуть бути застосовані на практиці [3, 5].

Розроблений і представлений у статтях [5, 6] ПСА максимальних потоків у мережах використовує стратегію пошуку в ширину та одночасного визначення можливих шляхів потоків через мережу з відомими на певному кроці ЗМ пропускними здатностями дуг (ребер). У розробленому в [5, 6] ПСА розпаралелювання виконується за рахунок синхронізації процесів формування вузлів дерева вузловими процедурами, у яких одночасно виконується аналіз можливих значень додаткових, збільшувальних, потоків, що можуть розповсюджуватися по наступних визначених ребрах ЗМ (за рахунок паралельного виклику відповідних вузлових процедур). Тут виникає можливість на одній ітерації виконувати паралельно аналіз декількох збільшувальних потоків через ЗМ.

У ПСА вузлові процедури можуть виконуватися, якщо до них за схемою мережі (1) надійшли всі вхідні потоки. Для контролю синхронізації вузлових процедур уводять кроковий параметр послідовності виконання процедур і надходження потоків . Значення параметра вказує «довжину» шляху від витоку до відповідного вузла в ЗМ. Якщо на кроці до вузла-процедури надійшов вхідний потік, процедура переходить у стан активності, а в разі надходження всіх вхідних параметрів – стає готовою і паралельно виконує виклик усіх вихідних вузлів-процедур, передаючи їм розраховані нею параметри можливих потоків за цими шляхами. При цьому сама переходить до стану «виконано», а число активних вузлів зменшується на одиницю. Система синхронізації контролює число активних процедур на кроках . За параметром також виконують контроль можливого блокування процесів формування маршрутів через ЗМ, зокрема – коли немає жодного вузла, до якого на кроках надійшли всі вхідні потоки. У такому випадку передбачено передачу синхронізувального «нульового» потоку. Вибір вузла-процедури для розблокування обирають за такими ознаками: мінімальна кількість відсутніх вхідних потоків, зп рівності – мінімальність номера кроку активізації процедури , за рівності цих параметрів – менша кількість вихідних вузлів. Виникнення відзначених процесів блокування може бути можливе під час аналізу багатопродуктових потоків. У подальших процедурах синхронізувальний потік ураховують в алгоритмі, як і всі інші.

Детальне описання структури базового паралельного синхронного алгоритму (БПСА) розрахунку максимального потоку в мережі (1) наведено у [6]. На його основі можна побудувати алгоритми аналізу інших категорій потоків (багатопродуктових, нечітких, динамічних та ін.) [5, 6]. Загальна схема БПСА пошуку максимального потоку, запропонованого в [5, 6], наведена в табл. 1. На відміну від традиційних методів розрахунків максимальних потоків у мережах, БПСА на прямому ходу об’єднує всі три основних етапи класичних алгоритмів МП: 1) розрахунок усіх можливих шляхів через мережу; 2) вибір одного шляху з мінімальним значенням довжини; 3) пропуск цим шляхом максимального доповнювального потоку. При цьому також виконують коригування пропускних здатностей дуг мережі. Сутність ефективності БПСА полягає в тому, що за рахунок спеціальної процедури синхронізації створюється можливість обробки декількох зворотних потоків одночасно, тобто на одному етапі аналізу мережі.

Таблиця 1

Схема базового синхронного паралельного алгоритму пошуку максимального потоку

Table 1

Scheme of the basic synchronous parallel algorithm for finding the maximum flow

Встановити значення , пропускні здатності всіх дуг модифікованої мережі дорівнюють вихідній (прямий хід ).

До тих пір, поки не досягнутий стік t: Синхронно виконувати передачу потоку по мережі відповідно до номерів вузлів , контролюючи їх активність і готовність. Для готових вузлів виконувати передачу максимального вхідного потоку у вузли, які виходять. Сформувати всі варіанти шляхів через мережу. Знайти величини потоків за кожним із можливих шляхів.

Змінити напрямок потоку на протилежний (зворотний хід ).

Поки не досягнутий вузол (джерело) s, виконувати: Аналіз зворотних додаткових неперервних потоків. Процедурe оцінки умов розпаралелювання потоків у мережі на основі аналізу умов із визначення раціональних зворотних потоків. Фіксаці. вузлів зворотних маршрутів.

Перерахунок розміру додаткового потоку , якщо – кінець алгоритму.

Коригування відповідно до . Модифікація мережі . Перейти на крок 2.

Відповідно до наведеної у табл. 1 схеми паралельного алгоритму планування МП на прямому ходу БПСА будують усі можливі шляхи через мережу. Разом із цим одночасно оцінюють максимальну пропускну здатність кожного можливих шляхів. На наступному етапі, у разі зворотного ходу алгоритму через мережу, формують справжні величини потоків, а також перевіряють можливість їх незалежного додаткового обліку. Узята така схема обробки потоків у вузлах мережі:

;

.

Додатковий потік: ,
– максимальний вхідний потік .

Стани вузлів моделі мережі: ЧЕКАЄ, АКТИВНИЙ, ГОТОВИЙ, ПЕРЕДАНО.

Рис. 1. Схема паралельних потоків
у вузлах моделі мережі

Fig. 1. Scheme of parallel flows in the nodes
of the network model

Особливість БПСА полягає в тому, що для забезпечення можливості паралельної (на одному етапі аналізу) обробки декількох потоків застосовано процедури синхронізації зворотних потоків. Процедура синхронізації враховує виявлені під час дослідження властивості синхронізованих потоків у мережах. Призначення процедури синхронізації – вибір вузла мережі для передачі умовного потоку синхронізації (розблокування алгоритму БПСА за однакових властивостей вузлів). Ураховують таку послідовність вимог щодо параметрів вузла: входження до множини активних вузлів мережі; мінімальна кількість неактивізованих вхідних потоків; мінімальна відстань від витоку мережі до вузла; максимальне число вхідних потоків до вузла; мінімальний номер вузла в мережі. На основі проведення «процедури розблокування» обирають один вузол мережі, якому передають потік синхронізації, що забезпечує реалізацію БПСА.

У роботах [5–7] розроблено паралельні алгоритми для неоднорідних потоків БПСА, що мають таке уточнене представлення (табл. 2):

– підмережа -ого продукту.

Таблиця 2

Схема паралельного алгоритму пошуку максимального потоку для неоднорідних потоків

Table 2

Scheme of the parallel algorithm for finding the maximum flow for inhomogeneous flows

Для кожного продукту встановити початкові значення ; .

Незалежно виконати паралельний аналіз усіх продуктів, використовуючи БПСА (без обмежень на загальну пропускну здатність).

Виділити роздільну множину, визначити потоки продуктів за дугами цієї множини.

Вирішити конфлікт продуктів на кожній із дуг роздільної множини (з урахуванням загального обмеження на пропускну здатність), модель (2).

Розрахувати оцінки потоків продуктів за всіма дугами роздільної множини.

Розрахувати потоки продуктів по мережі.

Контроль умов закінчення або ж коригування мереж .

Наведемо окремі функції вузлових процедур ПСА детальніше, ураховуючи можливості неоднозначності цих розрахунків, а саме умови щодо рівності величин декількох максимальних вхідних або мінімальних збільшувальних потоків за маршрутами. Якщо величину мають кілька вхідних вузлів, за виступає вхідний вузол із меншим (відповідає найкоротшому шляху до вузла за числом кроків), за рівності параметрів беруть вузол із меншим числом вихідних ребер. За рівності кількох мінімальних збільшувальних потоків, режим , за також обирають вузол із меншим , за рівності – вузол із меншим числом вихідних ребер. Як свідчить наведений перелік умов визначення вхідних–вихідних вузлів ПСА, вибір вузлів для розвитку процесу формування оптимальних потоків носить неточно визначений, евристичний характер. Потенційно залишається можливість існування певних структур мережі, для яких наведення умов щодо визначення таких оптимальних кроків алгоритму буде неможливим. Створення в рамках ПСА процедури, що дозволяє виконувати усунення такого роду невизначеності, означає отримання універсального уніфікованого паралельного алгоритму для аналізу потоків у мережах.

У [5, 6] також наведена процедура і результати планування потоків на основі принципу компромісу:

(2)

де – величина компромісного потоку k-ого продукту; – його максимальний потік у мережі. Модель формування компромісних потоків (2) в окремих випадках не відображає принцип справедливого розподілу ресурсів мережі між конкурувальними потоками. Зокрема, у (2) не враховано, що окремі потоки можуть мати ненульові мінімальні величини, завжди позитивні, незалежно від змін інших. У цих випадках планування компромісних потоків раціонально виконувати з урахуванням фактичних мінімальних рівнів потоків, що виконано у наступному розділі.

Результати

Дослідимо питання щодо формування універсального паралельного синхроного алгоритму (УПСА) розрахунку максимальних потоків у мережах, розроблено відповідної уніфікованої процедури, а також програмного комплексу для планування неоднорідних, конкурувальних потоків у транспортних мережах, які враховують потреби модифікації компромісу (2).

Проведені розрахунки МП для багатьох складних мережних моделей дозволили визначити умови та вимоги, виконання яких забезпечувало реалізацію завдань оптимального планування потоків, а також запропонувати форму УПСА. По-перше, у моделі на рис. 1 додатковий потік мав бути мінімальним або максимальним, та однозначно встановити, яким саме, не вдалося. По-друге, відповідно до п. 4.2 БПСА (табл. 1) неможливо гарантувати повноту умов раціонального вибору, а також їх упорядкування.

У результаті аналізу встановлене правило розпаралелювання для п. 4.2, яке усуває зазначені вище недоліки евристичного алгоритму. У разі виникнення умов невизначеності щодо вибору наступних вузлів, в УПСА виконують процедуру паралельного запуску зворотних потоків, які не детермінуються переліком списку умов раціонального вибору (див. наведений вище перелік). При цьому встановлено, що така процедура є достатньою, забезпечує реалізацію завдання розрахунку МП для будь-якої послідовності та числа умов вибору. Уведення в п. 4.2 БПСА такої процедури розпаралелювання перетворює його на УПСА.

Для модифікування моделі компромісних потоків (2), з урахуванням деяких можливих позитивних мінімальних потоків, у наведеній вище схемі НПСА, у п. 4 (табл. 2), необхідно додатково реалізувати завдання – визначити мінімальні можливі потоки для кожного із продуктів. Для цього необхідно окремо для кожного продукту розрахувати максимальні потоки maxV_k, а також при цьому визначити об’єми всіх інших продуктів, що проходять мережею. Мінімальне значення потоку продукту V_j серед усіх рішень для інших максимальних потоків буде дорівнювати minV_j під час формування компромісу типу (2). Остаточно в п. 4 НПСА для моделі компромісу (2) потрібно використовувати величини (V – minV_k), які визначені вище.

На основі наведених модифікацій було створено програмний комплекс, призначений для планування однорідних, багатопродуктових та компромісних потоків у транспортних та інформаційних мережах.

На рис. 2–4 представлені фрагменти програмної реалізації.

На рис. 2 зображено редактор інтерактивного моделювання мереж та панель інструментів. Панель складається з функціональних блоків: зміна режиму; розрахунок максимального потоку та діапазону потоків; зміна ваги дуг (пропускна здатність); встановлення витоку та стоку; виведення знайдених потоків; виведення початково заданого графа; відкриття нового вікна з таблицею результуючих потоків, їх шлях та величина; встановлення налаштувань програми до початкових значень; завантаження наявних графів мереж із бібліотек моделювання; збереження графа у вигляді зображення; збереження результатів роботи програми у вигляді текстового файлу; виведення помилок під час роботи з програмою.

Рис. 2. Розрахунок максимального однопродуктового потоку

Fig. 2. Calculation of maximum one-commodity flow

Рис. 3. Виведення результуючих потоків (зі зміною структури мережі)

Fig. 3. Output of the resulting flows (with network structure change)

На рис. 3 зображена мережа зі знайденими потоками. Значення ребер знайдених потоків отримане сумуванням величин результуючих потоків, що проходять через ребра, ребра без потоків не відображаються.

Рис. 4. Виведення результуючих потоків
у вигляді таблиці

Fig. 4. Output of the resulting flows
in the form of a table

На рис 4. зображена таблична форма з результуючими потоками, їх величиною та шляхом. Шлях визначає індекси вузлів, по яких пройшов потік.

Рис. 5. Вихідна модель однопродуктової мережі

Fig. 5. The output model of one-commodity network

На рис. 5 зображена однопродуктова мережа, що складається із 45 вузлів та 91 дуги. Максимальний потік цієї мережі дорівнює 100. На рис. 6 представлено оптимальне рішення завдання розрахунку максимального потоку.

Рис 6. Максимальний однопродуктовий потік
через мережу

Fig. 6. Maximum one-commodity flow
through the network

Наукова новизна та практична
значимість

У статті розроблено новий універсальний паралельний синхронний алгоритм та процедуру розрахунку оптимальних однорідних, багатопродуктових та конкурентних потоків у транспортних мережах.

Практична цінність отриманих результатів визначається універсальними можливостями та ефективністю процедури планування неоднорідних потоків у мережах на основі застосування нового паралельного синхронного алгоритму, а також розробленим програмним комплексом, який забезпечує можливість вирішення завдань аналізу і планування багатопродуктових потоків у транспортних мережах, а також реалізації завдань розрахунку конкурувальних моделей формування транспортних та інформаційних потоків.

Висновки

Розроблено та досліджено можливості паралельного синхронного алгоритму розрахунку максимальних неоднорідних потоків у транспортних мережах, який придатний для розрахунку однопродуктових, багатопродуктових та формування компромісних потоків за рахунок застосування моделей раціонального вибору. Наведені приклади демонструють придатність, ефективність і широкі можливості застосування паралельного алгоритму для вирішення завдань аналізу та оптимального планування неоднорідних потоків у транспортних мережах.

Список використаних джерел

1. Гасников В. А. Введение в математическое моделирование транспортных потоков : Учебное пособие. Москва : МЦНМО, 2013. 428 с.

2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы : построение и анализ. Пер. с англ. 2-е изд. Москва : Вильямс, 2005. 1296 с.

3. Скалозуб В. В., Цейтлин С. Ю., Чередниченко М. С. Интеллектуальные информационные технологии и системы железнодорожного транспорта : монография. «Системные технологии моделирования сложных процессов». Днепр, 2016. С. 560–589.

4. Скалозуб В. В., Паник Л. А. О построении обобщенных моделей планирования неоднородных транспортных потоков. Системные технологии. 2016. № 5 (106). С. 94–101.

5. Скалозуб В. В., Панік Л. О. Паралельні синхронні алгоритми аналізу та планування неоднорідних потоків у транспортних мережах. Системные технологии. 2017. № 5 (112). С. 183–197.

6. Скалозуб В. В., Паник Л. А. Реализация динамических, конкурентных и нечетких моделей планирования многопродуктовых потоков в транспортных сетях. Наука и прогрес транспортy. 2018. № 3 (75).
   С. 113–127. DOI: 10.15802/stp2018/133742

7. Филлипс Д. И., Гарсиа-Диас А. Методы анализа сетей. Москва : Мир, 1984. 496 с.

8. Bozhenyuk А., Gerasimenko E. Algorithm for Monitoring Minimum Cost in Fuzzy Dynamic Networks. Information Technology and Management Science. 2013. Vol. 16. Iss. 1. P. 53–59. DOI: 10.2478/itms-2013-0008

9. Bozhenyuk А. V., Gerasimenko E. M., Kacprzyk J. Maximum and Minimum Cost Flow Finding in Networks in Fuzzy Conditions. Flows in Networks Under Fuzzy Conditions. 2016. Vol. 346. P. 23–75. DOI: 10.1007/978-3-319-41618-2_2

10. Capuni I., Zhuri N., Dardha R. TimeStream: Exploiting video streams for clock synchronization. Ad Hoc Networks. 2019. Vol. 91. P. 236–248. DOI: 10.1016/j.adhoc.2019.101878

11. Holzhauser M., Sven O. Krumke, Clemens Thielen. Maximum flows in generalized processing networks. Journal of Combinatorial Optimization. 2016. Vol. 33. Iss. 4. P. 1226–1256. DOI: 10.1007/s10878-016-0031-y

12. Kovacs P. Minimum-cost flow algorithms : An experimental evaluation EGRES Technical Report. EGRES Technical Report. 2013. No. 4. P. 1–40. URL : https://web.cs.elte.hu/egres/tr/egres-13-04.pdf (дата звернення: 17.05.2018).

13. Reardon L. Networks and problem recognition: advancing the Multiple Streams Approach. Policy Sciences. 2018. Vol. 51. Iss. 4. P. 457–476. DOI: 10.1007/s11077-018-9330-8

14. Rezende P., Kianpisheh S., Glitho R., Madeira E. An SDN-Based Framework for Routing Multi-Streams Transport Traffic Over Multipath Networks. ICC 2019 – 2019 IEEE International Conference on Communications (ICC). Shanghai. China. 2019. P. 1–6. DOI: 10.1109/ICC.2019.8762061

15. Schiopu C., Ciurea E. The Maximum Flows in Planar Dynamic Networks. Intern. Journal of Computers Communications&Control. 2016. Vol. 11. Iss. 2. P. 282–291. DOI: 10.15837/ijccc.2016.2.2444

16. Sifaleras A. Minimum cost network flows: problems, algorithms, and software. YUJOR. 2013. Vol. 23. Iss. 1. DOI: 10.2298/YJOR121120001S

В. в. скалозуб^1*, Л. А. панИк^2*, А. Д. панарин^3*

^1*Каф. «Компьютерные информационные технологии», Днипровский национальный университет железнодорожного транспорта имени академика В. Лазаряна, ул. Лазаряна, 2, Днипро, Украина, 49010, тел. +38 (056) 373 15 35,
эл. почта skalozhubtk@gmail.com, ORCID 0000-0002-1941-4751
^2*Каф. «Компьютерные информационные технологии», Днипровский национальный университет железнодорожного транспорта имени академика В. Лазаряна, ул. Лазаряна, 2, Днипро, Украина, 49010, тел. +38 (056) 373 15 35,
эл. почта leon140377@gmail.com, ORCID 0000-0003-1343-3000
^3*Каф. «Компьютерные информационные технологии», Днипровский национальный университет железнодорожного транспорта имени академика В. Лазаряна, ул. Лазаряна, 2, Днипро, Украина, 49010, тел. +38 (056) 373 15 35,
эл. почта sashapanarin@mail.ru, ORCID 0000-0001-9050-463X

УНИФИЦИРОВАННЫЙ параллельный алгоритм

и программный КОМПЛЕКС оптимального

планирования НЕОДНОРОДНЫХ ПОТОКОВ В СЕТЯХ

Цель. В статье предусмотрено разработать универсальный унифицированный параллельный синхронный алгоритм, предназначенный для реализации задач по расчету максимальных однопродуктовых и многопродуктовых потоков, а также создать программный комплекс, обеспечивающий формирование плоскостных графовых моделей потоков и выполняющий оптимальное планирование неоднородных потоков в транспортных и других сетях. Методика. В работе исследованы возможности ранее созданного и всесторонне проверенного эвристического параллельного синхронного алгоритма расчета максимальных однопродуктовых и многопродуктовых потоков в сетях, установлены его потенциальные ограничения и определены дополнительные усовершенствованные процедуры, которые превращают эвристический алгоритм в универсальный параллельный. Предложенный параллельный синхронный алгоритм использует стратегию поиска в ширину при одновременном определении возможных путей потоков через сеть с оценкой их пропускных способностей. При этом исследована возможность на одной итерации выполнять параллельно анализ нескольких увеличивающих потоков по сети. Результаты. Предложен универсальный унифицированный параллельный синхронный алгоритм расчета максимальных потоков в сетях, разработана унифицированная процедура и программный комплекс для планирования неоднородных, а также конкурентных потоков в транспортных и других сетях. Разработанный программный комплекс реализует задачи по формированию плоскостных графовых моделей сетей, для которых решается задача оптимального планирования неоднородных и конкурирующих многокритериальных потоков в транспортных сетях. Научная новизна. Разработан новый универсальный унифицированный параллельный синхронный алгоритм и процедура расчета оптимальных однородных, многопродуктовых и конкурирующх потоков в транспортных сетях. Практическая значимость. Ценность полученных результатов определяется универсальными возможностями и эффективностью процедуры планирования неоднородных потоков в сетях на основе применения нового параллельного синхронного алгоритма, а также разработанным программным комплексом, который обеспечивает возможность решения задач анализа и планирования однородных и многопродуктовых потоков в транспортных сетях, реализации задач расчета конкурирующих моделей формирования транспортных и информационных потоков. Программный комплекс имеет встроенный редактор интерактивного моделирования сетей и панель инструментов, что обеспечивает как создание новых, так и загрузку существующих графов сетей из библиотек моделирования, сохранение оптимальных потоков в сети в виде изображения и в виде текстового файла, вывод ошибок при работе с программой.

Ключевые слова: транспортные сети; максимальные потоки; параллельные алгоритмы; неоднородные и конкурирующие потоки; программное обеспечение

V. V. skalozub^1*, L. а. panik^2*, A. D. Panarin^3*

^1*Dep. «Computer Information Technology», Dnipro National University of Railway Transport named after Academician
V. Lazaryan, Lazaryana St., 2, Dnipro, Ukraine, 49010, tel. (056) 373 15 35, e-mail skalozhubtk@gmail.com,
ORCID 0000-0002-1941-4751
^2*Dep. «Computer Information Technology», Dnipro National University of Railway Transport named after Academician
V. Lazaryan, Lazaryana St., 2, Dnipro, Ukraine, 49010, tel. (056) 373 15 35, e-mail leon140377@gmail.com,
ORCID 0000-0003-1343-3000
^3*Dep. «Computer Information Technology», Dnipro National University of Railway Transport named after Academician
V. Lazaryan, Lazaryana St., 2, Dnipro, Ukraine, 49010, tel. (056) 373 15 35, e-mail sashapanarin@mail.ru,
ORCID 0000-0001-9050-463X

unified PARALLEL ALGORITHM AND

PROGRAMMING COMPLEX OF

OPTIMAL PLANNING OF non-uniform

FLOWS IN the NETWORKS

Purpose. The purpose of the article is to develop a universal unified parallel synchronous algorithm for the implementation of tasks for calculation of maximum one- and multicommodity flows, as well as the creation of a software complex that provides the formation of surface graph models of flows and performs optimal planning of non-uniform flows in transport and other networks. Methodology. The paper investigates the possibilities of previously created and comprehensively verified heuristic parallel synchronous algorithm for calculating maximum one- and multicommodity flows in the networks, establishes its potential limitations, and determines additional advanced procedures that transform the algorithm into a universal parallel algorithm. The proposed parallel synchronous algorithm uses a width-first search strategy while simultaneously identifying possible paths of flows through the network with an estimation of their throughput. Herewith the possibility of analyzing several incremental flows across the network in one iteration was studied. Findings. The article proposes a universal unified parallel synchronous algorithm for calculating maximum flows in networks and develops a unified procedure and software package for planning of non-uniform as well as competitive flows in transport and other networks. The developed software complex implements the problems of formation of surface graph models of networks, for which the problem of optimal planning of non-uniform and competitive multicriteria flows in transport networks is solved. Originality. The article develops a new universal unified parallel synchronous algorithm and procedure for the calculation of optimal uniform, multicommodity and competitive flows in transport networks. Practical value. The practical value of the obtained results is determined by the universal capabilities and efficiency of the procedure for planning non-uniform flows in the networks based on the application of a new parallel synchronous algorithm, as well as the developed software complex, which provides the ability to solve the problems of analysis and planning of uniform and multicommodity flows in transport networks, as well as the implementation of calculation tasks of competitive models of transport and information flows formation. The software complex has a built-in editor of interactive network modeling and a toolbar, which provides both creation of new and downloading existing graphs of networks from the modeling libraries, preservation of optimum flows in the network in the form of an image and a text file, output of errors when working with the program.

Keywords: transport networks; maximum flows; parallel algorithms; non-uniform and competitive flows; software

references

1. Gasnikov, V. A. (2013). Vvedenie v matematicheskoe modelirovanie transportnykh potokov: Uchebnoe posobie. Moscow: MTSNMO. (in Russian)

2. Kormen, T. K., Leyzerson, C. I., Rivest, R. L., & Shtayn, K. (2011). Algoritmy: Postroenie i analiz. Moskow: Williams. (in Russian)

3. Skalozub, V. V., Tseytlin, S. Y., & Cherednichenko, M. S. (2016). Intellektualnye informatsionnye tekhnologii
   i sistemy zheleznodorozhnogo transporta: monografiya. In A. I. Mikhaleva (Ed.). Sistemnye tekhnologii modelirovaniya slozhnykh protsessov. Dnipro. (in Russian)

4. Skalozub, V. V., & Panik, L. А. (2016). The construction of generalized models for planning heterogeneous transport flows. System technologies, 5(106), 94-101. (in Russian)

5. Skalozub, V. V., & Panik, L. O. (2017). Parallel Synchronous Algorithms of Analysis and Planning of Inhomogeneous Flows in Transpotnic Networks. System technology, 5(112), 183-197. (in Ukranian)

6. Skalozub, V. V., & Panik, L. O. (2018). Implementation of the dynamic, competitive and fuzzy models for planning of the multi-product flows in transport networks. Science and Transport Progress, 3(75), 113-127. (in Russian)

7. Fillips, D. I., & Garsia-Dias, A. (1984). Metody analiza setey. Moscow: Mir. (in Russian)

8. Bozhenyuk, А. & Gerasimenko, E. (2013). Algorithm for Monitoring Minimum Cost in Fuzzy Dynamic Networks. Information Technology and Management Science, 16(1), 53-59. DOI: 10.2478/itms-2013-0008 (in English)

9. Bozhenyuk, A. V., Gerasimenko, E. M., Kacprzyk, J., & Rozenberg, I. N. (2016). Maximum and Minimum Cost Flow Finding in Networks in Fuzzy Conditions. Flows in Networks Under Fuzzy Conditions, 346, 23-75. Cham: Springer. DOI: 10.1007/978-3-319-41618-2_2 (in English)

10. Capuni, I., Zhuri, N., & Dardha, R. (2019). TimeStream: Exploiting video streams for clock synchronization. Ad Hoc Networks, 91, 236-248. DOI: 10.1016/j.adhoc.2019.101878 (in English)

11. Holzhauser, M., Krumke, S. O., & Thielen, C. (2016). Maximum flows in generalized processing networks. Journal of Combinatorial Optimization, 33(4), 1226-1256. DOI: 10.1007/s10878-016-0031-y (in English)

12. Kovacs, P. (2013). Minimum-cost flow algorithms: An experimental evaluation EGRES Technical Report. EGRES Technical Report, 4, 1-40. Retrieved from https://web.cs.elte.hu/egres/tr/egres-13-04.pdf (in English)

13. Reardon, L. (2018). Networks and problem recognition: advancing the Multiple Streams Approach. Policy Sciences, 51(4), 457-476. DOI: 10.1007/s11077-018-9330-8 (in English)

14. Rezende, P., Kianpisheh, S., Glitho, R., & Madeira, E. (2019). An SDN-Based Framework for Routing Multi-Streams Transport Traffic Over Multipath Networks. ICC 2019–2019 IEEE International Conference on Communications (ICC), 1-6. DOI: 10.1109/ICC.2019.8762061 (in English)

15. Schiopu, C., & Ciurea, E. (2016). The Maximum Flows in Planar Dynamic Networks. International Journal of Computers Communications & Control, 11(2), 282-291. DOI: 10.15837/ijccc.2016.2.2444 (in English)

16. Sifaleras, A. (2013). Minimum cost network flows: Problems, algorithms, and software. YUJOR, 23(1), 3-17. DOI: 10.2298/YJOR121120001S (in English)

Надійшла до редколегії: 02.10.2019

Прийнята до друку: 04.02.2020

Creative Commons Attribution 4.0 International

doi: 10.15802/stp2020/200748
© В. В. Скалозуб, Л. О. Панік, О. Д. Панарін, 2020