Gezgin satıcı problemi için veri madenciliği tabanlı bir model önerisi
Data mining based model for the traveling salesman problem
- Tez No: 372716
- Danışmanlar: PROF. DR. ALPASLAN FIĞLALI
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: Türkçe
- Üniversite: Kocaeli Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 100
Özet
Gezgin Satıcı Problemi, belirli sayıda şehirden oluşan ve şehirler arasındaki uzaklıkların tanımlı olduğu bir şebekede, bütün şehirlere sadece bir kere uğramak ve başlanılan şehre geri dönmek şartıyla oluşturulacak en kısa turun bulunmasını amaçlayan bir problemdir. Temel bir problem türü olarak rotalama, sırlama, çizelgeleme gibi problemlerin modellenmesine ve çözümüne de temel oluşturur. Gezgin Satıcı Problemi, NP-zor grubunda yer alan bir problem olduğundan kesin çözümünün elde edilmesi problem boyutu büyüdükçe çok uzun süreler almaktadır. Veri madenciliği büyük veri yığınları içindeki anlamlı ve kullanılabilir bilginin ortaya çıkarılmasında kullanılan bir yöntemdir. Birçok alanda oldukça fazla miktardaki verinin analizi yoluyla daha önce keşfedilmemiş bilgilerin belirlenmesine olanak sağlamaktadır. Bu çalışmada, gezgin satıcı probleminin çözümüne yönelik veri madenciliği temelli bir yöntem önerilmiştir. Veri madenciliği tekniklerinden ardışık zamanlı örüntüler tekniği benzeri bir algortima ile rassal olarak üretilen gezgin satıcı turlarında en çok tekrar eden şehir çiftleri tespit edilmiştir. Sonrasında bu şehir çiftlerinin matamatiksel modele bir kısıt olarak eklenmesiyle çözüm kalitesini mümkün olduğunca koruyarak çözüm süresinin azaltılmasına çalışılmıştır. Önerilen yöntem literatürde yer alan veri kümelerine uygulanmış ve elde edilen sonuçlar tartışılmıştır.
Özet (Çeviri)
Traveling Salesman Problem is to find a shortest possible tour that visits each city exactly once for a given list of cities and back to the starting city. As a major problem, it provides modeling and solution of many other problems such as routing, sequencing, scheduling etc. Since the traveling salesman problem is a well-known NP-hard problem, it takes too long times solving the problem optimally when the problem size grows. Data mining is a method that is used detecting of meaningful and usable knowledge in large datas. By analyzing considerable amounts of data, data mining enables determination of knowledges that is not previously discovered. In this study, a data mining based algorithm is proposed for the solution of the traveling salesman problem. An algorithm based on sequence mining is used to identify the most repetitive pairs of cities in the travelling salesman tours that is generated randomly. Then these pairs of cities is added to mathematical model as constraints to decrease the solution time of the model. The proposed method is applied on literature problems and the results are discussed.
Benzer Tezler
- Gezgin satıcı problemi için veri madenciliği tabanlı sezgisel bir yaklaşım
A heuristic approach based on data mining for travelling salesman problem
SEMİYE GÖNÜLOL
Yüksek Lisans
Türkçe
2009
Endüstri ve Endüstri MühendisliğiKocaeli ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALPASLAN FIĞLALI
- A genetic algorithm for the biobjective traveling salesman problem with profits
Çok amaçlı kar getiren gezgin satıcı problemi için genetik bir algoritma
SERDAR KARADEMİR
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. DR. ESRA KARASAKAL
DOÇ. DR. HALDUN SÜRAL
- Software frameworks for production scheduling and analytical benchmarking
Üretim çizelgeleme ve analitik kıyaslamalar için yazılım çatıları
ALP EREN AKÇAY
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. GÜRDAL ERTEK
- Modeling static and dynamic dial-a-ride problem
Müşteri rotalama probleminin statik ve dinamik olarak modellenmesi
DİLEK EKİZ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SANEM SARIEL
- Traveling salesman problem: Solution with branch and data correction algorithms
Gezgin satıcı problemi: Dallan ve sınırla ve veri düzeltme algoritmaları ile çözüm
HÜSEYİN YILMAZ
Yüksek Lisans
İngilizce
2001
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI