Geri Dön

Relative distances approach for multi-traveling salesmen problem

Çoklu gezgin satıcı problemi için göreli mesafeler yaklaşımı

  1. Tez No: 857480
  2. Yazar: EMRE ERGÜVEN
  3. Danışmanlar: PROF. DR. FARUK POLAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2024
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 102

Özet

Bu çalışma, Çoklu Gezgin Satıcı Problemini çözmeyi amaçlamaktadır. Bu problemlerde, görevler (kargo teslimatı, depo yerleştirimi) birden çok etmen (gezgin satıcı, otonom robot) tarafından tamamlanmaya çalışılır. Bu gibi problemlerde iki ana hedef vardır; birincisi toplam kat edilen mesafeyi minimize etmektir, ikincisi de bir etmen tarafından kat edilen maksimum mesafeyi minimize etmektir. Bu çözümdeki ana öncelik toplam kat edilen mesafeyi minimize etmektir. Fakat tamamen toplam kat edilen mesafeyi minimize etmeye odaklanmak, bir etmen tarafından kat edilen maksimum mesafeyi artırabilir. Bu çalışmada sunulan yöntem, bir etmen tarafından kat edilen maksimum mesafeyi de makul bir seviyede tutmaktadır. Problemin kombinatoryal yapıda olması sebebiyle maliyeti minmize eden bir çözümü bulmak imkansızdır (günümüz koşullarında). Gerçek hayatta uygulanabilirlik için çözümün hızlı bir şekilde bulunması gerekmektedir. Yani, şu söylenebilir ki; problemin üçüncü hedefi, çözüm bulunana kadarki karmaşıklığı ve harcanan zamanı düşürmektir. Çoklu gezgin satıcı problemi, genellikle iki ayrı aşamada çözülmeye çalışılır. İlk aşamada görevler kullanıcılara farklı yaklaşımlarla verilir (k-ortalamalar kümesi, yoğunluk tabanlı mekansal uygulamaların gürültüyle kümelenmesi). İkinci aşama ise her gezgin için verilen görevlerin optimal sıralamasıdır. İkinci aşamadaki problem gezgin satıcı problemiyle aynıdır. Göreli Mesafe modelimiz bu fazları tek bir yöntemde özgün bir keşifsel yaklaşımla birleştirir. Modelimiz sayesinde görevler kolayca iptal edilebilir veya yeni görevler eklenebilir ve canlı planlama sağlanabilir. Yukarıda belirtilen tüm metodlar C++'da çalıştırılmış ve Python'da görselleştirilmiştir.

Özet (Çeviri)

This study aims to find a solution for the Multi-Traveling Salesman Problem (M-TSP). Within the problem, multiple tasks (e.g cargo delivery, warehouse placement) are executed by multiple agents (e.g traveling salesman, autonomous robots). There are two main objectives for these problems; the first one is minimizing the total path cost, and the second one is minimizing the maximum cost of salesmen (makespan). We mainly focused on minimizing the total cost. But fully focusing on decreasing the total cost mostly results with an increase on the makespan. Our method keeps the makespan in a reasonable range. Due to the combinatorial structure of the problem, finding the cost-optimal solutions is impossible (with current conditions). Solutions must be found quickly in order to be applicable in real-life. So, it can be said that the third objective of the problem is reducing the complexity and time to find the solutions. The MTSP problem is generally tried to be solved in two separate phases. In the first phase, tasks are assigned to salesmen with different approaches (e.g K-Means, DBSCAN). Second phase is finding optimal routes for each salesman. The problem within the second stage is identical to the Traveling Salesman Problem (TSP). Our relative distance model combines these phases within one method with a novel heuristic approach. With our model, tasks can be easily added and removed from the problem space and live-scheduling can be enabled. All of these methods mentioned are implemented on C++ and visualized on Python

Benzer Tezler

  1. Aşırı denizlerdeki gemi hareketlerinin cisim-tam dilim teorisi yaklaşımı ile simülasyona dayalı hesaplanması

    Simulation based calculation of ship motions in extreme seas with a body-exact strip theory approach

    KIVANÇ ALİ ANIL

    Doktora

    Türkçe

    Türkçe

    2017

    Gemi Mühendisliğiİstanbul Teknik Üniversitesi

    Gemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. DEVRİM BÜLENT DANIŞMAN

    PROF. DR. KADİR SARIÖZ

  2. Correlations between ground motion intensity measures and structural response parameters through nonlinear dynamic analyses

    Yer hareketi şiddet ölçütleri ve yapısal davranış parametreleri arasındaki korelasyonların doğrusal olmayan dinamik analizler yardımıyla bulunması

    UFUK HANCILAR

    Doktora

    İngilizce

    İngilizce

    2009

    Deprem MühendisliğiBoğaziçi Üniversitesi

    Deprem Mühendisliği Ana Bilim Dalı

    PROF. DR. ESER DURUKAL

  3. A 3d partial simulation of human artery and vein system using two-phase blood flow coupled with a thermal RBC aggregation model

    Termal rbc birikme modeli ile insan ana arter ve damar ağının üç boyutlu kısmi iki fazlı kan akışı simülasyonu

    ERKE ARIBAŞ

    Doktora

    İngilizce

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı

    PROF. DR. MUSTAFA SERDAR ÇELEBİ

  4. Endüstriyel kazalar için acil durum toplanma noktasının çok kriterli karar verme yöntemi ile seçimi

    Emergency assembly point selection with multi-criteria decision making method for industrial accidents

    ONUR HOŞCAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Mühendislik BilimleriGazi Üniversitesi

    Tedarik ve Lojistik Yönetimi Ana Bilim Dalı

    DOÇ. DR. SALİHA ÇETİNYOKUŞ

  5. Two novel MCDM approaches PODER and V-PARS: Evaluating micromobility modes in Paris and Istanbul

    İki yeni ÇÖKV yaklaşımı PODER ve V-PARS: Paris ve İstanbul'da mikromobilite modlarının değerlendirilmesi

    ESRA ÇAKIR

    Doktora

    İngilizce

    İngilizce

    2024

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

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

    PROF. DR. ABDULLAH ÇAĞRI TOLGA