Geri Dön

Optimizasyon algoritmalarının gezgin satıcı problemi üzerinde incelenmesi

Analysis of optimization algorithms based on traveling salesman problem

PDF İndir

  1. Tez No: 734941
  2. Yazar: MERT ÇALIŞ
  3. Danışmanlar: PROF. DR. SEMRA GÜNDÜÇ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2022
  8. Dil: Türkçe
  9. Üniversite: Ankara Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 69

Özet

Gezgin Satıcı Problemi aralarındaki mesafeler belli olan düğümlerin (şehir, nokta gibi) her birinden yalnızca bir defa geçilecek olması koşulu ile bir düğümden başlayıp tekrar aynı düğüme dönen en az maliyetli ya da en kısa yolu bulmayı amaçlayan bir problemdir. Bu problem araç rotası oluşturma, ulaşım rotaları oluşturulması, lojistik planlamaları ve elektronik devre tasarımı gibi birçok farklı konuya uygulanabilir. Problem genel olarak anlaşılması kolay fakat çözümü zor olan bir problemdir. Çözümün zorluğunun sebebi ise artan düğüm sayısına ile birlikte potansiyel rota sayısının da artması ve bununla birlikte problemin çözümü için gereken zamanın üstel olarak artmasıdır. Tez çalışması kapsamında literatürde daha önce problem üzerinde denenmiş olan yöntemler incelenmiş ve Lin-Kernighan Sezgisel yöntemi üzerinde bazı optimizasyon çalışmaları yapılmıştır. Algoritma üzerinde yapılan optimizasyon çalışmaları ile elde edilen yöntem ile Lin-Kernighan yönteminin karşılaştırılması yapılmıştır. Yapılan çalışmalar sonucunda uygulama üzerinde düğüm seçimlerinin ve sıralamalarının uygulamanın performansını etkilediği sonucuna varılmıştır. Uygulanan yeni yöntem ile bazı veri setleri üzerinde hem zamansal olarak iyileşmeler, hem de optimum sonuca ulaşma performansının arttığı gözlemlenmiştir.

Özet (Çeviri)

The Traveling Salesman Problem is a problem that aims to find the least costly or shortest path, starting from a node and returning to the same node by passing through only once each of the nodes (such as a city, a point) with certain distances between them. This problem can be applied to many different issues such as vehicle route creation, transportation routes creation, logistics planning and electronic circuit design. The problem is generally easy to understand but difficult to solve. The reason for the difficulty of the solution is that with the increasing number of nodes, the number of potential routes also increases, and the time required to solve the problem increases exponentially. Within the scope of the thesis study, the methods that have been tried on the problem before in the literature were examined and some optimization studies were carried out on the Lin-Kernighan Heuristics method. The comparison of the method obtained with the optimization studies on the algorithm and the Lin-Kernighan method was made. As a result of the studies, it was concluded that the node selections and rankings on the application affect the performance of the application. With the new method applied, it was observed that both temporal improvements and the performance of reaching the optimum result increased on some data sets.

Benzer Tezler

  1. Tez No

    201479

    Stokastik araç rotalama algoritmalarının karşılaştırmalı incelenmesi

    Comparative research of stochastic vehicle routing algorithms

    ULAŞ DARCAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2007

    Endüstri ve Endüstri MühendisliğiYıldız Teknik Üniversitesi

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

    YRD. DOÇ. DR. TUFAN DEMİREL

  2. Tez No

    816186

    Next generation wireless networks for social good

    Sosyal fayda için yeni nesil telsiz ağlar

    SULTAN ÇOĞAY

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ GÖKHAN SEÇİNTİ

  3. Tez No

    458689

    Gezgin satıcı probleminin çözümünde genetik algoritmanın parametrelerinin incelenmesi

    Investigation of parameters of genetic algorithm in the solution of traveling salesman problem

    MERYEM PULAT

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    EkonometriDokuz Eylül Üniversitesi

    Ekonometri Ana Bilim Dalı

    PROF. DR. İPEK DEVECİ KOCAKOÇ

  4. Tez No

    530338

    Analysis of crossover, mutation methods and rates of genetic algorithms applied on traveling salesman problem

    Genetik algoritmaların çaprazlama, mutasyon metodlarının ve parametrelerinin gezgin satıcı problemi üzerinde analizi

    ADNAN BAL

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    Bilim ve TeknolojiGalatasaray Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MURAT AKIN

  5. Tez No

    335283

    Optimizasyon problemlerinde bal arıları evlilik optımızasyonu algoritmasının (marriage in honey bee optimization-MBO) performansının geliştirilmesi

    The improving performance of marriage in honey bee optimization algorithm (MBO) on optimization problems

    YÜKSEL ÇELİK

    Doktora

    Türkçe

    Türkçe

    2013

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ERKAN ÜLKER

Geri Dön