УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта

јвтор:   рыгин ј.ј.,  упри€нов Ѕ.¬.
Ќазвание:  Ќахождение критических узлов транспортной сети на†основе построени€ замкнутой области
—татус:  опубликовано
»здательство:  »ѕ” –јЌ
√од:  2023
“ип:  стать€ вед.журн.
Ќазвание журнала:  ”правление большими системами
¬ыпуск:  106
Ѕиблиографи€:   рыгин ј.ј.,  упри€нов Ѕ.¬. Ќахождение критических узлов транспортной сети на†основе построени€ замкнутой области // ”правление большими системами. ¬ыпуск 106. ћ.: »ѕ” –јЌ, 2023. —.271-299. DOI: https://doi.org/10.25728/ubs.2023.106.10
–убрика:  ”правление техническими системами и†технологическими процессами
 лючевые слова:  транспортные сети, поиск критических узлов
 лючевые слова (англ.):  transport networks, critical object search
јннотаци€:  –ассматриваетс€ задача поиска критических узлов транспортной сети, решаема€ с помощью максимизации обобщенной стоимости проезда, котора€ зависит от потребности в движении и стоимости поездки между каждой парой узлов сети. ѕредлагаемый в работе метод €вл€етс€ улучшением полного перебора, основна€ сложность которого состоит в многократном вычислении матрицы минимальных стоимостей поездок. ћетод заключаетс€ в выделении замкнутого в определенном смысле множества вершин исходного графа. ¬ыделение замкнутого множества вершин графа позвол€ет осуществить редуцирование графа, декомпозицию соответствующих ему матриц и раздельные вычислени€ подматриц. ƒанные преобразовани€ позволили сократить вычислени€ при переборе вариантов. ѕостроен общий алгоритм нахождени€ критических узлов и проведена его оптимизаци€. «амкнутое множество разделено на внутреннее и граничное подмножества. ѕоказано, что алгоритм работает наиболее быстро при минимальной мощности граничного подмножества и оптимальной мощности внутреннего подмножества, дл€ определени€ которой предложен соответствующий алгоритм. “акже предложен алгоритм построени€ и расширени€ замкнутого множества. на его основе построен приближенный алгоритм нахождени€ оптимального замкнутого множества. ѕоказано, что сложность нахождени€ оптимального замкнутого множества во много раз меньше сложности улучшенного метода полного перебора.
јннотаци€ (англ.):  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.

¬ формате PDF

ѕросмотров: 112, загрузок: 27, за мес€ц: 3.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены