Geri Dön

An evolutionary approach to TSP: Crossover with convertional heuristics

GSP'ne evrimsel bir yaklaşım: Geleneksel sezgisel yöntemler ile çaprazlama

  1. Tez No: 143497
  2. Yazar: MELTEM SÖNMEZ
  3. Danışmanlar: YRD. DOÇ. DR. HALDUN SÜRAL, DOÇ. DR. NUR EVİN ÖZDEMİREL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Gezgin Satıcı Problemi, Evrimsel Algoritmalar, Geleneksel Sezgisel Yöntemler, Traveling Salesman Problem, Evolutionary Algorithms, Conventional Heuristics
  7. Yıl: 2003
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Ü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ı: 123

Özet

Gezgin satıcı probleminde (GSP), N adet şehri dolaşmak üzere yola çıkan bir satıcı, her şehri sadece bir kez dolaşır ve başladığı noktaya geri döner. Şehir sayısı artığında makul bir sürede en kısa rotayı bulmak güçleşir ve bu nedenle literatürde birçok sezgisel yöntem geliştirilmiştir. Bu çalışmada, GSP 'ne doğal evrimsel süreçleri model olarak kullanan evrimsel algoritmalar ile bilinen geleneksel sezgisel yöntemleri birleştiren bir çözüm yöntemi önerilmektedir. Geleneksel sezgisel yöntemlerden,“en yakın komşu önce”,“en kısa mesafe önce”ve“araya girme”, çaprazlama yöntemi olarak kullanılmış ve bu yöntemler GSP'nin yapıtaşları olan kenarları koruyabilmek için ebeveyn turların birleşhrıinden oluşan çizelgeye kısıtlanmıştır. Literatürden alman, şehir sayıları 52 ve 3038 arasında değişen bir problem kümesiyle çaprazlama yöntemlerinin performansı test edilmiştir. Hem çözüm kalitesi, hem de süresi bakımından ümit verici sonuçlar elde edilmiştir.

Özet (Çeviri)

In traveling salesman problem (TSP), salesman visits N cities exactly ones and returns back to where he starts. When problem size increase, it gets harder to find the optimal solution in a reasonable time; many heuristics are developed in literature for this reason. In this study, an approach that combines evolutionary algorithms, which simulate the natural evolution, with conventional heuristics is proposed. Conventional heuristics, namely, nearest neighbor, greedy and insertion, are used as crossover operators and they are restricted to a union graph generated by the parent tours, with the aim of preserving edges that are the building blocks for TSP. Performances of the algorithms are tested on problems, from the literature, with different sizes ranging from 52 to 3038. Promising results are obtained in terms of solution quality and computation time.

Benzer Tezler

  1. Tez No

    651213

    Determining the best settings for the operators and parameters of genetic algorithms: A methodology and its application to traveling salesperson problem

    Genetik algoritmaların operatörleri ve parametreleri için en iyi ayarları belirleme: Bir metodoloji ve gezgin satıcı probleminde uygulaması

    YAVUZHAN AKDURAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

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

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

    PROF. DR. MURAT CANER TESTİK

  2. Tez No

    287342

    An evolutionary approach to the traveling salesman problem with pickup and delivery based on depot insertion and removal moves

    Toplamalı dağıtımlı gezgin satıcı problemi için depo yerleştirme ve çıkarma tabanlı bir sezgisel algoritma

    VOLKAN ÇINAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2010

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

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

    DOÇ. DR. TEMEL ÖNCAN

  3. Tez No

    769355

    Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar

    Multiploid evolutionary algorithms with statistical methods for dynamic environments

    EMRULLAH GAZİOĞLU

    Doktora

    Türkçe

    Türkçe

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞE ŞİMA UYAR

  4. Tez No

    901374

    1908-1974 yılları arasında Türkiye'de solun dine bakışı

    The left's view of religion in Türkiye between 1908-1974

    HÜSEYİN ARSLAN

    Doktora

    Türkçe

    Türkçe

    2024

    Siyasal Bilimlerİstanbul Üniversitesi

    Siyaset Bilimi ve Kamu Yönetimi Ana Bilim Dalı

    DOÇ. DR. YUSUF DOĞAN ÇETİNKAYA

    DR. ÖĞR. ÜYESİ MUSTAFA GÖRKEM DOĞAN

  5. Tez No

    155686

    Kapasite kısıtsız tesis yerleşim problemleri için evrimsel yaklaşımlı tavlama benzetimi algoritması

    An evolutionary approach to the simulated annealing algorithm for solving uncapacitated facility location problems

    VECİHİ YİĞİT

    Doktora

    Türkçe

    Türkçe

    2004

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

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

    PROF.DR. ORHAN TÜRKBEY

Geri Dön