Geri Dön

Network flows with conflict constraints

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

  1. Tez No: 572892
  2. Yazar: ZEYNEP ŞUVAK
  3. Danışmanlar: PROF. İSMAİL KUBAN ALTINEL, PROF. MUSTAFA NECATİ ARAS
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. 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

  1. İ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

    Türkçe

    2017

    Mühendislik Bilimleriİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. KEMAL SELÇUK ÖĞÜT

  2. Ulaşım şebekesi tasarımı için çok amaçlı bir model

    A Multiobjective approach to transportation network design

    ALPASLAN FIĞLALI

  3. Bankacılıkta değişim yönetimi

    Change management in banking

    AYDIN ARGIN

    Doktora

    Türkçe

    Türkçe

    2000

    BankacılıkMarmara Üniversitesi

    Bankacılık Ana Bilim Dalı

    PROF. DR. NAZIM EKREN

  4. Atölyede iş çizelgeme

    Operations scheduling in job shops

    GÖKHAN KIPÇAK

    Yüksek Lisans

    Türkçe

    Türkçe

    1990

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. ATAÇ SOYSAL