Geri Dön

On a greedy heuristic for the multicommodity rent-or-buy problem

Çoklu eşya satın al ya da kirala problemine aç gözlü bir sezgisel

PDF İndir

  1. Tez No: 374437
  2. Yazar: OSMAN MELİH KÜRTÜNCÜ
  3. Danışmanlar: YRD. DOÇ. DR. ALİ ÇİVRİL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Melikşah Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 89

Özet

Bu tez, ünlü Steiner Ormanı Probleminin genelleştirilmiş bir hali ve önemli bir ağ tasarım problemi olan Çoklu Eşya Kirala veya Satın Al Problemi için üç yeni algoritma öne sürmektedir. Bu algoritmalar Kruskal, Boruvka ve Prim'in iyi billinen minimum yayılan ağaç algoritmalarından esinlenmişlerdir. Bizim algoritmalarımızın son geliştirilen algoritmalara kıyasla kötü olmasına rağmen, bizim algoritmalarımızın özellikle kenar ağırlıklarının yüksek aralıklarla değiştiği çizgelerde iyi bilinen Agrawal, Klein ve Ravi'nin (AKR) algoritmasından çok daha hızlı çalıştığını ve ona benzer sonuç verdiğini gösterdik. Özellikle, algoritmalarımız Öklid düzlemde bir ülkenin şehirlerini birbirine bağlayan gerçek dünya verisi için çok iyi bir alternatif teşkil etmektedirler. . Algoritmalarımızın Steienr Ormanı problemi için çalışma zamanları O((m+n log⁡n )k) olup (2-1⁄k) yaklaşık ve çalışma zamanı O(n^2 log⁡n) olan bir önceki algoritmaya göre daha iyidir ki burada m, n ve k sırası ile çizgedeki köşe, düğüm ve terminal çiftlerinin sayısıdır.

Özet (Çeviri)

This thesis introduces three new algorithms for an important network design problem called the Multicommodity Rent-or-Buy Problem which is a generalization of the famous Steiner Forest Problem. These algorithms are inspired by the well-known minimum spanning tree algorithms of Kruskal, Prim and Boruvka. Although our algorithms do not have good approximation ratio compared to the state-of-art, we show that they are much faster than the well-known approximation algorithm of Agrawal, Klein and Ravi (AKR) with similar solution costs, especially when the edge weights span a wide range. In particular, our algorithms turn out to be a very good alternative for AKR on real world data, where for example the points to be connected in the problem represents the cities of a country on the Euclidean plane. Thee running time of our algorithms for the Steiner Forest Problem is O((m+n log⁡n )k) which is an improvement over the previous (2-1⁄k) approximate algorithm with O(n^2 log⁡n) running time where m, n and k are the number of edges, vertices and terminal pairs in the graph respectively.

Benzer Tezler

  1. Tez No

    374424

    On a greedy heuristic for the Steiner forest problem

    Steiner ormanı problemi için açgözlü bir sezgisel

    BİLGE KAĞAN DEDETÜRK

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMelikşah Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ALİ ÇİVRİL

  2. Tez No

    129158

    Facility location decisions under vehicle routing considerations

    Dağıtım araçları rotası düşünülerek tesis yerleri belirlenmesi

    BARIŞ SELÇUK

    Yüksek Lisans

    İngilizce

    İngilizce

    2002

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

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

    DOÇ. DR. OSMAN OĞUZ

  3. Tez No

    176880

    A lagrangean heuristic for the two-stage modular capacitated facility location problem

    İki seviyeli modüler kapasiteli tesis yerleşimi problemi için bir lagrange sezgiseli

    SELİM SEVİNÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2008

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

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

    YRD. DOÇ. DR. SEDEF MERAL

  4. Tez No

    478625

    Solving a modified TSP problem by a greedy heuristic for cost minimization

    Modifiye bir gezgin satıcı problemi için açgözlü bir sezgisel ile maliyet minimizasyonu

    MURAT ÇAL

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

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

    DOÇ. DR. ALİ EKİCİ

  5. Tez No

    406540

    Planning of train movements in single track railways

    Tek hatlı demiryollarında tren hareketlerinin planlanması

    GÖKÇE AYDIN

    Doktora

    İngilizce

    İngilizce

    2015

    UlaşımYıldız Teknik Üniversitesi

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

    DOÇ. DR. İSMAİL ŞAHİN

Geri Dön