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ı, Veri düzeltme, Traveling Salesman Problem, Branch and Bound, Data Correction Algorithm. m, Travelling salesman problem, Data correction
  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ı: Belirtilmemiş.

Ö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

    208934

    Türk silahlı kuvetlerinde ring taşımacılık faaliyetlerinin maliyet etkinlik analizi ve ulaştırma modelleri yardımıyla güzergah optimizasyonu

    The cost activity analiysis of the ring transport events in Turkish armed forces and route optimization whit the help of transport models

    DAVUTHAN GÜNAYDIN

    Yüksek Lisans

    Türkçe

    Türkçe

    2006

    EkonometriMarmara Üniversitesi

    Ekonometri Ana Bilim Dalı

    YRD. DOÇ. DR. FATMA URFALIOĞLU

  3. Tez No

    167198

    The tool transporter movements problem in flexible manufacturing systems

    Esnek imalat sistemlerinde makine ucu taşıyıcısı problemi

    FATMA KILINÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2005

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

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

    PROF. DR. MERAL AZİZOĞLU

  4. Tez No

    21809

    Ulaşım şebekesi tasarımı için çok amaçlı bir model

    A Multiobjective approach to transportation network design

    ALPASLAN FIĞLALI

    Doktora

    Türkçe

    Türkçe

    1992

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

    PROF. DR. ATAÇ SOYSAL

  5. Tez No

    170957

    Sezgisel fonksiyonlar temelinde tabu arama ve genetik algoritmalarının gezgin satıcı problemine uygulanması

    Tabu search and application of genetic algorithms to traveling salesman problem in the basic of heuristic functions

    MUSTAFA BİLGEHAN İMAMOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2005

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ.DR. VASİF NABİYEV

Geri Dön