Geri Dön

Solving a modified TSP problem by a greedy heuristic for cost minimization

Modifiye bir gezgin satıcı problemi için açgözlü bir sezgisel ile maliyet minimizasyonu

  1. Tez No: 478625
  2. Yazar: MURAT ÇAL
  3. Danışmanlar: DOÇ. DR. ALİ EKİCİ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: Özyeğin Ü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ı: 61

Özet

Büyük bir alanı anında fotoğraflayabilmek yalnızca uydular tarafından mümkündür. Uydular, fotoğraf/izleme süreci için gerekli zamanı azaltmaya yardımcı olabilir, ancak uydu görüntüleri her zaman mevcut değildir ve bu görüntüler mevcut olsa dahi karar vericiler için değerlendirilmesi kolay değildir. Bu sebeple karar vericiler, önceden tanımlanmış bölgenin fotoğraflarını çekmek için insansız hava araçları da denilen gözetim uçakları kullanmaktadır. Bir alanı tanımlayan bir düğüm kümesi (ağ) göz önüne alındığında, her düğüm izlenmeli ve analiz edilmelidir. Bu anlamda sorun, Gezgin Satıcı Problemi olarak tanımlanabilir. Bununla birlikte, her düğüme gitmek ve fotoğraf çekmek pratik değildir. Bunun yerine göreceli yükseklik kavramından yararlanılabilir, yani başka bir düğümden daha yüksek ya da daha uygun bir konumda bir düğüm varsa, dronlar daha yüksek konumlandırılmış düğüme gidebilir, bir fotoğraf çekebilir ve mevcut düğüm tarafından görülen diğer düğümleri otomatik olarak izlemiş olur. Bu çalışmada, yukarıdaki gibi modifiye edilmiş Gezgin Satıcı Problemi (MGSP) için, hepsi ziyaret edilmeksizin tüm düğümleri kapsayan ve toplam seyahat masrafı ile fotoğraf çekme maliyetini minimize eden bir matematiksel model sunulmaktadır. Ardından, çözüm bulmak için sezgisel bir yöntem önerilmekte ve performansı değerlendirmek için sezgisel tarafından bulunan değerler optimum çözümlerle ve alt sınır çözümleri ile karşılaştırılmaktadır. Düşük fotoğraf maliyeti olan durumlarda algoritmanın optimum çözümün ve alt sınır değerlerinin %1 fazlasına kadar iyi sonuçlar verdiği, yüksek maliyetli durumlarda ise nodlar arası görsel erişime bağlı olarak optimum çözümün veya alt sınır değerlerinin %5-10 fazlasına kadar sonuçlar üretebildiği görülmektedir.

Özet (Çeviri)

Photographing a large area in an instant is only made possible by satellites. Satellites are able to help reducing the time required for the photographing/monitoring process, however, satellite images are not available all the time, and even if they exist, they are not easy to evaluate for decision makers. So decision makers use surveillance drones, also called unmanned aerial vehicles to take photos of the predefined region. Given a set of nodes defining an area, each node should be monitored and analyzed. In that sense, the problem may be defined as a variant of Traveling Salesman Problem. It is not practical, however, just to go to every node and take a shot. Instead, one can make use of the concept of relative heights, meaning if there is a node in a higher or more appropriate position than that of another node, drones can go to that higher positioned node, take a photo and are able to monitor the other node that is 'seen' by the current node. In this study, we provide a mathematical model for this modified TSP, in which we should cover all the nodes either by photographing or physical visits and minimize the total travel cost. Then, we provide a greedy heuristic to find solutions and compare the values with optimal solutions as well as lower bounds to evaluate performance. We observe that in low photo costs, our algorithm may provide solutions within 1% of the solutions or lower bounds on hand, and in high photo costs the algorithm is still able to provide good solutions up to 5-10% of the solutions or lower bounds on hand.

Benzer Tezler

  1. Yerel aramalı kesikli farksal evrim algoritması ve kesikli parçacık sürü en iyileme algoritması kullanarak gezgin satıcı probleminin çözümü

    Solving traveling salesman problem by discete differential evolution algorithm and discrete particle swarm optimization algorithm with local search

    YELİZ KOCAMAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2010

    İşletmeYaşar Üniversitesi

    İşletme Ana Bilim Dalı

    PROF. DR. MEHMET EDİP TEKER

    PROF. DR. MEHMET FATİH TAŞGETİREN

  2. A novel modified teaching-learning based algorithm and its applications

    Yeni bir değiştirilmiş öğretme-öğrenme tabanlı algoritma ve uygulamaları

    TAREQ MEQDAM TAREQ AL-BASHAQHA

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AHMET NUSRET TOPRAK

  3. Using modified whale optimization algorithm with a comparative analysis of different technique for solving traveling salesman problem

    Seyahat satışı sorununun çözümü için değiştirilmiş toptan optimizasyon algoritmasının kullanılması

    ALI ABDULLAH SALEH SALEH

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. MESUT ÇEVİK

  4. Using modified grey wolf optimization to solve traveling salesman problem

    Seyahat salesman problemini çözmek için modifiye gri kurt optimizasyonu kullanma

    HAMZAH GHAZI ABDULFATTAH

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Elektrik ve Elektronik MühendisliğiAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ SEFER KURNAZ

  5. A Constraint programming based transformation approach for a multi-objective and multi-mode resource investment project scheduling problem under fuzzy-stochastic environments

    Bulanık-stokastik ortamlarda çok amaçlı ve çok modlu bir kaynak yatırımlı proje çizelgeleme problemi için kısıt programlama tabanlı bir dönüştürme yaklaşımı

    GİZEM ÇAKIR

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Endüstri ve Endüstri MühendisliğiDokuz Eylül Üniversitesi

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

    DOÇ. DR. KEMAL SUBULAN