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
- Tez No: 374437
- Danışmanlar: YRD. DOÇ. DR. ALİ ÇİVRİL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Melikşah Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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 logn )k) olup (2-1⁄k) yaklaşık ve çalışma zamanı O(n^2 logn) 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 logn )k) which is an improvement over the previous (2-1⁄k) approximate algorithm with O(n^2 logn) running time where m, n and k are the number of edges, vertices and terminal pairs in the graph respectively.
Benzer Tezler
- 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
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMelikşah ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ ÇİVRİL
- 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
2002
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN OĞUZ
- 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
2008
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SEDEF MERAL
- 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
2017
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ EKİCİ
- Planning of train movements in single track railways
Tek hatlı demiryollarında tren hareketlerinin planlanması
GÖKÇE AYDIN
Doktora
İngilizce
2015
UlaşımYıldız Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSMAİL ŞAHİN