Gezgin satıcı probleminin DBSCAN kümeleme yöntemiyle analizi
Analizing traveling salesman problem with DBSCAN method
- Tez No: 743612
- Danışmanlar: DR. ÖĞR. ÜYESİ YILDIZ ŞAHİN
- 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: 2022
- Dil: Türkçe
- Üniversite: Kocaeli Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 33
Özet
Gezgin satıcı problemleri güncelliğini korumakta olan bir NP-Hard çizelgeleme problemi türüdür. Kümeleme algoritmaları ise birbirine yakın öğelerin optimal şekilde bir araya gelmesini amaçlayan algoritmalardır. Buradan yola çıkarak bir kümeleme algoritması olan DBSCAN algoritması ile üretilen kümeler iterasyonlarla genişletilerek gezgin satıcı problemi için iyi bir sonuç elde edilmek istenmiştir. Algoritma DBSCAN ile problem içinde küçük kümeler oluşturup, küme içi problem çözümleri üretir. Daha sonra kümeler genişletilerek problemdeki tüm noktaları kapsar ve en sonda tek bir çözüm ortaya koyar. Bu süreçte 2-opt algoritması son sonucu geliştirmek için kullanılmıştır. Algoritma en son 5 problemde denenmiş ve sonuçların en iyi bilinen değerlerden ortalama %22 sapmaya sahip olduğu belirlenmiştir.
Özet (Çeviri)
Traveling salesman problems are a type of NP-Hard scheduling problem that still keeps its actuality. Clustering algorithms, are algorithms that aim to optimally combine elements that are close to each other. In this regard, it is aimed to obtain good results for the traveling salesman problem by expanding the clusters produced by the DBSCAN clustering algorithm. The proposed algorithm creates small clusters within the problem via DBSCAN and generates in-cluster problem solutions. Then the clusters are expanded to cover all the points in the problem and merge into a single solution at the end. The 2-opt algorithm was used to improve the final resulting solution in this process. The algorithm has been tested in the last 5 benchmark problems and it has been determined that the results have an average deviation of 22% from their best-known solutions.
Benzer Tezler
- Afrika akbabaları optimizasyonu kullanılarak gezgin satıcı probleminin çözümü için verimli bir başlangıç popülasyonu oluşturma
Creating an efficient initial population to solve the traveling salesman problem using african vulture optimization
VELİ AKAY
Yüksek Lisans
Türkçe
2025
Mühendislik BilimleriVan Yüzüncü Yıl ÜniversitesiYapay Zeka ve Robotik Ana Bilim Dalı
PROF. DR. RIDVAN SARAÇOĞLU
- Relative distances approach for multi-traveling salesmen problem
Çoklu gezgin satıcı problemi için göreli mesafeler yaklaşımı
EMRE ERGÜVEN
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. FARUK POLAT
- Gezgin satıcı probleminin karınca kolonisi algoritması ile çözüm performansının arttırılmasında parametre optimizasyonu
Parameter optimization to increase solution performance of travelling Salesman problem by using ant colony algorithm
KUMRU AKŞEHİR
Yüksek Lisans
Türkçe
2019
İstatistikOndokuz Mayıs Üniversitesiİstatistik Ana Bilim Dalı
DOÇ. DR. TALAT ŞENEL
- Gezgin satıcı probleminin hadoop üzerinde çalışan paralel genetik algoritma ile çözümü
Parallel genetic algorithm to solve traveling salesman problem on hadoop cluster
HARUN RAŞİT ER
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. NADİA ERDOĞAN
- Gezgin satıcı probleminin çözümünde genetik algoritmanın parametrelerinin incelenmesi
Investigation of parameters of genetic algorithm in the solution of traveling salesman problem
MERYEM PULAT
Yüksek Lisans
Türkçe
2017
EkonometriDokuz Eylül ÜniversitesiEkonometri Ana Bilim Dalı
PROF. DR. İPEK DEVECİ KOCAKOÇ