Meta-heuristic solution approaches for traveling salesman and traveling repairman problems
Gezgin satıcı ve gezgin tamirci problemleri için meta-sezgisel çözüm yaklaşımları
- Tez No: 328463
- Danışmanlar: YRD. DOÇ. DR. ALİ SERDAR TAŞAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Mühendislik Bilimleri, Industrial and Industrial Engineering, Engineering Sciences
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Dokuz Eylül Ü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ı: 106
Özet
Gezgin satıcı problemi (GSP) uzun yıllardır yoğun bir şekilde çalışılan bir kombinatoryal optimizasyon problemidir. GSP, kat edilen toplam mesafeyi en aza indirmek için her noktaya sadece bir kez uğranılan bir Hamilton turu yaratma problemidir. Karınca kolonisi optimizasyonu (KKO), optimizasyon problemlerini çözmek için meta-sezgisel bir yaklaşımdır. Çalışmada, yerel arama sezgisellerinden yararlanan KKO tabanlı bir algoritma önerilmiştir. Önerilen algoritma iyi bilinen GSP veri setlerine uygulanmış ve sonrasında hesaplamalardan elde edilen sonuçlara göre algoritmanın performansı tartışılmıştır.Gezgin tamirci problemi (GTP) farklı konumlarda bulunan müşterilerin bekleme sürelerinin toplamını en aza indirmenin amaçlandığı bir Hamilton turu bulma problemidir. Genetik algoritmalar (GA) evrim sürecinden ilham alınarak yaratılmış meta-sezgisel çözüm yöntemleridir. İkinci çalışmada GTP'yi çözmek için genetik algoritmayı yerel arama sezgiseli ile birleştiren bir hibrit algoritma önerilmiştir. Önerilen algoritma literatürde çalışılmış bir dizi örneğe uygulanmıştır. Algoritmanın performansı hesaplama çalışmasının sonucuna göre değerlendirilmiştir.Bu çalışmaların amacı, büyük ölçekli GSP ve GTP problemlerini çözmek için gerçek hayat problemlerine uygulanabilen verimli ve etkili algoritmalar geliştirmektir.Üçüncü çalışma olarak, varsayımları temel alan bir kar felaketi durumu hakkında bir vaka çalışması GSP ve GTP olarak çalışılmıştır. Önerilen algoritmalar vakaya uygulanmış ve sonuçları tartışılmıştır.
Özet (Çeviri)
The traveling salesman problem (TSP) is a combinatorial optimization problem which has been extensively studied for years. TSP is the problem of creating a Hamiltonian cycle in which each node is visited only once to minimize total distance travelled. The ant colony optimization (ACO) is a meta-heuristic approach for solving optimization problems. In the study, an ACO based algorithm is proposed which utilizes local search heuristics. Proposed algorithm is applied to well-known TSP datasets and then the performance of the approach is discussed according to the results obtained from computations.The travelling repairman problem (TRP) is the problem of finding a Hamiltonian path in which the objective is to minimize total waiting time of all customers that are situated at different locations. Genetic algorithms (GA) are meta-heuristic solution methods which are created by taking inspiration from the evolution process. As a second study, a hybrid algorithm which combines genetic algorithm with a local search heuristic is proposed to solve TRP. Proposed algorithm is applied to a set of instances that have been studied in the literature. Performance of the approach is evaluated according to the results of the computational study.Aim of these studies is to develop efficient and effective algorithms that can be applicable to real life problems to solve large scale TSP and TRP problems.As the third study, a case study about a snow disaster situation based on some assumptions is examined as TSP and TRP. Proposed algorithms are applied to the case and results are discussed.
Benzer Tezler
- Gezgin satıcı problemleri ve çözüm algoritmaları üzerine
On the traveling salesman problems and solution algorithms
GÖZDE KIZILATEŞ
Yüksek Lisans
Türkçe
2013
MatematikEge ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. URFAT NURIYEV
YRD. DOÇ. MURAT ERŞEN BERBERLER
- Gezgin satıcı problemi için diferansiyel gelişim algoritması tabanlı bir metasezgisel önerisi
A differential evolution algorithm based metaheuristic proposal for the traveling salesman problem
ÜMİT TERZİ
Doktora
Türkçe
2009
Endüstri ve Endüstri MühendisliğiKocaeli ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALPASLAN FIĞLALI
- Integrating path planning and image processing with UAVs for disease detection and yield estimation in indoor agriculture
Kapalı alan tarımda hastalık tespiti ve verim tahmini için rota planlama ve görüntü işlemenin İHA'larla entegre edilmesi
ONAT ERDOĞMUŞ
Yüksek Lisans
İngilizce
2024
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDİNÇ ALTUĞ
- Performance analysis of meta - heuristic approaches for traveling salesperson problem
Buluşsal yaklaşımlarda bulunarak gezgin satıcı probleminin performans analizi
MURAT ERENTÜRK
Yüksek Lisans
İngilizce
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. ENDER ÖZCAN
- Solution Approaches for Sequence Dependent Traveling Salesman Problem
Sıraya Dayalı Seyyar Satıcı Problemi için Çözüm Yaklaşımları
SAMET TONYALI
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ FUAT ALKAYA