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ı, Traveling Salesman Problem, Branch and Bound, Data Correction Algorithm. m
- 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ı: 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
- 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
- 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
2024
Mekatronik MühendisliğiFırat ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CAFER BAL
DR. ÖĞR. ÜYESİ HARUN YETKİN
- 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
2014
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. HARUN REŞİT YAZĞAN
- 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
2020
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. BAHAR YETİŞ
- Time and reliability in vehicle routing problems
Başlık çevirisi yok
DUYGU TAŞ
Doktora
İngilizce
2013
Endüstri ve Endüstri MühendisliğiTechnische Universiteit EindhovenPROF. DR. TOM VAN WOENSEL
DR. NICO DELLAERT
DR. TON DE KOK