Finding critical nodes in a transportation network based on constructing a closed region
- Authors: Krygin A.A.1, Kupriyanov B.V.1
-
Affiliations:
- V.A. Trapeznikov Institute of Control Sciences of RAS
- Issue: No 106 (2023)
- Pages: 271-299
- Section: Control of technological systems and processes
- URL: https://journal-vniispk.ru/1819-2440/article/view/364086
- DOI: https://doi.org/10.25728/ubs.2023.106.10
- ID: 364086
Cite item
Full Text
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.
Keywords
About the authors
Andrey Aleksandrovich Krygin
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: andreyakr@yandex.ru
Moscow
Boris Vasil'evich Kupriyanov
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: kuprianovb@mail.ru
Moscow
References
КРЫГИН А.А., КУПРИЯНОВ Б.В. Определение крити-ческих узлов транспортной сети. – М.: Изд-во «УБС»,2023. – 24 c. ЛИПСКИЙ В. Комбинаторика для программистов. – М.:«Мир», 1988. ПАПАДИМИТРИУ Х.X., СТАЙГЛИЦ К. Комбинаторнаяоптимизация. Алгоритмы и сложность. – М.: «Мир»,1982. –512 с. BELL M.G.H., CASSIR C. Reliability of Transport Networks. –Baldock, Herts: Research Studies Press, 2000. BELL M.G.H., IIDA Y. Transportation Network Analysis. –Chichester: John Wiley and Sons, 1997. BI Y.C., WILLIAM H.K., LAM A.S., QINGQUAN L. ETAL. Vulnerability analysis for large-scale and congested roadnetworks with demand uncertainty // Transportation ResearchPart A: Policy and Practice. – 2012. – Vol. 46, Iss. 3. – P.501–516. – DOI: https://doi.org/10.1016/j.tra.2011.11.018. –URL: https://www.sciencedirect.com/science/article/pii/S096585641100187X). D’ESTE G.M., TAYLOR M.A.P. Modelling networkvulnerability at the level of the national strategic transportnetwork // Journal of the Eastern Asia Society forTransportation Studies. –2001. Vol. 4(2). – P. 1–14. D’ESTE G.M., TAYLOR M.A.P. Network vulnerability: anapproach to reliability analysis at the level of national strategictransport networks // In: The Network Reliability of Transport /Eds.: Y. Iida, M.G.H. Bell. – Oxford: Pergamon-Elsevier,2003. – P. 23–44. ESFEH M.A., KATTAN L., WILLIAM H.K., LAM M.S.ET AL. Road network vulnerability analysis consideringthe probability and consequence of disruptive events:A spatiotemporal incident impact approach // TransportationResearch Part C: Emerging Technologies. – 2021. – Vol. 136. –297Управление большими системами. Выпуск 106103549 – DOI: https://doi.org/10.1016/j.trc.2021.103549. –URL: https://www.sciencedirect.com/science/article/pii/S0968090X21005313. GUZE S. Graph Theory Approach to the Vulnerability ofTransportation Networks // Algorithms. – 2019. – Vol. 12(12). –P. 270. JENELIUS E., PETERSEN T., MATTSSON L.G.Importance and exposure in road network vulnerabilityanalysis // Transportation Research Part A: Policy andPractice. – 2006. – Vol. 40, Iss. 7. – P. 537–560. –DOI: https://doi.org/10.1016/j.tra.2005.11.003. – URL: https://www.sciencedirect.com/science/article/pii/ S096585640500162X . JENELIUS E., PETERSEN T., MATTSSON L-G. Importanceand exposure in road network vulnerability analysis //Transportation Research Part A Policy and Practice. – February2006. – Vol. 40(7). – P. 537–560. NEUMANN T., BEHRISCH M. Terminal reliability of roadnetworks with multiple destination options // Int. J. of Safetyand Security Eng. – 2018. – Vol. 8, No. 3. – P. 426–437. SUGIURA S., KURAUCHI F. Isolation vulnerabilityanalysis in road network: Edge connectivity andcritical link sets // Transportation Research Part D:Transport and Environment. – 2023. – Vol. 119. –P. 103768. – DOI: https://doi.org/10.1016/j.trd.2023.103768. –URL: https://www.sciencedirect.com/science/article/pii/S1361920923001657. VIVEK S., CONNER H. Urban road networkvulnerability and resilience to large-scale attacks //Safety Science. – 2022. – Vol. 147. – P. 105575. – DOI:https://doi.org/10.1016/j.ssci.2021.105575. – URL: https://www.sciencedirect.com/science/article/pii/S0925753521004173. WANG S., CHEN C., ZHANG J., GU X., HUANG X.Vulnerability assessment of urban road traffic systems basedon traffic flow // Int. Journal of Critical Infrastructure298Управление техническими системами и технологическими процессамиProtection. – 2022. – Vol. 38. – P. 100536. – DOI:https://doi.org/10.1016/j.ijcip.2022.100536. – URL: https://www.sciencedirect.com/science/article/pii/S1874548222000269.
Supplementary files
