Çok gezginli en küçük gecikme problemi için yeni karar modelleri
New formulations for multiple traveler minimum latency problem
- Tez No: 398857
- Danışmanlar: PROF. DR. İMDAT KARA
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Gezgin satıcı problemi, Travelling salesman problem
- Yıl: 2015
- Dil: Türkçe
- Üniversite: Başkent Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
En küçük Gecikme Problemi (EGP) rotalama problemlerinin temelini oluşturan Gezgin Satıcı Probleminin (GSP) bir türü olmaktadır. EGP, bir başlangıç düğümünden başlayarak, tüm düğümlere uğradıktan sonra başlangıç noktasında veya verilen bir düğümde sona eren Hamilton turunu veya yolunu araştırmaktadır. GSP bütün müşterilere uğramak için gerekli olan toplam zamanı en küçük yapmayı amaçlamakta, EGP ise tüm müşterilerin toplam gecikme zamanını en küçük yapmayı amaçlamaktadır. EGP'nin en önemli özel durumu olarak görülen çok gezginli uzantısı için kaynaklardaki yapılan çalışmalar incelendiğinde polinom sayıda ve üstel sayıda kısıta sahip iki farklı matematiksel model olduğu ancak bu modellere bakıldığında kısa sürede çözüme ulaşma açısından verimli olmadığı belirlenmiştir. Bu nedenle yeni karar modellerine ihtiyaç olduğu görülmüştür. Bu çalışma kapsamında ise, temel konu olarak ele alınan çok gezginli EGP için yapılacak çalışmanın altyapısını oluşturması amacıyla öncelikle EGP modelleri kaynaklarda bulunan kıyaslama problemi verileri kullanılarak sayısal analizlere tabi tutulmuştur. İşlem süresi (CPU) ve doğrusal programlama (LP) gevşetme değerleri yönüyle en iyi performans gösteren model belirlenmiştir. Çok gezginli EGP için üç tanesi yeni model bir tanesi kaynaklarda yer alan bir model olmak üzere toplam dört model ele alınıp kaynaklardaki farklı düğüm sayısına sahip kıyaslama problemleri ve gezgin sayıları için çözdürülerek en iyi performans gösteren model önerilmiştir. Yapılan bu karşılaştırmalı analizler sonucunda problem boyutu ve CPU süresi arasındaki ilişki ve gezgin sayısı ile CPU süresi arasındaki ilişki ile ilgili çıkarımlar da elde edilmiştir. Bu çalışmanın en önemli sonucu çok gezginli EGP için yeni bir modelin bilime katkı olarak sunulmasıdır.
Özet (Çeviri)
The Minimum Latency Problem (MLP) is a kind of Traveling Salesman Problem (TSP) which is the basis of the routing problems. MLP investigates the Hamilton tour or path, which starts from an initial node, after visiting all nodes, it ends at the starting or any given node. While TSP aims to make the smallest total time required to visit all customers, MLP aims to minimize total delay time of customers. When we review the literatüre, MLP with multiple traveler which is regarded as the most important exception of MLP, is modeled in two different ways: one with polynomial and the other with exponential number of constraints. However, both models are not efficient in terms of reaching a solution in a short time. Therefore the need for a new decision model is obvious. In this study, firstly MLP models are subjected to several quantitative analysis using available benchmarking problems in the literature. The purpose of this analysis is to create an infrastructure for the multiple traveling MLP. The best performing model is determined in terms of processing time (CPU) and linear programming (LP) relaxation values. Four models, one from literature and three new ones, are solved for benchmark problems with different number of nodes and different number of travelers and the best performing model is selected accordingly. As a result of this comparative analysis, we observe the relationship between problem size and CPU time and also the relationship between the number of travelers and CPU time. The most important result of this study is presented as a contribution to science, a new model for multiple traveling MLP.
Benzer Tezler
- Zaman pencereli tamirci problemi ve uzantılarının yeni matematiksel modelleri
New mathematical models for the traveling repairman problem with time windows and its extensions
GÖZDE ÖNDER UZUN
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiBaşkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İMDAT KARA
- Ağırlıklı toparlama dizili DD/KBÇE iletişim sistemleri için yayma kodlarının tanımlanmasında ve en iyilerinin belirlenmesinde yeni yaklaşımlar
New approaches to the description of spreading codes and to the determination of optimum spreading code set for DS/CDMA communication systems with weighted despreading sequences
İBRAHİM DEVELİ
Doktora
Türkçe
2003
Elektrik ve Elektronik MühendisliğiErciyes ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEBRAİL ÇİFTLİKLİ
- Fractal geometry inspired solution generation to enhance effectiveness of metaheuristic algorithms
Metasezgisel algoritmaların etkinliğini arttırmak için esin kaynağı fraktal geometri olan çözüm oluşturma
MELİKE ÖZTÜRK
Doktora
İngilizce
2020
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
PROF. DR. ÇİĞDEM ALABAŞ USLU
- Ortak hedefli röleli telsiz iletişim sistemlerinde bit ve enerji verimliliği analizi
Goodput and energy efficiency analysis for wireless relayed communication systems with common destination
SİNAN ATAN
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN ÜMİT AYGÖLÜ
- Linearity and efficiency improvement on RF power amplifiers
RF kuvvetlendiricilerde doğrusallık ve verimin iyileştirilmesi
ÖMER AYDIN
Doktora
İngilizce
2016
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik-Elektronik Ana Bilim Dalı
PROF. OSMAN PALAMUTÇUOĞULLARI