Gezgin satıcı problemi için veri madenciliği tabanlı bir model önerisi


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Kocaeli Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2014

Tezin Dili: Türkçe

Öğrenci: ATAKAN ALKAN

Danışman: Alpaslan Fığlalı

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Ö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.