Geri Dön

A new heuristic approach to TSP

Gezgin satıcı problemlerine yeni bir sezgisel yaklaşım

  1. Tez No: 233356
  2. Yazar: KUBİLAY A. ALPDOĞAN
  3. Danışmanlar: YRD. DOÇ. DR. SEROL BULKAN
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2008
  8. Dil: İngilizce
  9. Üniversite: Marmara Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 70

Ö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

  1. 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

    Türkçe

    2024

    Endüstri ve Endüstri MühendisliğiGazi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜL DİDEM BATUR SİR

  2. 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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolIşık Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OLCAY TANER YILDIZ

  3. 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

    İngilizce

    2020

    Endüstri ve Endüstri MühendisliğiMarmara Üniversitesi

    Mühendislik Yönetimi Ana Bilim Dalı

    PROF. DR. ÇİĞDEM ALABAŞ USLU

  4. Türkiye elektrik enerjisi talep tahmini için ağaç-tohum programlama yaklaşımı

    Tree-seed programming for estimation of Turkey electricity demand

    PARVANA YUNUSOVA

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA SERVET KIRAN

  5. 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

    Türkçe

    2009

    Endüstri ve Endüstri MühendisliğiKocaeli Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ALPASLAN FIĞLALI