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
- Tez No: 116332
- Danışmanlar: YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- 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
- Yıl: 2001
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- Gezgin satıcı problemi
Traveling salesman problem
VOLKAN M. ÖZALP
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN ÜLENGİN
- Özel düzenlenmiş plyometrik antrenmanların genç basketbolcuların anaerobik güç performansına etkisi
Effects of regular specific plyometric training on anaerobic power of young basketball players
YÜKSEL SAVUCU
Yüksek Lisans
Türkçe
2001
SporFırat ÜniversitesiBeden Eğitimi ve Spor Ana Bilim Dalı
DOÇ.DR. MEHMET KUTLU
- Hidrofoillerde derinlik ve kat-kat etkisinin incelenmesi
An Investigation of depth and cascade effect on hydrofoils
AYDIN ŞALCI
- Türkiye Taşkömürü Kurumu Armutçuluk Taşkömürü İşletme Müessesesi yeraltı ocaklarında yüksek basınçlı su jetleriyle kömür kazısının araştırılması ve uygulanabilirliği
The Investigation of coal excavation with high-pressure water jets and its applicability to the underground mines of Armutçuk hardcoal company of Turkish hardcoal enterprise
NURİ ALİ AKÇIN
Doktora
Türkçe
1986
Maden Mühendisliği ve Madencilikİstanbul Teknik ÜniversitesiPROF. DR. ŞİNASİ ESKİKAYA
- K.K.T.C. turizm arz talep yapısının araştırılması ve geleceğe yönelik konaklama sistemi çalışması
Başlık çevirisi yok
HASAN NURİ
Yüksek Lisans
Türkçe
1987
TurizmHacettepe Üniversitesiİşletme Ana Bilim Dalı
YRD. DOÇ. DR. DOĞAN YAŞAR AYHAN