Нахождение критических узлов транспортной сети на основе построения замкнутой области

Автор(ы): Крыгин А.А., Куприянов Б.В.

Выпуск: 106

Рубрика: Управление техническими системами и технологическими процессами

Год: 2023

Библиография: Крыгин А.А., Куприянов Б.В. Нахождение критических узлов транспортной сети на основе построения замкнутой области // Управление большими системами. Выпуск 106. М.: ИПУ РАН, 2023. С.271-299. DOI: https://doi.org/10.25728/ubs.2023.106.10

Дата опубликования: 30.11.2023

Ключевые слова: транспортные сети, поиск критических узлов

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

Author(s): Krygin A., Kupriyanov B.

Article title: Finding critical nodes in a transportation network based on constructing a closed region

Issue: 106

Year: 2023

Keywords: transport networks, critical object search

Abstract: The problem of finding critical nodes in a transportation network is considered, which is solved by maximizing the generalized cost of travel, which depends on the demand for movement and the cost of travel between each pair of network nodes. The proposed method in the paper is an improvement of exhaustive search, the main difficulty of which lies in the repeated computation of the matrix of minimum travel costs. The method consists of extracting a closed set of vertices from the original graph. The extraction of a closed set of vertices allows for graph reduction, decomposition of the corresponding matrices, and separate computations of sub-matrices. These transformations have helped reduce computations during the search for options. A general algorithm for finding critical nodes has been constructed and optimized. The closed set is divided into an internal and boundary subset. It has been shown that the algorithm works fastest with a minimum size of the boundary subset and an optimal size of the internal subset, for which a corresponding algorithm has been proposed to determine. An algorithm for constructing and expanding the closed set is also proposed, based on which an approximate algorithm for finding the optimal closed set is constructed. It has been shown that the complexity of finding the optimal closed set is much lower than the complexity of the improved exhaustive search method.