A new heuristic approach to TSP
Gezgin satıcı problemlerine yeni bir sezgisel yaklaşım
- Tez No: 233356
- Danışmanlar: YRD. DOÇ. DR. SEROL BULKAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Endüstri mühendisliği, Industrial engineering
- Yıl: 2008
- Dil: İngilizce
- Üniversite: Marmara Ü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
Bu çalışmada, NP-Hard olarak bilinen ve çözümüne ulaşılması imkansız olan veya henüz ulaşılamamış olan Gezgin Satıcı Problemlerine optimum veya yakın-optimum sonuç bulduracak yeni bir sezgisel metot geliştirilmiştir.Söz konusu metot, işletme alanında geçen ?memnun müşteri 2 kişiye; mutsuz müşteri ise 20 kişiye söyler? sözünden yola çıkılarak geliştirilmiştir. Toplumsal yapıdan model alınarak yaratılan algoritma, belirli sayıda insanların rassal olarak kat ettikleri güzergahlar üzerine yaptıkları yorum ve ?dedikodulardan? etkilenen sonraki neslin olumsuz yorumların aksini tercih etmeleri veya yepyeni güzergah deneme ihtiyacı duymaları üzerine kuruludur.Yeni yaklaşım, TSPLIB olarak bilinen elektronik Gezgin Satıcı Problemi kütüphanesindeki problemlemlere uygulanmıştır. Farklı ölçekteki problemlerin çözümleri; hesaplama süreleri, bilinen en iyi sonuca yüzde olarak yakınlık oranları not edilerek karşılaştırılmıştır.Sonuç itibari ile 20 şehire kadar olan asimetrik problemlerde optimum sonuç alındığı ve 20 ile 50 şehre kadar olan problemlerde %15. yakınlık oranıyla sonuç bulunduğu görülmüştür. Test sonuçlarının istatistiki güven aralığı, yaklaşık %100 güven seviyesinde optimal değerleri içermektedir. Son olarak, algoritmanın, En-kötü-vaka analizine göre opt-2 algoritmalarından daha iyi sonuç verdiği ispatlanmıştır.Yeni geliştirilen bu algoritmanın, ilk haliyle umut veren sonuçlar sağladığı sonucuna varılmıştır. Bu yeni algoritma, ileri aşamalarda daha çabuk evrimleşmeye ve literatürdeki diğer evrimleşmiş algoritmalardan daha iyi sonuçlar vermeye açıktır.
Özet (Çeviri)
In this study, a new heuristic method has been developed in order to find optimal or near-optimal solutions to unsolved or impracticaly NP Hard Travelling Salesman Problems.This new algorithm has been developed by inspiring from the word ?Satisfied customer tells it to 2 people; dissatisfied customer tells to 20 people? in marketing field. By modelling this social structure, given number of human beings make various routes and after completing their routes they start commenting and ?rumoring?. The next generation, affected by these rumors, tend to eliminate the routes of negative rumor concern or sometimes choose to try a new route.The new Algorithm has been applied to the problems from e-library called TSPLIB. The results are compared by means of excess over optimal percentages, interval estimates, and worst case analyses.As a result, it has been seen that the Algorithm provided with optimal solutions to at most 20-city problems; and had 15% excess over optimal ratio for the 20 to 50-city problems. Confidence interval of the test results include optimal values at a confidence level very close to 100%. Lastly, it is prooved that the Algorithm gives better results than opt-2 algorithm by worst case analysis.The new developed algorithm is a prospective heuristic while the technique is in its early stage. In this sense, Rumor Model is a nominator for easy and speedy revolution and having better results than of evoluted algorithms in the literature after retunings.
Benzer Tezler
- Esnek robotik hücrelerde hız değiştirme faaliyetli paralel makine çizelgeleme
Scheduling parallel machines with rate modifying activity in flexible robotic cells
İLAYDA BATTI PARLAR
Yüksek Lisans
Türkçe
2024
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜL DİDEM BATUR SİR
- Gezgin satıcı problemi
Traveling salesman problem
VOLKAN M. ÖZALP
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN ÜLENGİN
- Gezgin satıcı problemi için diferansiyel gelişim algoritması tabanlı bir metasezgisel önerisi
A differential evolution algorithm based metaheuristic proposal for the traveling salesman problem
ÜMİT TERZİ
Doktora
Türkçe
2009
Endüstri ve Endüstri MühendisliğiKocaeli ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALPASLAN FIĞLALI
- An hybrid approach to solve traveling salesman problem using genetic algorithm
Gezgin postacı problemine genetik algoritma kullanarak hibrid yaklaşım
CENGİZ ASMAZOĞLU
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolIşık ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. OLCAY TANER YILDIZ
- Creating an evacuation plan during an emergency by coordinating vehicles
Bir acil durumda araç koordinasyonu ile kurtarma planı oluşturma
HAZAL BACAKSIZ
Yüksek Lisans
İngilizce
2018
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ EKİCİ