Ulaştırma ve Lojistik Kongreleri

Ayrıt Kapasiteli Akış Ağlarında Lokal Korumalı Ağ Kırılma Problemi

Gökhan Karaköse
Dr. Öğr. Üyesi, Bartın Üniversitesi, Bartın, Türkiye

Ulaşım ağları toplumun refah seviyesine katkı sağladığı, tıbbı bakım gibi insanların kritik ihtiyaçların karşılanmasına olanak sağladığı için çok önemlidir. Bu ağlar deprem gibi rassal yıkımlar veya terörizm gibi kasıtlı saldırılara karşı korunmasız olabilmektedir. Genellikle elimizdeki kaynaklar kısıtlı olduğundan (bütçe, insan kaynakları gibi), ulaşım ağlarının korunması ve restorasyon işlemleri için kaynakların optimal kullanımı önemlidir. Fakat, sadece savunucular değil saldırganlarda ağın kritik bileşenlerini tespit etmekle ilgilenirler. Burada, saldırganlar ağın performansını düşürmek isterken, savunucular ağ kırılma olayı durumunda ağ performansını korumayı amaçlar. Oyun teorisi perspektifinde, biz her biri kendi sınırlı kaynaklarını kullanarak kendi amacını optimize etmek isteyen hem saldırganı hem de savunucuyu aynı anda modelliyoruz. Bu çalışmada, problemi üç oyunculu bir oyun olarak görüyoruz. İç problemde, bir ağ yöneticisi, kapasite kısıtlaması nedeniyle kayıp akış oluşmaması için ayrıt kapasiteli ağdaki akışları yönlendirmek ister. Orta düzeyde bir saldırgan, bir dizi düğümü kırarak ağdaki en zararlı olayı oluşturmak için sınırlı kaynaklarını en iyi şekilde kullanmayı amaçlar. Üst seviyede, sınırsız kaynaklarını her zaman saldırıya uğramış yerlerin mahallelerine (yani, saldırıya uğramış düğümlerin bitişik düğümlerine) yerleştiren bir savunucu vardır. Saldırganın, savunucunun yerel koruma gerçekleştirmesine dayanarak saldırı planını düzenlediği göz önüne alındığında, bu çalışma, ayrıt kapasiteli akış ağlarında yerel korumalı ağ kırılma problemi olan yeni bir problemi incelemektedir. Bu problemde, saldırgan, savunucunun saldırıya uğrayan düğümlerin komşularını koruyarak yerel alana müteakip saldırıyı ortadan kaldırmak amacıyla derhal harekete geçtiğini varsayarak, ayrıt kapasiteli bir akış ağında en yüksek kayıp akışını oluşturmak için p kadar düğümü kırmayı amaçlamaktadır. Sorunu çözmek için başlangıçta tek seviyeli bir optimizasyon modeli geliştirilmiştir ve daha sonra yeni bir formülasyon tanıtılmıştır. Hesaplama testleri, yeni formülasyonun, ilk formülasyona kıyasla en uygun çözümü elde etmek için gereken çözüm süresini önemli ölçüde azalttığını göstermiştir.

Anahtar Kelimeler: Akış Ağları, Ağ Kırma, Optimizasyon

The Network Interdiction Problem With Local Protection On Arc-Capacitated Flow Networks

Transportation networks are crucial as they support the well-being of society and enable people to meet their critical needs, such as medical care. Such networks can be vulnerable to random disruptions such as earthquake or intentional disruptions such as terrorism. In general, since the resources at hand are limited (e.g., budget, human resources), it is important to optimally utilize the resources for the protection and restoration processes of the transportation networks. However, not only defenders but also attackers are interested in detecting the critical components of the network. Here, the attackers wish to degrade the performance of the network whereas the defenders aim at preserving the network performance in the event of the network disruption. In game theoretic perspective, we simultaneously model both the attacker and the defender, each wishes to optimize his own objective function by use of his own limited resources. In this work, we consider problem as a game, with three players. In the inner problem, a network manager wants to direct flows on arc-capacitated network so that there is no lost flow occurred due to the capacity restriction. In the middle level, an attacker aims to optimally use his limited resources to post the most damaging event on the network by interdicting a set of nodes. In the upper level, there is a defender who always locates his unlimited resources to the neighborhoods of the attacked places (i.e., the adjacent nodes of the attacked nodes). Given that the attacker arranges his interdiction plan based on the fact that the defender performs a local protection, this work studies a novel problem, the network interdiction problem with local protection on arc-capacitated flow networks. In this problem, the interdictor aims to interdict p number of nodes to pose the highest lost flow on an arc-capacitated flow network while assuming the defender immediately acts for the purpose of eliminating subsequent attack on the local area by protecting the neighbors of the attacked nodes. To solve the problem, one-level optimization model is initially developed, and later a reformulation is introduced. Computational tests showed that the reformulation significantly decreases the solution time needed to obtain the optimal solution compared to the first formulation.

Keywords: Flow Networks, Optimization, Network Interdiction