Relative distances approach for multi-traveling salesmen problem
Çoklu gezgin satıcı problemi için göreli mesafeler yaklaşımı
- Tez No: 857480
- Danışmanlar: PROF. DR. FARUK POLAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2017
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İ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
- 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
2009
Deprem MühendisliğiBoğaziçi ÜniversitesiDeprem Mühendisliği Ana Bilim Dalı
PROF. DR. ESER DURUKAL
- 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
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. MUSTAFA SERDAR ÇELEBİ
- 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
2019
Mühendislik BilimleriGazi ÜniversitesiTedarik ve Lojistik Yönetimi Ana Bilim Dalı
DOÇ. DR. SALİHA ÇETİNYOKUŞ
- 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
2024
Endüstri ve Endüstri MühendisliğiGalatasaray ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ABDULLAH ÇAĞRI TOLGA