Çatışma kısıtlı ağ akışları

Telekomünikasyon, kablosuz ağlar, taşımacılık, tıp ve sağlık hizmetleri, çizelgeleme gibi alanlarda karşımıza çıkan birçok problemi ağ akış problemleri olarak modellemek yaygın bir yaklaşımdır. Bu tez bağlamında odaklanılan ise, ağ akış problemlerinin belirli okların aynı anda akış taşımasını engelleyen çatışma kısıtlı uzantısıdır. Ele alınan problemlerin bazıları daha önceden yazında var olan, bazıları da ilk defa bu tezde çalışılmış katmanlı ağlarda en küçük maliyetli kesişmeyen akış problemi, çatışma kısıtlı en küçük maliyetli akış problemi, çatışma kısıtlı en büyük akış problemi ve çatışma kısıtlı atama problemidir. Konteyner limanlarında kıyı vinci çizelgeleme problemini modellemek için ortaya çıkan katmanlı ağlarda en küçük maliyetli kesişmeyen akış probleminin NP-zor olduğu kanıtlanmıştır. Çatışma kısıtlı en küçük maliyetli akış probleminin güçlü NP-zorluğu ve polinom zamanlı yakınlaştırma algoritmasının bulunmazlığı gibi karma¸sıklık çözümleme sonuçlarına da ulaşılmıştır. Ayrıca, katmanlı ağlarda en küçük maliyetli kesişmeyen akış problemi ve çatışma kısıtlı atama problemi için polinom zamanda çözülebilen özel durumlar açıklanmıştır. Benzer şekilde, çatışma kısıtlı en küçük maliyetli akış problemi ve çatışma kısıtlı en büyük akış problemi için olurlu çözüm sayısını polinom bir sayıyla sınırlayan durumlar çatışma çizgesinden faydalanılarak işaret edilmiştir. Tüm problemler için çeşitli matematiksel gösterimler elde edilmiştir. Hızlı bir biçimde problem boyutunu küçülten ve olurlu bir çözüm bulan eniyileme öncesi işlemler önerilmiştir. Eldeki problemin özel yapısını kullanan etkili alt yordamlarla zenginleştirilmiş dal-sınır algoritması, yenilikçi yaklaşımlarla iyileştirilmiş matruşka araması ve güçlü kesiler kullanan Benders ayrıştırması gibi kesin çözüm yöntemleri geliştirilmiştir. Algoritmalar geniş bir örnek problem kümesi üzerinde denenmiş ve başarımlarının matematiksel gösterimlerini bir ticari eniyileme yazılımı ile çözmekten daha iyi olduğu sonucuna varılmıştır.