Solving the traveling salesman problem using metaheuristic algorithms
Metasezgisel algoritmalar kullanılarak gezgin satıcı probleminin çözülmesi
- Tez No: 489351
- Danışmanlar: PROF. DR. HALİFE KODAZ
- 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: 2017
- Dil: İngilizce
- Üniversite: Selçuk Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 114
Özet
Gezgin Satıcı Problemi (GSP), popüler ve klasik araştırma problemlerinden biridir ve kombinatoryal optimizasyon problemlerinin yaygın olarak bilinen yöntemlerinden biri olarak kabul edilmektedir. GSP, deterministik olmayan bir problemdir; bu nedenle gerçek dünyada ve günlük hayatımızda karşılaşılan bu sorunu çözmek için birçok metasezgisel algoritma yöntemleri kullanılmıştır. Farklı GSP'lerin çözümünde kullanılan çeşitli çözüm teknikleri vardır. GSP'yi çözebilmek için bugüne kadar ele alınan başlıca metasezgisel algoritmalar Benzetilmiş Tavlama (BT), Tabu Search (TS), Genetik Algoritma (GA), Memetik Algoritmalar (MA), Saçılım Araştırması (SA), Karınca Kolonisi Optimizasyonu (KKO) algoritmalarıdır. GSP, NP-Komple problem sınıfının bir üyesidir ve GSP'yi çözmek, özellikle bir problemin boyutu büyük olduğunda klasik matematiksel yöntemleri kullanarak zordur. Bu nedenle, doğru hesaplama süresine sahip çok sayıda metasezgisel yöntemler, GSP'yi çözebilmek için az miktarda zaman ve hesaplama maliyeti içinde en uygun çözümlere ulaşmak için geliştirilmiştir. Bu tez çalışmasında Kurbağa Sıçrama Algoritması, Karınca Kolonisi Optimizasyonu, Geliştirilmiş Parçacık Sürüsü Optimizasyonu ve Kurbağa Sıçrama Algoritmasının geliştirilmiş iki yöntemi kullanarak GSP çözülmeye çalışılmıştır. MATLAB programlama ortamını kullanılarak TSPLIB kütüphanesinden alınan problemler bahsedilen algoritmaları kullanarak çözülmüştür. Bu algoritmaların sonuçları analiz edilmiştir.
Özet (Çeviri)
The Travelling Salesmen Problem (TSP) is one of the popular and classical research problems, and it is accounted as one of the widely known of combinatorial optimization problems. The TSP is a NP-Complete problem; therefore many metaheuristic algorithm methods had been used to solve this problem which can be met in real world and our daily life. There are various solution techniques which are used for solving different kinds of TSPs. Major metaheuristic algorithms that was covered so far for solving TSP are the Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA), Memetic Algorithm (MA), Scatter Search (SA), Ant Colony Optimization (ACO), etc. TSP is a member of NP-Complete problem class and solving the TSP is difficult using classic mathematical methods especially when the size of problem is great. Therefore, large number of metaheuristic methods which have accurate calculation time have been improved for solving TSP inorder to reach optimal solutions within a small amount of time and computational cost. In this thesis study, we tried to solve TSP using Shuffled Frog Leaping Algorithm, Ant Colony Optimization, Improved Particle Swarm Optimization, and two improved versions of Shuffled Frog Leaping Algorithm. By using the MATLAB programming environment, problems which are taken from the TSPLIB library are solved using mentioned algorithms. The results of these algorithms have been analyzed.
Benzer Tezler
- Çoklu gezgin satıcı probleminin sezgisel algoritmalar ile çözümü
Solving the multiple traveling salesman problem using heuristic algorithms
SEVDA DAYIOĞLU GÜLCÜ
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HUMAR KAHRAMANLI
- Gezgin satıcı probleminin çözümü için guguk kuşu arama algoritma tabanlı yeni bir hibrit metasezgisel yöntem
A new hybrid metaheuristic method based on cuckoo search algorithm for solving the traveling salesman problem
MUSTAFA FURKAN BERKAYA
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKonya Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET SARUCAN
- Zaman pencereli tamirci problemi ve uzantılarının yeni matematiksel modelleri
New mathematical models for the traveling repairman problem with time windows and its extensions
GÖZDE ÖNDER UZUN
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiBaşkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İMDAT KARA
- The roaming salesman problem and its application to election logistics
Dolaşım satıcısı problemi ve seçim lojistiğine uygulanması
MASOUD SHAHMANZARİ
Doktora
İngilizce
2019
Mühendislik BilimleriKoç Üniversitesiİşletme (İngilizce) Ana Bilim Dalı
DOÇ. DR. DENİZ AKSEN
- A novel modified teaching-learning based algorithm and its applications
Yeni bir değiştirilmiş öğretme-öğrenme tabanlı algoritma ve uygulamaları
TAREQ MEQDAM TAREQ AL-BASHAQHA
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AHMET NUSRET TOPRAK