Bölgesel Talepli Yer Seçimi Problemi için Algoritmalar

2015-09-09
Dinler, Derya
Tural, Mustafa Kemal
Bu çalışmada, sürekli yer seçimi problemi üzerinde çalışılmıştır. Yer seçimi problemlerinin çoğunda talep birimleri uzayda birer nokta olarak varsayılmaktadır. Bu çalışmada ise talep birimleri bölgesel olarak tanımlanmıştır. Ele alınan problem şu şekilde özetlenebilir: verilen m tane kapalı poligonal ve/veya dairesel talep bölgesine servis sağlayacak q tane tesisin yerini ve talep bölgelerinin tesislere atanmasını tesisler ile onlara atanan talep bölgeleri arasındaki maksimum Öklit uzaklıkların ağırlıklı toplamını enazlayacak şekilde belirlemek. Bu problem çözülürken, her bir talep bölgesinin yalnızca bir tesise atanabileceği varsayımı yapılmıştır. Bahsedilen problemin hem bir tesis yeri hem de birden çoktesis yeri seçimi versiyonları için matematiksel programlama formülasyonları geliştirilmiştir. Tek tesis yeri seçimi problemi ikinci dereceden konik programlama (SOCP) problemi olarak modellenmiştir ve dolayısıyla polinom zamanda çözülebilmektedir. Ayrıca, bu problemi çözmek için çok boyutlu dolaysız arama yöntemini uyarlayan bir sezgisel yaklaşım geliştirilmiştir. Tüm talep bölgelerinin kenarları standart koordinat sistemine paralel olan dikdörtgensel alanlar olduğu durum için bu yaklaşımın yakınsadığı durumlarda optimal çözümü bulduğu gösterilmiştir. Geliştirilen çözüm yaklaşımları hem çözüm zamanı hem çözüm kalitesi açısından literatürdeki çalışmalar ile de kıyaslanmıştır. Birden çok tesis yeri seçimi problemi ise karışık tamsayılı SOCP problemi olarak modellenebilir. Büyük ölçekli problemler için bahsedilen formülasyon yetersiz kaldığından ötürü, problemi çözmek için yer seçimi-dağıtım yaklaşımı (location-allocation approach) kullanılmıştır.