In this thesis, we focus on the problem of location and protection planning of critical facilities. This problem involves a Stackelberg game between a system planner (defender) and a potential attacker. The system planner aims to both find the locations of p critical service facilities and determine the ones among them that should be protected. Following this twofold action, the attacker decides which facilities to interdict having the location and protection information of the opened facilities. This problem involves strategic decisions which can be taken either sequentially or simultaneously. In this study, we consider both of these cases. In the first case, the system planner first decides on the locations and then determines the protection plan of these facilities. In the second case however, the system planner gives concurrent decisions about location and protection of the facilities. Both cases are of a bilevel nature. Therefore, we formulate this problem as a bilevel mixed-integer programming problem. We propose two solution methods. The first one is a two-phase tabu search heuristic for the case which involves concurrent decision process and a sequential solution method for the second case where the system planner prefers to give sequential decisions. Both of the methods include a binary search tree embedded into it. The efficiency of the proposed algorithms is tested on an extensive amount of randomly generated test instances each with two budget levels, namely low and high.We also consider another case where the system planner does not have any financial resources to protect the facilities from an attack. This line of vision helps system planner to determine the critical facilities from the attacker?s perspective. The results show that the protection budget plays a significant role in maintaining the service accessibility after a possible attack.

Bu tez çalışmasında, kritik tesisler için yerseçimi ve koruma planlaması problemi üzerinde çalışılmıştır. Bu problem, bir sistem planlamacı (koruyucu) ve potansiyel saldırgan arasında gerçekleşen statik Stackelberg oyunu içerir. Sistem planlamacı, p kritik hizmet tesisinin yerseçimini yapmayı ve hangilerinin korunması gerektiğini belirlemeyi amaçlar. Bu iki aşamalı eylem gerçekleştikten sonra, tesislerin yerleşimi ve koruma durumları bilgisine sahip olan saldırgan, saldıracağı tesisleri belirler. Bu karar verme problemi, ardışık veya eş-zamanlı verilebilen stratejik ve taktiksel kararlar içerir. Bu çalışmada, bahsedilen her iki durum da göz önünde bulundurulmuştur. İlk durumda, sistem planlamacı öncelikle açılacak tesislerin yerlerine karar verir ve daha sonra bu tesisler için bir koruma planı hazırlar. İkinci durumda ise, sistem planlamacı tesislerin yerseçimi ve koruma planlamasını yaparken eş-zamanlı kararlar alır. Her iki durumda da problem, çift-düzeyli bir yapıya sahiptir. Bu nedenle, problem çift-düzeyli karışık-tamsayılı matematiksel programlama olarak modellenmiştir. Değişkenlerin sürekli olduğu durumda bile çift-düzeyli problemlerin çözümü oldukça zordur ve etkili algoritmalara ihtiyaç duyulur. Bu sebeple, problemin çözümünde sistem planlamacının eş-zamanlı karar verdiği durum için iki aşamalı Tabu Arama sezgiseli, ardışık kararların alındığı durum için ise bir sıralı çözüm yöntemi önerilmiştir. Önerilen her iki metod da çift-düzeyli problemin çözümünde ikili arama ağacı algoritmasından yararlanmaktadır. Algoritmaların testi, rassal olarak üretilen problemler üzerinde değişik koruma bütçesi miktarları kullanılarak denenmiş ve sonuçlar alınmıştır.Bu çalışmada ayrıca sistem planlamacının koruma bütçesine sahip olmadığı durum da incelenmiştir. Probleme bir de bu açıdan yaklaşılarak, saldırganın gözünden sistemdeki kritik tesislerin tespiti yapılmış olmaktadır. Elde edilen sonuçlar göstermektedir ki; koruma bütçesi saldırı sonrası hizmet verebilirliği devam ettirmede önemli bir role sahiptir.