Geri Dön

Multicommodity network flow problem with substitution

İkameli çok ürünlü ağ akışı problemi

PDF İndir

  1. Tez No: 392270
  2. Yazar: EKİN KÖKER
  3. Danışmanlar: DOÇ. DR. GÜVENÇ ŞAHİN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2013
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 63

Özet

Birden fazla ürünün ayrıt kapasiteleri gibi ortak kaynakları paylaştığı çok ürünlü ağ akış problemleri, tek ürünlü ağ akış problemlerinin genelleşmiş bir halidir. Tek ürünlü problemlerde ayrıtlar üzerindeki akış miktarları tam sayı olmaya zorlansa bile problem polinom zamanda çözülmesine karşın, problemin çok ürünlü ve ayrıt kapasiteli versiyonu NP-zor bir problemdir. Bu çalışmada çok ürünlü ağ akış probleminin ürünler arasında ikamenin mümkün olduğu daha da genelleşmiş bir halini tanımlıyoruz. İki veya üç ürünün yer aldığı, hem genel hem de ürüne özgü ayrıt kapasitelerin var olduğu problemlerin doğrusal tam sayılı programlama gösterimlerini matematiksel modeller olarak geliştiriyoruz. Kapasitesiz versiyonların matematiksel programlama gösterimlerindeki kısıt matrisinin tamamen ünimodüler olduğunu kanıtlıyoruz. Hipotez testi yöntemiyle rastgele yaratılan problemler üzerinden problem gösterimlerinin kapasiteli versiyonlarının deneysel hesaplama zorluğunu istatistiksel analiz yoluyla inceliyoruz. Kapasitelerin ve problem büyüklüğünün çözüm zamanına etkisini araştırıyoruz. Sonuçlarımız hem iki hem de üç ürünlü problemlerde hem genel hem de ürüne özgü kapasiteler probleme dahil edildiğinde çözüm zamanının önemli derecede arttığını gösteriyor. Problem boyutu büyüdükçe de çözüm zamanının arttığı ortaya çıkıyor. Son olarak iki ve üç ürünlü matematiksel modelleri çok ürünlü problem için genelleştiriyoruz.

Özet (Çeviri)

Multicommodity network flow problems are generalizations of single commodity network flow problems, where a number of commodities flow through the network often sharing common resources such as arc capacities. While the single commodity problem can be solved in polynomial time even when the flow quantities are imposed as integer values only, the integer multicommodity version of the problem with arc capacities is NP-hard. We introduce a generalization of the multicommodity network flow problem where substitution is possible amongst commodities. We develop mathematical models as the linear integer programming formulations of two-commodity and three-commodity problems with both commodity-specific and overall arc capacities. We prove that constraint matrices are totally unimodular in the mathematical programming formulations for the uncapacitated versions. We investigate the empirical computational difficulty of capacitated versions of the problem formulations through a computational study with randomly generated problems and statistical analysis with hypothesis testing. In particular, we explore the effect of capacities and the problem size on solution time. Our results show that solution time significantly increases for both two-commodity and three-commodity problems when both overall and commodity-specific capacities exist. Solution time significantly increases when problem size is increased. Finally, we generalize two and three-commodity models for the multicommodity problem.

Benzer Tezler

  1. Tez No

    216692

    Multimodal multicommodity routing problem with scheduled services

    Çok modlu tarifeli seferlere sahip taşıma şebekesinde çok ürünlü rotalama problemi

    BURAK AYAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2008

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    YRD. DOÇ. DR. HANDE YAMAN

  2. Tez No

    7976

    Heuristic methods for solving multicommodity network flow problems with discontinuous cost functions

    Başlık çevirisi yok

    KAYHAN KARAKUŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    1988

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    DOÇ. DR. İLHAN OR

  3. Tez No

    167308

    Minimum concave cost multicommodity network design

    Çok ürünlü en küçük içbükey maliyetli ağ tasarımı

    FATİH SAY

    Yüksek Lisans

    İngilizce

    İngilizce

    2005

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Bölümü

    Y.DOÇ.DR. CÜNEYT FEHMİ BAZLAMAÇCI

  4. Tez No

    119303

    Fleet assignment and aircraft routing problem in an airline company

    Bir havayolu şirketinde filo atama ve uçak rotalama problemi

    ZEYNEP CANAN AYDEMİR

    Yüksek Lisans

    İngilizce

    İngilizce

    2002

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SİBEL GÜVEN

  5. Tez No

    105806

    A 'Decision support system for deployment of Turkish Armed Forces in natural disasters'

    'Türk Silahlı Kuvvetlerinin doğal afetlerde kullanılmasında bir karar destek sistemi'

    EDİZ EKİNCİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2001

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. LİNET ÖZDAMAR

Geri Dön