Network flows with conflict constraints
Çatışma kısıtlı ağ akışları
- Tez No: 572892
- Danışmanlar: PROF. İSMAİL KUBAN ALTINEL, PROF. MUSTAFA NECATİ ARAS
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 208
Özet
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.
Özet (Çeviri)
It is a commonly used approach to model real life problems as network flow problems and they appear in a wide range of areas including telecommunication, wireless networks, transportation, healthcare and scheduling. Our focus in this thesis is on an extension of network flow problems with conflict constraints that prevent the simultaneous usage of some arc pairs to send flow. We particularly concentrate on four of them: the minimum cost noncrossing flow problem on layered networks, the minimum cost flow problem with conflicts, the maximum flow problem with conflicts and the assignment problem with conflicts. The minimum cost noncrossing flow problem on layered networks, which emerges from the quay crane scheduling problem in container terminals, is proven to be NP-hard. Further complexity results including the strong NP-hardness and the non-existence of polynomial time approximation algorithm for the the minimum cost flow problem with conflicts on general networks are also provided. Moreover, polynomially solvable special cases for the minimum cost noncrossing flow problem on layered networks and the assignment problem with conflicts, which is known to be NP-hard, are explored. Similarly, the conditions which limit the number of feasible solutions with a polynomial number are indicated for the minimum cost flow problem with conflicts and the maximum flow problem with conflicts taking advantage of the conflict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to find an initial feasible solution are defined. Exact solution algorithms including a branch-and-bound algorithm enriched with the subroutines that exploit the special structure of the considered problem, an improved Russian doll search algorithm and a Benders decomposition with strengthened cuts are proposed. The methods are tested on a large set of test instances and they are shown to be superior than solving the underlying mathematical formulations with a commercial optimization solver.
Benzer Tezler
- Montaj hatlarının dengelenmesinde çok amaçlı bir yaklaşım
Assembly line balancing
MURAT BASKAK
Yüksek Lisans
Türkçe
1991
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. MEHMET TANYAŞ
- İstanbul'da ışıklı yaya geçitlerinde sürücülerin yatay işaretlemeye uymama oranlarının trafik ışığı konumuyla ilişkisinin incelenmesi
Investigation of the relationship between the violation rates of road marking and the positions of the traffic light on the signalized pedestrian crossings in Istanbul
ZELİHA ÇAĞLA ÇAĞLAR
Yüksek Lisans
Türkçe
2017
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. KEMAL SELÇUK ÖĞÜT
- Ulaşım şebekesi tasarımı için çok amaçlı bir model
A Multiobjective approach to transportation network design
ALPASLAN FIĞLALI
- Atölyede iş çizelgeme
Operations scheduling in job shops
GÖKHAN KIPÇAK
Yüksek Lisans
Türkçe
1990
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ATAÇ SOYSAL