Enstitüler / Institutes
Permanent URI for this communityhttps://hdl.handle.net/11727/1390
Browse
3 results
Search Results
Item Otel seçimli gezgin satıcı problemi için karşıt çözüm temelli değişken komşu iniş sezgiseli(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2020) Akpinar, İperk Damla; Keçeci, BarışBu tez kapsamında Gezgin Satıcı Problemi (GSP)'nin bir versiyonu olan Otel Seçimli Gezgin Satıcı Problemi (OSGSP) ele alınmıştır. GSP, aralarındaki uzaklıkları bilinen noktaların her birine yalnız bir kez uğramak şartıyla, başlangıç noktasına dönen en az maliyetli turun bulunması problemidir. OSGSP ise günlük çalışma süresi/mesafesi kısıtı içermektedir. Bu kısıt, tüm noktaların bir seferde ziyaret edilmesini mümkün kılmamaktadır. Bu nedenle gezgin, gün (kısıtlı çalışma süresi/mesafesi) sonunda uygun bir bekleme (otel) noktasında duraklar (konaklar) ve bir sonraki gün, tura kaldığı otel noktasından başlayarak devam eder. Her otele uğrama zorunluluğu bulunmamakla birlikte bir otele birden fazla kez de uğranabilmektedir. Bir otelde başlayıp yine bir otelde son bulan sıralı noktalar kümesine "gezi", tüm müşterileri kapsayan sıralı geziler kümesine "tur" denmektedir. Problemde birincil amaç tur içinde yapılan gezi sayısını en küçüklemektir. İkincil amaç ise gezi başına geçen süre/mesafenin günlük çalışma süresi kısıtını aşmaması şartı ile turun toplam mesafesini en küçüklemektir. Tez çalışmasında, bu problemin çözümü için Değişken Komşu İniş algoritmasına dayalı bir algoritma geliştirilmiştir. En Yakın Komşu Prensibi (EYKP) ile başlangıç çözüm elde edilmiş ve bu çözümü iyileştirmek amacıyla Karşıt Çözüm Temelli Değişken Komşu İniş Sezgiseli (KÇTDKİS) uygulanmıştır. Elde edilen sonuçlar literatürde var olan diğer sezgisel algoritmalardan elde edilen sonuçlar ile karşılaştırılmıştır. Yapılan analizler sonucunda 120 problemin 35 tanesinde daha iyi sonuçlar elde edilmiştir. Ayrıca sonuçlar, yine literatürde var olan Cplex çözücüsü ile elde edilen sonuçlarla karşılaştırılmış ve 78 problemin 17'sinde ya optimal sonuçlar elde edilmiş ya da bilinen en iyi sonuçlardan daha iyi sonuçlara ulaşılmıştır. In this dissertation, The Travelling Salesperson Problem with Hotel Selection (TSPHS), which is a variant of The Travelling Salesperson Problem (TSP), is considered. TSP consist of a salesman and set of nodes known distances between them. The salesman has to visit each one of the nodes starting from a certain one and returning to the same node. The goal is to have the least cost tour during the salesman's trip. TSPHS includes daily working time / distance restriction. This constraint does not allow to visit all points at once. For this reason, the traveler stops (roosts) at a suitable waiting (hotel) point at the end of the day (limited working time / distance) and continues on the next day's trip from the hotel point where he stayed. There is no obligation to visit each hotel, and a hotel can be visited more than once. A set of ordered nodes starting and ending at a hotel is called a trip, and a set of ordered trips covering all nodes is called a tour. The primary objective of the problem is to minimize the number of trips. The secondary objective is to minimize the total distance of the tour, provided that the time / distance per trip does not exceed the daily working time limit. In the dissertation, an algorithm based on Variable Neighborhood Descent algorithm is developed for the solution of this problem. The starting solution with The Nearest Neighbor Principle (NNP) is obtained. Opposition Based Variable Neighborhood Descent (OBVND) Algorithm is applied to improve this solution. The results are compared with the other heuristic algorithms in the literature. As a result of the analysis, better results are obtained in 35 of 120 problem. In addition, the results are compared with those obtained with Cplex solvent, which is also available in the literature. In 17 of 78 problems, either optimal results are obtained or better results are obtained than the best known results.Item Çok gezginli en küçük gecikme problemi için yeni karar modelleri(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2015) Önder, Gözde; Kara, İmdatEn 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. 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.Item Seçici gezgin satıcı problemi için yeni matematiksel modeller(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2014) Yalçın, Papatya Sevgin; Kara, İmdatGezgin Satıcı Problemi (GSP), araç rotalama, çizelgeleme vb. pek çok gerçek hayat problemlerinin temelini oluşturur. Kaynaklardaki çalışmalara bakıldığında, GSP ve uzantılarında amaç olarak genellikle, toplam maliyetin, toplam kat edilen yolun veya toplam harcanan sürenin enküçüklenmesi esas alına gelmiştir. Son yıllarda, serimdeki tüm düğümlere uğrama kısıtı gevşetilerek, verilen bir bütçe veya seyahat süresi kısıtı altında, gezginin uğrayabileceği düğümlerden elde edilecek kar, kazanç vb. getiriler toplamının enbüyük olması istenen problemler de araştırmacıların ilgi odağı olmuştur. Kaynaklarda ”Orienteering problemi veya Seçici GSP (The Selective TSP)”, “Getiri Toplamalı GSP-(The Price Collecting TSP)” veya “Karlı Tur Problemi (Profitable Tour Problem)” olarak isimlendirilen bu tür problemler, “Getiri Yönlü GSP (Traveling Salesman Problems with Profits)” başlığı altında toplanmaktadır. Farklı isimlendirmeler olmakla birlikte, bu tür problemlerde, aynı kısıtlar altında farklı amaç fonksiyonlarının ele alındığı görülmektedir. GSP ve uzantılarında olduğu gibi, getiri yönlü problemlerin çözüm yaklaşımlarının da öncelikle sezgiseller veya özel algoritmalar üzerine yoğunlaştığı, matematiksel modellere yeterince önem verilmediği görülmektedir. Söz konusu durum göz önüne alınarak, bu çalışmada ilk olarak, getiri yönlü GSP’nin kaynaklarda var olan modelleri incelenmiş, sonra getiri yönlü GSP’lerin benzer matematiksel yapısı nedeniyle bu problemlerden biri olan Seçici GSP, diğer adıyla Orienteering problemi için bir düğüm tabanlı bir de ayrıt tabanlı iki yeni karar modeli önerilmiştir. Önerilen modeller, kısıt ve tamsayı değişken sayısı itibariyle polinom büyüklüktedir ve tamsayılı karar modellerini çözen herhangi bir paket programla doğrudan kullanılabilecek özelliktedir. Önerilen modellerin performanslarını görmek amacıyla, kaynaklarda yer alan karşılaştırma problemleri Vansteenwegen-Souffriau-Oudheusden modeli ve yeni modellerle, CPLEX 12.5 paket programı kullanılarak çözülmüştür. Elde edilen sonuçlar, çözüm süreleri ve doğrusal programlama gevşetme değerleri yönleriyle analiz edilmiş ve önerilen yeni ii modellerin çok üstün olduğu görülmüştür. Ayrıca, matematiksel karar modelleri ile bulunan eniyi değerlerin, kaynaklarda sezgisel algoritmalarla bulunan bilinen eniyi değerlerin çoğundan daha büyük olduğu tespit edilmiştir.