Geri Dön

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

  1. Tez No: 57026
  2. Yazar: AYDIN SİPAHİOĞLU
  3. Danışmanlar: İMDAT KARA
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1996
  8. Dil: Türkçe
  9. Üniversite: Eskişehir Osmangazi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2003

    Savunma ve Savunma TeknolojileriKara Harp Okulu Komutanlığı

    Harekat Araştırması Ana Bilim Dalı

    DR. HALUK AYGÜNEŞ

  2. 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

    Türkçe

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilişim Teknolojileri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MURAT SELEK

  3. 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

    İngilizce

    2010

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

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

    DOÇ. DR. TEMEL ÖNCAN

  4. 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

    Türkçe

    2007

    Endüstri ve Endüstri MühendisliğiYıldız Teknik Üniversitesi

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

    YRD. DOÇ. DR. TUFAN DEMİREL

  5. 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

    İngilizce

    2004

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

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

    YRD. DOÇ. DR. HALDUN SÜRAL