Geri Dön

Traveling salesman problem: Solution with branch and data correction algorithms

Gezgin satıcı problemi: Dallan ve sınırla ve veri düzeltme algoritmaları ile çözüm

  1. Tez No: 116332
  2. Yazar: HÜSEYİN YILMAZ
  3. Danışmanlar: YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Gezgin Satıcı Problemi, Dallan ve Sınırla, Veri Düzeltme Algoritması, Traveling Salesman Problem, Branch and Bound, Data Correction Algorithm. m
  7. Yıl: 2001
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 76

Özet

oz GEZGİN SATICI PROBLEMİ: DALLAN VE SINIRLA VE VERİ DÜZELTME ALGORİTMALARI İLE ÇÖZÜM YILMAZ, Hüseyin Yüksek Lisans, Elektrik ve Elektronik Mühendisliği Bölümü Tez Yöneticisi: Yrd. Doç. Dr. Cüneyt F. Bazlamaçcı Aralık 2001, 66 sayfa Simetrik gezgin satıcı problemi, katışımsal eniyileme problemlerinin tipik ve en çok bilinenlerinden biridir. NP-tam problemlerden olduğu için, en iyi sonuç amaçlı çözümler, bir şekilde ağaç arama algoritmalarına başvururlar. Ağaç arama algoritmaları, genellikle alt sınırlama, üst sınırlama, dallanma ve değişken sabitleme yaklaşımlarıyla birbirlerinden farklılık gösterirler. Lagrangean gevşetmesiyle birlikte 1-ağaç problemi, dallan ve sınırla tekniklerinde en çok kullanılan alt sınırlama tekniklerinden birisidir. Bu çalışma ilk olarak gezgin satıcı problemi için dallan ve sınırla temelli çözüm yöntemlerini araştırmaktadır. Daha sonra varolan dallanma kurallarının etkinlikleri deneysel ve karşılaştırmalı olarak incelenmiştir. Veri düzeltme ivalgoritması (DCA), girdi problem verisinin, her dallanışta polinom zamanlı çözülebilecek şekilde düzeltildiği öz yinelemeli bir dallan ve sınırla algoritmasıdır. Tez çalışması, veri düzeltme algoritmasının simetrik gezgin satıcı problemine 1-ağaç matrisleri kullanarak uygulanabilirliğini de araştırmaktadır.

Özet (Çeviri)

ABSTRACT TRAVELING SALESMAN PROBLEM: SOLUTION WITH BRANCH AND BOUND AND DATA CORRECTION ALGORITHMS YILMAZ, Hüseyin MSc, Department of Electrical and Electronics Engineering Supervisor: Asst. Prof. Dr. Cüneyt F. Bazlamaçcı December 2001, 66 pages The symmetric traveling salesman problem is one of the most famous and typical problems in combinatorial optimization. Being NP-complete, attempts for solving it to optimality mostly resort, one way or another, to tree search algorithms. The tree search algorithms generally differ in their lower bounding, upper bounding, branching and variable fixing approaches. The 1- tree problem in association with Lagrangean relaxation is among the most widely used lower bounding strategies reported in branch and bound techniques. This work first reviews the branch and bound based solution approaches for the traveling salesman problem. Then the effectiveness of the existing branching strategies is empirically evaluated against each other. The iidata correction algorithm (DCA), is a recursive branch and bound type algorithm in which the data of the given problem instance is 'corrected' at each branching in such a way that the new instance is polynomially solvable. The thesis also investigates the applicability of the data correction algorithm to the symmetric traveling salesman problem by using 1-tree matrices.

Benzer Tezler

  1. Tez No

    46358

    Gezgin satıcı problemi

    Traveling salesman problem

    VOLKAN M. ÖZALP

    Yüksek Lisans

    Türkçe

    Türkçe

    1995

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. FÜSUN ÜLENGİN

  2. Tez No

    885453

    Düşük hesaplama maliyetine sahip miyopik olmayan adaptif örnekleme ve çevresel izleme için Monte Carlo arama ağacı ve dallanma sınırlama yöntemlerinin uygulanması

    Application of Monte Carlo tree search and branch-and-bound methods for non-myopic adaptive sampling and environmental monitoring with low computational cost

    PERİHAN KARAKÖSE

    Doktora

    Türkçe

    Türkçe

    2024

    Mekatronik MühendisliğiFırat Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CAFER BAL

    DR. ÖĞR. ÜYESİ HARUN YETKİN

  3. Tez No

    361056

    Kümeleme ve genetik algoritma destekli yaklaşımlarla kapasite kısıtlı araç rotalama probleminin çözümü: perakende zincirinde uygulanması

    Solution of the capacity constraint vehicle routing problem with cluster and genetic algorithm based approach: a retail chain application

    TOLGA ŞEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

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

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

    DOÇ. DR. HARUN REŞİT YAZĞAN

  4. Tez No

    641342

    Optimization of last-mile deliveries with synchronous truck and drones

    Eşzamanlı kamyon ve insansız hava araçları ile son mil teslimatları eniyilemesi

    AYSU ÖZEL

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

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

    PROF. DR. BAHAR YETİŞ

  5. Tez No

    401361

    Time and reliability in vehicle routing problems

    Başlık çevirisi yok

    DUYGU TAŞ

    Doktora

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiTechnische Universiteit Eindhoven

    PROF. DR. TOM VAN WOENSEL

    DR. NICO DELLAERT

    DR. TON DE KOK

Geri Dön