Kentsel Yol Ağlarında Kritik Kenar Tespiti için Etkin Bir Algoritma

Year 2025, Volume: 15 Issue: 3, 744 - 754, 01.09.2025

Yeşim Aygül , Onur Uğurlu , Vahid Akram , Deniz Türsel Eliiyi

https://doi.org/10.21597/jist.1569294

Abstract

Bu çalışma, trafik ağlarının etkin yönetimi ve optimizasyonu için önemli bir problem olan Kritik Kenar Problemine odaklanmaktadır. Kritik Kenar Problemi, ağdan çıkarılması ile ağın bağlantısallığına en çok zarar verecek kenar kümesini belirlemeyi amaçlayan bir optimizasyon problemidir. Kritik Kenar Problemi trafik yönetimi, acil durum müdahaleleri, altyapı yatırımları ve ağ dayanıklılığını artırma gibi çok sayıda önemli uygulama alanına sahiptir. Bu çalışmanın temel motivasyonu özellikle büyük ölçekli gerçek hayat ağları üzerinde verimli bir şekilde kullanılabilecek yeni bir polinom zamanlı algoritmanın geliştirilmesidir. Geliştirilen algoritmanın efektifliği küçük ölçekli ağlar üzerinde klasik kaba-kuvvet yaklaşımıyla elde edilen optimal sonuçlarla karşılaştırılarak test edilmiştir. Önerilen yöntem, trafik sıkışıklığını azaltma, seyahat sürelerini kısaltma ve çevresel etkileri minimize etme gibi çeşitli kentsel zorluklarla başa çıkma potansiyeli taşımaktadır. Bu araştırma, büyük ölçekli trafik ağlarının anlaşılmasını ve verimli ulaşım sistemlerinin geliştirilmesini teşvik etmek için etkin bir yaklaşım sunmaktadır.

Keywords

Trafik ağları , Ağ analizi , Kritik kenarlar , Ağ algoritmaları

Supporting Institution

TÜBİTAK

Project Number

121F092

An Effective Algorithm for Critical Edge Detection in Urban Road Networks

Abstract

This study focuses on the Critical Edge Problem, which is an important problem for effectively managing and optimizing traffic networks. The Critical Edge Problem is an optimization problem that aims to determine the set of edges whose removal from the network will cause the most damage to the network's connectivity. The Critical Edge Problem has many important application areas, such as traffic management, emergency responses, infrastructure investments, and increasing network resilience. The primary motivation of this study is the development of a new polynomial-time algorithm that can be used efficiently, especially on large-scale real-life networks. The effectiveness of the developed algorithm was tested by comparing it with the optimal results obtained by classical brute-force approaches on small-scale networks, and the theoretical foundations and practical applications of the algorithm were comprehensively examined. The proposed method has the potential to tackle various urban challenges, such as reducing traffic congestion, shortening travel times, and minimizing environmental impacts. This research provides an effective method to promote the understanding of large-scale traffic networks and the development of efficient transportation systems.

Keywords

Traffic networks , Network analysis , Critical edges , Graph algorithms

Supporting Institution

TUBITAK

Project Number

121F092

References

• Bazgan, C., Toubaline, S., & Vanderpooten, D. (2013). Critical edges for the assignment problem: Complexity and exact resolution. Operations Research Letters, 41(6), 685-689.
• Brinkmeier, M. (2007). A simple and fast min-cut algorithm. Theory of Computing Systems, 41(2), 369-380.
• Diestel, R. (2012). Graph theory (4th ed.). Graduate Texts in Mathematics. Springer.
• Dinh, T.N., & Thai, M.T. (2011). Precise structural vulnerability assessment via mathematical programming. In Military Communications Conference, 2011-MILCOM 2011, IEEE (pp. 1351–1356).
• Eren, T., & Akdaş, E. (2023). Afet ve acil durum yönetiminde arama kurtarma ekiplerinin oluşturulması. Afet ve risk dergisi, 6(3), 1060-1073.
• Gauthier, P., Furno, A., & El Faouzi, N. E. (2018). Road network resilience: how to identify critical links subject to day-to-day disruptions. Transportation research record, 2672(1), 54-65.
• Grubesic, T.H., Matisziw, T.C., Murray, A.T., & Snediker, D. (2008). Comparative approaches for assessing network vulnerability. International Regional Science Review, 31(1), 88–112.
• Houck, D.J., Kim, E., O'Reilly, G.P., Picklesimer, D.D., & Uzunalioglu, H. (2004). A network survivability model for critical national infrastructures. Bell Labs Technical Journal, 8(4), 153–172.
• Jenelius, E., Petersen, T., & Mattsson, L.G. (2006). Importance and exposure in road network vulnerability analysis. Transportation Research Part A: Policy and Practice, 40(7), 537–560.
• Jilani, U., Asif, M., Zia, M. Y. I., Rashid, M., Shams, S., & Otero, P. (2023). A systematic review on urban road traffic congestion. Wireless Personal Communications, 1-29.
• Karimi, H., Ghadirifaraz, B., Shetab Boushehri, S. N., Hosseininasab, S. M., & Rafiei, N. (2021). Reducing traffic congestion and increasing sustainability in special urban areas through one-way traffic reconfiguration. Transportation, 1-24.
• Lalou, M., Tahraoui, M.A., & Kheddouci, H. (2018). The critical node detection problem in networks: A survey. Computer Science Review, 28, 92-117.
• Minh, Q. T., Le Hoang, H. N., & Nhat, M. N. (2022). Effective traffic routing for urban transportation capacity and safety enhancement. IATSS Research, 46(4), 574-585.
• Nagamochi, H., Ono, T., & Ibaraki, T. (1994). Implementing an efficient minimum capacity cut algorithm. Mathematical Programming, 67, 325–341.
• Pana-Micu, F. (2024). Graph theory algorithms in optimizing urban infrastructure in smart cities. In Proceedings of the Central and Eastern European eDem and eGov Days 2024 (pp. 125-129).
• Rashmi, R., Champawat, S., Varun Teja, G., & Lavanya, K. (2020). Analysis of road networks using the louvian community detection algorithm. In Soft Computing for Problem Solving: SocProS 2018, Volume 2 (pp. 749-757). Springer Singapore.
• Salmeron, J., Wood, K.R., & Baldick, R. (2004). Analysis of electric grid security under terrorist threat. IEEE Transactions on Power Systems, 19(2), 905–912.
• Smith, J.C., Prince, M., & Geunes, J. (2013). Modern network interdiction problems and algorithms. In Handbook of combinatorial optimization (pp. 1949-1987).
• Smith, J.C., & Song, Y. (2019). A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3), 797-811.
• Stoer, M., & Wagner, F. (1997). A simple min-cut algorithm. Journal of the ACM, 44(4), 585–591.
• Tekgöz, H., Kolukısa, N., & Karabatak, M. (2022). Trafik Işıklarının Optimum Planlaması için Çizge Tabanlı Çözüm Önerisi. Fırat Üniversitesi Mühendislik Bilimleri Dergisi, 34(1), 15-23.
• Walteros, J.L., & Pardalos, P.M. (2012). Selected topics in critical element detection. In Applications of mathematics and informatics in military science (pp. 9-26).
• Yu, E. Y., Chen, D. B., & Zhao, J. Y. (2018). Identifying critical edges in complex networks. Scientific reports, 8(1), 14469.