Gezgin satıcı araç turu belirleme problemleri için yeni alt tur engelleme kısıtları
The New subtour elimination constratins for traveling salesman and vehicle routing problems
- Tez No: 57026
- Danışmanlar: İMDAT KARA
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1996
- Dil: Türkçe
- Üniversite: Eskişehir Osmangazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 117
Özet
IV ÖZET Gezgin Satıcı Problemi (GSP), serimdeki bütün düğümlere bir gezgin tarafından yalnızca bir kez uğranmayı sağlayan en kısa yolun belirlenmesi problemidir. GSP ve ondan türeyen Çok Gezgin Satıcı Problemi (m-GSP) ile Araç Turu Belirleme Problemi (ATBP) uygulama alanları ve çözüm yöntemleri itibariyle literatürde geniş bir şekilde yer almıştır. Bu problemlerin eniyi çözümlerini bulabilmek için günümüze kadar farklı alt tur engelleme yaklaşımları içeren karar modelleri ve çeşitli yöntemler geliştirilmiştir. Ama çözüm yöntemleri genellikle üstel çözüm süresi gerektirmektedir. Bu nedenle GSP'nin eniyi çözümünün etkin olarak bulunması büyük önem taşımaktadır. Bu doktora tezinde GSP, m-GSP ve ATBP için geliştirilen farklı alt tur engelleme kısıtlarına değinilmiş ve ilk olarak GSP için yeni alt tur engelleme kısıtları geliştirilmiştir. Daha sonra aynı yaklaşım kullanılarak m-GSP ve ATBP için, bu problemlere özgü, yeni alt tur engelleme kısıtlan türetilmiştir. Yeni kısıtlarla oluşturulan modeller ve literatürdeki diğer modellerin bazıları, rassal olarak türetilen test problemlerinde denenmiş ve eniyi çözümlerin süreleri belirlenmiştir. Elde edilen sonuçlar karşılaştırılarak 30 düğümlü serimlere kadar yapılan deneylerde yeni alt tur engelleme kısıtlarının, üç problemde de oldukça iyi sonuçlar verdiği görülmüştür.
Özet (Çeviri)
ABSTRACT Traveling Salesman Problem (TSP) is to find the shortest path problem that visits every point exactly once by a traveler. TSP and its extended version Multiple Traveling Salesman Problem (m-TSP) and Vehicle Routing Problem (VRP) are presented widely in the literature with respect to solution methods and application areas. In order to find the optimum solution of these problems, many decision models and a variety of methods have been proposed with different subtour elimination constraints. However, these solution methods necessitate and exponential solution time that increase the importance of finding the optimum solution for TSP efficiently. This dissertation discusses different subtour elimination constraints found in the literature for TSP, m-TSP and VRP and introduces new set of subtour elimination constraints for TSP. Then, by adopting the same approach, new set of constraints for subtour elimination that are specific to m-TSP and VRP are derived. The proposed and several current models are experimented in a randomly generated test-bed and times to find the optimum solutions are determined. The cross comparisons of the results, in the experiments up to 30 city nodes graphs, showed that the proposed model is superior to other models for all three of the problems.
Benzer Tezler
- Nakliye uçak rotalarının belirlenmesinde dağıtım ve toplama yönetiminin karar destek unsuru olarak kullanılması
The use of PDPTW method as a decision support system in determining the routes of cargo planes
İBRAHİM İNCE
Yüksek Lisans
Türkçe
2003
Savunma ve Savunma TeknolojileriKara Harp Okulu KomutanlığıHarekat Araştırması Ana Bilim Dalı
DR. HALUK AYGÜNEŞ
- Farklı çevre şartlarında metasezgisel yöntemler ile quadrotor insansız hava aracı rota optimizasyonu ve gerçeklenmesi
Optimization and implementation of quadrotor unmanned aerial vehicle route with metaheuristic methods in different environmental conditions
HAYRİ İNCEKARA
Doktora
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilişim Teknolojileri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT SELEK
- An evolutionary approach to the traveling salesman problem with pickup and delivery based on depot insertion and removal moves
Toplamalı dağıtımlı gezgin satıcı problemi için depo yerleştirme ve çıkarma tabanlı bir sezgisel algoritma
VOLKAN ÇINAR
Yüksek Lisans
İngilizce
2010
Endüstri ve Endüstri MühendisliğiGalatasaray ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEMEL ÖNCAN
- 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
2007
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TUFAN DEMİREL
- Analysis of evolutionary algorithms for constrained routing problems
Evrimsel algoritmaların yan kısıtlı rotalama problemlerinde incelenmesi
ERDEM DEMİR
Yüksek Lisans
İngilizce
2004
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HALDUN SÜRAL