Gezgin satıcı problemlerinin çözümü için yerel arama algoritmalarının hibrit kullanımı
The hybrid use of local search algorithms for the solution of the traveling salesman problems
- Tez No: 928945
- Danışmanlar: DOÇ. DR. HASAN TEMURTAŞ
- 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: 2024
- Dil: Türkçe
- Üniversite: Kütahya Dumlupınar Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 53
Özet
Bu çalışma, Gezgin Satıcı Problemi'ni (GSP) optimize etmek için yerel arama tekniklerini, 2-opt, 3-opt, Slide ve Swap gibi yöntemlerle araştırmıştır. Yerel aramada 2-opt yöntemi, bir rotanın düzenlenmesini amaçlayarak rotayı tekrar geçmeden yeniden düzenlemeyi hedefler. 3-opt ise daha karmaşık bir yöntem olup, 2-opt yöntemine göre daha yavaş olabilir, ancak daha iyi sonuçlar elde edebilir. Her iki yöntemin de probleme bağlı olarak başarı performansı değişebilir. Bu çalışma, 2-opt, 3-opt, Slide ve Swap yöntemlerinin performanslarını dikkatli bir şekilde analiz etmiş ve karşılaştırmıştır. Ayrıca, algoritma performansını artırmak amacıyla bu tekniklerin belirli oranlarda kullanıldığı yeni bir hibrit arama tekniği olan HLSA (Hybrid Local Search Algorithm) algoritması geliştirilmiştir. HLSA algoritması, %30 2-opt, %30 3-opt, %20 Slide ve %20 Swap gibi belirli oranlarda bu teknikleri kullanarak tasarlanmıştır. HLSA algoritması titiz deneylerle test edilmiş ve diğer yerel arama algoritmaları ile karşılaştırılmıştır. Sonuçlar, HLSA algoritmasının diğer tekniklere göre daha hızlı ve daha başarılı sonuçlar elde ederek GSP problemini optimize ettiğini göstermektedir. Bu araştırma, Gezgin Satıcı Problemi'nin pratik uygulamalarında kullanılabilecek etkili bir çözüm sunmaktadır.
Özet (Çeviri)
In this thesis, the Traveling Salesman Problem (TSP) has been solved using the Local Search Optimization algorithm. The goal of TSP is to find the shortest route for a salesman to visit a specific group of cities, visiting each city only once and returning to the starting point. The local search algorithm has been employed to optimize TSP using methods such as 2-opt, 3-opt, Slide, and Swap. In local search, the 2-opt method aims to take an existing route and reorganize it without revisiting the same cities. The more complex 3-opt, although potentially slower than 2-opt, can yield better results. This study explores how TSP can be solved using the local search optimization algorithm. Furthermore, the performances of the 2-opt, 3-opt, Slide, and Swap methods have been analyzed and compared through experiments. To improve algorithm performance, the Local Search algorithm has been modified by randomly combining 30% 2-opt, 30% 3-opt, 20% Slide, and 20% Swap. This has reduced processing time and aimed to enhance the feasibility of problem resolution.
Benzer Tezler
- Karga ve yarasa tabanlı algoritmaların yeni versiyonlarının geliştirilmesi ve performanslarının değerlendirilmesi
Development of new versions of crow and bat based algorithms and evaluation of their performance
ZAHER AKHDIR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUSTAFA DANACI
- Ayrık optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı yeni yaklaşımlar
Jaya algorithm based new approaches for solving discrete optimization problems
MURAT ASLAN
Doktora
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MESUT GÜNDÜZ
- Ayrık optimizasyon problemlerinin çözümünde göçmen kuşlar optimizasyon (MBO) algoritmasının iyileştirilmesi
Improvement of migrating birds optimization (MBO) algorithm in solution of discrete optimization problems
VAHİT TONGUR
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ERKAN ÜLKER
- Ant colony optimization and greedy algorithm performance comparison in travelling salesman problem
Gezgin satıcı probleminde karınca kolonisi optimizasyonu ve greedy algoritması performans karşılaştırması
MERVE ECE GÖRGÜN
Yüksek Lisans
İngilizce
2024
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BERRİN DENİZHAN
- Developing and applying multi-threaded metaheuristic policies to solve combinatorial industrial engineering problems
Endüstri mühendisliğindeki kombinatoryal optimizasyon problemlerinin çözümü için çoklu iş parçacıklı metasezgisel politikalar geliştirilmesi ve uygulanması
İSMET KARACAN
Doktora
İngilizce
2023
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SEROL BULKAN
PROF. DR. ÖZLEM ŞENVAR