Нахождение критических узлов транспортной сети на основе построения замкнутой области
- Авторы: Крыгин А.А.1, Куприянов Б.В.1
-
Учреждения:
- ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
- Выпуск: № 106 (2023)
- Страницы: 271-299
- Раздел: Управление техническими системами и технологическими процессами
- URL: https://ogarev-online.ru/1819-2440/article/view/364086
- DOI: https://doi.org/10.25728/ubs.2023.106.10
- ID: 364086
Цитировать
Полный текст
Аннотация
Рассматривается задача поиска критических узлов транспортной сети, решаемая с помощью максимизации обобщенной стоимости проезда, которая зависит от потребности в движении и стоимости поездки между каждой парой узлов сети. Предлагаемый в работе метод является улучшением полного перебора, основная сложность которого состоит в многократном вычислении матрицы минимальных стоимостей поездок. Метод заключается в выделении замкнутого в определенном смысле множества вершин исходного графа. Выделение замкнутого множества вершин графа позволяет осуществить редуцирование графа, декомпозицию соответствующих ему матриц и раздельные вычисления подматриц. Данные преобразования позволили сократить вычисления при переборе вариантов. Построен общий алгоритм нахождения критических узлов и проведена его оптимизация. Замкнутое множество разделено на внутреннее и граничное подмножества. Показано, что алгоритм работает наиболее быстро при минимальной мощности граничного подмножества и оптимальной мощности внутреннего подмножества, для определения которой предложен соответствующий алгоритм. Также предложен алгоритм построения и расширения замкнутого множества. на его основе построен приближенный алгоритм нахождения оптимального замкнутого множества. Показано, что сложность нахождения оптимального замкнутого множества во много раз меньше сложности улучшенного метода полного перебора.
Ключевые слова
Об авторах
Андрей Александрович Крыгин
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: andreyakr@yandex.ru
Москва
Борис Васильевич Куприянов
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: kuprianovb@mail.ru
Москва
Список литературы
КРЫГИН А.А., КУПРИЯНОВ Б.В. Определение крити-ческих узлов транспортной сети. – М.: Изд-во «УБС»,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.
Дополнительные файлы
