Robust network design under polyhedral traffic uncertainty

Bu tez calısmasında talep tahminlerindeki degisikliklere karsı dayanıklı olan agların tasarımı incelenmistir. Olurlu talepler kumesinin gelisiguzel bir cokyuzlu ile tanımlandıgı durum dikkate alınmıstır. C¸ alısmanın amacı, bir cokyuzluye ait butun gerceklesmeler icin gecerliligi devam eden gurbuz ayrıt kapasitesi ve yol atama yapılandırmalarını belirlemektir. Aslen yarı-sonsuz karısık tamsayı programlama modelleri ile tanımlanan ve cok bilinen uc problem uzerinde calısılmıstır. Bu problemler icin acık ve tıkız formulasyonlara ek olarak alternatif formulasyonlar ve kesin cozum yontemleri gelistirilmistir. Dikkate alınan ilk problem Zahiri Ozel A˘g tasarımı ile ilgilidir. Hem klasik hortum modeli hem de rahat ulasılabilir trafik istatistiklerini kullanan, yeni ve daha az temkinli gurbuz bir talep modeli icin problemin tıkız dogrusal karısık tamsayı programlama formulasyonları onerilmistir. Bu modeller, orta ve buyuk olcekli ornekler icin mevcut ticari cozuculer kullanılarak cozulebiliyorken daha buyuk orneklerde kullanmak amacıyla birlesik bir dal-fiyat ve kesme yuzeyi algoritması gelistirilmistir. Ayrıca, elde edilen deneysel sonucların kapsamlı bir analizi de sunulmaktadır. ˙Incelenen ikinci problem, genel talep belirsizli˘gi durumunda trafik muhendisligi gerecleri ile gelistirilmis esnek En Kısa Yol Oncelikli Guzergah Atama (OSPF) problemidir. Bu konuda hedeflenen, yeterli esnekli˘gin sa˘glanması durumunda OSPF mekanizmasının MPLS gibi serbest yol atama yontemleri kadar yuksek bir performans gosterip gosteremeyecegini incelemektir. Soz konusu yol atama tekniklerinin bu kadar genel bir durum icin karsılaştırıldıgı daha baska bir calısma bilinmemektedir. Tezin bu bolumunde, oncelikle herhangi bir cokyuzlu ile her iki mekanizma i¸cin tıkız formulasyonlar verilmektedir. Ayrıca, ¸cokyuzlu talep tanımı i¸cin en iyi MPLS yol yapılandırmasının polinom zamanda hesaplanabilecegi vi gosterilmektedir. Daha sonra ise kesin ¸cozum yontemi olarak kullanılacak ve kesme yuzeyleri ile guclendirilmis bir dal-fiyat algoritması tanıtılmaktadır. Yeni gelistirilen esnek OSPF mekanizması, bu modeller ve ¸cozum yontemi kullanılarak MPLS'nin yanısıra mevcut OSPF tekni˘gi ile de karsılastırılmaktadır. Yeni durumda, kullanılan yonetim gerecleri sayesinde, mevcut OSPF mekanizmasının onemli derecede geli¸stirilebilece˘gi g¨osterilmi¸stir. Di˘ger yandan, bazı durumlarda MPLS'nin ve esnek OSPF'nin performanslarının kıyaslanabilir oldu˘gu da gozlenmistir. Tezde son olarak ¸cokyuzlu trafik talep belirsizl˘gi ile A˘g Y¨ukleme Problemi (NLP) ele alınmaktadır. Problemin, ¸cok urunlu durum i¸cin, tıkız bir form¨ulasyonu verildikten sonra olurlu ¸c¨oz¨um k¨umesinin bir alt uzaydaki izd¨u¸s¨um¨u incelenmektedir. Bu sayede mevcut en iyi NLP algoritmalarında bile kullanılmak zorunda kalınan ¨ol¸cev e¸sitsizlikleri bertaraf edilmi¸stir. Neticesinde do˘gan ¸coky¨uzl¨un¨un analizi ve problemin ¸cozumu onemli derecede kolayla¸smı¸stır. Bu suretle, olurlu trafik taleplerinin hortum modeli ile tanımlandı˘gı durum i¸cin problem ¸cokyuzlusunun ozellikleri incelenmi¸stir. Elde edilen ¨ozellikler, en iyi ¸c¨oz¨um de˘geri i¸cin ¨ust sınırları hesaplayan basit bir bulu¸ssal ile kuvvetlendirilmi¸s bir dal-kesi y¨onteminde kullanılmı¸stır. Son olarak, iyi bilinen a˘g tasarımı ¨ornekleri i¸cin kapsamlı deney sonu¸cları verilmi¸stir.