Seçici gezgin satıcı problemi için yeni matematiksel modeller
New mathematical formulations for the selective travelling salesman problem
- Tez No: 364255
- 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: Belirtilmemiş.
- Yıl: 2014
- 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ı: 64
Özet
Gezgin 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 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.
Özet (Çeviri)
Travelling Salesman Problem (TSP) is the basis of many real-life problems as vehicle routing, scheduling etc. The objective of TSP and its extensions is usually to minimize the total cost or the total amount of time spent or the total distance travelled. In recent years, researchers take an interest in problems which aim to maximize the profit such as revenue, income etc. by relaxation of the constraint which ensures to visit all nodes in the network, under the given budget or travel time constraint. In the literature, these problems are named as“The Selective TSP or Orienteering Problem ”,“The Prize-collecting TSP ”and“The Profitable Tour Problem”. These problems are gathered under the common name of“TSP with Profits”. Just as TSP and its extensions, it is clear that heuristic methods or special algorithms are primarily preferred as solution approaches of TSP with profits, therefore mathematical models don't attract enough attention. In the scope of this study, two new mathematical models (node-based and edge-based) have been presented for the Selective TSP which is the most popular problem of TSP with profits. Size of the new models is polynomial according to the numbers of its constraints and binary decision variables so that they can be solved by an integer-programming solver. Some of Orienteering Problem benchmark instances are solved with new models by using CPLEX 12.5 software. The results are compared to an existing model in literature and it is found that the new models are superior to the existing model. Besides, it has been detected that some of the optimal solutions of mathematical models are larger than the solutions of heuristics in the literature.
Benzer Tezler
- Otel seçimli oryantiring problemi için yeni matematiksel modeller
New mathematical models for orienteering problem with hotel selection
EZGİ GENCEL
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiBaşkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUSAN DERYA
- Genelleştirilmiş seçici gezgin satıcı problemleri için yeni matematiksel modeller
New mathematical formulations for the generalized selective travelling salesman problems
GÖZDE GÜRKAN ALTUNSOY
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiBaşkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TUSAN DERYA
- Genelleştirilmiş takım oryantiring problemi için yeni matematiksel modeller
New mathematical formulations for the generalized teamorienteering problems
EZGİ GÜL ULU GÖKALP
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiBaşkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUSAN DERYA
- Optimizing the operations of electronic component placement machines
Elektronik parça yerleştirme makinelerinin optimizasyonu
ALİ FUAT ALKAYA
Doktora
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
DOÇ. DR. EKREM DUMAN
PROF. DR. M. AKİF EYLER
- A Configuration of systematic approaches for drinking water distribution problem in metropolitan areas
Başlık çevirisi yok
SELİM KAHVECİOĞLU
Doktora
İngilizce
1997
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. SELİME SEZGİN