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ı: Belirtilmemiş.
Ö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
- Robot kollarda optimum hareket sentezi
Optimal trajectory synthesis for manipulation robots
ÖZGÜR TURHAN
- Lojistik köylerin raylı sistem taşımacılığı etkinliğinin değerlendirilmesi için çok kriterli bir değerlendirme yaklaşımı
A multi-criteria evaluation approach for assessing the efficiency of rail system transportation in logistics villages
DENİZ AY
Yüksek Lisans
Türkçe
2026
İşletmeEskişehir Teknik ÜniversitesiRaylı Sistemler Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ FATMA YAŞLI ŞEN
- 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Ş
- Obstacle avoidance for fixed wing aircraftby using control barrier functions
Sabit kanatlı uçaklar için kontrol bariyer fonksiyonlarının kullanılması ile çarpmadan kaçış
HURİYE NUR TOPRAK
Yüksek Lisans
İngilizce
2025
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiSavunma Teknolojileri Ana Bilim Dalı
DOÇ. DR. EMRE KOYUNCU