Akış Tabanlı P-Hub Ortanca Engelleme Problemi

Abstract

Serim önleme/kesme problemlerinde, bir serim üzerinde tanımlı bir sistemi optimal şekilde işletmeye çalışan bir serim kullanıcısı ile sistemin optimal çalışmasını engellemeye çalışan bir rakip/saldırgan olmak üzere iki oyuncu vardır. Problem, Stackelberg Oyunu mantığı içerisinde, iki seviyeli minimaks veya maksimin problemi olarak modellenebilir. Bu çalışmada, serim kesme problemi, p-hub ortanca problemi kapsamında ele alınmıştır. Serim kullanıcısının, maliyeti minimize edecek şekilde ana dağıtım üssü yer seçimi problemi çözdüğü; rakibin ise, sınırlı kaynaklar ile ana dağıtım üslerini kullanılamaz hale getirerek minimum maliyeti maksimize etmeye çalıştığı kabul edilmiştir. Serim kullanıcısın p-hub ortanca problemi, gerçek serim yapıları üzerinde ve akış tabanlı olarak modellenmiştir. Geliştirilen model, daha önceki çalışmalardan farklı olarak, tam serim yapısı gerektirmemekte ve üçgen eşitsizliğini sağlamayan durumlarda da doğru çözüm vermektedir. Önerilen modelin, hem çözüm zamanları hem de modelleme yetenekleri açısından literatürdeki tesis yeri seçimi önleme modellerine göre önemli avantajlar sunduğu görülmüştür.

There are two players in a network interdiction problem: a network user who wishes to operate a system optimally, and an opponent/interdictor who tries to prevent the system from operating optimally. Interdiction problems can be modeled as a bi-level min-max or max-min problem in the Stackelberg Game logic. In this thesis, we handle the interdiction problem within the context of the p-hub median problem. The network user solves the problem of locating p hubs to minimize the cost associated with operating the network. In response to the network user, the interdictor tries to maximize network user's cost by removing hub characteristics of effective hubs with its limited resources. The p-hub median problem of the network user is modeled on the flow-based networks. The model we develop in this study, unlike the previous literature, does not require the complete network and enables one to find the correct solution in cases that do not provide triangle inequality between nodes. Therefore, this new model provides significant advantages regarding the solution times and modeling capabilities compared to the facility interdiction models offered by the literature.