Haberleşme ve ulaşım ağlarında röle yerleştirme problemleri

Haberleşme ağlarında optik sinyallerin menzillerini artıran yenileyiciler, ulaşım ağlarında yüklerin, sürücülerin yada ulaştırma vasıtalarının değiştirildiği stratejik olarak seçilmiş noktalar, alternatif yakıt ile çalışan araçların uzun mesafeli yolculuklarını tamamlayabilmeleri için yol ağları üzerine yerleştirilen dolum istasyonları rölelerin değişik uygulama alanlarındaki kullanımlarına birer örnek teşkil etmektedir. Röleler değişik isimler ve fonksiyonlarla birçok haberleşme ve ulaşım ağının temel birer parçasıdır ve rölelerin ağlarda en iyi yerlerinin bulunması birçok uygulama alanında önemli bir problem olarak ortaya çıkmaktadır. Bu çalışmada, yazında yer alan değişik röle yerleştirme problemleri ele alınmış, yeni problemler tanıtılmış ve bu problemlerin ̧çözümü için etkin kesin çözüm yöntemleri önerilmiştir. Bu tez çalışmasında, röle yerleştirme problemlerine değişik ağ topolojileri, kapasiteleri, maliyetleri ve talep durumları perspektiflerinden yaklaşılarak önemli teorik sonuçlar elde edilmiştir. Röle yerleştirme problemlerini temel olarak diğer problemlerden ayıran ve çözümünü zorlaştıran ana husus ele alınan varlıkların ağdaki hareketini sınırlayan menzil kısıtlarıdır. Önerdiğimiz yol-parçacığı tabanlı formülasyonlar ile söz konusu menzil kısıtlarının ve oluşturulacak rotalar için ön görülecek daha genel sınırlandırmaların doğrudan ve etkin bir şekilde modellenmesi mümkün olmaktadır. Yol parçacığı tabanlı formülasyonların esnek yapıları kullanılarak değişik uygulamalarda ortaya çıkan ve bir birinden farklı özellikleri barındıran röle yerleştirme problemleri için etkin çözüm yöntemleri sunulmuştur. Gerçekçi problem örnekleri üzerinde yapılan kapsamlı hesapsal çalışmalar önerdiğimiz bu özgün yaklaşım ile geliştirdiğimiz kesin çözüm yöntemlerinin hesapsal performansının literatürde var olan en iyi sezgisel algoritmalar ile yarışabilecek seviyede olduğunu göstermektedir.