Robust network design under polyhedral traffic uncertainty
Çokyüzlü trafik belirsizliği durumunda gürbüz ağ tasarımı
- Tez No: 200407
- Danışmanlar: PROF. DR. MUSTAFA ÇELEBİ PINAR
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Robust network design, polyhedral tra±c uncertainty, Virtual Pri- vate Network, Open Shortest Path First, Network Loading Problem, Branch- and-Price. v
- Yıl: 2007
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 186
Özet
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.
Özet (Çeviri)
In this thesis, we study the design of networks robust to changes in demand estimates. We consider the case where the set of feasible demands is de¯ned by an arbitrary polyhedron. Our motivation is to determine link capacity or rout- ing con¯gurations, which remain feasible for any realization in the corresponding demand polyhedron. We consider three well-known problems under polyhedral demand uncertainty all of which are posed as semi-in¯nite mixed integer program- ming problems. We develop explicit, compact formulations for all three problems as well as alternative formulations and exact solution methods. The ¯rst problem arises in the Virtual Private Network (VPN) design ¯eld. We present compact linear mixed-integer programming formulations for the prob- lem with the classical hose tra±c model and for a new, less conservative, robust variant relying on accessible tra±c statistics. Although we can solve these formu- lations for medium-to-large instances in reasonable times using o®-the-shelf MIP solvers, we develop a combined branch-and-price and cutting plane algorithm to handle larger instances. We also provide an extensive discussion of our numerical results. Next, we study the Open Shortest Path First (OSPF) routing enhanced with tra±c engineering tools under general demand uncertainty with the motivation to discuss if OSPF could be made comparable to the general unconstrained routing (MPLS) when it is provided with a less restrictive operating environment. To the best of our knowledge, these two routing mechanisms are compared for the ¯rst time under such a general setting. We provide compact formulations for both routing types and show that MPLS routing for polyhedral demands can be computed in polynomial time. Moreover, we present a specialized branch- and-price algorithm strengthened with the inclusion of cuts as an exact solution iv tool. Subsequently, we compare the new and more °exible OSPF routing with MPLS as well as the traditional OSPF on several network instances. We observe that the management tools we use in OSPF make it signi¯cantly better than the generic OSPF. Moreover, we show that OSPF performance can get closer to that of MPLS in some cases. Finally, we consider the Network Loading Problem (NLP) under a polyhe- dral uncertainty description of tra±c demands. After giving a compact multi- commodity formulation of the problem, we prove an unexpected decomposition property obtained from projecting out the °ow variables, considerably simplifying the resulting polyhedral analysis and computations by doing away with metric in- equalities, an attendant feature of most successful algorithms on NLP. Under the hose model of feasible demands, we study the polyhedral aspects of NLP, used as the basis of an e±cient branch-and-cut algorithm supported by a simple heuristic for generating upper bounds. We provide the results of extensive computational experiments on well-known network design instances.
Benzer Tezler
- Kablosuz algılayıcı ağlarda belirsiz veri üretimi için gürbüz en iyileme
Robust optimization for uncertain data generation rate in wireless sensor networks
TESLİME GÜREL
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞEGÜL ALTIN KAYHAN
- Stokastik ve gürbüz model önerileri ile belirsizlik altında tam zamanında tedarik zincirinin tasarlanması
Designing just-in-time supply chain under uncertainty with stochastic and robust model suggestions
BEREN GÜRSOY
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SELİN SONER KARA
- Ömrünü tamamlamış araçların geri kazanımı için belirsizlik altında ağ tasarımı
Network design under uncertainty for the recovery of end-of-life vehicles
DUYGU ERDOĞAN
Yüksek Lisans
Türkçe
2020
Endüstri ve Endüstri Mühendisliğiİstanbul Ticaret ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BERK AYVAZ
- Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon
Logistic network design and optimization using hyperheuristic methods
VURAL EROL
Doktora
Türkçe
2017
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT BASKAK
PROF. DR. GÜLGÜN KAYAKUTLU
- Deep neural networks for robust time delay fault tolerant autonomous landing control system design under severe disturbances
Ağır bozuntular altında derin öğrenme tabanlı gürbüz zaman gecikmeli arıza toleranslı otomatik ıniş kontrol sistemi tasarımı
MUSTAFA ÇAĞATAY ŞAHİN
Yüksek Lisans
İngilizce
2019
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ NAZIM KEMAL ÜRE