Gezgin satıcı problemi için veri madenciliği tabanlı bir model önerisi
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
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. 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.
Collections