Gezgin satıcı problemleri ve çözüm algoritmaları üzerine
On the traveling salesman problems and solution algorithms
- Tez No: 376360
- Danışmanlar: PROF. DR. URFAT NURIYEV, YRD. DOÇ. MURAT ERŞEN BERBERLER
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Matematik, Mathematics
- Yıl: 2013
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Gezgin Satıcı Problemi NP-Tam sınıfına ait bir kombinatoryal optimizasyon problemidir. Problem uygulama alanının çok olmasından dolayı literatürde önemli bir rol oynar ve Gezgin Satıcı Problemi örneği olarak formüle edilebilen pek çok gerçek hayat uygulaması vardır. Literatürde Gezgin Satıcı Problemleri için çok sayıda kesin algoritma, yaklaşım algoritmaları, sezgisel algoritmalar ve metasezgisel algoritmalar önerilmiştir. Bu tezde Gezgin Satıcı Problemleri ele alınmış, problemler için geliştirilen çözüm yöntemleri incelenmiş ve bu problem için önerilen tur iyileştirme yöntemlerinden k-opt yöntemi modifiye edilerek Simetrik Gezgin Satıcı Problemi için yeni bir algoritma tasarlanmıştır. Algoritma C programlama dilinde kodlanmış ve TSPLIB Kütüphanesi örnekleri üzerinde test edilmiştir. Ayrıca Çoklu Gezgin Satıcı Problemi için de yeni bir sezgisel algoritma önerilmiştir. Bu algoritma da C dilinde kodlanarak TSPLIB Kütüphanesi örnekleri üzerinde hesaplama denemeleri yapılmış ve sonuçlar literatürde var olan benzer bir çalışma ile kıyaslanmıştır. Hesaplama sonuçları önerilen yöntemlerin etkinliğini göstermektedir.
Özet (Çeviri)
The traveling salesman problem is a combinatorial optimization problem which belongs to the class of NP-Hard. The problem plays an important role in literature owing to its plenty application area and there are a great number of real life applications which can be formulated as an instances of the traveling salesman problem. In the literature, there are several exact algorithms, approximation algorithms, heuristic algorithms and meta-heuristic algorithms which have been proposed for traveling salesman problem. In this thesis, the traveling salesman problem is studied, the solution approaches for the problem are investigated and a new heuristic algorithm are designed for symmetric traveling salesman problem by improving k-opt which is a tour improvement heuristic. The algorithm has been implemented in C language and has been tested on the TSPLIB library. Besides, a new heuristic algorithm is proposed for multiple traveling salesman problem. This algorithm has been implemented in C language and has been tested on the TSPLIB library too, and compared with a similar literature work. The experimental results show that the proposed algorithms are efficient.
Benzer Tezler
- Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms
Metasezgisel algoritmaların etkinliğini arttırmak için esin kaynağı fraktal geometri olan çözüm oluşturma
MELİKE ÖZTÜRK
Doktora
İngilizce
2020
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
PROF. DR. ÇİĞDEM ALABAŞ USLU
- Modeling static and dynamic dial-a-ride problem
Müşteri rotalama probleminin statik ve dinamik olarak modellenmesi
DİLEK EKİZ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SANEM SARIEL
- Yapay arı kolonisi algoritması kullanarak gezgin satıcı probleminin Türkiyedeki il ve ilçe merkezlerine uygulanması
Evaluation of traveling salesman problem to the nodes of city and township centers by using artificial bee colony algorithm
MELİKE RUHAN AKÇA
Yüksek Lisans
Türkçe
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiElektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. HASAN ERDİNÇ KOÇER
- Karınca kolonisi optimizasyonu (ACO) ve parçacık sürü optimizasyonu (PSO) algoritmaları temelli bir hiyerarşik yaklaşım geliştirilmesi
Development of a hierarchical approach based on ant colony optimization (ACO) and particle swarm optimization (PSO) algorithms
HÜSEYİN ELDEM
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERKAN ÜLKER
- Parçacık sürü optimizasyonu algoritmasının gezgin satıcı problemine uygulanması ve performansının incelenmesi
Application of particle swarm optimisation algorithm to travelling salesman problem and its performance investigation
MEHMET YASİN ÖZSAĞLAM
Yüksek Lisans
Türkçe
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiElektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. MEHMET ÇUNKAŞ