Уніфікований паралельний алгоритм та програмний комплекс оптимального планування неоднорідних потоків у мережах
Loading...
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Дніпровський національний університет залізничного транспорту імені академіка В. Лазаряна, Дніпро
Abstract
UKR: Мета. У статті передбачено розробити універсальний уніфікований паралельний синхронний алгоритм (УПСА), призначений для реалізації завдань із розрахунку максимальних однопродуктових і багатопродуктових потоків, а також створити програмний комплекс, який забезпечує формування площинних графових моделей потоків та виконує оптимальне планування неоднорідних потоків у транспортних та інших мережах. Методика. У роботі досліджено можливості раніше створеного та всебічно перевіреного евристичного паралельного синхронного алгоритму розрахунку максимальних однопродуктових і багатопродуктових потоків у мережах, встановлено його потенційні обмеження й визначено додаткові вдосконалені процедури, які перетворюють евристичний алгоритм в універсальний паралельний. Запропонований паралельний синхронний алгоритм використовує стратегію пошуку в ширину за одночасного визначення можливих шляхів потоків через мережу з оцінкою їх пропускних здатностей. При цьому досліджено можливість на одній ітерації виконувати паралельно аналіз декількох збільшувальних потоків через мережу. Результати. Запропоновано універсальний уніфікований паралельний синхронний алгоритм розрахунку максимальних потоків у мережах, розроблено уніфіковану процедуру та програмний комплекс для планування неоднорідних, а також конкурувальних потоків у транспортних та інших мережах. Розроблений програмний комплекс реалізує завдання щодо формування площинних графових моделей мереж, для яких вирішується завдання оптимального планування неоднорідних та конкурувальних багатокритеріальних потоків у транспортних мережах. Наукова новизна. Розроблено новий універсальний уніфікований паралельний синхронний алгоритм та процедуру розрахунку оптимальних однорідних, багатопродуктових та конкурувальних потоків у транспортних мережах. Практична значимість. Цінність отриманих результатів визначається універсальними можливостями та ефективністю процедури планування неоднорідних потоків у мережах на основі застосування нового паралельного синхронного алгоритму, а також розробленим програмним комплексом, який забезпечує можливість вирішення завдань аналізу і планування однорідних та багатопродуктових потоків у транспортних мережах, реалізації завдань розрахунку конкурентних моделей формування транспортних та інформаційних потоків. Програмний комплекс має вбудований редактор інтерактивного моделювання мереж та панель інструментів, що забезпечує як створення нових, так і завантаження наявних графів мереж із бібліотек моделювання, збереження оптимальних потоків у мережі у вигляді зображення та у вигляді текстового файлу, виведення помилок під час роботи з програмою.
RUS: Цель. В статье предусмотрено разработать универсальный унифицированный параллельный синхронный алгоритм, предназначенный для реализации задач по расчету максимальных однопродуктовых и многопродуктовых потоков, а также создать программный комплекс, обеспечивающий формирование плоскостных графовых моделей потоков и выполняющий оптимальное планирование неоднородных потоков в транспортных и других сетях. Методика. В работе исследованы возможности ранее созданного и всесторонне проверенного эвристического параллельного синхронного алгоритма расчета максимальных однопродуктовых и многопродуктовых потоков в сетях, установлены его потенциальные ограничения и определены дополнительные усовершенствованные процедуры, которые превращают эвристический алгоритм в универсальный параллельный. Предложенный параллельный синхронный алгоритм использует стратегию поиска в ширину при одновременном определении возможных путей потоков через сеть с оценкой их пропускных способностей. При этом исследована возможность на одной итерации выполнять параллельно анализ нескольких увеличивающих потоков по сети. Результаты. Предложен универсальный унифицированный параллельный синхронный алгоритм расчета максимальных потоков в сетях, разработана унифицированная процедура и программный комплекс для планирования неоднородных, а также конкурентных потоков в транспортных и других сетях. Разработанный программный комплекс реализует задачи по формированию плоскостных графовых моделей сетей, для которых решается задача оптимального планирования неоднородных и конкурирующих многокритериальных потоков в транспортных сетях. Научная новизна. Разработан новый универсальный унифицированный параллельный синхронный алгоритм и процедура расчета оптимальных однородных, многопродуктовых и конкурирующх потоков в транспортных сетях. Практическая значимость. Ценность полученных результатов определяется универсальными возможностями и эффективностью процедуры планирования неоднородных потоков в сетях на основе применения нового параллельного синхронного алгоритма, а также разработанным программным комплексом, который обеспечивает возможность решения задач анализа и планирования однородных и многопродуктовых потоков в транспортных сетях, реализации задач расчета конкурирующих моделей формирования транспортных и информационных потоков. Программный комплекс имеет встроенный редактор интерактивного моделирования сетей и панель инструментов, что обеспечивает как создание новых, так и загрузку существующих графов сетей из библиотек моделирования, сохранение оптимальных потоков в сети в виде изображения и в виде текстового файла, вывод ошибок при работе с программой.
ENG: 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 builtin 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.
RUS: Цель. В статье предусмотрено разработать универсальный унифицированный параллельный синхронный алгоритм, предназначенный для реализации задач по расчету максимальных однопродуктовых и многопродуктовых потоков, а также создать программный комплекс, обеспечивающий формирование плоскостных графовых моделей потоков и выполняющий оптимальное планирование неоднородных потоков в транспортных и других сетях. Методика. В работе исследованы возможности ранее созданного и всесторонне проверенного эвристического параллельного синхронного алгоритма расчета максимальных однопродуктовых и многопродуктовых потоков в сетях, установлены его потенциальные ограничения и определены дополнительные усовершенствованные процедуры, которые превращают эвристический алгоритм в универсальный параллельный. Предложенный параллельный синхронный алгоритм использует стратегию поиска в ширину при одновременном определении возможных путей потоков через сеть с оценкой их пропускных способностей. При этом исследована возможность на одной итерации выполнять параллельно анализ нескольких увеличивающих потоков по сети. Результаты. Предложен универсальный унифицированный параллельный синхронный алгоритм расчета максимальных потоков в сетях, разработана унифицированная процедура и программный комплекс для планирования неоднородных, а также конкурентных потоков в транспортных и других сетях. Разработанный программный комплекс реализует задачи по формированию плоскостных графовых моделей сетей, для которых решается задача оптимального планирования неоднородных и конкурирующих многокритериальных потоков в транспортных сетях. Научная новизна. Разработан новый универсальный унифицированный параллельный синхронный алгоритм и процедура расчета оптимальных однородных, многопродуктовых и конкурирующх потоков в транспортных сетях. Практическая значимость. Ценность полученных результатов определяется универсальными возможностями и эффективностью процедуры планирования неоднородных потоков в сетях на основе применения нового параллельного синхронного алгоритма, а также разработанным программным комплексом, который обеспечивает возможность решения задач анализа и планирования однородных и многопродуктовых потоков в транспортных сетях, реализации задач расчета конкурирующих моделей формирования транспортных и информационных потоков. Программный комплекс имеет встроенный редактор интерактивного моделирования сетей и панель инструментов, что обеспечивает как создание новых, так и загрузку существующих графов сетей из библиотек моделирования, сохранение оптимальных потоков в сети в виде изображения и в виде текстового файла, вывод ошибок при работе с программой.
ENG: 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 builtin 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.
Description
В. Скалозуб: ORCID 0000-0002-1941-4751; Л. Панік: ORCID 0000-0003-1343-3000; О. Панарін: ORCID 0000-0001-9050-463X
Keywords
транспортні мережі, максимальні потоки, паралельні алгоритми, неоднорідні та конкурувальні потоки, програмне забезпечення, транспортные сети, максимальные потоки, параллельные алгоритмы, неоднородные и конкурирующие потоки, программное обеспечение, transport networks, maximum flows, parallel algorithms, non-uniform and competitive flows, software, КІТ
Citation
Скалозуб В. В., Панік Л. О., Панарін О. Д. Уніфікований паралельний алгоритм та програмний комплекс оптимального планування неоднорідних потоків у мережах. Наука та прогрес транспорту. 2020. № 1 (85). С. 56–67. DOI: 10.15802/stp2020/200748.