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: Mühendislik Bilimleri, Endüstri ve Endüstri Mühendisliği, Engineering Sciences, Industrial and Industrial Engineering
- Anahtar Kelimeler: Gezgin satıcı problemi, Kümeleme, Kümeleme analizi, Optimizasyon, Çok amaçlı birleşi problemleri, Travelling salesman problem, Clustering, Cluster analysis, Optimization, Multiobjective combinatorial optimization
- 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ı: Belirtilmemiş.
Ö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 çözümünde sinirsel ağ yaklaşımı
Neural network approach in the solution of traveling salesman problem
KAAN ASLAN
Yüksek Lisans
Türkçe
1999
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. A. SERMET ANAGÜN
- Gezgin satıcı probleminin çözümüne yönelik algoritmik yaklaşımlar
Gezgin satici probleminin çözümüne yönelik algoritmik yaklaşimlar
SERÇİN ÖZKAN
Yüksek Lisans
Türkçe
2010
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ORHAN TÜRKBEY
- 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